On this page:
6.1 Conditional execution
6.2 Meaning of Con programs
6.3 An Example of Con compilation
6.4 A Compiler for Con
6.5 Correctness and random testing
7.9

6 Con: branching with conditionals

When you come to a fork in the road, take it.

    6.1 Conditional execution

    6.2 Meaning of Con programs

    6.3 An Example of Con compilation

    6.4 A Compiler for Con

    6.5 Correctness and random testing

6.1 Conditional execution

Let’s now consider adding a notion of conditionals to our target language.

We’ll call it Con.

We will use the following concrete syntax: (if (zero? e0) e1 e2).

This leads to the following grammar for concrete Con:

image

And abstract grammar:

image

Which can be modeled with the following definitions:

con/ast.rkt

  #lang racket
  (provide Int Prim1 IfZero)
   
  ;; type Expr =
  ;; | (Int Integer)
  ;; | (Prim1 Op Expr)
  ;; | (IfZero Expr Expr Expr)
  ;; type Op = 'add1 | 'sub1
  (struct Int (i)           #:prefab)
  (struct Prim1 (p e)       #:prefab)
  (struct IfZero (e1 e2 e3) #:prefab)
   

The parser is similar to what we’ve seen before:

con/parse.rkt

  #lang racket
  (provide parse)
  (require "ast.rkt")
   
  ;; S-Expr -> Expr
  (define (parse s)
    (cond
      [(integer? s) (Int s)]
      [else
       (match s
         [(list 'add1 e) (Prim1 'add1 (parse e))]
         [(list 'sub1 e) (Prim1 'sub1 (parse e))]
         [(list 'if z1 e2 e3)
          (match z1
            [(list 'zero? e1)
             (IfZero (parse e1) (parse e2) (parse e3))])]
         [_ (error "Parse error")])]))
   
6.2 Meaning of Con programs

The meaning of Con programs depends on the form of the expression and the new form is an if-expression.

Let’s consider some examples (using concrete notation):

The semantics is inductively defined as before. There are two new rules added for handling if-expressions: one for when the test expression means 0 and one for when it doesn’t.

image    image    image

image    image

The interpreter has an added case for if-expressions, which recursively evaluates the test expression and branches based on its value.

con/interp.rkt

  #lang racket
  (provide interp)
  (require "ast.rkt" "interp-prim.rkt")
   
  ;; Expr -> Integer
  (define (interp e)
    (match e
      [(Int i) i]
      [(Prim1 p e)
       (interp-prim1 p (interp e))]
      [(IfZero e1 e2 e3)
       (if (zero? (interp e1))
           (interp e2)
           (interp e3))]))
   
   

We’ve also made one trivial change, which is to move interp-prim1 to its own module. This will be useful in the future when more primitive operations are added, we won’t have to clutter up the interpreter:

con/interp-prim.rkt

  #lang racket
  (provide interp-prim1)
   
  ;; Op Integer -> Integer
  (define (interp-prim1 op i)
    (match op
      ['add1 (add1 i)]
      ['sub1 (sub1 i)]))
   

We can confirm the interpreter computes the right result for the examples given earlier (using parse to state the examples with concrete notation):

Examples

> (interp (parse '(if (zero? 0) (add1 2) 4)))

3

> (interp (parse '(if (zero? 1) (add1 2) 4)))

4

> (interp (parse '(if (zero? (if (zero? (sub1 1)) 1 0)) (add1 2) 4)))

4

> (interp (parse '(if (zero? (add1 0)) (add1 2) (if (zero? (sub1 1)) 1 0))))

1

The argument for the correctness of the interpreter follows the same structure as for Blackmail, but with an added case for if-expressions.

6.3 An Example of Con compilation

Suppose we want to compile (if (zero? 8) 2 3)...

We already know how to compile the 8, 2, and 3 part.

What needs to happen?

We can determine whether 8 evaluates to 0 using a comparison instruction: (Cmp rax 0). To do the conditional execution, we will need to jump to different parts of the code to either execute the code for 2 or 3. There are several ways we could accomplish this, but we take the following approach: immediately after the comparison, do a conditional jump to the code for the then branch when zero. Should the jump not occur, the next instructions will carry out the evaluation of the else branch, then (unconditionally) jump over the then branch code.

To accomplish this, we will need two new labels: one for the then branch code and one for the end of the then branch code. The gensym function can be used to generate symbols that have not appeared before.

In total, the code for this example would look like:

(let ((l0 (gensym))
      (l1 (gensym)))
  (list (Mov 'rax 8)
        (Cmp 'rax 0)
        (Je l0)
        (Mov 'rax 3)
        (Jmp l1)
        (Label l0)
        (Mov rax 2)
        (Label l1)))
6.4 A Compiler for Con

Notice that the (Mov 'rax 8), (Mov rax 3) and (Mov rax 2) parts are just the instructions generated by compiling 8, 2 and 3. Generalizing from this, we arrive at the following code for the compiler:

(let ((l0 (gensym 'if))
      (l1 (gensym 'if)))
  (append (compile-e e1)
          (list (Cmp 'rax 0)
                (Je l0))
          (compile-e e3)
          (list (Jmp l1)
                (Label l0))
          (compile-e e2)
          (list (Label l1))))

This will require extending our use of a86 instructions; in particular, we add Jmp, Je, and Cmp instructions.

The complete compiler code is:

con/compile.rkt

  #lang racket
  (provide (all-defined-out))
  (require "ast.rkt" a86/ast)
   
  ;; Expr -> Asm
  (define (compile e)
    (prog (Label 'entry)
          (compile-e e)
          (Ret)))
   
  ;; Expr -> Asm
  (define (compile-e e)
    (match e
      [(Int i)           (compile-integer i)]    
      [(Prim1 p e)       (compile-prim1 p e)]
      [(IfZero e1 e2 e3) (compile-ifzero e1 e2 e3)]))
   
  ;; Integer -> Asm
  (define (compile-integer i)
    (seq (Mov 'rax i)))
   
  ;; Op Expr -> Asm
  (define (compile-prim1 p e)
    (seq (compile-e e)
         (match p
           ['add1 (Add 'rax 1)]
           ['sub1 (Sub 'rax 1)])))
   
  ;; Expr Expr Expr -> Asm
  (define (compile-ifzero e1 e2 e3)
    (let ((l1 (gensym 'if))
          (l2 (gensym 'if)))
      (seq (compile-e e1)
           (Cmp 'rax 0)
           (Je l1)
           (compile-e e3)
           (Jmp l2)
           (Label l1)
           (compile-e e2)
           (Label l2))))
   

Let’s take a look at a few examples:

Examples

> (define (show s)
    (displayln (asm-string (compile (parse s)))))
> (show '(if (zero? 8) 2 3))

        global entry

        default rel

        section .text

entry:

        mov rax, 8

        cmp rax, 0

        je if6205

        mov rax, 3

        jmp if6206

if6205:

        mov rax, 2

if6206:

        ret

> (show '(if (zero? 0) 1 2))

        global entry

        default rel

        section .text

entry:

        mov rax, 0

        cmp rax, 0

        je if6207

        mov rax, 2

        jmp if6208

if6207:

        mov rax, 1

if6208:

        ret

> (show '(if (zero? 0) (if (zero? 0) 8 9) 2))

        global entry

        default rel

        section .text

entry:

        mov rax, 0

        cmp rax, 0

        je if6209

        mov rax, 2

        jmp if6210

if6209:

        mov rax, 0

        cmp rax, 0

        je if6211

        mov rax, 9

        jmp if6212

if6211:

        mov rax, 8

if6212:

if6210:

        ret

> (show '(if (zero? (if (zero? 2) 1 0)) 4 5))

        global entry

        default rel

        section .text

entry:

        mov rax, 2

        cmp rax, 0

        je if6215

        mov rax, 0

        jmp if6216

if6215:

        mov rax, 1

if6216:

        cmp rax, 0

        je if6213

        mov rax, 5

        jmp if6214

if6213:

        mov rax, 4

if6214:

        ret

And confirm they are running as expected:

Examples

> (define (tell s)
    (asm-interp (compile (parse s))))
> (tell '(if (zero? 8) 2 3))

3

> (tell '(if (zero? 0) 1 2))

1

> (tell '(if (zero? 0) (if (zero? 0) 8 9) 2))

8

> (tell '(if (zero? (if (zero? 2) 1 0)) 4 5))

4

6.5 Correctness and random testing

The statement of correctness follows the same outline as before:

Compiler Correctness: For all expressions e and integers i, if (e,i) in image, then (asm-interp (compile e)) equals i.

Again, we formulate correctness as a property that can be tested:

Examples

> (define (check-compiler e)
    (check-equal? (asm-interp (compile e))
                  (interp e)
                  e))

Generating random Con programs is essentially the same as Blackmail programs, and are provided in a random.rkt module.

Examples

> (require "random.rkt")
> (random-expr)

'#s(Prim1 sub1 #s(Int -2))

> (random-expr)

'#s(Int -2)

> (random-expr)

'#s(Int 2)

> (random-expr)

'#s(Prim1 add1 #s(Int -1))

> (for ([i (in-range 10)])
    (check-compiler (random-expr)))