Thank you for your comment

Beau­tiful Racket / tuto­rials

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:

  1. Boolean expres­sions, using the rela­tional oper­a­tors < > = and <> (meaning “not equal”) and the logic oper­a­tors and or and not. In BASIC, every Boolean expres­sion eval­u­ates to 0 (denoting false) or 1 (denoting true).

  2. The if state­ment tests a condi­tion, which is a Boolean expres­sion. If the condi­tion is true, we execute the state­ment after then, other­wise the state­ment after else. If there is no else state­ment, the program continues to the next line.

    Alter­na­tively, the if condi­tion can be a numer­ical expres­sion, which is treated as false if zero, true other­wise. The then and else state­ments can also be numer­ical expres­sions, which are treated as the desti­na­tion of a goto.

    #lang basic-demo-2
    10 x = 3
    20 if x > 0 then print x else 5 * 10
    30 x = x - 1
    40 goto 20
    50 print "done"
    ℘
10 x = 3
20 if x > 0 then print x else 5 * 10
30 x = x - 1
40 goto 20
50 print "done"
    copy to clipboard
    3
    2
    1
    done
    3
2
1
done
    copy to clipboard

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):

basic/lexer.rkt
#lang br
(require brag/support)

(define-lex-abbrev digits (:+ (char-set "0123456789")))

(define-lex-abbrev reserved-terms (:or "print" "goto" "end" "+"
":" ";" "let" "=" "input" "-" "*" "/" "^" "mod" "(" ")" "if"
"then" "else" "<" ">" "<>" "and" "or" "not"))

