Consider at least two different approaches to taking a “block structured program” (for our purposes, a program with nested lambdas) and transforming it to the sort of program we could run easily on our standard machines. Both of the techniques we will study solve the problem of sub-expressions like (lambda (a) (* a y)). To put a finer point on it, if we don’t do something we will lose the context-specific meaning of y when we use this function. When we call (f 7) then we can figure out that a ought to be 7. But with y we are out of luck.

So, the first possibility, is to transform each such function into something like (lambda (a y) (* a y)). That is, every function should take in all the values of its free variables. All except for global the names of global functions; if we are in some (define foo ...) then we will not have to pass the name foo in also; such global functions names will not be a problem. By changing the arity of such inner, local functions, we also force a change to the calling procedure. The call sites of this function must now also pass along the values for those parameters. This transformation can be expensive—n^3 in a naive implementation, and n^2 when very clever. But as a consequence of this transformation, your inner functions are now scope-free, so you can lift them up (thus the name) to global definitions. Your whole program becomes a set of mutually recursive definitions. We might call this first step “combinator conversion”, and then the second, semi-trivial step lambda lifting. Notice this transformation does not, in and of itself, address the use of higher-order functions; it simply permits block-structured programming.

We have also omitted small details like coming up with adequate global names for formerly-anonymous inner functions. In this model, letrec causes no difficulty. The names of all functions are potentially mutually recursive, certainly mutually accessible, globals.

The other alternative is “closure conversion.” In closure conversion, we convert each such inner function to a closure. A closure is a way to “close over” an open lambda expression (“open” meaning the sub-expression like (lambda (a y) (* a y)) has free variables in it.) We transform the each such function into a pair consisting of a a pointer to a code block and an environment, a mapping consisting of the meanings of the free variables. Inner, nested lambda expression have free variables. The two major approaches are: pass those in too as additional parameters wherever you call the function, or keep track of the meanings of the free variables from the context of the function. Here, unlike lambda lifting, we don’t get mutually recursive functions for free.

So the “closure conversion approach” splits in two possibilities here. The closure conversion approach itself keeps all of the mutually scoped function-names in each others’ environments, as another part of their environment. With the “supercombinator approach”, instead there is a mutual-recursion combinator that solves the problem of mutual recursion without having the heretofore mutually-referring expressions refer to each other.

Updated: