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 if6206

        mov rax, 3

        jmp if6207

if6206:

        mov rax, 2

if6207:

        ret

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

        global entry

        default rel

        section .text

entry:

        mov rax, 0

        cmp rax, 0

        je if6208

        mov rax, 2

        jmp if6209

if6208:

        mov rax, 1

if6209:

        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 if6210

        mov rax, 2

        jmp if6211

if6210:

        mov rax, 0

        cmp rax, 0

        je if6212

        mov rax, 9

        jmp if6213

if6212:

        mov rax, 8

if6213:

if6211:

        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 if6216

        mov rax, 0

        jmp if6217

if6216:

        mov rax, 1

if6217:

        cmp rax, 0

        je if6214

        mov rax, 5

        jmp if6215

if6214:

        mov rax, 4

if6215:

        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(Int 1)

> (random-expr)

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

> (random-expr)

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

> (random-expr)

'#s(IfZero #s(Prim1 add1 #s(Prim1 sub1 #s(Prim1 sub1 #s(Int -3)))) #s(Prim1 sub1 #s(Int -8)) #s(Prim1 add1 #s(Int -2)))

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