Dive deeper into macros: stackerizer

Simpli­fying a vari­adic func­tion

In stackerizer, our + and * oper­a­tions will take any number of argu­ments. To use the mathy word, they are vari­adic. But in our stacker target language, those + and * oper­a­tions take only two argu­ments (mathy word = dyadic). So our first chal­lenge is to figure out how to decom­pose a call to a vari­adic func­tion into some combi­na­tion of calls to a dyadic func­tion.

Let’s set up a simple test case:

Of course, when we run this, we’ll get an error:

That should be totally unsur­prising. Our "stackerizer.rkt" is almost blank. Let’s update it like so:

First, we’ll provide our + and * func­tions, just as we did in stacker.

We stip­u­lated in spec­i­fi­ca­tion and setup that stackerizer would only take one S-expres­sion as input. There­fore, we’ll make a stackerizer-mb that accepts one S-expres­sion, denoted by EXPR, and passes it through. As we did in stacker, we use rename-out to export this macro with the correct #%module-begin name.

When we run "stackerizer-test.rkt", we’ll get a new result:

Very good. But our + expres­sion has four argu­ments. We need to put that oper­a­tion in terms of dyadic oper­a­tions.

Hope­fully we remember from sixth-grade math that addi­tion is asso­cia­tive and commu­ta­tive. That means we can group the argu­ments as we wish, and perform the addi­tions in any order. For instance, this S-expres­sion will eval­uate to same result as the last one:

This new expres­sion uses only dyadic oper­a­tions. The first addi­tion combines (+ 3 4), the next addi­tion combines (+ 2 first-result), and so on. Further­more, this pattern of nested addi­tions could be extended to any number of argu­ments.  + Being able to iden­tify patterns in code is an essen­tial skill for writing good macros, since a macro works by matching patterns in the code and system­at­i­cally rear­ranging their elements.

Let’s consider another way we could decom­pose this expres­sion into dyadic oper­a­tions:

Also math­e­mat­i­cally sound. But suppose that our argu­ments are instead 1 2 3 4 5. Where would we put the 5? The decom­po­si­tion pattern above is a dead end, because it only works with an even number of argu­ments.

Whereas with our first pattern, it’s easy to include a new argu­ment:

In effect, we can think of this as the spec­i­fi­ca­tion for our vari­adic-to-dyadic macro: the macro needs to rewrite an expres­sion like (+ 1 2 3 4 5) to look like (+ 1 (+ 2 (+ 3 (+ 4 5)))), for any number of argu­ments.

From pattern to macro

Now we can write the macro that will convert the vari­adic + into a dyadic version using this pattern. Let’s add this code to "stackerizer.rkt":

This is the first time we’ve seen define-macro-cases. It works like define-macro. But instead of matching a single syntax pattern, it lets us specify a series of patterns to match. It works like a cond expres­sion: when a left-hand syntax pattern matches, the code on the right side of the branch—also known as a syntax template, for self-evident reasons—is returned. Other­wise, the next pattern is tested.

We’re also doing some­thing sneaky: we’re naming our macro +. This means that we’ll over­ride the usual defi­n­i­tion of + (= a func­tion that adds) and turn it into a macro that does some­thing else.

What does it do, exactly? Let’s start with the first branch:

The pattern on the left will match a single-argu­ment addi­tion like (+ 42). The + in the pattern matches liter­ally.  + An iden­ti­fier in a syntax pattern matches an iden­ti­fier in the input “liter­ally” when both their datums and their bind­ings match (also known as matching in the sense of free-identifier=?) We’ll match the argu­ment within the pattern to the pattern vari­able FIRST. Within a syntax pattern, an all-caps iden­ti­fier like FIRST will match anything and assign it that name.

As for the addi­tion oper­a­tion itself, (+ FIRST) is equiv­a­lent to adding nothing. So we’ll just return a syntax object containing only our FIRST pattern vari­able. As usual, to make a syntax object within the current lexical context, we use the #' prefix, so the result is #'FIRST. Easy.

