In object oriented programming an object is a value with a well-defined interface. The internal state of the object is closed to the outside world (encapsulation), but the behaviour of an object can be modified by redefining one or more of the functions in the object’s interface, typically through subclasses (inheritance). The internal state of the object is open to, and can be extended by, such subclasses. This is known as the open/closed principle.
For some problem domains this way of modelling is extremely suitable, and so one may wonder if we can take a similar approach in a purely functional language like Haskell, without losing purity. An obvious choice is to model an object as a record of functions that correspond to the public interface to that object. For example, we might define the “interface” of counters as
and we can define a “constructor” for this class as
The problem with this approach is that it does not allow us to “redefine methods” in any meaningful way. In particular, suppose we tried to define a “subclass”1 of counters which doubles the count in the
If we tried this
we will get 3, not 6. In this blog post we will explain what open recursion is, provide some runnable examples that you can evaluate one step at a time to develop a better intuition for how it works, and show how it can be used to solve the problem above. These results are not new, but we hope that this blog post can serve to make them a bit more accessible to a larger audience.
We then discuss how we can extend this approach using lenses to allow “inheritance” to also extend the “state” of the object.
Most beginner Haskell students study the factorial function:
Many find it confusing because the concept of recursion, or self-reference, is hard to grasp at first. To a seasoned Haskell programmer recursion comes completely naturally, but they too might have to stop and think to answer the following question: can we define
fac in such a way that we can later extend it? For example, we’d like to be able to define a function
skim that subtracts 1 (i.e. “skims from the top”) from the result of every recursive call; that is,
skim should be equivalent to
but it should be defined in terms of
fac. At the risk of stating the obvious, this is not a solution:
since although it subtracts 1 from the final result of
fac, it doesn’t do this at every recursive call.
The problem is that as defined
fac cannot be extended; the recursive call to
fac is fixed (“resolved”) at the definition point; it will always call itself, no matter how we wrap it. If we want to avoid this, we need to “delay” the resolution of that recursive call. Concretely, instead of calling itself,
fac will take an additional parameter:
The intuition is that when we pass “itself” as that r parameter, we recover the original factorial function. We do that through the use of
To understand how this works, step through the evaluation2 of the computation of 5 factorial
Note that the function we call is
fix fac, and that every time we expand that we end up with
fac (fix fac); in other words, the recursion argument is the same as the function we call. This corresponds to our intuition above that we must pass the function “itself” as its recursion argument.
So what is this useful for? Well, it is now possible to define
skim in terms of
skim also takes the function for the recursive call as an argument; this would for example make it possible to introduce further “extensions” later on. Only once we call
fix do we “tie the knot”:
Note that each time we expand
fix skim, we end up with
skim (fix skim); in other words, the recursive call that we pass to both
fix skim. Delaying the resolution of the recursive call, leaving the recursion “open”, is the key ingredient that makes it possible to adjust the result of
fac at every recursive call.
Let’s now go back to the example at the start of this blog post. Hopefully it should now be clear why the definition of
twice as stated did not work: the recursion in
mkCounter is resolved too early; when we construct a new object in
tick, we want to construct a new “twice” object, not a new base object. We can use the exact same open recursion technique to make that happen. The definition of the “interface” itself remains unchanged
but we add an additional “recursion argument” to
This works in precisely the same way that
skim did, except that instead of subtracting 1 from the result of each recursive call, we now override
display after each recursive call to
mkCounter. Step through the evaluation of
to see this happening in detail:
Note that, as before,
fix twice evaluates to
twice (fix twice), so that the recursion parameter that we pass to both
twice will be
fix twice; thus, although we do not redefine
tick, it still constructs the right kind of object.
Before we continue discussing how we can extend the state of the object, we will briefly recap lenses. If this is old hat to you, feel free to skip this section.
Lenses are a big topic in their own right, and there is no way we can do them justice in this blog post. We will recap the concepts we need for our purposes, but if you have never seen lenses before, this section may not be the most accessible introduction.
Lens a b is essentially a way to “access” a small part (of type
b) of a larger structure (of type
a); we can both
get that smaller part and we can
Lenses form a category; all that means is that we can always construct a lens from a structure to itself, and that we can compose lenses:
As an example, here are the lenses for the first and second component of a pair:
second come from
When we inherit from a class in object oriented programming, in addition to redefining some functions we can also extend the state of the object: we can add more fields. Let’s see how we can do this in our approach to modelling objects. Let’s start with a minor extension of the
In our “base” implementation, both
tock just increment the counter’s internal state:
But now suppose we want to “inherit” from this base implementation, and introduce a “new field” so that we can count the ticks and tocks separately. If we follow the same approach as above, we’ll find that we’ll soon get stuck:
ticktock counter needs two integers in its state, for the two separate counters. But which
self do we pass to
mkCounter? We can’t just pass
self argument directly, because the types don’t line up. In the definition above we have left open a hole
_reconstruct :: Int -> (Int, Int). That is, we somehow have to reconstruct the “extended” state of the subclass from just the state of the superclass. Why is this necessary? Well, let’s trace the constructor calls for the first
tick after the
ticktock counter is constructed:
- We start with
fix ticktock (0, 0)
- This unfolds to
ticktock (fix ticktock) (0, 0)
mkCounter (fix ticktock . reconstruct) 0.
- Notice what happens in
self (n + 1), which expands to
(fix ticktock . reconstruct) (n + 1)
fix ticktock (reconstruct (n + 1))
This means that although
tickis constructing a
ticktockcounter (rather than a base
mkCounter), every time we call
tickthe state of the subclass is reconstructed from the state of the superclass.
Clearly, this is not going to work. Instead what we need to do is parameterize the constructors with the state of the object; something like
Of course, this signature as it stands can’t quite work, because now
mkCounter doesn’t know anything about
st. To make it work, we will pass a lens to
mkCounter that gives it access to the state it needs:
In object oriented programming, subclasses can only extend the state of the superclass; they cannot remove fields. This is also the intuition of the lens parameter: it tells the constructor of the “superclass”: the state may have been extended, but it will at least contain the state that you need.
With this generalization we can now define
ticktock gets a lens parameter (because its state may later be extended again). The
self parameter that we pass to
mkCounter is now just the unmodified
self parameter that
ticktock gets; the only difference is that the lens argument we pass to
ticktock is the composition of the lens argument to
_1, essentially telling
mkCounter that the first component of the pair or integers in
ticktock is the state that
mkCounter should use.
When we now evaluate
we will get
It is important when writing code to choose the right way to model the problem domain. For some problem domains the most natural way to model it is object oriented programming. Of course, since we are Haskell programmers, we’d ideally like this to be referentially transparent object oriented programming, with no side effects.
Object oriented programming in Haskell has a long history, with encodings ranging from the very ambitious in Haskell’s Overlooked Object System by Oleg Kiselyov and Ralf Lämmel, to the very minimal in the use of OOP in the design of the Yi editor as described by JP Bernardy, and everything in between, such as Ruben de Gooijer’s masters thesis wxHaskell for the web or the recent blog post series on Object-Oriented Haskell by Tobias Dammers.
The use of open recursion to model inheritance is well-known; for instance, it is described in Chapter 18, Case Study: Imperative Objects in Pierce’s excellent book Types and Programming Languages. It is also a key component in Bruno Oliveira’s paper The Different Aspects of Monads and Mixins. Of course, the use of explicit fixpoints has myriad other uses also; for instance, explicit fixpoints at the type level is what makes designs such as Data types à la carte by Wouter Swierstra possible. Despite being well-known, it can nonetheless be confusing; our hope is that this blog post can help to make the technique more accessible.
The use of lenses as we presented it in this blog post to allow “subclasses” to extend the state is to the best of my knowledge novel, although Jonathan Brachthäuser’s master’s thesis on Modularization of Algorithms on Complex Data Structures in Scala comes close. In hindsight it seems a very natural solution to the problem. It also provides a very direct implementation of the open/closed principle, where subclasses have full access to the object’s internal state, but only the public API is visible to external clients.
Interestingly, it also generalizes subtyping in traditional object oriented languages. While encapsulation (state hiding) in OOP languages means that an object’s internal state can be changed without affecting clients of that object, it is not possible to change an object’s internal representation in subclasses. In our approach this is perfectly possible, as long as there is a lens from the state of the subclass to the state of the superclass; in general, this lens can be arbitrary complex (although efficiency should be considered, of course).