Monday, December 1, 2008

Prototypes: Encoding OO-style inheritance in Haskell

In this post I will sketch an encoding for OO-style inheritance in Haskell, and show how this is used to in Yi to write code that can be customized.

This can also serve as an introduction to the concepts defined in module Data.Prototype (currently found in Yi sources)


Inheritance can create structures which are difficult to understand. Since a given method call can call dispatch to a number of methods at run-time, tracking what is going on might be tricky. Sometimes however, inheritance is exactly the construct we need.

Imagine you have the following piece of code:

a :: A
a = fa b c

b :: B
b = fb a c

c :: C
c = fc a b

That is, a, b and c are values defined in terms of each other.

You would like users to be able to customize a’s value. However, if the change actually occurs in the definition of c, you don’t want them to copy-paste the whole set of definitions. It would be preferable to amend only the definition for c and reuse the rest. Unfortunately, a’s value is closed, so this is not possible.

This situation seems to cry for inheritance. In an object oriented language, the solution is obvious: make a, b and c methods of a class. The user can then inherit it and override the definition of c.

In Yi, color themes have a similar structure: specific styles are defined in terms of base styles. If a user changes a base style, the change should be reflected automatically in all the styles that derive from it. As in the toy example above, we do not want the user to redefine everything from the ground up.

So, what can we do, since Haskell lacks inheritance?

Encoding prototypes

All is not lost! Pierce (TAPL, paragraph 18.10) has taught us that inheritance can be encoded as open recursion. The trick is to make the reference to the self object explicit. We can do so in Haskell by putting the definitions in a record and a lambda.

data Proto = Proto {a :: A, b :: A, c :: C}
proto = \self -> Proto {
  a = fa (b self) (c self),
  b = fb (a self) (c self),
  c = fc (a self) (b self)

We can retrieve our original definitions by taking the fix-point:

abc = fix proto

Of course, this works only because Haskell is lazy (and because the original definition did not introduce an infinite recursion in the first place). If the fields of the record are marked strict, this ceases to work.

Given that definition, it is easy to customize the value as follows:

customizedProto = \self -> proto self {
   c = userFunction (a self) (b self)

customizedABC = fix customizedProto

The Data.Prototype module generalizes this example, and defines types and functions to corresponding to the prototype and inheritance abstractions.


Yi is intended to be highly customizable. In many instances, we can use compositional abstractions to provide customization. In some other instances, we prefer to provide a prototype that user can patch.

Despite Haskell lacking inheritance, we see that the basic concepts of lambda expression and lazy evaluation can be combined to provide a very lightweight encoding for prototypes, and we take advantage of this in Yi.


Kashyap said...

I'd appreciate it very much if you could post a working(complete) Haskell code to demonstrate this.

Anupam Jain said...

Can this not be done by using typeclasses in Haskell?

class Foo X where
a :: X -> A
a x = fa (b x) (c x)
b :: X -> B
b x = fb (a x) (c x)
c :: X -> C
c x = fc (a x) (b x)

data Bar = Bar

instance Foo Bar where
a x = some_other_calculation

davidaleman said...

Excellent and simple Blog. I like this because it’s informative and simple nature.nice job keep it up.

document editor online

Yagamy Light said...

@Kashyap, actually, the first example

data Proto = Proto {a :: A, b :: A, c :: C}
proto = \self -> Proto {
a = fa (b self) (c self),
b = fb (a self) (c self),
c = fc (a self) (b self)

says it all, it just needs a bit of thinking about. The proto function does nothing more than a simple initialization of members of the ADT. It's the obvious thing you'd do anyway if you wanted to initalize them, and the only interesting idea the post have is the custody of the values into an ADT.

The abc = fix proto is harder because of brevity of the explanation. My guess is that the function fix calls the proto with an indentity element, thus retrieving the original values. Note, that for that to work the values have to be instances of the Monoid typeclass (because how otherwise the function would know whether an identity even exist).

P.S.: @OP, c'mon, "forbidden tags: code, pre", are you serious? I dunno, I hope the readers would differ the code and the rest of sentences.

Yagamy Light said...

A fix to fix: an identity have to have both the ADT and values.

P.S.: @davidaleman nice spam, I'm sure @OP didn't even notice