Make a language in one hour: stacker

Designing our reader

Recall the purpose of the reader:

Let’s visu­alize what our reader needs to accom­plish. At the end of the tuto­rial, our stacker-test.rkt program will look like this:

The first line—#lang reader "stacker.rkt"—is nota­tion that means “use the "stacker.rkt" module as the reader for this language.” But for now, let’s focus on the program instruc­tions below the #lang line:

Clearly, these are not paren­the­sized forms. How can we get there? We can see that stacker has one instruc­tion per line. So the simplest idea—never a bad place to start—would be for our reader to wrap paren­theses around each line:

The good news—these now look more like the paren­the­sized forms we need. The bad news—they’re not useful. Recall that a paren­the­sized form in Racket is treated as a func­tion call. But numbers aren’t func­tions. So expres­sions like (4) and (8) will produce errors.

Let’s try it in DrRacket. Open a new window with the default #lang br language at the top and try eval­u­ating (4):

We’ll get an error telling us that 4 is not a “proce­dure”—another word for a func­tion—“that can be applied to argu­ments”:

Our other two paren­the­sized forms—(+) and (*)—are valid func­tion calls. Again, we can verify this by eval­u­ating them in DrRacket:

But as it stands, they’re being eval­u­ated without any input argu­ments.  + Math fans can figure out why it makes sense that (+) eval­u­ates to 0 and (*) to 1. That’s wrong. They’re supposed to take their input from the top of the stack.

Our first idea—wrap­ping our argu­ments with paren­theses—won’t work. We need to handle the inter­ac­tion of our stack and the argu­ments in the program more care­fully.

Instead, suppose we have an inter­me­diary func­tion—call it handle—that inspects each instruc­tion and decides what to do. Further suppose that we wrap each program argu­ment like so:

What have we accom­plished? Our stacker argu­ments will no longer be treated as func­tion calls. Rather, they’re now input to another func­tion:

Now that we know what our reader needs to do, we can program it.

A peek into the future

“Wait—where does this magical handle func­tion come from?” Remember the other indis­pens­able part of our language:

With the reader, we’re putting our program into the proper form. With the expander, we’ll give meaning to these forms. So our handle func­tion will even­tu­ally be avail­able through our expander.

If it seems sneaky to make plans around a nonex­is­tent func­tion, don’t panic. The reader and expander always exist as a coop­er­ating pair. But they have distinct roles. So we want to put things in the right place. The handle func­tion itself belongs in the expander, not the reader.

Having glimpsed the future, we return to the code.

Program­ming our reader: output

As the first step in running a source file with a #lang line, Racket passes the source code to the reader for the language. It does this by invoking a func­tion called, by conven­tion, read-syntax. Every reader must export a read-syntax func­tion. Racket passes two argu­ments to read-syntax: the path to the source file, and a port for reading data from the file. We’ll come back to these.

For now, let’s consider the output. Every read-syntax has one job: to return code describing a module, pack­aged as a syntax object. Racket will replace the orig­inal source code with this module. This module, in turn, will invoke the expander for our language, trig­gering the full expan­sion of the module. After that, the module will be eval­u­ated normally by the Racket inter­preter. But all this happens under the hood—from the outside, all we see is that our orig­inal source code has been converted into a result.

Let’s step through these new concepts by working through a sample read-syntax:

To create a func­tion, we use define:

This line sets up a func­tion called read-syntax that accepts two argu­ments. These are posi­tional argu­ments, so we can name them what­ever we like. We’ll be boring and call them path and port.

We also need to export read-syntax so it’s avail­able outside this file. In Racket, all defi­n­i­tions are private by default. To make a defi­n­i­tion public, we use provide:

The body of read-syntax performs two tasks.

First, it reads the source code from port. A port is a generic inter­face for input (or output) that can be read (or written) incre­men­tally—that is, piece by piece. For instance, if we stop reading an input port, the port remem­bers where we stopped. The next time we read from the port, we can resume from the same place. Input ports are useful when we’re wary of the size of the file on the other side. It might be too humon­gous to fit into memory.

In stacker, that won’t be a problem. So let’s just read every­thing from our port at once:

