Lambda the Ultimate

The fundamental point made in the paper should seem natural to most LtU readers: In order to reason about programming language semantics one should look for programming language/calculus pairs.

The paper contrasts CBN and CBV, and shows the differences between the Lambda Calculi appropriate for describing each of them.

90 minute video presentation from Marc Feeley, along with accompanying PowerPoint slides and source code, for a Scheme to C compiler. Good discussion of continuations and closures, as well as some dipping into the area of compiler construction.

How to write a simple Scheme to C compiler, in Scheme. In only 90 minutes! And although not supporting the whole Scheme standard, the compiler supports fully optimized proper tail calls, continuations, and (of course) full closures. The compiler is implemented using two important compilation techniques for functional languages: closure conversion and CPS-conversion.

The emphasis is on the 4 major problem areas that crop up in an attempt to convert Scheme to C:

• tail-calls a.k.a. tail-recursion opt.
• first-class continuations
• closures of indefinite extent
• automatic memory management i.e. GC

The solution presented gives a series of source-to-source transformations. Stage 1 of the compiler expands the 'let' forms in the Scheme code. Stage 2 converts continuations to CPS. Stage 3 converts the code to closures using encapsulated closure objects. Stage 4 is not presented but touches on how the results would lend itself to a GC implementation.