Lambda the Ultimate

From the 2005 ACM SIGPLAN Workshop on ML, here is An Applicative Control-Flow Graph Based on Huet's Zipper, by Norman Ramsey and João Dias.

We are using ML to build a compiler that does low-level optimization. To support optimizations in classic imperative style, we built a control-flow graph using mutable pointers and other mutable state in the nodes. This decision proved unfortunate: the mutable flow graph was big and complex, it led to many bugs. We have replaced it by a smaller, simpler, applicative flow graph based on Huet's (1997) zipper. The new flow graph is a success; this paper presents its design and shows how it leads to a gratifyingly simple implementation of the dataflow framework developed by Lerner, Grove, and Chambers (2002).

In the hope that maybe some of you will find this interesting, I decided to post some details about my Master's thesis project. Inspired by the Join calculus and Martin Odersky's Funnel language, I have developed a concurrent language (code-named Vodka) which separates the definition of function symbols and function bodies, combining familiar Join-calculus synchronization solutions with a multimethod-based approach to object-orientation. Here is a Dining Philosophers solution, explaining the decoupling of function symbols and bodies and a set of slides about the whole project. More code examples are available from the website.

Python and Ruby have been of some inspiration, too, which is reflected in Vodka's dynamic nature and its syntactic support for dealing with generators. Generators, however, need not be sequential but can yield values concurrently. There is some more example code (a small web server written in Vodka) which illustrates this.

The Vodka compiler/interpreter is written in Nice and runs Vodka programs on the Java VM. The runtime system allows a close integration of existing Java classes and makes efficient use of multiprocessor hardware, due to a transactional memory model and Doug Lea's work-stealing task library FJTask.