4 Assignment 4: Interpreters
Inverting the adage that a data type is just a simple programming language, we take the position that a programming language is, semantically, just a complex data type; evaluation of a program is just another operation in the data type.
——Mitch Wand
Assignment
Place your code in a file named a4.rkt and submit it to Autograder.
Part 1: Interpreters and Higher Order Function Representation
In recent lectures, we’ve learned how to write an interpreter that takes a Racket expression and returns the result of evaluating that expression. We have also learned to make it representation independent with respect to environments and closures. We have written helper functions that manipulate the representations of environments and closures: extend-env, apply-env, empty-env, apply-clos and make-clos. In Part 1, we will implement two interpreters in total: the basic representation dependent (RD) interpreter, and the representation independent (RI) interpreter, along with helper functions for the RI interpreter.
You must define a set of environment helpers that uses functional (higher-order) representation of environments. Call the representation-dependent version value-of, and the representation independent version value-of-fn.
Notice these names may be different from those presented in lecture. This is a framework for how you should name your procedures and helpers:
(define value-of ...) (define value-of-fn ...) (define empty-env-fn ...) (define extend-env-fn ...) (define apply-env-fn ...) (define apply-clos-fn ...) (define make-clos-fn ...) Your interpreter must handle the following forms: numbers, booleans, variables, lambda-abstraction, application, zero?, sub1, *, if, and let
Unlike in Racket, here let can bind only one variable.
Remember, your solutions should be compositional.
You may have seen the expansion of (let ((x e)) body) as ((lambda (x) body) e). When you are comfortable with the environment, however, you can implement let without using this expansion.
As usual, these references are not required, but yield a wider understanding of what we’re doing, see Reynolds and Danvy.
> (value-of '((lambda (x) (if (zero? x) #t #f)) 0) (lambda (y) (error 'value-of "unbound variable ~s" y))) #t > (value-of '((lambda (x) (if (zero? x) 12 47)) 0) (lambda (y) (error 'value-of "unbound variable ~s" y))) 12 > (value-of '(let ([y (* 3 4)]) ((lambda (x) (* x y)) (sub1 6))) (lambda (y) (error 'value-of "unbound variable ~s" y))) 60 > (value-of '(let ([x (* 2 3)]) (let ([y (sub1 x)]) (* x y))) (lambda (y) (error 'value-of "unbound variable ~s" y))) 30 > (value-of '(let ([x (* 2 3)]) (let ([x (sub1 x)]) (* x x))) (lambda (y) (error 'value-of "unbound variable ~s" y))) 25 > (value-of '(let ((! (lambda (x) (* x x)))) (let ((! (lambda (n) (if (zero? n) 1 (* n (! (sub1 n))))))) (! 5))) (lambda (y) (error 'value-of "unbound variable ~s" y))) 80 > (value-of '(((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) (lambda (y) (error 'value-of "unbound variable ~s" y))) 120 > (value-of-fn '((lambda (x) (if (zero? x) #t #f)) 0) (empty-env-fn)) #t > (value-of-fn '((lambda (x) (if (zero? x) 12 47)) 0) (empty-env-fn)) 12 > (value-of-fn '(let ([y (* 3 4)]) ((lambda (x) (* x y)) (sub1 6))) (empty-env-fn)) 60 > (value-of-fn '(let ([x (* 2 3)]) (let ([y (sub1 x)]) (* x y))) (empty-env-fn)) 30 > (value-of-fn '(let ([x (* 2 3)]) (let ([x (sub1 x)]) (* x x))) (empty-env-fn)) 25 > (value-of-fn '(((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-fn)) 120
Part 2: Interpreters and Data Structural Representation
In part 2, we will implement one interpreter: the representation independent (RI) interpreter using data structural representations for environments and closures, along with helper functions for the interpreter.
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-clos-ds and make-clos-ds for value-of-ds.
(define value-of-ds ...) (define empty-env-ds ...) (define extend-env-ds ...) (define apply-env-ds ...) (define make-clos-ds ...) (define apply-clos-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