Now the less easy second branch:

The syntax pattern in this branch will match a vari­adic addi­tion like (+ 1 2 3 4 5). The first argu­ment is matched to FIRST, and the remaining argu­ments are matched to NEXT ..., where the ellipsis gathers every­thing that follows. Note that a pattern vari­able with an ellipsis is allowed to match zero argu­ments. That means this pattern could also match some­thing like (+ 42). But in this macro, our first branch will match that case, so (+ 42) would never reach this branch. That also means that the pattern in this branch is guar­an­teed to match two or more argu­ments.

On the right side, we decom­pose our vari­adic addi­tion into a dyadic addi­tion. For proto­typing purposes, we’ll simu­late the conver­sion by using the place­holder 'dyadd symbol to repre­sent a dyadic addi­tion. We see it has two argu­ments, as it must. The first argu­ment will be FIRST.

The second argu­ment, however, is where the magic happens. We take the rest of our argu­ments, which are stored in NEXT ..., and pass them as input to our + macro. This idea of a func­tion or macro calling itself is known as recur­sion. We’ll be seeing a lot more of it. The core idea of recur­sion is breaking down a task into smaller versions of the same task. Here, every time the macro reaches this branch, it peels off the first argu­ment, and recur­sively calls itself using the other argu­ments. Even­tu­ally, there will only be one argu­ment left, which will be handled by the first branch.

Let’s see how this works. Save "stackerizer.rkt" and try running these test files. This time, every + in the test program will be inter­preted as a call to our new + macro. When called with one argu­ment, the macro just returns that argu­ment:

When called with more argu­ments, the macro calls itself recur­sively, thereby returning recur­sively nested lists with 'dyadd.

Notice how this last result follows the (+ 1 (+ 2 (+ 3 (+ 4 5)))) pattern we designed earlier. We’re on the right track. In fact, to get things a little closer to the goal, let’s go into our + macro and swap out 'dyadd with '+ like so:

Let’s be clear: that '+ is a symbol consisting of one literal plus sign. It is not the same as the vari­able + that repre­sents our macro (just like the string "+" also is not the same as +). Let’s save "stackerizer.rkt" and try running "stackerizer-test.rkt" again:

That takes us even closer to the goal. We’ll also need to deal with *, of course, but that will follow the same pattern. Let’s return to that after we’ve tackled the other lingering problem we left for ourselves.

From nested to flat

stacker only han­dles a flat list of argu­ments, but stackerizer allows nested expres­sions. So we have to flat­ten the nest­ed struc­ture into an equiv­a­lent list.

As before, we’ll start by working through a simple example. In the last section, we figured out how to convert a stackerizer expres­sion like (+ 1 2 3 4) into one that looks like (+ 1 (+ 2 (+ 3 4))). This time, suppose we start with that:

How would we write that nested expres­sion in stacker? The expres­sion would be eval­u­ated from inner­most to outer­most, so the initial (+ 3 4) expres­sion would start our stacker program:

This would leave 7 on the stack. So if we wanted to then add 2, we would write:

And then 1:

From this, the pattern emerges: we just remove the paren­theses, keeping the argu­ments in order, and then “rotate” the program 90 degrees coun­ter­clock­wise. We do that by printing them in reverse order, one per line.

This kind of trans­for­ma­tion is best accom­plished in our stackerizer-mb. Let’s update it as follows:

Recall that in the first version, we just passed through the EXPR argu­ment untouched. This time, we’ll flatten it (which is equiv­a­lent to removing the inner paren­theses) and reverse the order. After that, we use for-each with displayln to print each item in this list on a sepa­rate line. When we run our test program again:

We’ll now get:

At this point, it might be clearer why we used the '+ symbol in our macro: when printed with displayln, it looks just like an ordi­nary + oper­ator in a stacker program.

We’re one giant step closer to the goal. We just need to go back and put in our * oper­ator.

Macros making macros

The easy way to support our * oper­a­tion would be to copy the macro we made for + and change it to use *:

