1.12 First-class Procedures: Code is Data

1.12.1 Preface: What’s wrong with Exprs-Lang v8?

Actually, not much. With structured data types, Exprs-lang v8 is a pretty good language now.

Exprs-bits-lang v8 is sufficiently expressive to act as a reasonable compiler backend for many languages. It’s roughly at the abstraction level of C. It provides raw access to memory, pointers, labels (function pointers) and bitwise operations, but also non-tail calls and some nice syntactic properties like algebraic expressions.

Exprs-lang v8 adds safety on top of that language, although this safety does come at a cost. One major limitation in Exprs-lang v8 is the lack of abstractions over computation. We have lots of abstraction over data, but it’s common to want to abstract over computation—first-class procedures, objects, function pointers, etc. Exprs-lang v8 prevents even passing function pointers to ensure safety.

In this chapter, we add the ability to easily abstract over computations at any point via first-class procedures. Many languages provide some version of this—Python, JavaScript, Ruby, Racket, Scheme, Java, and many more. They enable the programmer to create a suspended computation, and pass it around as a value. The procedure closes over the environment in which it was created, capturing any free variables and essentially creating an object with private fields. They can be used as the foundations for object systems, to represent call backs or continuations, and provide a safe, lexically scoped alternative to function pointers.

Now, lambda can appear in any expression. We can still define procedures at the top-level using define, although the semantics will change.

We add a new data structure to the language as well: procedures. These are implicitly constructed by lambda. They support two operations, in addition to call: the tag-checking predicate procedure? and procedure-arity, for inspecting how many parameters the procedure expects take.

This is a syntactically small change, but it has massive implications.

1.12.2 Procedures, Closures and Closure Conversion

So far, procedures in our language have been compiled directly to labeled code—a suspended computation that is closed except for its declared parameters. We have not treated procedures as values, nor considered what happens if a procedure appears in value context. The closest representation of the value of a procedure we had was the label to its code. In earlier source languages, we disallowed passing procedures as values, to ensure safety.

1.12.2.1 The First-class Procedure

To support first-class procedures, we need to compile procedures to a data structure. This data structure allows us to construct a procedure value, pass it around and return it, call it (safety), and captures both the procedure’s code, but also any information we need about the procedure.

To add a new data structure, we need a new primary tag and a new collection of primitive operations. We use the tag #b010 for procedures.

In the source language, we expose the primitive operations procedure? and procedure-arity. However, the compiler intermediate languages expose a few more operations that the compiler needs to make use of to implement procedure calls.

Every instance of lambda compiles to a procedure. The procedure now has three pieces of information: its arity for dynamic checking; the label to its code, the computation it executes when invoked; and its environment, the values of the free variables used in the definition of the procedure. We compile each application of a procedure to dereference and call the label of the procedure, but also to pass a reference to the procedure itself as a parameter. Essentially, the procedure is an object, and receives itself as an argument. Each "free variable" x is a field of that object, and are compiled to references to self.x.

Our procedure data structure is essentially a vector containing a label to the code and the values of each free variable in its environment.

The challenge in implementing procedures is primarily in compiling lambda down to the procedure primitives, then specifying the representation of these procedure primitives in terms of calls to labelled code. All compiler passes below specify-representation remain unchanged.

Until now, all procedures were bound at the top-level in a set of mutually-recursive definitions. To work with first-class procedures in intermediate languages, we need to be able to represent sets of mutually recursive definitions that appear as expressions. We introduce the letrec construct to aid with this. (letrec ([aloc e] ...) e_2) binds each aloc in each e, including its own right-hand-side, as well as binding all alocs in e_2. For now, we only consider a restricted form of letrec that only binds procedures.

1.12.2.2 The Closure

Our procedure data structure implements a closure, a procedure’s code paired with the values of free variables from the environment in which the procedure was created. This allows us to create procedures that refer to variables outside of their own scope, but still retain references to those variables even when the procedure is passed to a different scope.

As an intermediate step in compiling first-class procedures, we introduce explicit closure primitives which compile to the procedure primitives. There is no primary tag for this data structure, since it will be implemented by the lower-level procedure data type.

Closures support two operations. First, you can call a closure with (closure-call e es ...), which essentially extracts the label from the closure e and calls the procedure at that label with the argument (es ...). Second, you can dereference an environment variable from the closure with (closure-ref e value_i), extracting the value at index value_i from the environment of the closure e.

