5 Con: branching with conditionals

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

5.1 Conditional execution

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

We’ll call it Con.

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

Together this leads to the following grammar for Con:

Which can be modeled with the following data type definition:

con/ast.rkt

#lang racket

;; type Expr =

;; | Integer

;; | `(add1 ,Expr)

;; | `(sub1 ,Expr)

;; | `(if (zero? ,Expr) ,Expr ,Expr)

We will also need a predicate for well-formed Con expressions, but let’s return to this after considering the semantics and interpreter.

5.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.

• the meaning of a if expression (if (zero? e0) e1 e2) is the meaning of e1 if the meaning of e1 if the meaning of e0 is 0 and is the meaning of e2 otherwise.

Let’s consider some examples:

• '(if (zero? 0) (add1 2) 4) means 3.

• '(if (zero? 1) (add1 2) 4) means 4.

• '(if (zero? (if (zero? (sub1 1)) 1 0)) (add1 2) 4) means 4.

• '(if (zero? (add1 0)) (add1 2) (if (zero? (sub1 1)) 1 0)) means 1.

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.

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 (all-defined-out))

;; Expr -> Integer

(define (interp e)

(match e

[(? integer? i) i]

[`(add1 ,e0)

(+ (interp e0) 1)]

[`(sub1 ,e0)

(- (interp e0) 1)]

[`(if (zero? ,e0) ,e1 ,e2)

(if (zero? (interp e0))

(interp e1)

(interp e2))]))

We can confirm the interpreter computes the right result for the examples given earlier:

Examples

> (interp '(if (zero? 0) (add1 2) 4))
3
> (interp '(if (zero? 1) (add1 2) 4))
4
> (interp '(if (zero? (if (zero? (sub1 1)) 1 0)) (add1 2) 4))
4
> (interp '(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.

5.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?

• Execute the code for 8 leaving the result in 'rax,

• check whether 'rax holds zero,

• if it does, execute the code for 2,

• if it doesn’t, execute the code for 3.

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 else branch when non-zero. Should the jump not occur, the next instructions will carry out the evaluation of the then branch, then (unconditionally) jump over the else branch code.

To accomplish this, we will need two new labels: one for the else branch code and one for the end of the else 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:

'((mov rax 8)

(cmp rax 0)

(jne if-else-begin)

(mov rax 2)

(jmp if-else-end)

if-else-begin

(mov rax 3)

if-else-end)

5.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 ((c0 (compile-e e0))

(c1 (compile-e e1))

(c2 (compile-e e2))

(l0 (gensym "if"))

(l1 (gensym "if")))

`(,@c0

(cmp rax 0)

(jne ,l0)

,@c1

(jmp ,l1)

,l0

,@c2

,l1))

This will require extending our representation of x86 instructions; in particular, we add 'jmp, 'jne, and 'cmp instructions:

con/asm/ast.rkt

#lang racket

;; type Asm = [Listof Instruction]

;; type Instruction =

;; | `ret

;; | `(mov ,Arg ,Arg)

;; | `(add ,Arg ,Arg)

;; | `(sub ,Arg ,Arg)

;; | `(cmp ,Arg ,Arg)

;; | `(jmp ,Label)

;; | `(je  ,Label)

;; | `(jne ,Label)

;; | Label

;; type Label = Symbol

;; type Arg =

;; | Reg

;; | Integer

;; type Reg =

;; | `rax

We omit the printer code, which is mundane. See asm/printer.rkt for details.

The complete compiler code is:

con/compile.rkt

#lang racket

(provide (all-defined-out))

;; Expr -> Asm

(define (compile e)

`(entry

,@(compile-e e)

ret))

;; Expr -> Asm

(define (compile-e e)

(match e

[(? integer? i) `((mov rax ,i))]

[`(add1 ,e0)

(let ((c0 (compile-e e0)))

`(,@c0

(add rax 1)))]

[`(sub1 ,e0)

(let ((c0 (compile-e e0)))

`(,@c0

(sub rax 1)))]

[`(if (zero? ,e0) ,e1 ,e2)

(let ((c0 (compile-e e0))

(c1 (compile-e e1))

(c2 (compile-e e2))

(l0 (gensym "if"))

(l1 (gensym "if")))

`(,@c0

(cmp rax 0)

(jne ,l0)

,@c1

(jmp ,l1)

,l0

,@c2

,l1))]))

5.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 , 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)

'(sub1 (add1 1))

> (random-expr)

'(add1 (if (zero? (add1 (sub1 6))) (if (zero? (sub1 1)) (sub1 3) -1) (sub1 (add1 -3))))

> (random-expr)

'(add1 (sub1 (if (zero? (sub1 -3)) (if (zero? -8) -1 3) (add1 1))))

> (random-expr)

'(add1 (sub1 4))

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