Felleisen: How to Design Class Hierarchies

My talk will instead present a novel approach to the first-year programming curriculum. Specifically, I will explain how a functional semester ideally prepares students for the true essence of object-oriented programming according to Alan Kay: the systematic construction of small modules of code and the construction of programs without assignment statements. Experience shows that these courses prepare students better for upper-level courses than a year of plain object-oriented programming. Initial reports from our students' co-op employers appear to confirm the experiences of our upper-level instructors. (full abstract)

We discussed this approach (FP as an introduction to OOP) before. This presentation is from FPDE 2005.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

bad link

The posted link has an extra quote, its actually here



A functional approach to object-oriented methods

This may be a bit off the topic (and already been discussed), but implementing an object method with a curried function seems to work quite well.

In a Haskell-like language, I have a selection type class defined something like:

class Select a where
   (.)            :: (a -> Name -> *);

Where Name is a type for an identifier as a value. (.) can be appropriately overloaded for expressions such as:

(socket.send) "Hello, world!\n"

The point here is that socket.send might be defined:

sendSocket::(FileDescriptor -> String -> Int); 

instance Select Socket where
   (.) socket #send = sendSocket (get_fd socket)


For a non-statically determined value the type class method effectively becomes a virtual method.

The advantage seems to be that the cleaner semantics of FP type classes can achieve a satisfactory OO style where required.


I can see some benefits to this method of teaching, but to some extent it promotes the teacher's ideology at the expense of the students.

Despite the quotes used to introduce the presentation, creating a new World on every state change is not how object-oriented programming is normally done. I've tried writing programs in Java using immutable objects, and found that it works well for leaf objects but gets awkward for larger data structures. It goes against the grain of most libraries; for example, it requires you to use non-standard collection classes. Writing class constructors for objects with a large number of fields gets awkward very quickly, and so does updating a single field deep in a hierachy. It doesn't seem right to set up beginners so they have to try to solve these problems.

There are workarounds (see my blog) but it means a lot of reinventing the wheel instead of going along with the grain of the language.


From the slides I don't necessarily see how being an FP'er first makes you directly a better OOP'er (although I'd say it makes you a better P'er regardless of the order), either. However, I'd disagree that this is at the expense of the students. A lot of top schools stopped using SICP in favor of the usual suspects, which is more detrimental imho.

