Make a language in one hour: stacker

The expander

To recap—every language in Racket has two essen­tial compo­nents:

We’re done with our reader. Now we’ll make our expander.

First, why is it called an expander? Recall that our reader consisted of a read-syntax func­tion that surrounded each line of the source file with (handle ...), in essence “expanding” it. The expander will perform a similar process on the rest of the code, with the help of macros.

Intro­ducing macros

It turns out that a lot of things in Racket that look like normal func­tions are actu­ally copying & rewriting code when the program is compiled (an event we’ll call compile time) rather than being invoked when the program is eval­u­ated (an event we’ll call run time). Suppose we use and within a program like so:

From afar, and looks like a func­tion. But it’s not. Rather, at compile time, this use of and gets expanded—that is, rewritten—so it looks like this:

This is the code that actu­ally gets eval­u­ated at run time. Let’s not be alarmed. These nested if condi­tionals mean the same thing as our orig­inal and. The expander has simply rewritten the and expres­sion as the equiv­a­lent nested if expres­sions.

Within Racket, and belongs to a special and impor­tant class of func­tions called macros. Macros have a restricted inter­face: they take certain code as input (pack­aged as a syntax object), and return other code as output (also as a syntax object). Thus, macros are some­times known more precisely as syntax trans­formers. We can think of them as a sophis­ti­cated form of search-and-replace—they’re like regular expres­sions designed to work on code frag­ments, rather than strings.

Strictly speaking, macros are func­tions, but it’s conven­tional in Racket to call them macros, and reserve the term func­tion for a proce­dure that’s eval­u­ated at run time. So if we talk about “converting a func­tion into a macro”, that’s the intended contrast.

Macros are also known, espe­cially within the Racket docu­men­ta­tion, as syntactic forms or just forms—a nice term, because it empha­sizes that a macro doesn’t eval­uate the code it gets as input. Rather, it imple­ments a template for putting items into certain posi­tions, like filling in the blanks of a form. We could, for instance, use the and form like this:

If and were a func­tion, these argu­ments would be eval­u­ated first, and the program would end with error: boom before the argu­ments were ever passed to and.

But because and is a macro, it happily rewrites our code as usual:

When this new code runs, we still get an error, of course. But the and macro was able to complete its work anyhow. This brings us to the three golden rules of macros:

Under this defi­n­i­tion, our read-syntax func­tion doesn’t qualify as a macro. It didn’t take a syntax object as input—rather, it took two input argu­ments (a path and an input port) and made a syntax object from that.

Because macros run at compile time and have a restricted inter­face, they’re not as versa­tile as ordi­nary func­tions. For this reason, a macro is not the tool of first resort. Still, macros are useful & impor­tant because they can do things that ordi­nary func­tions cannot.

As we’ll see, the linchpin of our expander will be a macro.

Before we enter the hall of the macro king

Racket’s macro system is its crown jewel. Refined for nearly 20 years, it’s a work of great science and beauty. It’s also funda­mental to how Racket models the imple­men­ta­tion of languages. There­fore, anyone who wants to make languages with Racket has to be willing to learn a few things about macros.

That said, though the macro system is always rewarding, it’s not always easy. For most program­mers, these are new & unfa­miliar concepts. Don’t panic. These ideas aren’t esoteric or compli­cated. They just intro­duce a new way of thinking about program code. Most of us haven’t thought about code this way because we haven’t worked with languages with an elegant macro system like Racket’s.

What does the expander do?

If the reader was respon­sible for the form of the code, we could say the expander is respon­sible for its meaning. The expander’s job is to prepare the code so Racket can eval­uate it.

Prepare it how? The code can be eval­u­ated only if every name used in the code has a connec­tion to an actual value or func­tion. In Racket, a “name used in the code” is called an iden­ti­fier. “A connec­tion to an actual value or func­tion” is called a binding. So we’d say that the expander prepares the code for eval­u­a­tion by ensuring that every iden­ti­fier has a binding. Once an iden­ti­fier has a binding, it becomes a vari­able.

We already came across the ideas of iden­ti­fiers and bind­ings when we tested our stacker reader without an expander. Recall that we got this error:

Now we know what it means. The code from the reader referred to a handle iden­ti­fier, e.g.:

This expres­sion means “call handle with the argu­ment 4.” But the expander hadn’t given handle a binding. Thus we got the “unbound iden­ti­fier” error.

