Understanding and Implementing a Macro System

Macros are a powerful tool that allow programmers to extend the syntax of a language. In a language with macros, features like for-loops, while-loops, and pattern matching can be implemented as a library by users of the langauge! In this post, we’ll discover what macros are, how and why to use them, and how to implement a tiny language with a simple macro system.

For this post, you’ll need some familiarity with Racket, but no familiarity with macros is required. If you don’t know what something is, click on the variable name in the code and you’ll be taken to its documentation.

Let’s say you want to swap two variables, x and y. This is how we’d do it normally:

If we did this often, it’d get pretty annoying to have to do the same thing every time. We should try to abstract it! Let’s write a function, swap!, to do it for us:

It didn’t work! This is because when you mutate an argument to a function, it doesn’t affect the variable you passed in. If we passed in some mutable structure like a box, we could mutate the box, but that’s not we want. We want to mutate variables. Is there a way to pass in a variable itself? Sort of, but not with regular old functions like this.

If you like to make abstractions to avoid repeating yourself, you’ve likely hit this sort of wall before. You want to make some abstraction, but functions aren’t enough for what you need.

One way to solve this problem is to dynamically generate code. For example, we could make a special pre-processor that detects usages of swap! and replaces them with the code that swaps the two variables.

That would work, but it sounds very messy. We’d need to make a parser for Racket programs, we’d have to carefully detect usages of things like swap!, and we’d have to implement all of the rewrite rules we want in the pre-processor. But what if this pre-processor was integrated into the language itself? After all, Racket already has a parser for Racket programs!

This is basically what a macro system is. Macros are like rewrite rules that rewrite the code before it runs. Racket, of course, already has macros:

We define macros with something like define-syntax-rule and we use them with the same syntax as function calls.

Macros are great for little rewrite rules like this, but they are also good for more complicated syntactic abstractions. For example, let’s pretend Racket doesn’t have any looping mechanisms. How would we implement while loops?

One easy way to do this would be recursion:

When you do a while loop like (while condition body ...) using recursion, it will generally look like this:

If the condition is truthy, we run the body and then recur to loop again. If it’s not, we’ll just stop looping and return nothing. And we need to kick the whole thing off with a call to go.

The actual implementation of the macro looks exactly like what we wrote:

The (let () ...) is just a little trick to allow us to use define and multiple expressions in the result of our macro.

This is pretty cool, and a little more complicated than our swap! macro, but it’s still just scratching the surface of what macros are capable of. We can implement entire domain specific languages with macros like match and class, and we can even embed entire programming languages like mini kanren.

Now that we know what macros are, let’s implement them! To do this, we’re going to make a little programming language that has a macro system. It won’t be as nice as Racket’s macro system, but it’ll give a sense of how macros work.

Before we start doing anything fancy with macros, let’s build a regular old interpreter for the lambda calculus.

We are, of course, going to be using s-expressions as syntax. For those unfamiliar, an s-expression is either an atom, like a variable name or a number, or a parentheses-enclosed list of s-expressions. This simple representation makes syntax very easy to manipulate as data, which is exactly what our macros will end up doing.