Because we want to implement safe procedure application, we add a third field to the closure: its arity, the number of arguments expected by the code of the closure.

1.12.2.3 Closure Conversion

The main problem with compiling first-class procedure is that we need to lift their code to the top-level, but they have references to free variables which go out of scope if we move the procedure definition. We deal with this by converting all procedures to closures, rebinding the free variables in the code as explicit dereferences from the closure’s environment, then lifting the now-closed code definitions to the top-level. This process is called closure conversion.

Closure conversion is not the only way to implement first-class procedures. An alternative that can avoid some of the allocation cost of closures is defunctionalization, but this does not work well with separate compilation.

A variable is considered free in a scope if it is not in the set of variables bound by that scope, if it is referenced in any expression in which the scope binds variables, and if the reference is not bound. A variable is bound if it is referenced inside a scope for which it is declared in the set of variables bound by that scope.

1.12.3 Administrative Passes

Allowing procedures to be bound in two different ways is great for programmer convenience, but annoying for a compiler writer. Before we get to implementing procedures, we simplify and regularize how procedures appear in our language.

The first big benefit to the programmer comes in check-exprs-lang. Since we finally have a procedure data type, and procedure primitives to enable dynamic checking, we can finally stop type checking programs. Now, it is valid and does not cause undefined behaviour to pass procedures as arguments, return procedures, or call an arbitrary variables with an arbitrary number of arguments. The language will dynamically check whether any of those expressions is safe before attempting to execute them

procedure (check-exprs-lang p) → exprs-lang-v9

p : any

Validates that input is a well-bound Exprs-lang v9 program. There are no other static restrictions.

As usual with uniquify, the only change is that all names x are replaced by abstract locations aloc.

Unlike in previous versions, there are no labels after uniquify. All of our procedures are data, not merely code, and cannot easily be lifted to the top level yet, so it is now the job of a later pass to introduce labels.

Below we define Exprs-unique-lang v9. We typeset the changes with respect to Exprs-lang v9.

procedure (uniquify p) → exprs-unique-lang-v9?

p : exprs-lang-v9?

Resolves all lexical identifiers into unique abstract locations.

Not much changes in implement-safe-primops. The target language of the pass, Exprs-unsafe-data-lang v9, is defined below.

Note that this pass does not implement safe call, but can be safely applied to arbitrary data—a later pass will implement dynamic checking for application.

procedure (implement-safe-primops p) → exprs-unsafe-data-lang-v9?

p : exprs-unique-lang-v9?

Implement safe primitive procedures by inserting procedure definitions for each primitive operation which perform dynamic tag checking, to ensure type and memory safety.

Now we implement call in terms of unsafe-procedure-call and unsafe-procedure-arity. Note that we cannot simply define call as a procedure, like we did with other safe wrappers, since it must count its arguments, and we must support a variable number of arguments to the procedure.

If we statically track the arity of procedures, we can optimize this transformation in some cases.

procedure (implement-safe-call p) → exprs-unsafe-lang-v9?

p : exprs-unsafe-data-lang-v9?

Implement call as an unsafe procedure call with dynamic checks.

Some procedures now appear in local expressions, and some appear defined at the top-level. This presents two problems. First, our compiler later assumes that all data (as opposed to code) is locally defined—we have no way to define top-level, labelled data. Since procedures are data, we need to transform top-level bindings of procedures into local bindings, so the rest of the compiler will "just work". Second, our compiler later assumes that all code (as opposed to data) is globally defined—we expect code to appear only at the top-level. That’s not true when lambda is used in a local expression.

To deal with these, we introduce two small administrative passes: define->letrec and dox-lambdas.

First, in define->letrec, we elaborate define into a local binding form letrec, which will be used to bind all procedures.

letrec, unlike let, supports multiple bindings in a single form, and each bound expression can refer to any variable in the set of bindings for the letrec. This is important to capture mutually-recursive functions, and has the same binding structure as our top-level defines.

Design digression:

In general, a language might impose additional semantics on define, such as allowing defined data to be exported and imported at module boundaries. This would require additional handling of define, and the ability to generate labelled data in the back-end of the compiler. We continue to ignore separate compilation and linking, so we treat define as syntactic sugar for letrec.

Below we define Just-Exprs-lang v9.