This is an optional Lab X assignment.

The goal of this assignment is to develop a program that evaluates programs. This demonstrates that not only are we program designers, but also programming language designers.

Go forth and design beautiful languages.

---

Problem X1: cond

Extend the meta-circular evaluator (eval.scm) to handle cond expressions.

Note that

   (cond [question answer])

is equivalent to

   (if question 
       answer 
       (error 'cond "all question results were false"))

and

   (cond [else answer])

is equivalent to

   answer

and

   (cond [question1 answer1] 
         [question2 answer2] 
         ... 
         [questionN answerN])

is equivalent to

   (if question1 
       answer1 
       (cond [question2 answer2] 
             ... 
             [questionN answerN])

Problem X2: Lazy evaluation

With lazy evaluation (sometimes called "normal order evaluation"), we fully embrace the college student mindset: Don't do anything until we absolutely have to, that is, we delay the computation of everything we can.

Delaying means the construction of a thunk: a data object having (unevaluated) code, and an environment in which it is to be (later) evaluated. (When have we done this before?!)

When a user-defined procedure (closure) is applied, we bind each parameter to a thunk instead of binding it to a value.

Procrastination stops at the following points:

Applying procedures: You can't apply a thunk---you need to force its evaluation so you get a procedure to apply.

Applying primitive procedures: You can't add two thunks, or take the first of one. What about cons? (A design decision.)

Conditionals: When evaluating an if expression, a thunk isn't good enough--- you need to evaluate the test to see if it is true or false.

Thunks can be represented as follows:

   (define-struct thunk (exp env))

A Thunk is a (make-thunk Expression Environment).

Our evaluator can now return values or delayed computations. Let's call the union of these two data definitions a Suspend:

   ;; A Suspend is one of:
   ;;  - a Value
   ;;  - a Thunk

The fundamental operations we need will be:

   ;; force-it : Suspend -> Value
   ;; Stop procrastinating and just do it.
   (define (force-it obj)
      (cond [(thunk? obj)
             (actual-value
               (thunk-exp obj)
               (thunk-env obj))]
            [else obj]))

   ;; actual-value : Expression Environment -> Value
   ;; Evaluate the expression (which can result in a thunk),
   ;; then force the possible suspended computation.
   (define (actual-value exp env)
      (force-it (ev exp env)))

We will need to change the data definitions and contracts of our existing procedures in the following way:

   ;; A Binding is (list Variable Suspend)

   ;; lookup : Variable Environment -> Suspend

   ;; extend-env : [Listof Symbol] [Listof Suspend] Environment -> Environment

   ;; ev : Expression Environment -> Suspend

   ;; app : Closure [Listof Thunk] -> Suspend

The actual code for lookup and extend-env doesn't need to change.

Modify the env and app procedures to realize a Lazy Scheme programming language.

Notice that in Eager Scheme (the Scheme we know and love), you can't define your own myif procedure that works like a conditional:

   (define (myif test conseq alt)
     (cond [test conseq]
           [else alt]))

Explain why not. Could we get away with this sort of thing in a Lazy Scheme? Why or why not?