Assignment 3: Environments and Interpreters

Implement the interpreter presented in lecture, along with the helper procedures for environments.

You must define two sets of environment helpers: one that uses higher-order (functional) representation of environments, and one that uses data structural representation of environments.

Your interpreter must handle the following Scheme expressions: booleans, numbers, variables, lambda, application, let, zero?, sub1, *, and if.

let does half the work of lambda, and you may have seen the expansion of (let ((x e)) body) as ((lambda (x) body) e). However, when you have a handle on the environment, you can implement let in its own right. Therefore you must not use lambda or anything that behaves like lambda in your interpreter's line for let expressions.

For the pattern matching to work correctly, your application line should come last.

Place all of your code in a file named a3.scm and submit it to Vincent.

Your code must pass these test cases. Of course, these tests are not exhaustive; you must add your own tests as well. Remember to place the definition of the test macro at the top of your file.

(define-syntax test
  (syntax-rules ()
    ((_ title tested-expression expected-result)
     (let* ((expected expected-result)
            (produced tested-expression))
       (if (equal? expected produced)
           (printf "~s works!\n" title)
           (error
            'test
            "Failed ~s: ~a\nExpected: ~a\nComputed: ~a"
            title 'tested-expression expected produced))))))
  
(test "let-a"
  (value-of
   '(let ([y (* 3 4)])
      ((lambda (x) (* x y)) (sub1 6)))
   (empty-env))
  60)

(test "let-b"
  (value-of
   '(let ([x (* 2 3)])
      (let ([y (sub1 x)])
        (* x y)))
   (empty-env))
  30)

(test "let-c"
  (value-of
   '(let ([x (* 2 3)])
      (let ([x (sub1 x)])
        (* x x)))
   (empty-env))
  25)

Brainteaser (Extra Credit, Hard!):

Brainteaser (Extra Credit, Ultra Mega Hard!):