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

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.

Conclusion

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.