Go with the flow: basic

We saw how we were able to use cuts and splices to stream­line our parse tree into a shape pretty close to that of our pseudocode in spec­i­fi­ca­tion and setup.

This is our sample program:

This was the pseudocode:

And this is the parse tree that results from the parser:

Here in the expander, we need to take this code the rest of the way, so that it works as a BASIC program.

Key tasks

According to the spec­i­fi­ca­tion and setup, these are the key missing pieces:

Since we went through the trouble of collecting source loca­tions, we should also try to apply them wher­ever sensible.

Let’s start by creating an "expander.rkt" module in our basic project:

Turning program lines into func­tions

Usually the first thing we write for our expander is the indis­pens­able #%module-begin macro. This time, let’s instead figure out our line func­tions first.

In wires, we learned how we could use a macro to make a func­tion corre­sponding to each wire defi­n­i­tion. The idea here is similar: make a func­tion that corre­sponds to each line defi­n­i­tion. These line defi­n­i­tions are repre­sented in our parse tree by b-line nodes. A simple version of our b-line macro would look like this:

We know from our parser grammar that a b-line contains a line number followed by zero or more state­ments. Thus, we can create a macro using a syntax pattern that matches these argu­ments. In the syntax template, we insert a (void) because the body of a func­tion needs to have at least one expres­sion, and STATEMENT ... may have zero elements. Other­wise, the (void) is benign.

We can quickly test our macro by grab­bing the first line from our parse tree and entering it on the REPL:

But when we do that, we get an error:

The problem is that Racket doesn’t accept numbers as iden­ti­fiers. So if we want to make a func­tion for line 30, we have to give it a different name. We can do this by prefixing our line number with line-. So line 30 will become a func­tion called line-30.

We can derive a new iden­ti­fier using prefix-id, which creates a new iden­ti­fier by putting a prefix onto an existing one. Here, we attach line- to the front of our #'NUM iden­ti­fier.  + Reminder: though the pattern vari­able is called NUM (without the #' prefix) we can only use it inside a syntax template. So #'NUM is the world’s smallest syntax template that holds NUM. We can then use with-pattern to assign this new iden­ti­fier to the pattern vari­able LINE-NUM, and substi­tute it into our syntax template:

This time, when we enter the first line of our parse tree on the REPL, we don’t get an error:

We can verify that line-30 is a func­tion:

But we can’t run the func­tion yet, because we haven’t defined b-rem inside:

That’s OK. What’s impor­tant is that the new iden­ti­fier is working. In fact, if we were feeling lazy, we could stop here.

But no—we would feel terrible if we ignored source loca­tions. There are two source loca­tions we want to apply to our new code.

First, we want our new LINE-NUM iden­ti­fier to have the same loca­tion as NUM. That way, if an error arises that concerns LINE-NUM, then NUM will be high­lighted in the source.

By default, prefix-id doesn’t apply a source loca­tion. We can change this by using its optional #:source argu­ment and passing #'NUM as the value. prefix-id will grab the source loca­tion of #'NUM and apply it to LINE-NUM:

Second, we want our whole func­tion defi­n­i­tion to have the same loca­tion as the orig­inal b-line node. That way, if an error arises during the func­tion, the orig­inal program line will be high­lighted. By default, our syntax template does not transmit a source loca­tion to the new code.

To fix this, we need to roll out two new items: syntax/loc and caller-stx.

We may remember that the #' prefix we’ve been using with syntax objects and syntax templates is just short­hand for syntax. So these two expres­sions are the same:

If we want to apply a source loca­tion to our new syntax object, we can use syntax/loc instead of plain syntax. The first argu­ment of syntax/loc is a syntax object whose source loca­tion we want to borrow for the new syntax object:

We want to use the source loca­tion of the orig­inal b-line node, so we need a syntax object that repre­sents the whole node. We can’t use #'NUM or #'(STATEMENT ...), because those argu­ments are inside the b-line node, and thus have different source loca­tions.

When we use define-macro, the orig­inal input to the macro—before it’s matched to the defining syntax pattern—is made avail­able in a special vari­able called caller-stx. This vari­able is only avail­able in the body of the define-macro (or define-macro-cases). We can see how this works in this toy example, where mac prints caller-stx before listing the argu­ments passed to the macro:

caller-stx contains the whole expres­sion that invoked the macro, including mac itself.

Thus, we can finish our b-line macro by using syntax/loc for the syntax template, and passing caller-stx as the source-loca­tion argu­ment:

Usually we’d also provide the b-line macro. This time, we’ll wait till the end of our expander, and export them as a set.

Our module-begin macro

Now that we know how our line func­tions will work, we’re ready to start our #%module-begin. This will be the first macro executed when our program starts:

As usual, we give our macro a tempo­rary name and rename it in our provide expres­sion. Rather than define the macro with the single argu­ment PARSE-TREE, we use the pattern (b-program LINE ...). This just lets us unpack the b-program node into a series of LINE ... argu­ments right away, instead of defining a sepa­rate b-program macro.

We know that each of these LINE ... argu­ments will be converted into a func­tion defi­n­i­tion. So we just insert them directly into our syntax template.

Next, we need to set up a hash table of line numbers and line func­tions, and pass it to our main program loop:

We call this new hash table line-table. We further suppose that our main func­tion will be called run (we still need to write it, however). We pass any return value of run to void to discard it.

Now for the hash table itself. Racket has multiple kinds of hash tables. We always like to pick the fastest one for the job:

Our line-table is a mapping of numbers to func­tions that won’t change during the program run. There­fore, we’re looking for an immutable hash table that compares keys with eqv? (because eq? doesn’t work with numbers).  + See equality for a full expla­na­tion of the differ­ences between equality tests. So our fastest option is hasheqv.

The hasheqv constructor func­tion takes an indef­i­nite list of alter­nating keys and values. But because of the way the ... oper­ator works in a macro, it’s hard to make a list of alter­nating argu­ments. What we can do instead is make a series of indi­vidual lists of key–value pairs—a NUM followed by a LINE-FUNC—and combine them with append and apply:

Our macro is almost done. We just need to manu­fac­ture the values for (NUM ...) and (LINE-FUNC ...). We can intro­duce these pattern vari­ables into our syntax template using with-pattern:

We need to pair (NUM ...) with a list of line numbers. Where do we get these? This requires a little bit of pattern-matching clev­er­ness. We know that each raw LINE argu­ment is shaped like so:

It would be nice if we could just extract the NUM field from inside each LINE. We can—if we make a syntax pattern that matches each whole LINE, with NUM as a submatch. We can even use the same pattern we used to define the b-line macro:

What happens in the high­lighted code? The right-hand syntax object #'(LINE ...) is matched against the left-hand syntax pattern ((b-line NUM STATEMENT ...) ...). Because there’s an ellipsis at the top level of each, each indi­vidual LINE is matched against the subpat­tern (b-line NUM STATEMENT ...). This produces the list of NUM matches that we want. It also produces a list of STATEMENT matches, but we don’t need them, so we just ignore them.  + It’s a common idiom in syntax patterns to notate a delib­er­ately ignored element with an under­score, so this pattern could be written (b-line NUM _ ...).

To generate the LINE-FUNC ... names, we first put those NUM matches inside a new syntax template as #'(NUM ...). Then, just as we did in the b-line macro, use prefix-id to prefix each of them with line-. (This time, we don’t need to worry about source loca­tions.) With this update, the finished macro looks like this:

By the way, why can we subject our b-line elements to two rounds of pattern matching? Under Racket’s eval­u­a­tion rules, macros are eval­u­ated from the outside in. There­fore, the b-module-begin macro will go first, matching the b-line nodes, but also passing them through to its syntax template as LINE .... Later, these elements will be further expanded using the b-line macro, converting them into func­tion defi­n­i­tions.

The main loop

Our main program loop will be handled by a run func­tion that takes a table of numbers and line func­tions, called line-table, as input:

Beyond that, according to our spec­i­fi­ca­tion and setup, run needs to do the following:

Let’s write the core loop for run, and then go back and add the change-line and end-program signals.

First we need to put our line numbers into numer­ical order:

The keys of line-table are the line numbers. We use hash-keys to get them as a list, and then sort to put them into increasing order. We use list->vector to convert these numbers to a vector, which is a list-like data struc­ture that’s faster than an ordi­nary list when we can foresee needing random access to elements. And we can—a BASIC program can jump arbi­trarily from line to line with goto.

To run the program, we use a for/fold loop:

This loop has one accu­mu­lator value, line-idx, that points at a loca­tion in line-vec. We start at 0. The loop iter­ates over i, an infi­nite stream of inte­gers produced by in-naturals. (Recall that we used a similar tech­nique to handle bf-loop elements in the bf expander.) We won’t do anything with i, but we need to have at least one iter­ator.

Using #:break, we stop our loop if our current line-idx is greater than or equal to the vector-length of line-vec (which would make it an invalid index value).

Other­wise, we look up the corre­sponding line-num in line-vec using vector-ref. Then we look up the corre­sponding line-func in line-table using line-num as the key. We execute line-func. Then we add1 to line-idx and keep going.

That’s all we’d need for a simple program without goto or end.

Excep­tional behavior

Now we add the change-line and end-program signals.

In spec­i­fi­ca­tion and setup, we pledged to imple­ment these signals using excep­tions. An excep­tion is a run-time value that pauses the current eval­u­a­tion and travels back through the calling chain of func­tions. Excep­tions are usually initi­ated with raise. The excep­tion travels up through the calling chain until it reaches an excep­tion handler, which is a func­tion that processes the excep­tion. Excep­tion handlers are usually estab­lished using with-handlers. If no excep­tion handler catches an excep­tion, it stops the program.

Here’s a simple example (though there are more elab­o­rate ones in errors and excep­tions):

thrower turns every argu­ment into an excep­tion. catcher uses with-handlers to wrap thrower with an excep­tion handler that only applies to numbers. with-handlers comprises a series of clauses with a pred­i­cate on the left, and a single-argu­ment func­tion on the right. If the excep­tion matches the pred­i­cate, the func­tion is called, with the excep­tion as the input. So if we pass a number to catcher, the excep­tion handler catches it and returns 'got-number. But if we pass an argu­ment directly to thrower, or a non-number to catcher, then the excep­tion handler isn’t invoked, and we get an uncaught-excep­tion error.

In our run func­tion, our goal will be to use excep­tions not to trigger errors, but rather as a way of jumping out of our program loop. Specif­i­cally, our goto and end state­ments will each use raise to raise an excep­tion. Back in run, we’ll use with-handlers to catch these excep­tions and take action.

First we need to make our excep­tions. In prin­ciple, though we can use any kind of value for an excep­tion, it makes sense to create special pred­i­cates, so that the signal can be uniquely tested. A quick way to mint new pred­i­cates is to make a new struc­ture type with struct:

struct creates a new struc­ture type with the name and optional fields in paren­theses. It also manu­fac­tures supporting func­tions: a constructor, a struc­ture pred­i­cate, and getters for each field (if any).  + And setters, if the struc­ture type is marked as #:mutable. So when we say:

We actu­ally end up with three func­tions:

Invoked like so:

Now we’re ready to imple­ment goto and end, which in our parse tree became b-goto and b-end:

b-goto uses raise to send up an excep­tion using an instance of the change-line-signal struc­ture type, holding a value of expr. Like­wise, b-end raises an excep­tion using end-program-signal.

Then we use with-handlers to catch these excep­tions. The end-program-signal needs to get us out of the main program loop. So we locate the excep­tion handler on the outside of our for/fold expres­sion, using end-program-signal? as the pred­i­cate, and the excep­tion handler returning (void):

The second use of with-handlers that catches change-line-signal needs to be placed so it inter­cepts the return value of the loop, which is ordi­narily (add1 line-idx)

Let’s step through what’s happening in this excep­tion handler. An instance of the change-line-signal struc­ture type is passed to the excep­tion handler as input, and called cls. We extract the val field from the excep­tion as clsv, which is supposed to be a line number. We check that clsv is an exact-positive-integer? and that it appears as a value in line-vec. For this, we use vector-member, which returns its index in the vector, or #f if it doesn’t exist. In that unfor­tu­nate circum­stance, we raise an error saying the line couldn’t be found.

The strag­glers

All that’s left is to imple­ment the remaining pieces of our parse tree—b-rem, b-print, b-sum, and b-expr:

As usual, we just follow the grammar, which at this point should feel like vaca­tion:

Providing en masse

Finally, we have to provide all our macros and func­tions that imple­ment parts of the parse tree. Since we had the fore­sight to prefix them all with b-, we can use matching-identifiers-out to export them all at once:

We start with all-defined-out, which included every func­tion and macro defined in the module, and then winnow this down with the regular expres­sion #rx"^b-", which selects every func­tion and macro starting with b-.

Finished expander

Putting every­thing together, our expander should look like this: