Write a meta circular interpreter for the core of Proto.  In
particular, it must handle a simplified version of proto including:

  SPECIAL FORMS

    QUOTE   (QUOTE ,value)
    IF      (IF ,test ,then ,else)
    SEQ     (SEQ ,@forms)
    FUN     (FUN ,sig ,@body)
    LET     (LET ((,name ,value) ...) ,@body)
    LOC     (LOC ((,name (,name ...) ,@body) ...) ,@body)
    LAB     (LAB ,name ,@body)
    FIN     (FIN ,protected-form ,@cleanup-forms)
    DV      (DV ,name ,value)
    SET     (SET ,name ,value)

  CALLS

    call    (,form ,@args)

  LITERALS

    literal ,value

You can use the full language of Proto (as defined in Proto's doc) in
writing the interpreter.  The source for the runtime libraries is also
available on our course website.  You can also use the following
implementation of environments:

  (dv <frame> <assocs>)

  (dv <env> (isa <any>))
    (slot <env> (env-next <env>))  
    (slot <env> (env-frame <frame>) (isa <frame>))  

  (dv $empty-env (isa <env>))

  (dm env-define-binding! ((env <env>) (name <sym>) (value <any>))
    (set (elt (env-frame env) name) value))

  (dm env-extend! ((env <env>) (names <lst>) (values <lst>) => <frame>)
    (let ((new-env (isa <env> (set env-next env))))
      (do2 (fun (name value) (set (elt (env-frame new-env) name) value))
           names values)
      new-env))

  (dm env-binding-value ((env <env>) (name <sym>) => <any>)
    (if (== env $empty-env)
        nul
        (let ((value (elt (env-frame env) name)))
          (if (== value nul)
              (env-binding-value (env-next env) name)
              value))))

  (dm env-binding-value-setter ((value <any>) (env <env>) (name <sym>))
    (if (== env $empty-env)
        nul
        (if (== (elt (env-frame env) name) nul)
            (set (env-binding-value (env-next env) name) value)
            (set (elt (env-frame env) name) value))))

and the following functions for picking apart sexpressions:

  (dm sexpr-if-test ((exp <lst>) => <any>)
    (2nd exp))

  (dm sexpr-if-then ((exp <lst>) => <any>)
    (3rd exp))

  (dm sexpr-if-else ((exp <lst>) => <any>)
    (if (empty? (tail (tail (tail exp))))
        #f
        (head (tail (tail (tail exp))))))

  (dm sexpr-begin-actions (begin-exp => <lst>)
    (tail begin-exp))

  (dm sexpr-variable-name ((exp <lst>) => <any>)
    (1st exp))

  (dm sexpr-variable-name (exp => <any>)
    exp)

  (dm sexpr-definition-variable ((defn <lst>) => <any>)
    (2nd defn))

  (dm sexpr-definition-value (defn => <any>)
    (3rd defn))

  (dm sexpr-assignment-variable ((assn <lst>) => <any>)
    (2nd assn))

  (dm sexpr-assignment-value ((assn <lst>) => <any>)
    (3rd assn))

  (dm sexpr-let-bound-variables ((let-exp <lst>) => <lst>)
    (map head (2nd let-exp)))

  (dm sexpr-let-values ((let-exp <lst>) => <lst>)
    (map 2nd (2nd let-exp)))

  (dv $sexpr-begin-tag 'seq)

  (dm sexpr-last-exp? ((seq <lst>) => <log>)
    (empty? (tail seq)))

  (dm sexpr-first-exp ((seq <lst>) => <any>)
    (head seq))

  (dm sexpr-rest-exps ((seq <lst>) => <lst>)
    (tail seq))

  (dm sexpr-let-values ((let-exp <lst>) => <lst>)
    (map 2nd (2nd let-exp)))

  (dm sexpr-let-body ((let-exp <lst>) => <any>)
    (tail (tail let-exp)))

  (dv $sexpr-method-tag 'fun)

  (dm sexpr-make-begin ((exp <lst>) => <lst>)
    (pair $sexpr-begin-tag exp))

  (dm sexpr-lab-name ((exp <lst>) => <any>)
    (2nd exp))

  (dm sexpr-lab-body ((exp <lst>) => <lst>)
    (tail (tail exp)))

  (dm sexpr-fin-protected-form ((exp <lst>) => <any>)
    (2nd exp))

  (dm sexpr-fin-cleanup-forms ((exp <lst>) => <any>)
    (tail (tail exp)))

  (dm sexpr-function-parameters (defn => <lst>)
    (3rd defn))

  (dm sexpr-function-body (defn => <any>)
    (tail (tail (tail defn))))


Your interpreter should also preseed its base environment with the
following primitives: pair, head, tail, empty?, +, -, <, =, and ==.
These primitives should be available to programs fed to your
interpreter.

Name your eval function evol in order to avoid collision with the
built-in eval function.

Your interpreter should be able to correctly reproduce these input
output pairs:

  1
    => 1
  #t
    => #t
  #f
    => #f
  '()
    => ()
  '(1)
    => (1)
  '1
    => 1
  (IF #t 1 2)
    => 1
  (IF #f 1 2)
    => 2
  (IF 0  1 2)
    => 1
  (SEQ)
    => #f
  (SEQ 1)
    => 1
  (SEQ 1 2)
    => 2
  (+ 1 2)
    => 3
  (- 1 2)
    => -1
  (> 1 2)
    => #f
  (= 1 1)
    => #t
  (LET ((x 1)) x)
    => 1
  (LET ((x 1) (y x)) y)
    => 1
  (LET ((x 0)) (SET x 1) x)
    => 1
  (LAB ret 1)
    => 1
  (LAB ret (ret 1) 2)
    => 1
  (FIN 1 2 3)
    => 1
  (LET ((x 0)) (LAB ret (FIN (ret 2) (SET x 1))) x)
    => 1
  (DV x 1)
    => #f
  (SEQ (DV x 1) x)
    => 1
  (SEQ (DV x 0) (SET x 1) x)
    => 1
  ((FUN () 1))
    => 1
  ((FUN (x) x) 1)
    => 1
  ((FUN (x y) (+ x y)) 1 2)
    => 3
  (LOC ((f (x) x)) (f 1))
    => 1
  (LOC ((f (x) (g x)) (g (y) y)) (f 1))
    => 1
  (LOC ((f (x) (if (< x 2) x (* x (f (- x 1)))))) (f 5))
    => 120
  (SEQ (DV c (FUN (x) (if (empty? x) x (pair (+ (head x) 1) (c (tail x))))))
       (c '(1 2 3)))
    => (2 3 4)

Feel free to ask questions by email at oodl-fac@ai.mit.edu or by
stopping by our office at room 802 the AI Lab (NE-43).  

There will probably be bugs in this early version of Proto so please
bear with us and definitely let us know what problems you run into.
Keep checking the web site:

  http://www.ai.mit.edu/projects/dynlangs/oodl-course/spring01/

for new versions of Proto and its documentation as we fix bugs and
fill out the documentation.

This assignment is due Thursday 22FEB01 before class.  Please email it
to us at: oodl-fac@ai.mit.edu.