Within the expander, we have three basic tech­niques for adding bind­ings to code:

We’ll use all three tech­niques in our stacker expander.

Designing our expander

As we did with our reader, let’s pencil out what our expander needs to do.

In our case, the code we’re getting from the reader will look like this:

From this sample, we can set out the tasks for our expander:

Once we have these elements in place, the stacker language will work.

Program­ming our expander: output

Let’s think about the state of our code when the expander starts. The reader has just finished its work—meaning read-syntax has returned code describing a module expres­sion, pack­aged inside a syntax object. For example, if the stacker reader started with source code like this:

It would return the following module as a syntax object:

This becomes the starting input for the expander.

We saw that Racket starts the reader for a language by invoking a func­tion called, by conven­tion, read-syntax. Simi­larly, Racket starts the expander for a language by invoking a macro called, by conven­tion, #%module-begin. Every expander must export a #%module-begin macro.  + #%module-begin belongs to a special class of macros called inter­po­si­tion points.

Racket converts the module expres­sion above into an invo­ca­tion of the #%module-begin macro by passing it the code inside the module:

Like any macro, #%module-begin will take this code as its input. And like any macro, #%module-begin will rewrite it as neces­sary and return the new code pack­aged as a syntax object. This new code will replace the whole #%module-begin expres­sion above, and expan­sion & eval­u­a­tion will continue from there.

Because every Racket language exports a #%module-begin, the most common way to imple­ment the #%module-begin in a new language is as follows:

Let’s open "stacker.rkt" and update it like so:

At the top, we see good old read-syntax, just as we left it.

Below that, our defi­n­i­tion of #%module-begin. Let’s step through each part.

When we made our reader, we saw that an ordi­nary func­tion is defined with a list of input argu­ments. But because a macro gets a chunk of code, we typi­cally define a macro with a syntax pattern instead. A syntax pattern is like a regular expres­sion: it breaks down the input into pieces so they can be manip­u­lated & rearranged.

Our ordi­nary define doesn’t support syntax patterns in the first line. Instead, we use define-macro, which does. This first line says we’re defining a macro called stacker-module-begin. HANDLE-EXPR is a pattern vari­able—meaning, a named match within the syntax pattern. When used with an ellipsis ..., this pattern vari­able will match each line of the code passed to the macro. (We’ll defer the details till later, though the curious can detour through syntax patterns.)

Then we have the return value of our macro:

Syntax objects in Racket are so common that we have a few ways to make them. In our read-syntax we’re using datum->syntax to make a syntax object from module-datum.

This time, we’re using some new nota­tion—the prefix #'—to make code into a syntax object. It’s similar to the ' prefix we’ve already used that makes code into a datum. But the #' prefix not only creates the datum, but also captures the current lexical context, and attaches that to the new syntax object. Lexical context is the fancy phrase for “a list of avail­able vari­ables”. In prac­tice, what it means is that a syntax object made with #' will be able to access all the vari­ables defined at that point in the code.

One of these is the HANDLE-EXPR ... pattern vari­able. Those lines of code will just be merged into the new syntax object.

Another vari­able is #%module-begin. Recall that our plan is to take our input code and pass it to the next #%module-begin in the chain. When we go into DrRacket and put the cursor over the #%module-begin, we see a purple arrow and a popup message that says imported from "br/quicklang":

We don’t need to explic­itly import this #%module-begin. When we use any language, including br/quicklang, we get access to its bind­ings. And br/quicklang, like every language, provides its own #%module-begin.  + We could also import and use the #%module-begin from another language, but in this case, there’s no need.

Finally we have to make stacker-module-begin avail­able outside stacker.rkt:

As before, we use provide. But this time, we use the rename-out qual­i­fier so that stacker-module-begin is avail­able outside this source file with the correct #%module-begin name.

Why didn’t we just name our macro #%module-begin at the start? Suppose we had written our macro like this:

The problem here is that we’d be creating a naming conflict between two #%module-begin macros: the new one we’re defining, and the one from br/quicklang that we’re hoping to rely on. As it stands, this newly defined #%module-begin will just call itself, creating an infi­nite loop. Thus, we give our new #%module-begin macro a tempo­rary, non-conflicting name, and change it as part of the provide expres­sion.

Testing our expander

