4 Assignment 4: Environments and Interpreters

This week’s assignment only has one question and it builds on top of last assignment 3

Assignment

Place your code for interpreter in a file named ”a4.rkt” and submit it to Autograder.

• You must define set of environment helpers: that uses data-structural representation of environments. Call the representation-independent version with data-structural helpers value-of-ds. Your data structures should be the association list representation.

• Association list environments are a list of variable-value list of two members like '((a 1) (b 2) (c 3)). This means that the variable a has the value 1, the variable b has the value 2 and the variable c has the value 3. You add new variable-value list by cons-ing them to the left of the old environment. For example, if a new b variable is defined, then the env would look like this '((b 5) (a 1) (b 2) (c 3)). Notice that the new b on the left shadows the old b with the value 2.

• Also make your closures representation independent using tagged list data structure. You should write two closure helper functions for this interpreter. Write apply-closure-ds and make-closure-ds for value-of-ds.

  (define value-of-ds ...)

  (define empty-env-ds ...)

  (define extend-env-ds ...)

  (define apply-env-ds ...)

  (define make-closure-ds ...)

  (define apply-closure-ds ...)

• Your interpreter must handle the following forms: numbers, booleans, variables, lambda-abstraction, application, zero?, sub1, *, if, and let. For this part you can use the value-of interpreter from assignment-3

• Remember, your solutions should be compositional.

> (value-of-ds

'((lambda (x) (if (zero? x)

#t

#f))

0)

(empty-env-ds))

#t

> (value-of-ds

'((lambda (x) (if (zero? x)

12

47))

0)

(empty-env-ds))

12

> (value-of-ds

'(let ([y (* 3 4)])

((lambda (x) (* x y)) (sub1 6)))

(empty-env-ds))

60

> (value-of-ds

'(let ([x (* 2 3)])

(let ([y (sub1 x)])

(* x y)))

(empty-env-ds))

30

> (value-of-ds

'(let ([x (* 2 3)])

(let ([x (sub1 x)])

(* x x)))

(empty-env-ds))

25

> (value-of-ds

'(((lambda (f)

(lambda (n) (if (zero? n) 1 (* n ((f f) (sub1 n))))))

(lambda (f)

(lambda (n) (if (zero? n) 1 (* n ((f f) (sub1 n)))))))

5)

(empty-env-ds))

120