Assignment 4 - Representation Independence and Dynamic Scope

This assignment comprises three parts.

Part I:

Write an interpreter that is representation-independent with respect to both environments and procedures. You must define two versions of the closure and apply-proc helper functions: one which uses higher-order (that is, functional) representation of procedures, and another that uses data-structural representation of procedures. You may use either data-structural or procedural representation of environments.

You must test your interpreter, using both sets of procedual helper functions. At a minimum, you should run the following test:

(test 'fact
  (value-of
    (quote
      ((let ([! (lambda (!)
                  (lambda (n)
                    (if (zero? n)
                      1
                      (* n ((! !) (sub1 n))))))])
         (! !))
       5))
    (empty-env))
  120)

Part II:

You will then add dynamic scope to your interpreter.

First, add the d-lambda form to your interpreter; d-lambda is a variant of lambda that implements dynamic scope.

Then redefine the higher-order version of closure and apply-proc as necessary.

Here are two tests that should pass once you have added d-lambda to the interpreter:

(define let-static
  '(let ([x 2])
     (let ([f (lambda (e) x)])
       (let ([x 5])
         (f 0)))))

(define let-dynamic
  '(let ([x 2])
     (let ([f (d-lambda (e) x)])
       (let ([x 5])
         (f 0)))))

(test "let-test-static"
  (value-of let-static (empty-env))
  2)

(test "let-test-dynamic"
  (value-of let-dynamic (empty-env))
  5)

Once the tests above pass, re-define your data structural implementation of apply-proc and closure, in order to support d-lambda. You must not change your definition of value-of.

Part III:

In addition to the code for your interpreter, you must describe, in as much detail as possible, how your interpreter evaluates the expression
```
(let ([y (* 3 4)])
  ((lambda (x) (* x y)) (sub1 6)))
```
Explain the order in which the sub-expressions are evaluated, when the environment is extended (and with which bindings), which environment is saved when the procedure is created, and so on. Pay special attention to procedure creation and application. A complete, detailed description of this process will be between a quarter of a page and half a page in length. To repeat:
A complete, detailed description of this process will be between a quarter of a page and half a page in length.

If your description is not detailed enough, or is significantly flawed, you will be asked to orally explain how the interpreter works to either Ramana or Will.

Place your code from Parts I and II (including any test programs), and your description from Part II, in a file named `a4.scm` and submit it to Vincent. Comment-out your description using semi-colons (`;`), so that your file loads under Chez.

There are two brainteasers this week--try either one, or both! (Extra credit given only if you have completed the rest of the assignment.)

Brainteaser: Write another interpreter, representation independent with respect to both closures and environments (using any representation you like), which includes support for multiple-argument lambda, let, let*, and d-lambda expressions.

Super Mondo Brainteaser!: Add to your interpreter a limited version of the fluid-let form, named flet, which uses the following "macro" expansion:

(flet ((x e)) body)

=>

(let ((t x))
  (begin
    (set! x e)
    (let ((v body))
      (begin
        (set! x t)
        v))))

In order to implement flet, you will need to add both set! and begin to your interpreter. Once you have done so, the following tests should pass:

(define flet-1
  '(let ((x 3))
     (let ((f (lambda () x)))
       (flet ((x 4))
         (f)))))

(define flet-2
  '(let ((x 3))
     (let ((f (lambda () x)))
       (let ((x 5))
         (flet ((x 4))
           (f))))))

(test "flet-1"
  (value-of flet-1 (empty-env))
  4)

(test "flet-2"
  (value-of flet-2 (empty-env))
  3)

Assignment 4 - Representation Independence and Dynamic Scope

This assignment comprises three parts.

Part I:

Part II:

Part III:

A complete, detailed description of this process will be between a quarter of a page and half a page in length.

If your description is not detailed enough, or is significantly flawed, you will be asked to orally explain how the interpreter works to either Ramana or Will.

Place your code from Parts I and II (including any test programs), and your description from Part II, in a file named a4.scm and submit it to Vincent. Comment-out your description using semi-colons (;), so that your file loads under Chez.

**A complete, detailed description of this process will be between a quarter of a page and half a page in length.**

Place your code from Parts I and II (including any test programs), and your description from Part II, in a file named `a4.scm` and submit it to Vincent. Comment-out your description using semi-colons (`;`), so that your file loads under Chez.