We convert the contents of port to a list of strings by passing it to port->lines. We store the result in src-lines. (In this toy example, we won’t actu­ally use src-lines, but we will later on, in the finished version of this func­tion.)

The second task of read-syntax is to return code describing a module. In Racket, a module is the basic orga­ni­za­tional unit for program code. Like every­thing else in Racket, a module is an expres­sion. The code for a module expres­sion follows this pattern:

So our sample module code:

Means “a module named lucy, using the expander from the br language, that eval­u­ates the expres­sion 42.”

The module name is arbi­trary. It doesn’t affect how the module works.

The expander, however, is highly conse­quen­tial. It deter­mines how the expres­sions inside the module are inter­preted. Here, we can use the br short­hand because that language is already installed. But we can also use an explicit path string to desig­nate a source file with an expander, for instance:

We still need to convert our module code into a syntax object, which is a way of treating code as data. We can use a syntax object to store a chunk of source code so it can be eval­u­ated later. Here’s how we do that:

Finally, we need to return this syntax object as the result of the func­tion. Racket has no explicit return state­ment. The return value of a func­tion is just the last expres­sion that appears in its body. So as long as our syntax object is the last expres­sion in the body of read-syntax, we’re good.

Now we under­stand every­thing that’s happening in "stacker.rkt". We’ve defined a read-syntax func­tion that, when invoked, will return a syntax object describing a module, which can be eval­u­ated later.

Trying our sample reader

“Eval­u­ated later—like when?” When we invoke the stacker language. Let’s see how this works. We return to "stacker-test.rkt". This time, let’s insert some dummy argu­ments:

When we first tried to invoke the "stacker.rkt" language from within "stacker-test.rkt", we got an error, because we hadn’t yet made a reader.

Now we have. So let’s save the file and run it again. This time, we’ll get a different result:

What’s happening this time? The #lang reader line is respon­sible for invoking the reader for stacker. To do this, Racket calls our read-syntax func­tion. Our func­tion returns a syntax object that describes a module.

Here’s what happens next: the source code in "stacker-test.rkt" is entirely replaced with the syntax object returned by read-syntax. So under the hood, this file:

Becomes this:

Once our syntax object gets moved into its new loca­tion as real code, it looks just like our module-expres­sion datum, except that it’s no longer quoted. This makes sense—when we made the module datum, we wanted to treat the code as data, so we prefixed it with '. Now we want to reverse the alchemy, and treat the data as code. So it gets unquoted. After that, the module expres­sion is eval­u­ated, producing 42.

Let’s persuade ourselves that nothing spooky has happened. Our read-syntax is respon­sible for reading the lines of our source file (for now, ignoring them) and returning a syntax object. The new magic we’re witnessing is that after Racket has passed the source code to read-syntax as an input port, it replaces that source code with the result from read-syntax.

Let’s ensure that we’re unim­pressed by this magic. We can accom­plish the same trans­for­ma­tion by hand. We replace the #lang line and source code in "stacker-test.rkt" with our module code (this time without the ' prefix, because we want the code to be eval­u­ated), and run it:

Once again we get 42. In general, every source file that begins with a #lang line gets converted to a module by the language reader. This is why source files in Racket are also known as modules. (For more, see the #lang line.)

This proved that we can make a round trip from a source file to the stacker reader and back. The major problem with our reader is that it’s not doing anything with the src-lines we read from the source file. So let’s fix that.

Program­ming our reader: input

Right now, we’re ignoring the lines of our input source file. So we’ll upgrade our reader to complete two new tasks:

To do this, let’s swap out the read-syntax in "stacker.rkt" for a new version:

As we’ll see in the next section, this code will raise an error when we try to use it as a language. But let’s step through each line to see what it does, and then we’ll be able to under­stand the error.

As we did before, we use port->lines to retrieve the lines from our input port—each repre­senting an argu­ment in a stacker program—as a list of strings. We store this list in src-lines. (In this project, we don’t need path, so we’ll ignore it.)

