On two occasions I have been asked [by members of Parliament],–“Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?” […]

This assignment has three parts. In addition to an improved `lex`

, we expect you to turn in **three interpreters**: `value-of-fn`

, `value-of-ds`

, and a third, `value-of-dynamic`

with your implementation of dynamic scope. H311/B521 students will have a fourth interpreter.

You should be able to use the a4-student-tests.rkt file to test your solutions.

> (require "a4-student-tests.rkt") > (test-file #:file-name "a4.rkt") ...

and that should get you going. Of course, **these tests are not exhaustive; you should add your own tests as well**.

When we implemented `lex`

before, it could handle variables, application, and `lambda`

-abstraction forms. Extend your previous definition of `lex`

so that it can handle not only those forms, but also numbers, `zero?`

, `sub1`

, `*`

, `if`

, and `let`

. This should be a fairly straightforward extension, but it also serves as a chance to improve a misbehaving `lex`

from Assignment 2. In order to better disambiguate numbers from lexical addresses, you should transform a number `n`

into `(const n)`

.

> (lex '((lambda (x) x) 5) '()) ((lambda (var 0)) (const 5)) > (lex '(lambda (!) (lambda (n) (if (zero? n) 1 (* n (! (sub1 n)))))) '()) (lambda (lambda (if (zero? (var 0)) (const 1) (* (var 0) ((var 1) (sub1 (var 0))))))) > (lex '(let ((! (lambda (!) (lambda (n) (if (zero? n) 1 (* n ((! !) (sub1 n)))))))) ((! !) 5)) '()) (let (lambda (lambda (if (zero? (var 0)) (const 1) (* (var 0) (((var 1) (var 1)) (sub1 (var 0))))))) (((var 0) (var 0)) (const 5)))

For this part of the assignment, use **one** of your interpreters from last week's assignment as a starting point. You may pick either `value-of`

, `value-of-fn`

or `value-of-ds`

. But for Part II you should pick, and stick with, a *single* representation of environments. If you choose to start with `value-of`

, leave your environments representation dependent using higher-order functions. If you chose to start with `value-of-fn`

change either all three of `empty-env-fn`

, `apply-env-fn`

, and `extend-env-fn`

to `empty-env`

, `apply-env`

, and `extend-env`

. If you chose to start with `value-of-ds`

change all three of `empty-env-ds`

, `apply-env-ds`

, and `extend-env-ds`

, to `empty-env`

, `apply-env`

, and `extend-env`

. In either of the latter two cases, use these new names for the environment helpers in your interpreter. Having done so, create two *new* interpreters that are representation independent with respect to closures: `value-of-fn`

and `value-of-ds`

, respectively.

1. ''value-of-fn'' should use a functional representation of closures. 2. ''value-of-ds'' should use a data-structural representation of closures.

You should write two new closure helper functions for each of your interpreters. Write `apply-closure-fn`

and `closure-fn`

for `value-of-fn`

, and write `apply-closure-ds`

, and `closure-ds`

for `value-of-ds`

.

Your interpreters must work for at least these test cases. Of course, **these tests are not exhaustive; you should use your own tests as well**.

> (value-of-fn '((lambda (x) (if (zero? x) 12 47)) 0) (empty-env)) 12 > (value-of-fn '(let ([y (* 3 4)]) ((lambda (x) (* x y)) (sub1 6))) (empty-env)) 60 > (value-of-fn '(let ([x (* 2 3)]) (let ([y (sub1 x)]) (* x y))) (empty-env)) 30 > (value-of-fn '(let ([x (* 2 3)]) (let ([x (sub1 x)]) (* x x))) (empty-env)) 25 > (value-of-ds '((lambda (x) (if (zero? x) 12 47)) 0) (empty-env)) 12 > (value-of-ds '(let ([y (* 3 4)]) ((lambda (x) (* x y)) (sub1 6))) (empty-env)) 60 > (value-of-ds '(let ([x (* 2 3)]) (let ([y (sub1 x)]) (* x y))) (empty-env)) 30 > (value-of-ds '(let ([x (* 2 3)]) (let ([x (sub1 x)]) (* x x))) (empty-env)) 25

The second part of this week's assignment is to create an interpreter that uses *dynamic scope*.

The interpreters we have been writing so far have been implemented in such a way that, if there are variables that occur free in an a procedure, they take their values from the environment in which the `lambda`

expression is defined. We accomplish this by creating a closure for each procedure we see, and we save the environment in the closure. This technique is called *static binding of variables*, or *static scope*. Lexical scope is a kind of static scope.

Alternatively, we could implement our interpreters such that any variables that occur free in the body of a procedure get their values from the environment from which the procedure is *called*, rather than from the environment in which the procedure is *defined*.

For example, consider what would happen if we were to evaluate the following expression in an interpreter that used lexical scope:

(let ([x 2]) (let ([f (lambda (e) x)]) (let ([x 5]) (f 0))))

Our lexical interpreter would add `x`

to the environment with a value of `2`

. For `f`

, it would create a closure that contained the binding of `x`

to `2`

, and it would add `f`

to the environment with that closure as its value. Finally, the inner `let`

would add `x`

to the environment with a value of `5`

. Then the call `(f 0)`

would be evaluated, but since it would use the value of `x`

that was saved in the closure (which was `2`

) rather than the value of `x`

that was current at the time `f`

was called (which was `5`

), the entire expression would evaluate to `2`

.

Under dynamic scope, we wouldn't save the value of `x`

in the closure for `f`

. Instead, the application `(f 0)`

would use the value of `x`

that was current in the environment at the time it was called, so the entire expression would evaluate to `5`

.

As you can see, dynamic scope is a little strange, but it does have its uses.

Define `value-of-dynamic`

, an interpreter that implements dynamic scope. You can start with the dynamically-scoped interpreter we wrote in class that used `match-let`

. You should be able to share your environment helpers from Parts I and II above, but you should not implement an abstraction for closures as well. Instead, the value of a `lambda`

abstraction should be that same lambda abstraction. In the same way the value of a number is that same number. You'll find then, that when you go to evaluate an application, there's only one environment in which you *can* evaluate the body. This is a pretty simple change. To liven things up a little (and also to allow us a more interesting test case), this interpreter should also implement `let`

, `if`

, `*`

, `sub1`

, `null?`

, `zero?`

, `cons`

, `car`

, `cdr`

, and `quote`

. When evaluating the expression `(cons 1 (cons 2 '()))`

`value-of-dynamic`

should return `(1 2)`

. Now `quote`

is a bit of a tricky beast. So here's the `quote`

line for the interpreter.

[`(quote ,v) v]

> (value-of-dynamic '(let ([x 2]) (let ([f (lambda (e) x)]) (let ([x 5]) (f 0)))) (empty-env)) 5 > (value-of-dynamic '(let ([! (lambda (n) (if (zero? n) 1 (* n (! (sub1 n)))))]) (! 5)) (empty-env)) 120 > (value-of-dynamic '(let ([f (lambda (x) (cons x l))]) (let ([cmap (lambda (f) (lambda (l) (if (null? l) '() (cons (f (car l)) ((cmap f) (cdr l))))))]) ((cmap f) (cons 1 (cons 2 (cons 3 '())))))) (empty-env)) ((1 1 2 3) (2 2 3) (3 3))

4. We've been talking a whole lot about representation independence. It would sure be nice to have a single interpreter where we could just pass in the various helper functions. That way we could write the interpreter once, pass in implementations of our environment and closure helpers, and then get an interpreter that will just take the expression we want to evaluate, that uses those helpers. From such a definition, it is obvious on first inspection of this single interpreter is indeed representation independent with respect to both environments and closures.

So let's do it.

Write a single function named `value-of-ri`

that'll take `empty-env`

, `extend-env`

, `apply-env`

, `closure`

, and `apply-closure`

, and return an interpreter expecting a single expression. You'll need to pass an additional parameter to your closure helper functions, so define them as `closure-fn-ri`

and `apply-closure-fn-ri`

`closure-ds-ri`

and `apply-closure-ds-ri`

, and make sure they take this additional parameter. Go ahead and include your regular `if`

, `*`

, `sub1`

, `zero?`

, `let`

, forms, along with numbers and booleans, and `lambda`

-calculus expressions. **You should not pass your helper functions to recursive calls.** Here's what the calls to initially kick off the interpreter should look like.

>((value-of-ri empty-env-fn extend-env-fn apply-env-fn closure-fn-ri apply-closure-fn-ri) '((lambda (x) x) 5)) 5 >((value-of-ri empty-env-ds extend-env-ds apply-env-ds closure-ds-ri apply-closure-ds-ri) '((lambda (x) x) 5)) 5 >((value-of-ri empty-env-fn extend-env-fn apply-env-fn closure-ds-ri apply-closure-ds-ri) '((lambda (x) x) 5)) 5 >((value-of-ri empty-env-ds extend-env-ds apply-env-ds closure-fn-ri apply-closure-fn-ri) '((lambda (x) x) 5)) 5

Your solution should involve a letrec.