(define basic-lexer
  (lexer-srcloc
   ["\n" (token 'NEWLINE lexeme)]
   [whitespace (token lexeme #:skip? #t)]
   [(from/stop-before "rem" "\n") (token 'REM lexeme)]
   [reserved-terms (token lexeme lexeme)]
   [(:seq alphabetic (:* (:or alphabetic numeric "$")))
    (token 'ID (string->symbol lexeme))]
   [digits (token 'INTEGER (string->number lexeme))]
   [(:or (:seq (:? digits) "." digits)
         (:seq digits "."))
    (token 'DECIMAL (string->number lexeme))]
   [(:or (from/to "\"" "\"") (from/to "'" "'"))
    (token 'STRING
           (substring lexeme
                      1 (sub1 (string-length lexeme))))]))

(provide basic-lexer)
#lang br
(require brag/support)

(define-lex-abbrev digits (:+ (char-set "0123456789")))

(define-lex-abbrev reserved-terms (:or "print" "goto" "end" "+"
":" ";" "let" "=" "input" "-" "*" "/" "^" "mod" "(" ")" "if"
"then" "else" "<" ">" "<>" "and" "or" "not"))

(define basic-lexer
  (lexer-srcloc
   ["\n" (token 'NEWLINE lexeme)]
   [white­space (token lexeme #:skip? #t)]
   [(from/stop-before "rem" "\n") (token 'REM lexeme)]
   [reserved-terms (token lexeme lexeme)]
   [(:seq alpha­betic (:* (:or alpha­betic numeric "$")))
    (token 'ID (string->symbol lexeme))]
   [digits (token 'INTEGER (string->number lexeme))]
   [(:or (:seq (:? digits) "." digits)
         (:seq digits "."))
    (token 'DECIMAL (string->number lexeme))]
   [(:or (from/to "\"" "\"") (from/to "'" "'"))
    (token 'STRING
           (substring lexeme
                      1 (sub1 (string-length lexeme))))]))

(provide basic-lexer)
copy to clipboard

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:

b-if : /"if" b-expr /"then" (b-statement | b-expr)
                   [/"else" (b-statement | b-expr)]
b-if : /"if" b-expr /"then" (b-state­ment | b-expr)
                   [/"else" (b-state­ment | b-expr)]
copy to clipboard

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:

  1. or

  2. and

  3. not

  4. The rela­tional oper­a­tors (< > = and <>)

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:

basic/parser.rkt
#lang brag
b-program : [b-line] (/NEWLINE [b-line])*
b-line : b-line-num [b-statement] (/":" [b-statement])* [b-rem]
@b-line-num : INTEGER
@b-statement : b-end | b-print | b-goto
             | b-let | b-input | b-if
b-rem : REM
b-end : /"end"
b-print : /"print" [b-printable] (/";" [b-printable])*
@b-printable : STRING | b-expr
b-goto : /"goto" b-expr
b-let : [/"let"] b-id /"=" (b-expr | STRING)
b-if : /"if" b-expr /"then" (b-statement | b-expr)
                   [/"else" (b-statement | b-expr)]
b-input : /"input" b-id
@b-id : ID
b-expr : b-or-expr
b-or-expr : [b-or-expr "or"] b-and-expr
b-and-expr : [b-and-expr "and"] b-not-expr
b-not-expr : ["not"] b-comp-expr
b-comp-expr : [b-comp-expr ("="|"<"|">"|"<>")] b-sum
b-sum : [b-sum ("+"|"-")] b-product
b-product : [b-product ("*"|"/"|"mod")] b-neg
b-neg : ["-"] b-expt
b-expt : [b-expt ("^")] b-value
@b-value : b-number | b-id | /"(" b-expr /")"
@b-number : INTEGER | DECIMAL
#lang brag
b-program : [b-line] (/NEWLINE [b-line])*
b-line : b-line-num [b-state­ment] (/":" [b-state­ment])* [b-rem]
@b-line-num : INTEGER
@b-state­ment : b-end | b-print | b-goto
             | b-let | b-input | b-if
b-rem : REM
b-end : /"end"
b-print : /"print" [b-print­able] (/";" [b-print­able])*
@b-print­able : STRING | b-expr
b-goto : /"goto" b-expr
b-let : [/"let"] b-id /"=" (b-expr | STRING)
b-if : /"if" b-expr /"then" (b-state­ment | b-expr)
                   [/"else" (b-state­ment | b-expr)]
b-input : /"input" b-id
@b-id : ID
b-expr : b-or-expr
b-or-expr : [b-or-expr "or"] b-and-expr
b-and-expr : [b-and-expr "and"] b-not-expr
b-not-expr : ["not"] b-comp-expr
b-comp-expr : [b-comp-expr ("="|"<"|">"|"<>")] b-sum
b-sum : [b-sum ("+"|"-")] b-product
b-product : [b-product ("*"|"/"|"mod")] b-neg
b-neg : ["-"] b-expt
b-expt : [b-expt ("^")] b-value
@b-value : b-number | b-id | /"(" b-expr /")"
@b-number : INTEGER | DECIMAL
copy to clipboard

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:

basic/elements.rkt
#lang br
(require "line.rkt" "go.rkt"
         "expr.rkt" "misc.rkt" "cond.rkt")
(provide
 (all-from-out "line.rkt" "go.rkt"
               "expr.rkt" "misc.rkt" "cond.rkt"))
#lang br
(require "line.rkt" "go.rkt"
         "expr.rkt" "misc.rkt" "cond.rkt")
(provide
 (all-from-out "line.rkt" "go.rkt"
               "expr.rkt" "misc.rkt" "cond.rkt"))
copy to clipboard

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

basic/cond.rkt
#lang br
(require "go.rkt")
(provide b-if b-or-expr b-and-expr b-not-expr b-comp-expr)

(define (bool->int val) (if val 1 0))
(define nonzero? (compose1 not zero?))

(define-macro-cases b-or-expr
  [(_ VAL) #'VAL]
  [(_ LEFT "or" RIGHT)
   #'(bool->int (or (nonzero? LEFT) (nonzero? RIGHT)))])

(define-macro-cases b-and-expr
  [(_ VAL) #'VAL]
  [(_ LEFT "and" RIGHT)
   #'(bool->int (and (nonzero? LEFT) (nonzero? RIGHT)))])

(define-macro-cases b-not-expr
  [(_ VAL) #'VAL]
  [(_ "not" VAL) #'(if (nonzero? VAL) 0 1)])
#lang br
(require "go.rkt")
(provide b-if b-or-expr b-and-expr b-not-expr b-comp-expr)

(define (bool->int val) (if val 1 0))
(define nonzero? (compose1 not zero?))

(define-macro-cases b-or-expr
  [(_ VAL) #'VAL]
  [(_ LEFT "or" RIGHT)
   #'(bool->int (or (nonzero? LEFT) (nonzero? RIGHT)))])

(define-macro-cases b-and-expr
  [(_ VAL) #'VAL]
  [(_ LEFT "and" RIGHT)
   #'(bool->int (and (nonzero? LEFT) (nonzero? RIGHT)))])

(define-macro-cases b-not-expr
  [(_ VAL) #'VAL]
  [(_ "not" VAL) #'(if (nonzero? VAL) 0 1)])
copy to clipboard

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:

(define (nonzero? x) (not (zero? x)))
(define nonzero? (compose1 not zero?))
(define (nonzero? x) (not (zero? x)))
(define nonzero? (compose1 not zero?))
copy to clipboard

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:

basic/cond.rkt
#lang br
(require "go.rkt")
(provide b-if b-or-expr b-and-expr b-not-expr b-comp-expr)

(define (bool->int val) (if val 1 0))
(define nonzero? (compose1 not zero?))

(define-macro-cases b-or-expr ···)
(define-macro-cases b-and-expr ···)
(define-macro-cases b-not-expr ···)

(define b= (compose1 bool->int =))
(define b< (compose1 bool->int <))
(define b> (compose1 bool->int >))
(define b<> (compose1 bool->int not =))

(define-macro-cases b-comp-expr
  [(_ VAL) #'VAL]
  [(_ LEFT "=" RIGHT) #'(b= LEFT RIGHT)]
  [(_ LEFT "<" RIGHT) #'(b< LEFT RIGHT)]
  [(_ LEFT ">" RIGHT) #'(b> LEFT RIGHT)]
  [(_ LEFT "<>" RIGHT) #'(b<> LEFT RIGHT)])
#lang br
(require "go.rkt")
(provide b-if b-or-expr b-and-expr b-not-expr b-comp-expr)

(define (bool->int val) (if val 1 0))
(define nonzero? (compose1 not zero?))

(define-macro-cases b-or-expr ···)
(define-macro-cases b-and-expr ···)
(define-macro-cases b-not-expr ···)

(define b= (compose1 bool->int =))
(define b< (compose1 bool->int <))
(define b> (compose1 bool->int >))
(define b<> (compose1 bool->int not =))

(define-macro-cases b-comp-expr
  [(_ VAL) #'VAL]
  [(_ LEFT "=" RIGHT) #'(b= LEFT RIGHT)]
  [(_ LEFT "<" RIGHT) #'(b< LEFT RIGHT)]
  [(_ LEFT ">" RIGHT) #'(b> LEFT RIGHT)]
  [(_ LEFT "<>" RIGHT) #'(b<> LEFT RIGHT)])
copy to clipboard

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:

basic/cond.rkt
#lang br
(require "go.rkt")
(provide b-if b-or-expr b-and-expr b-not-expr b-comp-expr)

(define (bool->int val) (if val 1 0))
(define nonzero? (compose1 not zero?))

(define-macro-cases b-or-expr ···)
(define-macro-cases b-and-expr ···)
(define-macro-cases b-not-expr ···)

(define b= ···)
(define b< ···)
(define b> ···)
(define b<> ···)

(define-macro-cases b-comp-expr ···)

(define-macro-cases b-if
  [(_ COND-EXPR THEN-EXPR) #'(b-if COND-EXPR THEN-EXPR (void))]
  [(_ COND-EXPR THEN-EXPR ELSE-EXPR)
   #'(let ([result (if (nonzero? COND-EXPR)
                       THEN-EXPR
                       ELSE-EXPR)])
       (when (exact-positive-integer? result)
         (b-goto result)))])
#lang br
(require "go.rkt")
(provide b-if b-or-expr b-and-expr b-not-expr b-comp-expr)

(define (bool->int val) (if val 1 0))
(define nonzero? (compose1 not zero?))

(define-macro-cases b-or-expr ···)
(define-macro-cases b-and-expr ···)
(define-macro-cases b-not-expr ···)

(define b= ···)
(define b< ···)
(define b> ···)
(define b<> ···)

(define-macro-cases b-comp-expr ···)

(define-macro-cases b-if
  [(_ COND-EXPR THEN-EXPR) #'(b-if COND-EXPR THEN-EXPR (void))]
  [(_ COND-EXPR THEN-EXPR ELSE-EXPR)
   #'(let ([result (if (nonzero? COND-EXPR)
                       THEN-EXPR
                       ELSE-EXPR)])
       (when (exact-posi­tive-integer? result)
         (b-goto result)))])
copy to clipboard

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:

basic/cond.rkt
#lang br
(require "go.rkt")
(provide b-if b-or-expr b-and-expr b-not-expr b-comp-expr)

(define (bool->int val) (if val 1 0))
(define nonzero? (compose1 not zero?))

(define-macro-cases b-or-expr
  [(_ VAL) #'VAL]
  [(_ LEFT "or" RIGHT)
   #'(bool->int (or (nonzero? LEFT) (nonzero? RIGHT)))])

(define-macro-cases b-and-expr
  [(_ VAL) #'VAL]
  [(_ LEFT "and" RIGHT)
   #'(bool->int (and (nonzero? LEFT) (nonzero? RIGHT)))])

(define-macro-cases b-not-expr
  [(_ VAL) #'VAL]
  [(_ "not" VAL) #'(if (nonzero? VAL) 0 1)])

(define b= (compose1 bool->int =))
(define b< (compose1 bool->int <))
(define b> (compose1 bool->int >))
(define b<> (compose1 bool->int not =))

(define-macro-cases b-comp-expr
  [(_ VAL) #'VAL]
  [(_ LEFT "=" RIGHT) #'(b= LEFT RIGHT)]
  [(_ LEFT "<" RIGHT) #'(b< LEFT RIGHT)]
  [(_ LEFT ">" RIGHT) #'(b> LEFT RIGHT)]
  [(_ LEFT "<>" RIGHT) #'(b<> LEFT RIGHT)])

(define-macro-cases b-if
  [(_ COND-EXPR THEN-EXPR) #'(b-if COND-EXPR THEN-EXPR (void))]
  [(_ COND-EXPR THEN-EXPR ELSE-EXPR)
   #'(let ([result (if (nonzero? COND-EXPR)
                       THEN-EXPR
                       ELSE-EXPR)])
       (when (exact-positive-integer? result)
         (b-goto result)))])
#lang br
(require "go.rkt")
(provide b-if b-or-expr b-and-expr b-not-expr b-comp-expr)

(define (bool->int val) (if val 1 0))
(define nonzero? (compose1 not zero?))

(define-macro-cases b-or-expr
  [(_ VAL) #'VAL]
  [(_ LEFT "or" RIGHT)
   #'(bool->int (or (nonzero? LEFT) (nonzero? RIGHT)))])

(define-macro-cases b-and-expr
  [(_ VAL) #'VAL]
  [(_ LEFT "and" RIGHT)
   #'(bool->int (and (nonzero? LEFT) (nonzero? RIGHT)))])

(define-macro-cases b-not-expr
  [(_ VAL) #'VAL]
  [(_ "not" VAL) #'(if (nonzero? VAL) 0 1)])

(define b= (compose1 bool->int =))
(define b< (compose1 bool->int <))
(define b> (compose1 bool->int >))
(define b<> (compose1 bool->int not =))

(define-macro-cases b-comp-expr
  [(_ VAL) #'VAL]
  [(_ LEFT "=" RIGHT) #'(b= LEFT RIGHT)]
  [(_ LEFT "<" RIGHT) #'(b< LEFT RIGHT)]
  [(_ LEFT ">" RIGHT) #'(b> LEFT RIGHT)]
  [(_ LEFT "<>" RIGHT) #'(b<> LEFT RIGHT)])

(define-macro-cases b-if
  [(_ COND-EXPR THEN-EXPR) #'(b-if COND-EXPR THEN-EXPR (void))]
  [(_ COND-EXPR THEN-EXPR ELSE-EXPR)
   #'(let ([result (if (nonzero? COND-EXPR)
                       THEN-EXPR
                       ELSE-EXPR)])
       (when (exact-posi­tive-integer? result)
         (b-goto result)))])
copy to clipboard

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:

#lang basic
10 x = 3
20 if x > 0 then print x else 5 * 10
30 x = x - 1
40 goto 20
50 print "done"
℘
10 x = 3
20 if x > 0 then print x else 5 * 10
30 x = x - 1
40 goto 20
50 print "done"
copy to clipboard
3
2
1
done
3
2
1
done
copy to clipboard

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

#lang basic
10 print 2 < 4 rem 1
20 print 2 > 4 rem 0
30 print 2 = 4 rem 0
40 print 2 <> 4 rem 1
50 print 2 < 4 or 2 > 4 or 2 = 4 rem 1
60 print 2 < 4 and 2 > 4 and 2 = 4 rem 0
70 print not 2 > 4 or not 2 < 4 rem 1
℘
10 print 2 < 4 rem 1
20 print 2 > 4 rem 0
30 print 2 = 4 rem 0
40 print 2 <> 4 rem 1
50 print 2 < 4 or 2 > 4 or 2 = 4 rem 1
60 print 2 < 4 and 2 > 4 and 2 = 4 rem 0
70 print not 2 > 4 or not 2 < 4 rem 1
copy to clipboard
1
0
0
1
1
0
1
1
0
0
1
1
0
1
copy to clipboard

Let’s also try the various styles of if:

#lang basic
10 if 2 < 4 then print "true" else print "false"
20 if 2 > 4 then print "true" else print "false"
30 if 2 > 4 then goto 50
40 print "not"
50 print "true"
60 if 2 < 4 then 40 + 40 else 70
70 print "not"
80 print "true"
℘
10 if 2 < 4 then print "true" else print "false"
20 if 2 > 4 then print "true" else print "false"
30 if 2 > 4 then goto 50
40 print "not"
50 print "true"
60 if 2 < 4 then 40 + 40 else 70
70 print "not"
80 print "true"
copy to clipboard
true
false
not
true
true
true
false
not
true
true
copy to clipboard

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:

(or (= 1 1) (collapse-solar-system))
(and (= 0 1) (start-zombie-apocalypse))
(or (= 1 1) (collapse-solar-system))
(and (= 0 1) (start-zombie-apoc­a­lypse))
copy to clipboard

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:

(or (λ () (= 1 1)) (λ () (collapse-solar-system)))
(and (λ () (= 0 1)) (λ () (start-zombie-apocalypse)))
(or (λ () (= 1 1)) (λ () (collapse-solar-system)))
(and (λ () (= 0 1)) (λ () (start-zombie-apoc­a­lypse)))
copy to clipboard

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

← prev next →