Closure conversion is the last of the three most fun transformations in our compiler. (The first two are code generation and K-normalization.) It gets us from higher-order Scheme to “closed” first-order Scheme. Closure conversion is a simple, popular, efficient way to implement nested lambdas.

(If you’re reading this handout in a hurry just before lab,¹ the key sections are the introduction, the three species of variables, and the section on embedding.)

Introduction

Here’s a standard μScheme function that returns a lambda:

(define o (f g)
  (lambda (x) (f (g x))))

In a definitional interpreter, when we call

(o not positive?)

the interpreter allocates a closure, which I’ll write this way:

⦇ (λ(x) (f (g x))), { f ↦ not, g ↦ positive? } ⦈

The “unimproved” uscheme interpreter used in CS 105 copies the entire environment, but this example shows the “improved” version, which builds an environment that contains only the variables that appear free in the λ expression (f and g).² When this closure is called with an actual parameter $v$, the interpreter extends the saved environment with a binding x ↦ $v$, then evaluates the body of the λ expression.

How should this closure be translated into a low-level intermediate language? By playing the same game that we played during K-normalization: instead of keeping an environment ρ around at run time, we’ll use the environment only at compile time. The compiler will remember the locations of f and g and will pop them straight into the generated code. But unlike formal parameters or let-bound local variables, f and g won’t be in registers—they’ll be in a closure.

The translation is driven by the representation of closures. The closure above is represented by a record that contains a function pointer and two “slots”:

The function pointer points to the virtual-machine instructions that implement the inner λ. (It actually points a to struct VMFunction, which records not only the VM instructions but also the fact that this λ expects a single parameter.)
The two slots, which are numbered 0 and 1, contain the values of f and g.

Inside the lambda, the values of f and g are obtained by indexing into the closure record. By convention, the closure record of a running function is in register $r0—a convention that you have already implemented. Variables stored in a closure record are called captured, so in the abstract syntax, the indexing operation is written CAPTURED 0 for f and CAPTURED 1 for g. In the concrete syntax of my assembly language, I write $r0⟨0⟩ and $r0⟨1⟩.

Now that I know the representation of the closure, I can translate the anonymous λ into K-normal form. The closure is in $r0, and according to our calling convention, x arrives in register $r1. The internal lambda, whose body is (f (g x)), might be K-normalized like this:

let f = $r0⟨0⟩ in     -- take f from slot 0 of the closure in $r0
let g = $r0⟨1⟩ in     -- take g from slot 1 of the closure in $r0
let t = g($r1) in    -- call g(x)
f(t)                 -- return f(g(x))

To make this code work, o has to allocate the closure record that is eventually stored in $r0. And that’s the rest of the translation: o allocates the closure record, associates it with the inner λ, and initalizes each slot. This computation is expressed in abstract syntax by a new CLOSURE form. The form (lambda (x) (f (g x))) is closure-converted into

((["x"], ...), [LOCAL "f", LOCAL "g"])

where the ... is the conversion of the body, which looks like this:

FUNCALL (CAPTURED 0, [FUNCALL (CAPTURED 1, [LOCAL "x"])])

Why it works: the three species of variables

Closure conversion, like K-normalization, gets good performance out of variables. To understand it, we must refine our understanding of variables.

In vScheme, there is only one species of variable. In module 5, we introduced Disambiguated vScheme, which has two species of variables: local and global. Now we split the non-global variables into two distinct species, resulting in three overall. The three species are relative to a given function $f$.

A global variable is introduced using val, define, or set, outside the scope of any function. Or it is the name of a primitive.
A local variable is introduced using let or lambda, inside $f$ itself.
A captured variable is also introduced using let or lambda, but it is introduced in a function that encloses $f$.

This classification is already partially implemented: the disambiguation pass from module 5 distinguishes GLOBAL variables from LOCAL variables. To implement closure conversion, we have to examine the LOCAL variables more closely: which ones are truly local, and which ones are captured? There’s a simple answer:

The captured variables of a lambda expression $e$ are precisely those variables that are identified as LOCAL during the disambiguation pass and are free in $e$.

Once the captured variables are stored in a closure record, we are guaranteed fast, constant-time access to every variable.

Summary of the translation

Pure, higher-order vScheme is converted into first-order code by this transformation:

Every lambda is replaced by the allocation and initialization of a closure record. The record holds the lambda’s code and the values of the captured variables.
In the body of the lambda, every reference to the value of a captured variable is replaced by an indexing operation that looks for the value in the closure record that replaces the lambda.

Because the source language is pure, a captured variable is not mutated. Mutability is a feature you can support if you want to earn depth points.

Representations and syntactic forms

Higher-order functions are supported by one new value representation in the SVM and by two new syntactic forms in some of the intermediate languages.

In the SVM

In the SVM, a closure is represented by code, plus $n$ captured variables, each in its own slot.

struct VMClosure {
  struct VMFunction *f;
  int nslots;
  struct Value captured[];
};

This structure is allocated by instruction mkclosure, read and written by instructions getclslot and setclslot, and supported by instructions call and tailcall.

If you replace the struct VMFunction * pointer with a pointer to machine code, you get the representation that is used in native-code compilers.

In Closed Scheme

In the intermediate languages, we need a form that allocates a closure and another form that refers to the value of a captured variable. Adding those forms to First-Order Scheme defines Closed Scheme. The new types and syntactic forms are as follows:

