Into the rapids: more basic

Now that we’ve supple­mented our existing numbers with vari­ables and input, we’d like to manip­u­late them more freely, by using them together in expres­sions.

In BASIC, an expres­sion is a sequence of argu­ments and oper­a­tions that can be eval­u­ated to produce a result. Roughly, a BASIC expres­sion is one that relies on math­e­mat­ical or logical oper­a­tors:

Unlike Racket, BASIC is not made exclu­sively of expres­sions. Rather, it’s a mix of state­ments (like print) and expres­sions. Also, BASIC relies on stan­dard infix nota­tion (with the oper­a­tions written between the argu­ments) as opposed to Racket’s prefix nota­tion.

Previous over­sim­pli­fi­ca­tions

At the end of vari­ables and input, we left our parser like this, pledging that we would improve our casual handling of expres­sions and numbers:

So far, we’ve made some simpli­fying but unre­al­istic assump­tions. Let’s look at the b-expr rule near the bottom. The only kind of expres­sion we support is b-sum, which is a series of b-number elements with + between them:

Once parsed, the b-number nodes are spliced, so in the parse tree, this expres­sion becomes:

Our corre­sponding b-sum func­tion in "expr.rkt" is like­wise casual:

Of course, real BASIC expres­sions aren’t limited to flat lists of values, summed together. We have to support gnarlier expres­sions with a variety of oper­a­tions, and subex­pres­sions within, like the one we saw above:

To do this, we obvi­ously have to add some new math oper­a­tors—namely - (subtrac­tion), * (multi­pli­ca­tion), / (divi­sion), ^ (expo­nen­ti­a­tion), and mod (modulo). But we also need to confront some subtler consid­er­a­tions previ­ously avoided.

Asso­cia­tivity & prece­dence

Throughout the tuto­rials we’ve noted the impor­tance of choosing wisely when modeling elements of a program­ming language with Racket. Usually, the best choice is the one that’s most anal­o­gous. For example, in vari­ables and input, we imple­mented BASIC vari­ables directly as Racket vari­ables (rather than indi­rectly, as a Racket hash table).

This time, however, we have to model infix expres­sions, which have no direct analog in Racket—in fact they don’t exist at all.  + Racket’s limited infix nota­tion is just prefix nota­tion, cosmet­i­cally rearranged.

More­over, we can’t just casu­ally convert infix expres­sions to Racket expres­sions, the way we did with b-sum. Infix expres­sions are eval­u­ated according to certain rules:

Taking these rules together, our orig­inal gnarly example:

Would be written in Racket like so:

Angles of attack

We need to figure out a method of trans­forming any BASIC infix expres­sion into a Racket expres­sion that correctly imple­ments the asso­cia­tivity & prece­dence rules. Since Racket doesn’t directly support infix expres­sions, we have two choices:

Parsing with asso­cia­tivity & prece­dence

We know that in Racket, run-time expres­sions are eval­u­ated from inner­most to outer­most. We also know that when the parser descends into a new rule, it creates a subnode in the parse tree inside the current node. So every new rule moves us farther inward.

There­fore, we can indi­rectly control eval­u­a­tion priority through parsing. Every time we want to give an expres­sion more priority, we can invoke another parser rule, which will move that expres­sion deeper in the parse tree.

As for infix oper­a­tions, we can treat asso­cia­tivity and prece­dence of oper­a­tions as two vari­eties of eval­u­a­tion priority.

Asso­cia­tivity of oper­a­tions can be created through recur­sive parsing rules.

Even though an infix expres­sion can be indef­i­nitely long, we can always break it into a series of two-argu­ment compu­ta­tions—the current infix oper­ator applied to the argu­ment on its left and right. (This is how we would proceed with pencil & paper; it’s also how we converted our previous infix exam­ples into Racket code.)

We already used this idea of dyadic decom­po­si­tion in the stackerizer language. In that case, we converted vari­adic expres­sions into dyadic ones by recur­sively calling a macro.

In a parser, we can accom­plish some­thing similar by recur­sively calling a parsing rule. Suppose we have this grammar:

And we parse the string a+b+c+d:

We get this result:

Now suppose we only want sum nodes that are dyadic at maximum. We can update the sum rule with a recur­sive refer­ence, and remove the * quan­ti­fier so it only matches one or two elements:

Now the parse tree changes:

Our recur­sive use of sum is on the right side of the pattern. There­fore, subn­odes are formed around each right-hand element. That means that we’re assigning eval­u­a­tion priority from right to left: (sum "d") is eval­u­ated, then (sum "c" ···), etc.

If we want to enforce left-to-right asso­cia­tivity, we can just swap the posi­tion of the recur­sive sum in the pattern:

This produces a parse tree with left-to-right priority:

Prece­dence of oper­a­tions can be created through a chained hier­archy of parsing rules. Again, a simple example. Suppose we have this grammar:

And we parse the string a+b*c:

We get this parse tree:

Following the tech­nique we learned above, we enforce left-to-right asso­cia­tivity by recur­sively calling the op rule as the left element in its pattern. This means that a+b will be eval­u­ated first.

But suppose that instead, we want b*c to be eval­u­ated first. If we change op to sum, and insert a mult subrule into our grammar:

Then the b*c substring will be nested more deeply, and thus eval­u­ated first:

The key maneuver here is slightly coun­ter­in­tu­itive: we’re chaining our grammar rules so that every sum node contains mult subn­odes, and every mult node lives inside a sum parent node. Our string a+b*c, which looks like it contains two oper­a­tions, becomes five oper­a­tions in our parse tree.

But we won’t panic. This chaining ensures that our multi­pli­ca­tions always have higher eval­u­a­tion priority than our sums, because they’re nested deeper in the parse tree. And the extra one-argu­ment instances of our oper­a­tions can be boiled out by the expander—e.g., (sum (mult "a")) can just become "a". If we ignore these trivial oper­a­tions, the parse tree looks like this:

Which is exactly what we wanted.

Relying on these two parsing tech­niques, we can now imple­ment BASIC infix expres­sions with asso­cia­tivity and prece­dence. We can also use these tech­niques to imple­ment subex­pres­sions, which we can think of as a further layer of prece­dence.

Lexer updates

As always, we start by updating "lexer.rkt" to recog­nize the new tokens we’ll be using in the source. To the reserved-terms list we add our other math oper­a­tors (-*/^ and mod), plus paren­theses (to support subex­pres­sions):

Parser updates

Next we add the parser rules that handle oper­ator prece­dence. In BASIC, oper­a­tions are ordered from lowest to highest prece­dence like so:

Then, within a prece­dence level, oper­a­tions are performed from left to right.

Following the approach we discov­ered in the last section, we intro­duce a series of chained parser rules corre­sponding to each level of prece­dence. Each of these rules will call itself recur­sively on the left side of its pattern to enforce left-to-right asso­cia­tivity:

b-sum parses both addi­tion and subtrac­tion oper­a­tions; b-product parses multi­pli­ca­tion, divi­sion, and modulo oper­a­tions. We defi­nitely don’t want to break these indi­vidual oper­a­tions into chained rules, because it would improp­erly create prece­dence among them. Rather, we’ll think of b-sum and b-product as “sets of oper­a­tions at the same level of prece­dence” and sort out the details in the expander.

The nega­tion rule b-neg has no recur­sive element because it only takes one argu­ment.

Near the bottom, we’ve intro­duced a new b-value rule that encom­passes numbers, iden­ti­fiers, and subex­pres­sions. The subex­pres­sion pattern recur­sively relies on b-expr, which means that expres­sions can be nested to any depth.

Expander updates

In "expr.rkt", we keep our previous b-expr func­tion, but every­thing else will be replaced:

In each of the macros imple­menting the parse-tree rules, we start by handling the trivial one-argu­ment case. After that, we match the oper­a­tion token, and convert the expres­sion to the corre­sponding Racket func­tion.

We also intro­duce a tiny bit of new nota­tion: in a syntax pattern, we can use an under­score _ to mean “match anything”. We use it in our macro patterns so that we can avoid inces­santly repeating the name of the macro, which we know always appears first.  + The under­score is commonly used to indi­cate some­thing in a pattern that we plan to ignore. We used anal­o­gous nota­tion in match when we wrote the syntax colorer.

Every­thing is straight­for­ward except divi­sion. Unlike Racket, BASIC has no concept of an exact rational frac­tion. It only uses floating-point frac­tions. So in the divi­sion expres­sion, we include 1.0 to force a floating-point result.

Testing our expres­sions

First, let’s try our orig­inal gnarly expres­sion:

And compare it to the equiv­a­lent Racket code:

A promising start. Let’s now test our prece­dence rules, by making expres­sions that have higher-prece­dence oper­a­tions on the right:

Let’s also see if our left-to-right asso­cia­tivity works:

We also check that we can do the same oper­a­tions with vari­ables instead of numbers:

Not bad. If we want to add more oper­a­tions at new levels of prece­dence, we can insert them into our existing chain of parsing rules. We’ll see how this works in the next section on condi­tionals.

Using func­tions instead of macros

By the way—in our "expr.rkt" module, macros aren’t manda­tory. We’re not doing anything tricky. If we wanted, the macros could be rewritten as func­tions without affecting program behavior. For instance, we could use define-cases (which is like define-macro-cases, but for func­tions) to handle the different calling patterns, and case to choose the func­tion to apply:

This imple­men­ta­tion will work the same way.

Which is better? The rule of thumb is that we should use func­tions where we can, and macros where we must. Why? Because macros get eval­u­ated at compile time (which has a cost) and they create more run-time code, which in turn has to be compiled and inter­preted (which also has a cost). Calling func­tions at run time is typi­cally more effi­cient.

But claims about perfor­mance always depend on the context. In this case, the competing macros and func­tions are both tiny. Some casual bench­marking with a BASIC test program suggests they’re essen­tially equal in speed. So we’ll stick with the macro solu­tion. But the alter­na­tive exists.