Assignment 3: Environments and Interpreters

It (the computer) is a medium that can dynamically simulate the details of any other medium, including media that cannot exist physically. It is not a tool, although it can act like many tools.

This assignment is due at 11:59 p.m. on Tuesday, February 2 (not on Monday as usual).

In the next two lectures, you'll see how to write an interpreter, value-of, that takes a Scheme expression and returns the result of evaluating that expression. Your task for this assignment is to implement the interpreter presented in lecture, along with the helper procedures for environments. Place all of your code in a file named a3.scm and submit it to Vincent.

Please read the following instructions carefully:

• 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.
• 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.
• Your code must pass the following three 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)

Here is rembersum*even, with its helpers base, stuff, and grow. rembersum*even takes a nested list ls of values, removes all of the even numbers, and returns a sum of the even numbers in a pair with the new nested list. For example:

> (rembersum*even '(5 (((7)) 9) 11))
(0 5 (((7)) 9) 11)
> (rembersum*even  '(2 3 (8 (c 6 7) 4 8 #t) 8 () 2 9))
(38 3 ((c 7) #t) () 9)

Complete the definition of grow so that rembersum*even works properly, and include all four definitions in the file you turn in.

(define base
  (lambda (t)
    `(0 . ,t)))
 
(define stuff
  (lambda (w)
    `(,w . macht-nicht)))
 
(define grow
  (lambda (f)
    (lambda (c)
      (let ((c^ _____))
        __________))))
 
(define rembersum*even
  (lambda (ls)
    (cond
      [(null? ls) (base '())]
      [(pair? (car ls))
       ((grow (lambda (a) ((grow (lambda (d) (base (cons a d)))) (rembersum*even (cdr ls)))))
        (rembersum*even (car ls)))]
      [(and (number? (car ls)) (even? (car ls)))
       ((grow (lambda (__) (rembersum*even (cdr ls)))) (stuff (car ls)))]
      [else ((grow (lambda (d) (base (cons (car ls) d)))) (rembersum*even (cdr ls)))])))

Change the behavior of rembersum*even so that it returns a pair with a flat list of the even numbers it removes. Do this by changing only the definitions of base, stuff, and grow. Name the new procedure remberlist*even. For example:

> (remberlist*even '(5 (((7)) 9) 11))
(() 5 (((7)) 9) 11)
> (remberlist*even  '(2 3 (8 (5 6 7) 4 8 7) 8 () 2 9))
((2 8 6 4 8 8 2) 3 ((5 7) 7) () 9)