For example, the expression (add1 1) is represented as (list 'add1 1). The first element of the list is a symbol, 'add1, which represents a variable name. The second element is the number 1. Numbers just represent themselves.

To create s-expressions, we can use quote:

quote is so important, there is special syntax for it:

quote takes in an expression and returns the expression itself as data instead of evaluating it.

Another useful tool for building s-expressions is quasiquote and unquote:

quasiquote is like quote, but we can escape the quotation with unquote to actually evaluate an expression instead of just putting it right in the output as-is. This is sort of like format strings in Python or template literal strings in JavaScript, but for making s-expressions instead of strings.

Of course, this has a shorthand too:

In our little language, macros will be functions that take in an expression and return an s-expression. We’ll call these functions transformers. Like in Racket, macro usages will look just like function calls. But when a function call expression is a macro usage, instead of evaluating the function and arguments and passing them to the function, we’ll pass the whole macro usage expression to the transformer function.

For example, here’s what swap! will look like:

The transformer takes in the expression (swap! x y), which is a list of three elements. The second and third are x and y respectively. The first is just swap!. These types of macros are very annoying to write, which is one of the reasons why we have tools like define-syntax-rule.

For now, we’ll start out by making an interpreter for a language with just lambda expressions, function applications, variables, and constants like numbers. I’ll assume you’re somewhat familiar with lambda calculus interpreters so I won’t explain it in depth:

match has quasiquote patterns, which match quoted forms as their s-expressions and unquoted forms as patterns. So the pattern `(lambda ,argnames ,body) is equivalent to the pattern (list 'lambda argnames body).

We’re using a hasheq to represent our runtime environment mapping variables to values. We’re also using Racket functions to represent our functions, which is kind of cheating. But we’re not interested in writing a lambda calculus interpreter, we’re interested in writing a macro system! So we’ll leverage as much of Racket’s interpreter as we can.

Let’s also add some built-in functions and special forms:

Since we’re representing functions as Racket functions, we can just put Racket functions into our initial environment to add built-ins.

if, let, and begin are unsurprising. For quote, we just return expr without evaluating it. Also, we used a list pattern for it, but we could’ve used `(quote ,expr) or even `',expr. I just decided to use a list pattern to avoid confusion, but these three patterns are equivalent.

You might be wondering how we can use the apostrophe shorthand in our language like in the last example. The racket parser (technically, the reader) translates 'expr into (quote expr) before macros expand or code runs (macro expansion refers to macro usages being re-written). So in the last example, our interpreter actually ends up getting the s-expression (list 'list 1 (list 'quote (list 'add1 'x))).

Now let’s implement quasiquote:

We recursively go through the expression’s children searching for unquote and evaluating those expressions when we find them. Without unquotes, we end up reproducing the original expression like quote. This is a much simpler, less powerful version of Racket’s quasiquote, but it’ll suffice for us.

Now, we’re ready to implement macros!

First, we made a struct for our transformers so we can distinguish between regular functions and macros. And to create macros, we have a different version of let called let-macro that turns the value into a transformer before binding it to the variable. Then, all we had to do was modify the application case to check if the function is a transformer or not. If it is a transformer, we apply it to the entire expression, which produces another expression. Finally, we evaluate the resulting expression. That’s it! Now we have macros.

The transformer stuff is really all there is to macros in our system. We only bothered doing quasiquote and all those other things so it would be easier for users of our language to write macros.

Racket’s macro system is much more sophisticated than the one we implemented here, of course. Unlike our language, Racket expands all macros away before any of the code runs. Another nice thing Racket’s macro system does is handle variable collisions for you. Remember how we made a tmp variable in our swap! macro? What if we did (swap! tmp y)? It’d break, right? Actually, no:

Racket’s macro system has a concept of macro hygiene, which makes it so you don’t have to worry about these kinds of variable collisions. It just takes care of it for you. How it works is really cool and worth its own post, so I won’t explain it here. But in our language, to avoid this problem, when writing macros, we have to use gensym to avoid user-supplied variables colliding with macro-introduced variables or vice-versa. gensym creates a unique symbol, so we don’t have to worry about collisions.

Speaking of swap!, unfortunately, the language we made doesn’t have mutable variables, so we can’t implement it. But if we had mutable variables, the code we wrote a while ago for it would work in our language. I chose not to implement mutable variables in this post because it complicates the interpreter and I wanted to keep it simple so we could focus on the macro system.

One interesting thing about our language is that macros are defined and expanded dynamically, rather than before the program runs like in Racket. Transformers are also evaluated against the current environment, which means they have access to local variables. In a language where expansion happens before the code runs, you wouldn’t be able to use local variables in the transformer directly.

Macros are very cool, and there has been a lot of work on developing powerful, easy-to-use macro systems over the years. This post just scratches the surface of what’s possible, but hopefully it gave some understanding of how a macro system works and why they’re so useful.