Week 14 Set b

Due Date Wed 12/5 at 9:00pm (Week 14)

Purpose To explore StackLang & Compilers

Graded Exercises You’ve seen most of an interpreter for StackLang in class. We’ve modified that code slightly below. In particular, we incorporated variables into our definition of Value, as that should make it easier for you to define and use pairs (Exercise 3). This means that, unlike it class, there is only one push instruction, which takes a value. Note, of course, that the Symbol case is essentially a placeholder for a Value, as it should always be substituted away before actually being used. But we want it in the grammar so we can substitute everywhere we use Values.

;

; StackLang ;;

;

; P ::= (i-1,...,i-n)

; i ::= ret v | ret 'x | sub | if0 P P | call | lam x.P

; S ::= (v-1, ..., v-n)

; v ::= n | thunk P

;

; (P,S) ==> S'

;

; (i,P,S) ==> S'

; A Program is a [List-of Instruction]

; An Instruction is a:

; - (list 'push Value)

; - (list 'sub)

; - (list 'mul)

; - (list 'add)

; - (list 'if0 Program Program)

; - (list 'call)

; - (list 'lam Symbol Program)

; A Stack is a [List-of Value]

; A Value is a:

; - Symbol

; - (list 'num Number)

; - (list 'thunk Program)

;

; INTERPRETER ;;

;

; interp : Program Stack -> Stack

; runs a program with a given starting stack, producing the final stack or erroring.

(define (interp prog stk)

(cond

[(empty? prog) stk]

[(cons? prog) (interp-instr (first prog) (rest prog) stk)]))

(check-expect (interp (list '(push (num 2)))

(list))

(list '(num 2)))

(check-expect (interp (list '(push (num 2)) '(push (num 1)) '(sub))

(list))

(list '(num -1)))

(check-error (interp '((push x))

(list)))

(check-expect (interp (list '(push (thunk ((push (num 1))))) '(call))

(list))

(list '(num 1)))

(check-expect (interp (list '(push (num 0)) '(if0 ((push (num 10))) ((push (num 20)))))

(list))

(list '(num 10)))

(define p1 (list '(push (num 1)) '(push (thunk ((lam x ((push x)))))) '(call)))

(check-expect (interp p1 (list))

(list '(num 1)))

(define p2 (list '(push (num 2)) '(push (num 1)) '(push (num 3)) '(push (thunk ((lam 'x ((sub)))))) '(call)))

(check-expect (interp p2 (list))

(list '(num -1)))

; interp-instr : Instruction Program Stack -> Stack

; runs an instruction with a stack and rest of program, producing the final stack or erroring.

(define (interp-instr i prog stk)

(cond

[(symbol=? (first i) 'push)

(if (symbol? (second i))

(error "Trying to interp a free variable: " (second i))

(interp prog (cons (second i) stk)))]

[(symbol=? (first i) 'sub) (interp-sub prog stk)]

[(symbol=? (first i) 'add) (interp-add prog stk)]

[(symbol=? (first i) 'mul) (interp-mul prog stk)]

[(symbol=? (first i) 'if0) (interp-if0 (second i) (third i) prog stk)]

[(symbol=? (first i) 'call) (interp-call prog stk)]

[(symbol=? (first i) 'lam) (interp-lam (second i) (third i) prog stk)]))

(check-expect (interp-instr '(sub)

(list)

'((num 1) (num 2)))

(list '(num -1)))

(check-expect (interp-instr '(push (num 1))

(list '(sub))

'((num 1)))

(list '(num 0)))

(check-expect (interp-instr '(push (num 1))

(list)

'((num 1)))

'((num 1) (num 1)))

; interp-sub : Program Stack -> Stack

; applies subtraction and then continues running the rest of the program on resulting stack

(define (interp-sub prog stk)

; DEFINE ME!

stk)

; interp-add : Program Stack -> Stack

; applies addition and then continues running the rest of the program on resulting stack

(define (interp-add prog stk)

; DEFINE ME!

stk)

; interp-mul : Program Stack -> Stack

; applies multiplication and then continues running the rest of the program on resulting stack

(define (interp-mul prog stk)

; DEFINE ME!

stk)

; interp-call : Program Stack -> Stack

; pops a Program off the top of the stack and continues running the program, erroring if no thunk.

(define (interp-call prog stk)

(cond

[(< (length stk) 1)

(error "Could not apply 'call, as the stack was empty.")]

[(or (not (list? (first stk)))

(not (equal? 'thunk (first (first stk)))))

(error "Could not apply 'call, as the top of the stack was not a thunk.")]

[else (interp (append (second (first stk)) prog)

(rest stk))]))

(check-expect (interp-call (list)

(list (list 'thunk '((push (num 1))))))

(list '(num 1)))

(check-expect (interp-call (list)

(list (list 'thunk '((sub))) '(num 2) '(num 1)))

(list '(num 1)))

; interp-if0 : Program Program Program Stack -> Stack

; pops a number off the stack;

; if number is 0, run thn Program followed by prog on the resulting stack,

; otherwise run els Program and then prog on the resulting stack;

; error if no number on top of stack.

(define (interp-if0 thn els prog stk)

; DEFINE ME!

stk)

; —————————————————-

; interp-lam : Symbol Program Program Stack -> Stack

; substitutes into a lambda and stores result on the stack

(define (interp-lam x body prog stk)

(cond

[(< (length stk) 1)

(error "could not apply 'lam, as the stack was empty")]

[else (interp (append (substitute x (first stk) body) prog)

(rest stk))]))

(check-expect (interp-lam 'x (list '(push x)) '()

(list '(num 1)))

(list '(num 1)))

; substitute : Symbol Value Program -> Program

; substitutes free occurrences of x with v in prog

(define (substitute x v prog)

(cond [(empty? prog) prog]

[(cons? prog) (cons (substitute-instr x v (first prog)) (substitute x v (rest prog)))]))

(check-expect (substitute 'x '(num 1) (list '(push x) '(push (num 2))))

(list '(push (num 1)) '(push (num 2))))

(check-expect (substitute 'x '(num 1) (list '(push x) '(lam x (push x))))

(list '(push (num 1)) '(lam x (push x))))

; substitute-instr : Symbol Value Instruction -> Instruction

; substitutes free occurrences of x with v in instruction i

(define (substitute-instr x v i)

(cond

[(symbol=? (first i) 'push)

(list 'push (substitute-val x v (second i)))]

[(symbol=? (first i) 'sub) i]

[(symbol=? (first i) 'mul) i]

[(symbol=? (first i) 'add) i]

[(symbol=? (first i) 'if0) (list 'if0 (substitute x v (second i))

(substitute x v (third i)))]

[(symbol=? (first i) 'call) i]

[(symbol=? (first i) 'lam)

(if (not (symbol=? (second i) x))

(list 'lam (second i) (substitute x v (third i)))

i)]))

(check-expect (substitute-instr 'x '(num 1) '(push x))

'(push (num 1)))

(check-expect (substitute-instr 'x '(num 1) '(lam x ((push x))))

'(lam x ((push x))))

; substitute-val : Symbol Value Value -> Value

; substitutes free occurrences of x with v in original value v0

(define (substitute-val x v v0)

(cond [(symbol? v0)

(if (symbol=? x v0) v v0)]

[(symbol=? (first v0) 'num) v0]

[(symbol=? (first v0) 'thunk) (list 'thunk (substitute x v (second v0)))]))

Exercise 1 In the above interpreter, we are missing the implementation and test cases for the 'sub,'add,'mul, and if0 cases. Please fill in the definitions and add appropriate test cases.

Exercise 2 When writing programs in stack languages (or, more likely, when generating stack programs, as they are less likely to be written by hand), there are certain common stack "bookkeeping" functions that we want to be able to use. Please implement the following as StackLang Programs (i.e., a [List-of Instruction]). These should not handle errors (i.e., if they are applied when there are not enough values on the stack, the interpreter will report the error).

; dup : Program

; dup duplicates the top value on the stack,

; transforming a stack from v1,v2,v3... to v1,v1,v2,v3...

(define dup ...)

; drop : Program

; drop drops the top value from the stack,

; transforming a stack from v1,v2,v3... to v2,v3...

(define drop ...)

; swap : Program

; swap swaps the top two values on the stack,

; transforming a stack from v1,v2,v3... to v2,v1,v3...

(define swap ...)

Exercise 3 In Week 13 Set b you added pairs to the Simply Typed Language, and we would like to add them as values to StackLang as well.

Please extend the Value definition and add a new instruction unwrap which expects a pair to be on the top of the stack, removes it, and pushes the two elements of the pair (right _below_ left) onto the stack. Update any other aspects of the interpreter (in particular, substitution) that you need.

Exercise 4 In Week 13 Set b, you extended the Simply Typed Language with sum types and a case statement. We want to be able to use those in the programs that we write in the Simply Typed Language, which means we need to be able to compile them to StackLang so that we can run them with our interpreter.

Assuming that you have a function compile which will compile the rest of the Simply Typed Language (which you will see starting Monday), write the three helper functions that translate inleft, inright, and case into StackLang, and corresponding test cases. Please consult Week 13 Set b for the behavior of case.

; An Expression is a:

; - Number

; - Boolean

; - (list '+ Expression Expression)

; - (list 'if Expression Expression Expression)

; - (list 'var Symbol)

; - (list 'lam Symbol Type Expression)

; - (list 'app Expression Expression)

; - (list 'pair Expression Expression)

; - (list 'fst Expression)

; - (list 'snd Expression)

; - (list 'inleft Type Type Expression)

; - (list 'inright Type Type Expression)

; - (list 'case Expression Symbol Expression Symbol Expression)

; This 'compile' function is partially complete. We will further work on it in

; class on Wednesday, but you can write tests that only use expressions that it

; can compile. Note that our compile assumes the following Expression

; definition: If you chose a different one for inleft/inright/case, that's

; okay, as long as it is essentially equivalent.

; compile : Expression -> Program

; translates a Simply Typed Expression into a StackLang Program

(define (compile e)

(cond [(number? e) (list (list 'push (list 'num e)))]

[(boolean? e) ...]

[(symbol=? (first e) '+) (append (compile (second e)) ; n1, ...

(compile (third e))  ; n2,n1 ...

'((add)))]

[(symbol=? (first e) 'if) ...]

[(symbol=? (first e) 'var) (list (list 'push (second e)))]

[(symbol=? (first e) 'lam) ...]

[(symbol=? (first e) 'app) ...]

[(symbol=? (first e) 'pair) ...]

[(symbol=? (first e) 'fst) ...]

[(symbol=? (first e) 'snd) ...]

[(symbol=? (first e) 'inleft) (compile-inleft (fourth e))]

[(symbol=? (first e) 'inright) (compile-inright (fourth e))]

[(symbol=? (first e) 'case)

(compile-case (second e) (third e) (fourth e) (fifth e) (sixth e))]))

; compile-inleft : Expression -> Program

; translates Expression in an inleft into corresponding StackLang Program

(define (compile-inleft e)

; DEFINE ME

...)

; compile-inright : Expression -> Program

; translates Expression in an inright into corresponding StackLang Program

(define (compile-inright e)

; DEFINE ME

...)

; compile-case : Expression Symbol Expression Symbol Expression -> Program

; translates Expressions, bindings, and branches of a case into corresponding StackLang Program

(define (compile-case e x e1 y e2)

; DEFINE ME

...)