Follow the grammar: bf

Admit­tedly, we took a few short­cuts in stacker. To be fair, we had a lot of ground to cover. We had to learn about the two essen­tial compo­nents of a Racket language—the reader and the expander. We had to learn some basic concepts of the Racket language itself like expres­sions and macros. In funstacker we filled in some details about func­tional program­ming.

But with that under our belt, we can migrate toward a more real­istic tech­nique that can be adapted to other language projects. In this tuto­rial, we’ll lay the foun­da­tion for this new tech­nique. In the rest of the tuto­rials, we’ll refine and adapt it.

Here, we’ll imple­ment a real (but still simple) program­ming language called bf. We’ll orga­nize this tuto­rial around a new idea—a grammar, which lets us specify the struc­ture of a language. We’ll also add two new pieces to our reader: a parser and a tokenizer, which will help us convert our bf source code into a struc­tured repre­sen­ta­tion of a program.

Intro­ducing BF

bf was created as an exer­cise in program­ming-language mini­malism.  + bf is a common abbre­vi­a­tion of its full name, which rhymes with drain­suck. The bf language uses only eight char­ac­ters, which are never­the­less suffi­cient to make it Turing complete. For instance, here’s the tradi­tional “Hello World” program in bf:

And here’s a facto­rial gener­ator:

We can try these (and other) bf programs in DrRacket by using #lang bf-demo. This is the imple­men­ta­tion that we’ll build from scratch in this tuto­rial:

Is bf good for anything? In the sense of profes­sional advance­ment, no. But even though bf code looks cryptic, its under­lying struc­ture is simple. There­fore, it’s a good way to learn how to trans­late the spec­i­fi­ca­tion of a language into an imple­men­ta­tion. (Writing programs in bf will remain hard, however.)

How BF works

When a bf program starts, it creates an array of bytes in memory (by conven­tion 30,000 bytes long, each byte initial­ized to 0) and a pointer into that array (initial­ized to the 0 posi­tion). The current byte is the byte in the array at the loca­tion indi­cated by the pointer.

Then it runs the code of the bf program, which consists of six oper­a­tions:

bf also has a looping construct [···] that will repeat the code within the brackets until the current byte is zero. If the current byte is already zero, the loop will not run. Loops can be recur­sively nested within other loops.

Any other char­ac­ters in the source code, including white­space, are ignored.

Now intel­lec­tu­ally armed, we can puzzle out what this bf program will do:

We picture our array of bytes and our pointer at 0 (the first byte).

Greatest language ever! consists of char­ac­ters that are ignored.

++++-+++-++-++ is 11 incre­ments and 3 decre­ments of the current (first) byte, meaning we end up with a value of 8 in the current byte. (The + and - oper­a­tions could be in any order, and the result would be the same.)

[ A loop starts. The current byte isn’t 0, so we go inside the loop.

> The pointer moves to the second byte and, with the same

++++-+++-++-++ pattern, leaves a value of 8 there as well.

< We move the pointer back to the first posi­tion and

- decre­ment the value of that byte from 8 to 7.

] At the end of the loop, the current byte is 7, not 0, so we do it again. The value in the first byte thus serves as a loop counter. The loop will there­fore run a total of 8 times, leaving a value of 0 in the first byte and 64 in the second byte. After that:

> We move back to the second byte.

. We print the second byte. The char­acter with value 64 is:

Yes, that’s a lot of effort to print an @ sign. (We can run this program with #lang bf-demo to verify that it does.) Though bf may be inef­fi­cient, it’s not illog­ical. We might now recog­nize that this looping tech­nique is the basis of the “Hello World” program we saw before:

Don’t spend too long penciling it out, however—that’s why we’re making a bf inter­preter.

Process for imple­menting BF

Recall that every language in Racket must provide two func­tions:

As it turns out, a lot is riding on the S-expres­sions produced by the reader. Why? Because they become the input to the expander, and thereby influ­ence the rest of the imple­men­ta­tion. If our reader produces clean, well-struc­tured S-expres­sions, writing our expander will be easier. If not, then it won’t.

In stacker, we designed the language so that each line of the source became one S-expres­sion. That was simple, but not real­istic. Most program­ming languages have a more intri­cate struc­ture. A bf program, for instance, might be a flat list of oper­a­tions. But it also might have loops nested to any depth. We won’t be able to rely on the same shortcut.

“So how do we convert bf code into S-expres­sions? It doesn’t look anything like Racket.” There’s a secret weapon we can use to convert any well-spec­i­fied program­ming language—no matter how weird—into S-expres­sions. That tool is a grammar.