Let’s see if our simple #%module-begin works. Here’s what "stacker.rkt" should look like:

Now run "stacker-test.rkt" (which is the same as ever):

We get an error. It begins:

That’s the same error we got when we tried to run our program without an expander. But we haven’t gotten around to defining handle yet, so we shouldn’t be surprised that the error persists.

Can we at least check that our macro is working? Sure. Let’s reuse the shortcut we used to test the reader the first time: adding a ' prefix to the output so it gets converted back into literal code. This time, we add the ' prefix to the HANDLE-EXPR inside our macro defi­n­i­tion like so:

Now when we run "stacker-test.rkt", we get:

What we’re seeing is our source code, converted into (handle ···) expres­sions by the read-syntax func­tion in our reader, then converted into datums by the #%module-begin macro in our expander, and then printed in the output window of DrRacket.

That’s good news—we’ve veri­fied that we can make a round-trip from our source file, through our reader, through our expander, and back. We’re another step closer to hav­ing a work­ing lan­guage.

Let’s remove the ' prefix we just added to the front of HANDLE-EXPR, and move on.

Program­ming our expander: bind­ings

When we designed our expander, we set out three tasks:

We completed the first task—we made #%module-begin. So now we need to work on the other two—imple­menting a stack and creating bind­ings for our iden­ti­fiers.

First the stack, which we imple­ment using Racket list oper­a­tions:

Our stack starts out as the empty list.

pop-stack! removes the top argu­ment from the stack and returns it. We do this in three steps. First, we get the first argu­ment from the stack and assign it to a tempo­rary arg vari­able. Second, we set! our stack equal to the rest of the argu­ments after the first.  + By conven­tion, Racket func­tions that update the value of a vari­able are named with a ! at the end. For other naming conven­tions, see func­tions. Third, we return arg as the result.

push-stack! puts a new argu­ment on the stack. We do this with cons. cons is one of the oldest Lisp func­tions, getting its name from its role constructing a new item in memory. (For more about cons, see pairs.) Every time we cons an item onto the list, we create a new list that’s one bigger. After we push the argu­ment, we set! our stack equal to this new, larger stack.

Now let’s add our long-awaited handle func­tion. Let’s remember how handle is invoked in a stacker program:

We observe that it can have zero or one argu­ment. If it has an argu­ment, it’s either a number or a stack oper­ator (either + or *). So let’s add the following handle func­tion:

Then we step through each line:

We define our handle func­tion to take one argu­ment, called arg. By declaring arg in brackets with a default value of #f, we make it an optional argu­ment. So if handle is called with an argu­ment, arg takes that value; if not, arg is set to #f.

This cond intro­duces a condi­tional expres­sion with two branches. The condi­tion on the left side of a branch is tested. If the condi­tion is true, the expres­sions on the right side of the branch are eval­u­ated. If the condi­tion fails, we move to the next branch.  + Further details in Booleans and condi­tionals. The first branch tests if arg is a number?. If so, we put it onto the stack with push-stack!.

In the second branch, we test if arg is equal? to one of our stack oper­a­tors. If so, we retrieve the first two elements from the stack with two calls to pop-stack!. We apply arg to these values by putting it in the func­tion posi­tion of a new expres­sion with the stack values as argu­ments. We store the result in op-result. We then push op-result onto the stack.

What if handle is called with no argu­ments, and arg is #f? We were always plan­ning to ignore that case. So we don’t need to add a branch to our cond expres­sion to deal with it. We just let it fall through. Like­wise, any other input that doesn’t meet one of our condi­tions will be ignored.

Finally, we make handle avail­able outside our source file with the usual provide.

We also need to provide bind­ings for + and *. This is easy, because our br/quicklang language already defines these func­tions. We just need to borrow these bind­ings for stacker. We can do that by adding one more provide to our source file:

Our "stacker.rkt" should now look like this:

Testing our expander with bind­ings

We’re getting close. Let’s run our "stacker-test.rkt" file, which still looks like this:

The good news—no errors.
The bad news—no program result, either.

This is a simple fix. The result of our program is what­ever value is sitting on top of the stack at the end. So we add one line to our stacker-module-begin, to display the first element of our stack after all the HANDLE-EXPR lines have been eval­u­ated:

If we run "stacker-test.rkt" one more time, we get:

That’s it—we’ve made our first program­ming language.