2 Interpreters🔗

2.1 Cond [60 Points]🔗

cond in Plait works by evaluating the first branch whose guard evaluates to #t, like:

> (cond     [(> 1 2) 'first-branch]     [(= 10 20) 'second-branch]     [(> 4 3) 'third-branch])

- Symbol

'third-branch

In this exercise we will make an interpreter for a language with a cond-like construct. We will use the following abstract syntax and value data structures:

(define-type Value

[numV (n : Number)]

[boolV (b : Boolean)])

(define-type Arm

(arm [guard : CondExp] [body : CondExp]))

(define-type CondExp

[numC (n : Number)]

[boolC (b : Boolean)]

[greaterthanC (e1 : CondExp) (e2 : CondExp)]

[addC (left : CondExp) (right : CondExp)]

[condC (arms : (Listof Arm))])

2.1.1 Definitional Interpreter [30 Points]🔗

Implement a definitional interpreter interp-cond of type (CondExp -> Value) that evaluates CondExp programs. To get a feeling for how condE is supposed to behave, you see how cond works in Plait programs by using the Plait interpreter. For example:

> (interp-cond (condC (list (arm (boolC #t) (numC 10))

(arm (boolC #f) (numC 20)))))

(numV 10)

> (interp-cond (condC (list (arm (greaterthanC (numC 20) (numC 10)) (numC 15))

(arm (boolC #f) (numC 20)))))

(numV 15)

Your interpreter is allowed to raise runtime errors if illegal program operations are performed, such as attempting to add a boolean and number. If there are no valid arms for a cond, raise a runtime error by using error.

2.1.2 Small-Step Interpreter [30 Points]🔗

Examples of stepping condC:

(condC (list (arm (boolC #f) (numC 10))

(arm (boolC #t) (addC (numC 10) (numC 20)))))

--> (condC (list (arm (boolC #t) (addC (numC 10) (numC 20)))))

--> (addC (numC 10) (numC 20))

--> (numC 30)

Another example:

(condC (list (arm (greaterthanC (numC 20) (numC 10)) (numC 10))

(arm (boolC #t) (numC 20))))

--> (condC (list (arm (boolC #t) (numC 10))

(arm (boolC #t) (numC 20))))

--> (numC 10)

Your interpreter is allowed to raise runtime errors if illegal program operations are performed, such as attempting to add a boolean and number. Be very careful about simplification order; you will not receive full credit if simplifications are not performed in precisely the specified order. If you are confused, you can ask a question on Piazza like "Is this a valid step?", give us a concrete example of a step, and we will answer yes or no.

2.2 Uniquify [40 Points]🔗

You are tired of dealing with shadowing, so you’ve decided to implement a function called uniquify that, when given an abstract syntax tree for LetLang, renames all shadowed variables to unique names (i.e., names that are guaranteed not to be bound anywhere else in the program). This way, you can tell a variable’s scope just by looking for its unique binding in the program!

We will use the following abstract syntax for this problem:

(define-type Exp

[numE (n : Number)]

[plusE (l : Exp) (r : Exp)]

[varE (s : Symbol)]

[let1E (var : Symbol)

(assignment : Exp)

(body : Exp)])

2.2.1 Rename [10 Points]🔗

You run into a challenge almost immediately: even if we generate unique names, we need a way to replace the existing name in your abstract syntax tree with your newly generated unique one. Notice how our current subst function does not do that.

Write function (update-names oldname newname e) of type (Symbol Symbol LetExpr -> LetExpr) that that replaces all variables with name oldname in e with the name newname regardless of scoping rules (i.e., ignoring shadowing). You can assume that newname will never appear in e.

Example behavior:

(test (update-names (let1E 'x (numE 10) (varE 'x)) 'x 'y)

(let1E 'y (numE 10) (varE 'y)))

2.2.2 Uniquify [30 Points]🔗

Implement uniquify using update-names. Your solution should additionally use the following fresh-name! function, which you can assume is guaranteed to produce a unique name whenever it is called (don’t worry about understanding how it works; we will cover mutation later):

(define counter (box "###"))

(define (fresh-name!)

(string->symbol (begin

(set-box! counter (string-appnd "a" (unbox counter)))

(unbox counter))))

Try calling it a few times and see how it behaves.

If we assume variables can’t be shadowed, we can simplify our interpreter to remove the check for shadowing:

;;; perform substitution *without checking for shadowing*

(subst-uniq : (Symbol Number Exp -> Exp))

(define (subst-uniq id assignment body)

(type-case Exp body

[(numE n) (numE n)]

[(plusE l r) (plusE (subst-uniq id assignment l) (subst-uniq id assignment r))]

[(varE s) (if (symbol=? s id) (numE assignment) (varE s))]

[(let1E innervar innerassignment innerbody)

(let1E innervar (subst-uniq id assignment innerassignment)

(subst-uniq id assignment innerbody))

]))

Your uniquify function should be implemented so that the provided interpreter interp-uniq obeys the rules of lexical scope that we discussed in class, even though it uses the broken substitution function. Example behavior:

(test (interp-uniq (uniquify (let1E 'x (numE 10)

(let1E 'x (numE 20) (varE 'x)))))

20)