The curious bit is that the slides don't show what can be done with OOP that couldn't be done with FP alone, which begs the question as to why one would transition from ocaml to java. (Disclaimer: I am not saying that such examples can't exist. I was just expecting them as a motivation to this study. In their absence, the motivation seems to be "we have to teach OOP because somebody wants us to.")

OT: Taking a look at your blog I saw that you had misunderstood static single assignment a while ago. It's not supposed to a help a human programmer manage state. See this.

Somebody does want you to!

"we have to teach OOP because somebody wants us to"

I think that is precisely the motivation in this case; their motivations were clear by slide 5 - the ultimate goal of the education they are developing is preparation for industry (where people do need to understand OOP).

This is even clearer on the last page: "To produce the best OO programmers, teach FP, and then move on." If the goal from the beginnning is to produce the best object oriented programmers, and you're showing how FP is a means to that end, then the omission that you find "curious" would be unnecessary if included - the presentation is about teaching, not comparing languages...

Would FP work if destroyed values were pushed on the stack?

I recognize the problem you are talking about and indeed, it has been a problem of mine too. It is also the first thing that my colleagues asked me when I introduced them in the concept of immutable state.

Specifically, they found it highly illogical that, in order to modify a single bit of the program's state, they would have to copy all the data structures. It especially became a problem with databases: there is no way that these people could accept that, for example, in order to change a customer's name all the records from a recordset would have to be copied around. And they were right too, because when we tried to do it in Java, the debugging session was horribly slow, to the point of being unusable.

But what if the destroyed value was pushed on the stack, then restored at subroutine return? wouldn't that make a programming language safe, keeping referential transparency, without sacrifizing performance? it would be like saying 'the destructive update is valid for as long as this subroutine is executed'.

Impedance mismatch?

Axilmar, I believe this is a common case of impedance mismatch between imperative & functional paradigms. Functional compilers *don't* copy the data. Tail-calls and lack of pre-image references optimize down to the 'normal' imperative implementation (looping & in-place updates).

Because C/Java/etc compilers don't expect to gain any benefits from these optimizations, they are not included. Thus "pure" functional code compiled by them is very slow. A good example is a recursive list structure with 1000s of items, in Haskell it would be no problem, in C/Java it would cause a stack overflow.

Your idea of keeping the modified values on the stack is a common idiom in C++ to achieve exception safety. Once the modification is complete (and correct) the update occurs using swap(), an atomic, zero-exception state update.

Re: Impedance mismatch

I believe this is a common case of impedance mismatch between imperative & functional paradigms. Functional compilers *don't* copy the data.

Speaking as an ex-imperative programmer myself, I think this mismatch arises conceptually because imperative programmers tend to think of programming language features in terms of a machine-oriented model, even when they're programming in a high-level language — or put slightly differently, they think in terms of a fairly direct and straightforward mapping from their language to a machine model. Essentially, the machine model is the common denominator in terms of which all language features can be understood, informally serving the same sort of purpose as the lambda calculus does for functional languages.

FP separates the programming model from the machine representation much more strongly — the model is mathematical and abstract, with little if any concession to the machine, and the translation to the machine is supposed to be mostly automatic and behind the scenes, with certain exceptions for reasons such as performance.

One of the leaps that imperative programmers need to make is to recognize that in many applications and circumstances, it really is possible to not worry about the machine and just program in a way appropriate to the language's model. Programmers in many higher-level languages already do this with respect to some kinds of features, e.g. memory management, OO objects, etc., but they're not used to the degree to which FP languages deprecate the machine, and tend to be quite skeptical of it, mostly without good reason.

And yet, that's no longer the Machine.

With the addition of microcode, out of order execution, pipelining, code morphing, etc. the reality is quickly distancing itself from the Machine model.

If there is some way to measure the distance between an abstraction and what really happens, I'd like to see how the Machine model, lambda calculus, etc. map onto various architectures like today's CPUs, graph reduction, etc.

But I have to code in a way that data seem to be copied.

But I have to code in a way that data seem to be copied, even if they are not copied in the end. For example, if I have an object model, a tree let's say, with a root node containing two other nodes, and something is changed in one of the two other nodes, then I have to reconstruct my tree with the new value and return it to the main loop. I have to provide all the reconstructing tree code, i.e. to initialize a new tree etc. The compiler may optimize the code and just do the assignment, but the code will read like it copies the data, and the effort spent will be around coding the copying of data, only to be replaced by the compiler with an assignment.

The problem also lies when in debugging: it is not easy to debug an application when 1,000 records (for example) have to be copied around.


Replacing an item in a list or tree requires a predicate to nominate the node for replacement, a new value to replace it with, and the container itself. Pass these into a modified MAP function and you get the modified container out of it.

In this case you don't write any tree traversals or reconstruction code. Using MAP is not the most efficient method if you already know where the node is, as there are other algorithms to use.

Still, we have reduced the problem from "write some tree traversal/reconstruction code that copies nodes between two lists and modifies some value along the way" down to "choose algorithm A or B to perform the replacement". A much simpler problem with much less code involved. Let the compiler deal with making it efficient, and profile it to make sure you made the right algorithmic decision.

I'm still new to debugging functional code, but nothing has shown itself to be any worse than imperative debugging (so far).

But the whole tree needs to be reassembled, plus the new value .

But the whole tree needs to be reassembled, plus the new value. If a new list is created out of the MAP function because one element is changed, then the list is itself a new value, causing the container that the list is in to be copied etc: the copying propagates to the root element.

Therefore, I see no reduction in code as you say. The problem is especially difficult if the data tree is heterogeneous: then multiple functions, one for each container type should be provided.

As to debugging, I never meant it was more difficult, but rather slower: the non-optimized code copies whole trees of data at each function, and if the data are too many, then there are big pauses between debug steps.

Only the new value is created, all else is shared.

Because values are immutable, the new list can share values with the old list that they both have in common. The only newly created values are the new list, and the new value.

Oleg's ZipperFS is an example of something that's designed with maximal sharing in mind.

Maximal sharing means that changes are effectively stored as 'diffs' from the original value.

The copying you refer to doesn't happen (unless you force it with unboxed values or something).

But at least one value will be replaced at each tree level.

The problem is not about copying the data, but about coding all the unnecessary copying. If I have an object model in the form of a tree, with different types of records at each level, then if one bit changes somewhere in the tree, I have to code all the functions that duplicate the tree nodes at all levels. For every possible state change, I have to code all the needed functions for every state copy.

No copying in zippers

As shapr said, no copying is necessary if you can use sharing. In cases where the changes occur only at some hotspot, which can be moved around (a la cursor), zippers take care of sharing. You do not code copying in this case, as there is no copying (except when moving the cursor, but this is cheap - has a constant complexity per move). Even more, with Oleg's approach, you do not code the details of moving the cursor, it is obtained for free from the structure of data (if I understand the idea right).

Curiously, just today I read a paper coming to zippers from the perspective of natural languages - Types as graphs: continuations in type logical grammar (co-authored by Chung-chieh Shan - they conspired with Oleg to dominate the world with zipper-like structures, no doubt). Quite interesting reading by itself, the graphical presentation of continuations and contexts, and graphs as classes of equivalence for terms under "zipping" is a real eye-opener (section 3 is enough, if you are not interested in natural linguistics).

Define traversal once with Functor

For a Tree datatype like this:

data Tree a where
    Leaf   :: a -> Tree a
    Branch :: Tree a -> Tree a -> Tree a

Traversal can be defined with a Functor instance like so:

instance Functor Tree where
    fmap f (Leaf x)       = Leaf (f x)
    fmap f (Branch t1 t2) = Branch (fmap f t1) (fmap f t2)

Assuming this tree value:

anotherTree = Branch (Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 5)) (Branch (Leaf 9) (Leaf 0))

Making changes to the tree is easy:

*TreeTraverseDemo> fmap (+1) anotherTree
(Branch (Branch (Branch (Leaf 2), (Leaf 3)), (Leaf 6)), (Branch (Leaf 10), (Leaf 1)))

Or see the full source.

Does this answer your question?

Me, too

You need to know that functional programming includes "set-car!". Quick: what does this mean for this talk?

For my dissertation and pre-dissertation research I discussed the need for set! because of deep hierarchies, the need for most-sharing updates, etc. That was in 84-87. So I ended up studying the semantics and dimensions of language design, and functional is just the core; assignment -- when needed -- comes naturally with it.

To find out what this means for How to Design Classes, you will have to read the book. Not skim; read. And you will find out that "expense of students" is the worst possible characterization you could have come up with.