2013-08-05: Binding Forms in Racket and How to Implement Them

This post discusses a classic sequence of macros that show how to construct a "tower of languages" by building macros atop one another. In particular, the sequence focuses on the binding forms.

-

"Binding", in this context, refers to attaching values to identifiers. This feature is built-in to most languages through the features of function definition and function call. For instance, in the following sample the function f binds the identifier x and the function call attaches the value 1 to x:

It is possible to use this pattern to introduce purely local bindings. For instance, we can remove the duplication in the code:

By using a local function definition and immediately calling it:

This pattern works just fine for binding many things at the same time:

This kind of pattern is so widely used, it is the first basic binding form: let.

The definition is very simple:

However, the pattern fails when you want one binding to refer to another as in:

The reason why this does not work is clear by looking at the expansion where the use of x is clearly not inside the lambda.

We can allow this by using multiple lets in sequence:

This introduces us to the next binding form: let*.

The definition of let* is similarly simple, although rather than requiring only one pattern, it uses two:

Unfortunately, even this pattern fails when the references cannot be sequenced because they both refer to each other:

The problem is, of course, that odd? can refer to even? but not the reverse. In this case, it doesn’t matter what order they are written, because they won’t be called until both are defined. We can solve this with the pattern of doing the binding in one place and then filling in the values later with set!:

This pattern is captured in the letrec macro:

The implementation is even simpler than let*:

(In a real implementation, however, the initial binding is not #f, but a special undefined value that cannot be used in a useful way, like #f can. Unfortunately, there are some problems with such a value, but that’s a topic for another day.)

The last binding form we’ll discuss isn’t a standard one and doesn’t really have much of a use, but it’s very cute. It’s called letwreck and it combines all the best features of let, let*, and letrec but in a way where you can pick what behavior you want for each binding!

The key to letwreck is that each binding explicitly specifies which other bindings it can see:

The implementation is very exciting. The key idea is to use a letrec on the outside but with a new name for each binding. Then, inside of the right-hand sides, create a local macro that renames uses of the original name to the new name (but only for the ones explicitly mentioned.) Finally, around the body of the letwreck, rename all uses of the original names to the new ones. This renaming is accomplished through make-rename-transformer, which is a special macro-producing function that renames uses to its argument, where in function or identifier position, even when used with set!.

Isn’t that great? The idea for this macro comes as a response to a November 10th, 1995 comp.lang.scheme post from Shriram Krishnamurthi (my PhD advisor) when he was a fresh PhD student at Rice. It came from Alan Bawden, but no implementation was given at the time. (The earliest I can find is Petrofsky’s in 2001.) I think my implementation is particularly tight and beautiful.

1 Yo! It’s almost time to go!

But first let’s remember what we learned today!

All you need is lambda (all together, now!)

Actually, if you refer to 2013-07-15: Symmetry in Function Calls and Returns you’ll see that you can’t build everything on lambda once you have multiple value co-arguments.

The tower of macros can get tall quickly, particularly if you make very useful and generic macros.

Macros can do crazy things.

If you’d like to run this exact code at home, you should put it in this order: