Into the rapids: more basic

It’ll be diffi­cult to make any decent BASIC games without vari­ables and user input. Input is easy once we have vari­ables. Vari­ables are a little harder. But we’ll use the prin­ciple that’s served us well so far: study the behavior of BASIC vari­ables, and then figure out the most natural way to model this behavior in Racket.

Vari­ables in BASIC

Vari­ables work a little differ­ently in BASIC than in Racket:

Because BASIC programs rely almost entirely on global vari­ables and muta­tion, they are in some sense the antithesis of the func­tional program­ming tech­niques that are idiomatic in Racket. Still, we will not be deterred.

Tradi­tion­ally, BASIC vari­ables were limited to one letter, and vari­ables that held strings were one letter followed by $. We won’t preserve this tradi­tion, because it’s point­less and awful. Instead we’ll allow our BASIC vari­ables to be any sequence of alpha­betic or numeric char­ac­ters (or $) that starts with a letter. (Those who insist on one-letter names can still have them.)

Modeling BASIC vari­ables

We can foresee two possible approaches:

Before we answer that ques­tion, let’s agree that the hash-table idea is a loser. In general, BASIC vari­ables have a lot in common with Racket vari­ables. We’ll get more benefit from keeping those concepts tied together, rather than choosing some­thing with a less natural fit (= a hash table).

As always, we’ll have to update our lexer and our parser to handle vari­ables and vari­able-assign­ment state­ments. We’ll also have to update the expander to imple­ment the muta­tion under­lying these state­ments. But for us, that part will be easy—we’ve done it before.

Search and destroy

Let’s focus on the new problem. If we want to model BASIC vari­ables as Racket vari­ables, we need them all to be defined before we start running the indi­vidual lines of a program. So in a program like this:

We’d need x, y, and z to be defined (and initial­ized to 0) before the first line runs.

We know that any kind of setup work that needs to happen before the first line can live in the #%module-begin macro in our expander. For instance, we currently use this macro to set up a line-table before we call run to start the program:

Following that idea, if we had a list of the iden­ti­fiers in the BASIC program, we could insert a define expres­sion at the top of our #%module-begin for each, turning them into vari­ables.

So where do we get this list of iden­ti­fiers? In the last tuto­rial, we saw how we could use a syntax pattern to match b-line elements from our parse tree and extract a list of line numbers. That worked nicely because the lines were already acces­sible from the LINE ... pattern vari­able, and the line number was in the same loca­tion of every line.

This time, we can’t use that tech­nique. Unlike the line numbers, our iden­ti­fiers could be anywhere in the BASIC program. Somehow, we need to search the whole parse tree for uses of iden­ti­fiers, and extract them.

We could do this by shaking the parse tree more vigor­ously—for instance, recur­sively taking it apart with match and looking for iden­ti­fiers. This kind of frontal assault could work. But it also amounts to re-parsing the parse tree.

There­fore it would be nice to somehow consol­i­date this work inside our parser. It turns out that we can use cuts and splices in the parser—which we used before to simplify the parse tree—to also mark certain elements, like iden­ti­fiers, so they’re easy to find later.

Gone but not forgotten

In #lang brag, when we use a cut on a rule name, or a splice on a pattern element, we end up removing a rule name from a node in the parse tree. Suppose our grammar looks like this:

The code 123 would be parsed like so:

If we apply a cut to the list rule:

The list name disap­pears from the parse tree, but the elements remain:

Or, if we apply a splice to either appear­ance of list in the grammar:

Once again, the list name disap­pears from the parse tree, and the elements remain (though this time, those elements are spliced into the surrounding node):

As a conve­nience in these cases, #lang brag preserves the rule name by adding it as a syntax prop­erty to the residual elements.

Intro­ducing syntax prop­er­ties

A syntax prop­erty is a key–value field attached to a syntax object. The key has to be a symbol; the value can be anything. Syntax prop­er­ties are read and written using syntax-property. When writing a prop­erty, syntax-property takes three argu­ments—syntax object, key, and value—and returns a syntax object with the updated field. When reading, it takes a syntax object and key and returns the matching value. If the syntax object doesn’t have a syntax prop­erty with that key, the result is #f:

Syntax prop­er­ties offer us a way of anno­tating a syntax object with arbi­trary meta­data that would other­wise have to travel sepa­rately. They’re always optional. But what’s nice about syntax prop­er­ties is that they behave like source loca­tions: once a syntax prop­erty is set, it stays attached to a piece of syntax throughout its travels.

A limi­ta­tion of syntax prop­er­ties, however, is that they’re only avail­able while we’re manip­u­lating our code as a syntax object (say, within a macro at compile time). Once the code enters run time, the syntax prop­er­ties are no longer avail­able.

For now, let’s see how simple inspec­tion of syntax prop­er­ties works. First, we’ll look at the parse tree of a one-line program:

No big surprises there. But let’s switch to #lang basic-demo/parse-stx, which will reveal the whole syntax object that results from the parse process (we didn’t make this dialect in the first tuto­rial, but it’s included with the beautiful-racket library):

This time, DrRacket prints a syntax object into the REPL:

We can click on the triangle at the left of the syntax object, and then the triangle next to Syntax Info, to reveal what’s inside:

On the left we see the datum inside the syntax object, which is the same as the simple parse tree we saw before. On the right we see the extra infor­ma­tion that’s pack­aged into the syntax object.

On the datum side, let’s click on the line number 10, which started out inside a b-line node:

This updates the right side of the window with infor­ma­tion specific to the nested syntax object 10. As we can see, under Known prop­er­ties—a list of the syntax prop­er­ties attached to the object—are two prop­er­ties, 'rule and 'b-line-num. We can use the 'rule prop­erty to discover the name of the orig­inal produc­tion rule that enclosed our 10, namely 'b-line-num. In turn, the 'b-line-num prop­erty holds a syntax object repre­senting the orig­inal 'b-line-num rule name omitted from the parse tree.

Next, let’s go back to the datum side and click on the left paren­thesis next to b-print. This high­lights the whole b-print expres­sion. Recall that this started out wrapped inside a b-statement rule, which got spliced out:

As with 10, we see a syntax prop­erty called 'rule that tells us the name of the orig­inal enclosing rule, 'b-statement. In turn, there’s a 'b-statement prop­erty that holds the syntax object repre­senting the orig­inal node in the parse tree. (We also see two other syntax prop­er­ties: 'splice-rh-id and 'hide-or-splice. These are private values used by brag for other house­keeping.)

Finally, let’s click on either 2 inside b-sum. Again, we see a syntax prop­erty called 'rule, and another for the 'b-number node that was spliced out:

With that in mind, we can see the path toward imple­menting BASIC vari­ables.

What about input?

Oh, right. The input state­ment is just a let that takes its initial value from user input. When the program reaches the input state­ment, it will display a prompt and wait for the user to enter a value:

And then it finishes:

We’ll add support for input as we work on let.

The game plan

Now we’re ready. We have four tasks:

Our goal will be to run this sample program:

And get this result:

Where joyce repre­sents what­ever value is entered at the user prompt.

Lexer updates

In "lexer.rkt", we make two changes:

Our rule for iden­ti­fiers follows our orig­inal spec­i­fi­ca­tion: any sequence of alphabetic or numeric char­ac­ters, or $, begin­ning with an alpha­betic char­acter, so the full rule is this:

We convert our iden­ti­fier lexeme to a symbol with string->symbol. Why? Things that exist as symbols in the parse tree (for instance, rule names) are treated as iden­ti­fiers by the expander, and thus can have bind­ings attached to them. Whereas strings that reach the expander always remain strings. Obvi­ously, we want our 'ID tokens to be treated as iden­ti­fiers.

Parser updates

Moving on to "parser.rkt":

We add three rules: b-let, b-input, and b-id. We add b-let and b-input as possible matches on the right side of b-statement. We also add b-id to the b-number rule, so vari­ables can be used in expres­sions (that’s a little casual, but we’ll do better when we get to expres­sions). The b-id rule itself matches tokens of type ID.

As we have before, we use cuts on the right side of the b-let and b-input rules to omit syntactic elements that we won’t need later.

We also apply a splice to the b-id rule. This means that every­where b-id appears in the grammar, the iden­ti­fier will be spliced into the node. But it also means that these iden­ti­fiers will have their b-id syntax prop­erty set. Next, we use this syntax prop­erty to locate the iden­ti­fiers in the parse tree.

Updating the expander

We need to update our #%module-begin macro, and then imple­ment the b-let and b-input state­ments.

In our "expander.rkt" module, we make two changes:

In b-module-begin, we add a (VAR-ID ...) pattern that matches the iden­ti­fiers in our parse tree, which we extract with the helper func­tion find-unique-var-ids (about which, more below). We also add (define VAR-ID 0) ... to the body of the macro, which will create the vari­ables with their default value of 0.

Then the helper func­tion. Though a macro gener­ates code that is eval­u­ated at run time (also known as phase 0), the code that imple­ments the macro itself is eval­u­ated at compile time (also known as phase 1). Racket is strict about keeping these phases sepa­rate. So when we want to make a helper func­tion for the macro that we call from outside the syntax template, we have to intro­duce that func­tion at phase 1.

Within the expander, an easy way to do this is wrap the func­tion in begin-for-syntax, which is like begin, but shifts its contents into phase 1.

The find-unique-var-ids func­tion itself works as follows. We pass the argu­ment #'(LINE ...), which is a syntax object containing all the b-line nodes from the parse tree. We use stx-flatten to turn it into a flat list of syntax objects. (In so doing, we demolish the struc­ture of the parse tree, but that doesn’t affect our search—it just makes the data a little easier to handle.) We then iterate over these small syntax objects to find the ones with a syntax-property of 'b-id. These are the droids we’re looking for. We collect them into a list.

Because an iden­ti­fier can show up any number of times in a program, we use remove-duplicates to winnow our list to distinct iden­ti­fiers. Strictly speaking, no syntax object containing an iden­ti­fier will be a “dupli­cate” of another, because, among other things, they’ll all have unique source loca­tions. So we’d rather disre­gard these differ­ences. To do this, we use the #:key argu­ment, which is a func­tion that’s applied to the elements before comparing them. We use syntax->datum for this argu­ment so we can compare our syntax objects just on the basis of their under­lying datums.

Again, this isn’t the only way to find iden­ti­fiers in a parse tree. In this case, because we know we can find the iden­ti­fiers with the 'b-id syntax prop­erty, we can do a smash-and-grab.

Penul­ti­mately, we add two macros to "misc.rkt" to handle our b-let and b-input state­ments:

As promised, b-let simply uses set! to mutate the value of ID. b-input is phrased in terms of b-let. It uses the Racket library func­tion read-line to get input from a user prompt. By default, the input from read-line is a string. We attempt to convert it to a number with string->number. But if that returns #f, we return the raw str value.

Finally, we adjust b-sum to handle an edge case. A conse­quence of our new grammar is that when an iden­ti­fier appears on the right side of a let, it ends up wrapped in a b-expr. For instance, this program:

Gets parsed like this:

The problem is that x holds the string "foo", which gets passed to b-sum. This will cause an error, because a string can’t be an argu­ment to +.

To get around this, we’ll intro­duce a cute trick that we’ll reuse when we improve our expres­sions. We rewrite b-sum so that if we only get one argu­ment, we pass it through untouched. Other­wise, we apply + as usual. This way, our string value can pass through without error. More­over, we’ll still get the right answer if we have a single numer­ical argu­ment (because (+ number) is just number):

Testing our vari­ables

Let’s try our sample program:

When we run it, the program should stop at line 40 and put up a prompt at the REPL. We put in a value and type enter:

And then the program should finish:

Our persis­tence has paid off. By choosing to model our BASIC vari­ables as Racket vari­ables—rather than a hash table—we took a slightly steeper route. But in so doing, we made things simpler for ourselves as we continue to extend the language.

We’ve shown we can assign, print, and add vari­ables. But if we want more elab­o­rate oper­a­tions, we’ll have to upgrade our handling of expres­sions and values. That’s next.