1.13 Recursive Data

1.13.1 Preface: What’s wrong with Exprs-Lang v10

This Chapter still needs too much work. Contains too many hacks.

Exprs-lang v9 gave us the ability to write first-class lexically scoped local procedures, a powerful tool for abstracting over computation. However, without the ability to write recursive data, we could only write simple non-recursive local procedures. This makes implementing local loops annoying; we had to go through top-level definitions instead. By adding recursive data, we can implement first-class lexically-scoped recursive procedures (generalized loops), but also enacode other cyclic data such as stream.

Many languages support cyclic data through imperative mutation, but as we’ll see in this assignment, that’s a low-level implementation technique that the user need not be required to use. Instead, we can express cyclic data more abstractly through recursion and suspended computation. Unfortunately, the only suspended computation primitive we have is lambda, and our surface language is call-by-value, so this still requires a little encoding.

We add letrec, which we saw in the previous chapter, to the surface language. Unlike the previous version, this letrec is not restricted to bind only procedures. This apparently simple change has deep consequences.

In the surface language, letrec is restricted to only bind each name once in a single letrec. A letrec binds all names in a single mutually recursive scope, so later bindings are accessible to earlier bindings, and thus it wouldn’t make sense to have the same name bound multiple times in the same scope.

1.13.2 Compiling Recursion to Back-Patching Mutation

The rest of our compiler assumes that letrec only binds procedures. Compiling first-class procedures is complicated for reasons others than recursion, and keeping them separated is useful. To maintain this separation and avoid extending the closure conversion passes unnnecessarily, we can purify letrec, by compiling all non-procedure recursive bindings into a lower-level implementation of recursion.

This implements recursion through back-patching; we create an uninitialized variable, x.1, and reference this in a suspended computation before it is initialized. Then we initialize x.1 to the value that contains a pointer x.1. After that, later uses of x.1 can call that suspended computation, which will get the right value.

We don’t want to do this transformation for every letrec, because set! will be more expensive to compile than what we can do for letrec-bound procedures.

We’ve actually already seen this transformation; we did it when implementing closures, although its details were somewhat obscured. Closures are a form of recursive data—they have a binding to themselves in their environment. When we implemented closures as procedures, we translated the cletrec form into a let followed by several unsafe-procedure-set! calls to tie the knot.

1.13.3 Preliminary Passes

As usual, we don’t want to manipulate any bindings before we’ve uniquified, so first we modify uniquify.

Below we define Racketish-Unique.

As usual with uniquify, the only change is that all names x are replaced by abstract locations aloc. But we need to pay attention to the mutually recursive scope of letrec.

procedure (uniquify p) → racketish-unique?

p : racketish-core?

Resolves all lexical identifiers into unique abstract locations.

Next, we need to move define->letrec up, as the pass just after uniquify. This enables define to bind arbitrary expressions, but also simplifies our implementation of recursive binding.

procedure (define->letrec p) → just-exprs-lang-v10?

p : racketish-unique-v10?

Transform all top-level bindings into local bindings.

This complicates implement-safe-primop since they introduce defines...

Want implement-safe* to be just after uniquify. They should get to take advantage of as many surface features as possible.

1.13.4 Resolving Recursive Binding

Our first goal is ensure that letrec only binds procedures.

We define Assigned-lang v10.

In this language letrec only binds procedures. We also allow n-ary binding in let, to simplify the compiler pass. We add a single computation, (set! aloc e). Each let form is annotated with an info structure containing the list of alocs that are assigned in its body, and is used to keep track of mutable alocs.

A binding `[,x ,e] is a lambda binding if e is literally a lambda value.

Otherwise, the binding is complex.

Complex bindings `[,x ,e] are compiled as follows. First, we set up an initial let-binding to x to (void). Then, we introduce an auxiliary binding `[,xt ,e]. In it, e now has the correct binding, referring to x. But x does not have the right value. So we finally mutate x to have the value of xt, so now both xt and x have the same value, and the right recursive binding structure. This implements recursion using back-patching mutation, a technique called Landin’s Knot.

procedure (purify-letrec p) → assigned-lang-v10?

p : racketish-unique?

Compiles Racketish-Unique to Assigned-lang v10, transforming all letrec expressions to bind only procedures, and implementing recursive data structures through back-patching.

Previously, we did not expose set! beyond the backend of the compiler, so we must implement set!. We cannot simply expose set! from the backend of the compiler, because this version of set! behaves differently. It acts much more like Racket’s set-box!.

So now, we need to implement set! and the assigned locations to give them a box-like semantics, rather than a move semantics.

Below we define Exprs-safe-lang v10. We no longer have set! or impure computation; everything must be let-bound once more.

Remember that this pass happens before implement-safe-primops, and the safe version of vector-set! must be let-bound since it might return an error value.

procedure (convert-assigned p) → exprs-safe-lang-v10?

p : assigned-lang-v10?

Implement assigned variables using lower-level heap-allocated mutable data.