Next, we convert these strings into datums.  + Yes, the plural of datum ought to be data. But this poetic license will help us avoid confu­sion with the tradi­tional generic meaning of “data”. format-datums takes a list of strings and converts each of them using a format string. The ~a marks the place where the argu­ment string will be substi­tuted. So the string "4" from the source file will become the datum '(handle 4), and "+" will become '(handle +).

Then we make our module datum. Here we intro­duce a new bit of nota­tion: the back­tick ` is called quasi­quote. As the name implies, it works mostly the same way as the usual quote prefix '. The “quasi” part is that we can insert vari­ables into the list. To insert a single value, we use the unquote oper­ator, which is a comma , followed by the vari­able:

To insert a list of multiple values, we use the unquote-splicing oper­ator, which is a comma and at sign ,@ followed by the vari­able. The unquote-splicing oper­ator merges our sublist with the surrounding list:

Notice that if we use the unquote oper­ator with a sublist, the sublist will remain nested:

Now we can under­stand what’s happening in our module datum:

This datum describes a module called stacker-mod (another arbi­trary name). Because we haven’t written our stacker expander yet, we’ll temporarily use the br expander (meaning, this module will be inter­preted as source written in the br language).

We quasi­quote our module datum using ` so we can use ,@ inside to splice our src-datums into the body of the module. So if our src-datums were a list of three datums like this:

After splicing, our module datum will look like this:

We move on to the last line of our func­tion:

As before, we finish by converting our datum to a syntax object using datum->syntax, passing #f as the context argu­ment.

Finally, we (provide read-syntax) so the func­tion is avail­able outside this source file.

Testing our reader

Let’s make sure our updated reader works the way we hope, by testing it with some dummy values. Save "stacker.rkt". Update "stacker-test.rkt" as follows:

Don’t worry that this code isn’t a valid stacker program. Our reader doesn’t know anything about the meaning of stacker code, so it should work with any argu­ments. We might as well try it with a number, a string, and a boolean.

Run this file in DrRacket. What happens? You should get an error that starts like this:

This looks like bad news. But it tells us some­thing useful. Our code is trying to call the handle func­tion (which is what we wanted). But it’s not succeeding, because handle doesn’t exist yet. We’ll fix that shortly.

In the mean­time, how can we check the output of read-syntax? For debug­ging purposes, we can put in a tempo­rary shim. We add a second ' prefix to our format string in format-datums, like so:

What will happen now? Before we run "stacker-test.rkt" again, let’s think through this change. Recall that when our syntax object from read-syntax is moved into place, Racket unquotes it so that it can be eval­u­ated as code. By adding a second level of quoting, however, we’re protecting our src-datums from turning into code. Once they’re unquoted, they’ll still have a layer of quoting. They’ll still behave as data, and they’ll be printed out as usual.

Let’s run "stacker-test.rkt" and see if this idea works:

This looks mostly right: each argu­ment in "stacker-test.rkt"—42, "Hello world", and #t—has been wrapped as a paren­the­sized handle form. Because of the extra level of quoting, each of these forms is printed as a datum.

But that '(handle) at the top—where did that come from? Remember that every­thing in the source file gets passed to read-syntax. That includes the newline between the end of the #lang line and the first line with 42. For instance, update "stacker-test.rkt" like this and run it again:

Every line, including the blank lines, will be converted to handle form:

It’s possible to filter out mean­ing­less source code before we make the module expres­sion—but we’ll save that tech­nique for later. Here in stacker, we’ll just notice that blank lines will still generate calls to handle. So when we write handle, we should deal with them prop­erly.

To finish our test, let’s change "stacker-test.rkt" to use the input from our orig­inal sample program:

When we run this, we get:

Except for the quotes—which are there temporarily for debug­ging, and won’t exist on the real code—that’s exactly right.

We’re almost ready to move on. Let’s finish our reader by making two changes to read-syntax. First, since we’re done debug­ging, let’s remove the extra ' prefix from the format string in format-datums. Second, let’s change our module datum so that instead of invoking br as the expander, it will use "stacker.rkt". So the finished func­tion looks like this:

Of course, "stacker.rkt" doesn’t have an expander yet. We’ll add that next.