Lambda the Ultimate

Thanks.

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.

"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...

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'.

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.

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.

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, 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. 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.

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).

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.

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).

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?

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.