But this would break the heart of any expe­ri­enced Rack­e­teer. Since we’re making a macro anyhow, we might as well make one that can generate code for both these vari­ants.

Macros are perfectly happy to make other macros. We just have to ask. In "stackerizer.rkt", let’s delete our + macro and replace it with this new define-op macro:

How did we come up with this? Let’s convince ourselves that there’s nothing myste­rious happening here. We just need to follow the macro recipe we’ve used before. We start with the + macro we already made:

We wrap it inside a new define-macro form with the name define-op, taking a single argu­ment named OP, and apply the #' prefix to turn our existing code into a syntax object:

We replace the occur­rences of our specific + oper­a­tion with the new pattern vari­able OP. And when we say 'OP, it’s short­hand for (quote OP), so the OP is replaced with its actual value before the ' is applied:

And finally, some fiddly but neces­sary house­keeping. We want our ellipsis oper­a­tors to be used in the patterns of the result macros, not the define-op macro itself. So we “escape” them with the special (... ...) form:

More gener­ally, the (... pat) form means “escape all ellipses that appear within pat”. So (... ...) escapes a pattern consisting of a single ellipsis. We can also write longer patterns like (begin (... (foo ... (bar ...)))) and the two nested ellipses would be escaped, just as if we had escaped them indi­vid­u­ally by writing (begin (foo (... ...) (bar (... ...)))).

All that’s left to do is invoke our new macro with the desired names:

That’s it. Each call to define-op creates a new macro using the same template. Then, both + and * will be set up correctly.

Ellipsis power

Our define-op macro will work fine as is. But let’s learn one more thing about the ellipsis oper­ator, which turns out to be a serious macro power tool.

We saw that in a syntax pattern, an iden­ti­fier followed by an ellipsis like FOO ... will match a list of elements (including possibly zero elements). Then, when used in a syntax template, FOO repre­sents the first element of that list, and ... repre­sents the rest.

But when we use an ellipsis in a syntax template, it’s working harder than we might suppose. The ellipsis doesn’t just mean “put the other elements here”. It means “handle the other elements the same way we handled FOO”. So in a syntax template, we’re allowed to sepa­rate FOO and its ellipsis. What­ever we do to FOO ends up as a proto­type for the rest of the list, repre­sented by ....

Let’s try a simple example to see how this works. This lister macro will match its input argu­ments to the ARG ... pattern vari­able. Then we use ARG ... to insert them into the template in the same order:

Now consider the wrap macro below. It’s like lister. But in the syntax template, ARG is used sepa­rately from the ellipsis. We put ARG in a sublist with 42, and then the ellipsis takes care of doing the same thing to the rest of the matched argu­ments:

We can even use ARG multiple times in the template, and the ellipsis will still do the right thing:

Now we can recon­sider our define-op macro. Let’s replace it with a define-ops macro that will let us generate both our + and * oper­a­tions with one macro call. In the real world, this would be a point­less opti­miza­tion. But we’re just looking for a pretext to use another ellipsis. Here’s the new code:

What’s changed here?

First, we add an ellipsis to the initial syntax pattern for the macro, so instead of (define-op OP), we have (define-ops OP ...). This makes our macro vari­adic.

Then, within the syntax template, we surround every­thing with a new (begin ···) form. A syntax template can only contain one top-level expres­sion, so begin is just a way of grouping multiple expres­sions into one.

The code in the middle for the OP macro is the same as before. But after the end of this macro code, we add the ellipsis that corre­sponds to the OP pattern vari­able. This ellipsis applies this macro-code template to the other matched argu­ments, just as it was applied to OP.

Finally, we invoke our new macro with (define-ops + *).

Again, in the real world, we wouldn’t bother upgrading define-op to define-ops. But now we’ve seen how the ellipsis lets us repeat part of a syntax template for each member of a list of matched argu­ments.

Our finished expander should look like this:

Testing our language

Now let’s run our orig­inal test programs. First, the old favorite:

When we run this module, we get:

Then we try:

This time, we get:

Exactly right.