Into the rapids: more basic

Having done the heavy lifting in expres­sions, adding condi­tionals will seem like a vaca­tion.

We want to support two new BASIC elements:

This tuto­rial section is largely rein­force­ment of things we learned in previous sections. So let’s jump right in to the imple­men­ta­tion.

Lexer updates

As we have before, we start by updating "lexer.rkt" to recog­nize the new tokens. To the reserved-terms list we add if, then, and else; our new rela­tional oper­a­tors (<, >, and <>); plus and, or, and not. = is also a rela­tional oper­ator, but it’s already included on our reserved-terms list (because of its existing role as an assign­ment oper­ator):

Parser updates

Next we add the new parser rules.

First, we need a b-if rule to handle the if state­ment, with a manda­tory then clause and an optional else. We can have either a state­ment or an expres­sion after the then and else, so our whole rule will look like this:

We also add b-if as one of the choices for our b-statement rule.

Then we need rules for our logical oper­a­tors. Just like the oper­a­tors in math­e­mat­ical expres­sions, logical oper­a­tors are ranked from lowest to highest prece­dence:

After that, all the math­e­mat­ical oper­a­tors have higher prece­dence than the rela­tional oper­a­tors.

We already know how to enforce prece­dence—by chaining together parser rules. So we insert our logical oper­a­tors into the existing tower of prece­dence:

Between b-expr and b-sum we’ve inserted four rules for our logical oper­a­tors, so that they have lower prece­dence than the existing math­e­mat­ical oper­a­tors.

For the rules them­selves, we follow the same pattern that we used before, where the left element in each pattern is a recur­sive refer­ence to the rule (thus enforcing left-to-right eval­u­a­tion) and the right element chains to the next rule (thus enforcing prece­dence). The excep­tion is b-not-expr, because like b-neg, it only takes one argu­ment.

Because our rela­tional oper­a­tors all have the same prece­dence, we handle them with a single b-comp-expr rule (similar to what we did with b-sum and b-product).

Expander updates

We’ll start a new module called "cond.rkt" to hold our expander imple­men­ta­tion for condi­tionals. Let’s first update our "elements.rkt" so it picks up this new module:

Then we can start "cond.rkt" itself. First we make macros corre­sponding to the parser rules for our logical oper­a­tors:

Because BASIC Boolean expres­sions work in terms of nonzero-or-zero rather than true-or-false, we create a nonzero? pred­i­cate to test our condi­tions. The compose1 func­tion is common Racket short­hand for combining multiple func­tions into one, so these expres­sions are equiv­a­lent:

Consis­tent with BASIC protocol, we also use a bool->int func­tion to convert the Racket result of these oper­a­tions, which will be #f or some­thing else, to a simple 0 or 1 value.

Next we add the rela­tional oper­a­tors:

We create our BASIC rela­tional oper­a­tors by composing our bool->int helper func­tion with the corre­sponding Racket rela­tional oper­ator. Our b-comp-expr macro just dispatches to the correct oper­ator.

We finish off by adding a macro for b-if:

The first case of the b-if macro handles the situ­a­tion when ELSE-EXPR is omitted by adding (void) calling b-if again. At that point it will match the second case.

As we did above, we use nonzero? to test our condi­tion. We know from our parser rules that THEN-EXPR or ELSE-EXPR might be a state­ment or a numer­ical expres­sion, in which case it should be treated as a goto. We handle this by checking whether result is an exact-positive-integer? and if so, passing it to b-goto.

The completed "cond.rkt" module looks like this:

Testing our condi­tionals

With those improve­ments, our #lang basic should now be able to handle condi­tional expres­sions. Let’s start with our orig­inal test program:

A good start. Let’s try all of our rela­tional and logical oper­a­tors:

Let’s also try the various styles of if:

Every­thing checks out.

Func­tions vs. macros revis­ited

At the end of expres­sions, we saw that we often have a choice between func­tions or macros for imple­menting elements of a language. Usually, we prefer to use func­tions where we can, and reserve macros for when we really need them, because macros incur some extra costs. Though in simple cases, those costs are minor.

In this case, a little reflec­tion will reveal that we can’t imple­ment condi­tionals with ordi­nary func­tions. Why not? Because condi­tionals come with “short-circuiting” logic guar­an­teeing that no result expres­sion is eval­u­ated until it’s needed. Consider these exam­ples with or and and:

If or and and were imple­mented as func­tions, the nested expres­sions would be eval­u­ated first, including (collapse-solar-system) and (start-zombie-apocalypse). Not what we want.

Instead, these forms are imple­mented as macros, which rearranges the code at compile time so that at run time, things happen in the right order (or not at all).

How, specif­i­cally? During compile-time macro expan­sion, we can think of these forms as wrap­ping their expres­sions in lambdas to delay their eval­u­a­tion:

That way, the under­lying expres­sions are held in “suspended anima­tion” until they’re needed at run time.