type funcode = name list * exp   (* a lambda with no free variables *)
                                 (* eventually becomes a function ptr *)

type closure = funcode * exp list

datatype exp 
  = ...
  | CLOSURE  of closure
  | CAPTURED of int

In K-normal form

Your K-normal form has to be extended with these same two constructs. And as expected for K-normal form, every subexpression has to fit in a register. The CAPTURED form doesn’t have any subexpressions. And in the CLOSURE form, a funcode already fits in a register—that’s the LOADFUNC work you did way back in module 2. Each captured variable also fits in a register, so the representations can be defined like this:³

datatype 'a exp 
  = ...
  | CLOSURE  of 'a closure
  | CAPTURED of int
withtype 'a closure = ('a list * 'a exp) * 'a list
               (* the value of every captured variable is now in a register *)
type 'a funcode = 'a list * 'a exp

Re-embedding closure-converted code

Once you’ve implemented closure conversion, you’ll want to see if the converted code is right. Closure-converted code is first-order Scheme, extended with the two new forms listed above: allocate a closure, load a captured variable. To debug it, you’ll re-embed it into ordinary Scheme.

In the SVM, a closure is represented as a record. In vScheme, we have only cons cells to work with. We’ll embed a closure record as a pair: the first element contains the function pointer, and the second element holds the list of captured variables. To work with this embedding, the vScheme interpreter includes a primitive mkclosure and a predefined function CAPTURED-IN.

You can embed a reference to a captured variable by using the CAPTURED-IN function built into the vscheme interpreter:

(define nth (n xs)
  (if (= n 0)
    (car xs)
    (nth (- n 1) (cdr xs))))

(define CAPTURED-IN (i record) (nth i (cdr record)))

Closure conversion also changes the procedure-calling convention. To call a closure-converted function, we must pass the closure itself as an “extra” parameter.⁴ In the virtual machine, that extra parameter arrives in a dedicated register (register 0). But to embed things properly into vScheme, that parameter has to be added. So to embed code into a closure, we’ll represent it as a lambda expression without free variables, and we’ll add the closure record as an additional (first) parameter, imaginatively named $closure.⁵

I’ve modified the vScheme interpreter so it can call such a list as if it were a function, according to this equivalence:

APPLY (CONS_CELL ⟨f, ys⟩, vs) ≡ APPLY (f, CONS_CELL ⟨f, ys⟩ :: vs)

As part of the closure-conversion module, you will re-embed converted code into μScheme. You’ll have to implement only the two new forms:

Embed CAPTURED $i$ as a call to (CAPTURED-IN $i$ $closure).
Embed CLOSURE (funcode, es) as code that emulates the construction of a closure record: build a list that starts with the funcode, which is followed by the values of the captured variables es. The funcode is embedded as a lambda expression that has been modified to receive the extra $closure parameter.

With this embedding in place, you’ll be able to prettyprint and run your closure-converted code.

Here’s an example:

(define flip (f) (lambda (x y) (f y x)))

The lambda has one free variable, f, which will be stored in closure slot 0. The internal f becomes CAPTURED 0, which is embedded as (CAPTURED-IN 0 $closure). The NEWCLOSURE record is embedded as⁶

(mkclosure 
   (lambda ($closure x y) ((CAPTURED-IN 0 $closure) y x))
   (cons f '()))

And the entire definition is embedded as

(val flip 
   (mkclosure 
      (lambda ($closure f) 
         (mkclosure 
            (lambda ($closure x y) ((CAPTURED-IN 0 $closure) y x)) 
            (cons f '()))) 
      '()))

This closure can be called in the vscheme interpreter. For interactivity, I invoke vscheme with the -vv option:

$ vscheme -vv
-> (use flip.scm)
flip
-> (cons 'A 'B)
(A . B)
-> ((flip cons) 'A 'B)
(B . A)

A common mistake

By the time you’re ready to allocate a closure, not every captured variable is still a variable—a captured variable might refer to a slot in an outer closure. If you overlook this possibility, your UFT may generate code like this:

echo '(lambda (f) (lambda (x) (lambda (y) (f x y))))' | uft ho-cl
(cons
   (lambda ($closure1 f) ;; top level; no free variables and closure won't be used
      (cons
         (lambda ($closure2 x) ;; code for this function is faulty
            (cons
               (lambda ($closure3 y)
                  ((CAPTURED 1 $closure3) (CAPTURED 0 $closure3) y))
               (cons x
                  (cons f '())))) ;; this `f` is wrong
         (cons f '()))) ;; this `f` is in scope
   '())

To make it a little easier to see what’s going on, I’ve renumbered the three $closure parameters. When the intermediate lambda tries to build its closure, it attempts to refer directly to f, which it doesn’t have the rights to do. Think about what code should be generated instead.

A remote contingency, to be sure.↩
If you’ve taken CS 105 with me or with Kathleen Fisher, you’ve implemented this improvement.↩
It’s not possible to define both funcode and closure as type synonyms and to use funcode in the definition of closure. This limitation infuriates me.↩
The parameter is “extra” because it does not appear in the original source code.↩
In the SVM, such an addition is not necessary because the closure record is already passed in register 0. This is also how closures work in native-code compilers.↩
Because CAPTURED-IN is a predefined function, it is stored in a global variable, just like cons or car. It is therefore not considered a “free” variable—as you know, it compiles to GETGLOBAL, not GETLOCAL.↩