Follow the grammar: bf

In stacker we wrote our expander using imper­a­tive program­ming. In funstacker we upgraded the expander with func­tional program­ming. To nail down this contrast, we’ll do the same with bf: we’ll first write the expander in an imper­a­tive style, and then upgrade it to a func­tional style. (Those who already feel comfort­able with func­tional program­ming can move ahead to the next section.)

Starting the expander

Here’s where we left our expander at the end of the last section:

We don’t need to change anything in our manda­tory #%module-begin macro. So we’ll move on to the other macros and func­tions we need to handle the contents of PARSE-TREE.

Following the grammar into the expander

We saw how the reader follows the grammar while parsing the source code, producing a parse tree whose nodes cor­re­spond to the names and pat­terns of the pro­duc­tion rules of the grammar.

In turn, we can follow the grammar further, and use these produc­tion rules to design our expander. Once again, here’s our bf grammar:

What this grammar tells us is that we need to handle three types of parse-tree nodes—bf-program, bf-op, and bf-loop. In the expander, these will become the names of macros or func­tions that will imple­ment each type of node as stan­dard Racket code.

Further­more, the pattern on the right side of each rule tells us what kind of input the corre­sponding macro or func­tion has to accept. So we don’t have to bumble around in the dark. The grammar gives us specific marching orders.

Let’s say it one more time, because it’s such a tremen­dous shortcut:

Given a certain produc­tion rule, how do we know if we should imple­ment it with a macro or a func­tion? The rule of thumb is to use a func­tion where we can, and a macro where we must.

Often, a produc­tion rule does some­thing simple, like return its argu­ments in a list or print them. In those cases, the rule can be imple­mented with a func­tion.

But other times, the produc­tion rule needs us to rearrange the code in ways that an ordi­nary func­tion won’t support. In those cases, we can esca­late to a macro.

But for bf, we’ll only use macros, so we can get a little more prac­tice with how they work.

To see how this works, let’s pencil out a tiny example. This minia­ture bf program:

Will be parsed into a tree that looks like this:

Once we’ve written the corre­sponding macros, our expander will proceed as follows:

The result of this expan­sion needs to be a stan­dard Racket program that can be eval­u­ated to produce a result.

From grammar to syntax pattern

When we first used define-macro, we learned that the first line of the defi­n­i­tion relies on a syntax pattern. A syn­tax pat­tern does for syntax objects what a reg­u­lar expres­sion does for strings: it breaks down the input into pieces so they can be manip­u­lated & rearranged.

Let’s start with our bf-program macro. It’s easy—it doesn’t do anything. It’s just the top-level wrapper for the other bf commands that do the real work. According to the grammar, this macro has to be able to handle any number of bf-op or bf-loop argu­ments:

So we’ll define our macro using this syntax pattern:

The pattern has three parts.

Taken together, our syntax pattern above will define a macro called bf-program that can take any number of argu­ments, which are matched to OP-OR-LOOP-ARG ....

This syntax pattern will handle every possible pattern of argu­ments described by the bf-program produc­tion rule in the grammar. In general, as we convert the grammar into macros, we’ll essen­tially be trans­lating each produc­tion rule into a syntax pattern.

Here’s the rest of the bf-program macro:

We recall that the return value of a macro is a syntax template for the rewritten code. In this case, because bf programs have their own printing commands, we’ll just pass our input argu­ments to the func­tion void, which discards them.  + Similar to piping output to /dev/null in Unixy oper­ating systems, for those who have done that. When we write our syntax template, we use the pattern vari­ables and ellipses from the syntax pattern. When the macro is invoked, they’ll be replaced with the actual input.

Next, our bf-loop macro. Let’s review the produc­tion rule for bf-loop, so it can guide our syntax pattern for the macro defi­n­i­tion:

This is the same as the bf-program rule, but with "[" and "]" surrounding the bf-op or bf-loop argu­ments in the middle. So our syntax pattern for this macro will look similar to the bf-program macro, but with brackets added:

Now we can put in the macro:

We remember from how bf works that the argu­ments inside a loop are eval­u­ated repeat­edly until the current byte is zero. We can imple­ment this behavior with an until condi­tional, which keeps eval­u­ating its body expres­sions until the current byte is zero?. To get that value, we’ll call a current-byte func­tion that doesn’t exist yet (but we’ll add it in a minute).

From one syntax pattern to more

Now to handle bf-op. As we saw in the grammar and sample parse trees, a bf-op node holds a char­acter from the source code that tells us how bf-op should behave:

As we did with bf-program and bf-loop, we’ll trans­late this produc­tion rule into a syntax pattern for the bf-op macro.

The wrinkle this time is that bf-op has six possible patterns. To handle this, we’ll use a variant of define-macro called define-macro-cases that will let us set up our macro with six cases, one for each char­acter we might get from bf-op.

Similar to cond, define-macro-cases can have any number of branches. Each branch has a syntax pattern on the left, and a syntax template on the right. When the macro is invoked, each pattern on the left is tested in order. When a pattern matches, the syntax template on the right is returned. So if we just fill in the syntax patterns, we get this:

Our bf-op macro needs to convert these six patterns into func­tions that imple­ment the bf language. For now, let’s put in the names of those func­tions—we’ll fill in their defi­n­i­tions in a moment. The finished bf-op macro looks like this:

Now we need to add the missing func­tions that imple­ment the rest of the bf language.

Imple­menting the BF byte array

Recall from how bf works that when a bf program starts, it creates an array of 30,000 bytes (initial­ized to 0) and a pointer into that array (initial­ized to the 0 posi­tion). The array and the pointer are state values: they keep a record of what’s happened in the program so far.

We’ll follow this descrip­tion by imple­menting the byte array as a Racket vector. Unlike a Racket list, a vector is not a series of linked pairs. It’s just a block of memory, so it’s typi­cally better in situ­a­tions that require random, nonse­quen­tial access to data elements.  + See data struc­tures for more about which Racket data struc­tures are suit­able for which needs.

The make-vector func­tion takes two argu­ments: a size for the vector, and a default value for its cells. Our pointer can just be the number 0. Let’s add them to "expander.rkt":

Unlike our macros, we don’t have to provide our array vari­ables because they don’t need to be visible outside the expander. They’re just for internal use.

The current byte is the byte in the array at the loca­tion indi­cated by the pointer. So our current-byte func­tion just gets the value from arr at the posi­tion ptr using vector-ref:

Other func­tions also need to set the current byte. For that, we use vector-set!:

Then we need to make the func­tions used in our bf-op macro. The gt and lt func­tions—corre­sponding to the bf oper­a­tions > and <—increase or decrease the pointer by one. As we did in stacker, we mutate our state vari­able ptr, using set!:

The plus and minus func­tions—corre­sponding to the bf oper­a­tions + and -—increase or decrease the value of the current byte. We can express these oper­a­tions in terms of current-byte and set-current-byte!:

The period func­tion, corre­sponding to a . in bf code, writes the current byte to stan­dard output. We use the Racket library func­tion write-byte to help out:

Finally, the comma func­tion, corre­sponding to a , in bf code, sets the current byte to one read from stan­dard input. We can do this with the Racket func­tion read-byte:

Taken together, our expander should now look like this, with the new array imple­men­ta­tion high­lighted:

Testing our BF expander

Let’s confirm that our test file "atsign.rkt" is ready to go:

When we run this, we’ll see the result:

Great—this shows that the macros in our expander are success­fully converting a bf parse tree into func­tions that correctly imple­ment the bf language rules.

What if we try to run our “Hello World” bf program with our new imple­men­ta­tion?

How about that facto­rial gener­ator? (Warning: this program will emit facto­rials until you stop it. To inter­rupt a running program in DrRacket, use the menu options Racket → Ask the Program to Quit or Racket → Force the Program to Quit):

That’s it—we’ve success­fully imple­mented the bf language.  + … minus some fiddly porta­bility details, which are too dull to pursue here.

In real life, we’d want to run a larger set of sample programs before drawing opti­mistic conclu­sions. But we’ll defer that kind of stress testing for a later tuto­rial.

The big but

In this version of the expander, we imple­mented bf in an imper­a­tive-program­ming style. We set up two state values (arr and ptr) and called func­tions (gt, lt, plus, and minus) that mutated them. This wasn’t wrong—our test programs worked. And it had a certain logic, as bf itself is an imper­a­tive language. Who knows—on a certain set of test programs, this may even turn out to be the fastest approach.

But it’s not idiomatic in Racket, where func­tional program­ming is the favored style. So we’d be short­changing ourselves if we stopped here. Now that we have a mental model for how bf works as a Racket language, let’s convert our expander to a func­tional-program­ming style.