QUIZ #4 SOLUTIONS

1. implementation of thunks in the lazy evaluator

PART I

Why shouldn't the lazy evaluator implement thunks by transforming them into
above-the-line, meta-Scheme lambdas?

First, Louis's version of actual-value won't perform repeated forcings, so
it won't work on expressions that have been delayed multiple times.

Second, Louis's version of actual-value could try to force things that
aren't thunks.


There are, however, some deeper issues involved.  Why does it force some
things too many times and other things not enough times?  Is it possible to
rewrite actual-value (or force-it) to do the Right Thing, given Louis's
implementation of thunks?

The short answer:

The problem is that we can't mix automatic, below-the-line thunks (those
created automatically when invoking compound procedures) with
user-controlled, above-the-line thunks (those created explicitly using
lambda or delay).

When the lazy evaluator needs to return a value to the user, it
automatically forces any thunks necessary.  Suppose we create a thunk
explicitly using lambda.  Should the lazy evaluator force it automatically?


The long-winded answer:

The underlying system must be able to distinguish between a user-defined
procedure of no arguments and a thunk.  Unless thunks are given some
special representation from the perspective of the underlying system, it is
impossible to make this distinction.

Why is this distinction important?  Consider:

(define (identity x) x)

Now consider what happens when we try:

(identity (lambda () 'foo))

This SHOULD return a procedure of no arguments that returns the symbol FOO.

The lazy evaluator has to delay all arguments to compound procedure calls.
How should it treat the lambda?  Suppose we delay it, as usual.  With
Louis's changes, this would create a thunk that is equivalent to:

(lambda () (lambda () 'foo))

Now what?  When we need to print the result, we must force this thunk by
invoking it.  This, however, produces another procedure of no arguments.
Is this a thunk?  Should we force it again?

The reason we're unsure is because if we always delay arguments to compound
procedures, then compound procedures that call other compound procedures
risk delaying things multiple times.  Can we remedy this by making sure we
never delay anything more than once?  A plausible change would be to check
first if an argument is already a thunk; if it is, don't do anything; if it
isn't, delay it.  This, however, has the same problems as before!  How can
we even check if an argument is a thunk in the first place?

To make this more concrete, let's go back to the previous example:

(identity (lambda () 'foo))

If we choose NOT to delay evaluation of the lambda expression, when the
identity function ultimately returns (lambda () 'foo) as a result, how do
we know whether to force it or not?  Can we distinguish it from the result
of (identity (identity 'foo)) ?

We can't, so Louis's plan fails, as usual.


These issues are fairly subtle, so if you hadn't thought about this
beforehand the problem was hard.  I probably should have given a hint to
nudge everyone in the right direction, but I hope this problem made
everyone really think about the rationale behind the design of the lazy
evaluator.

A number of creative people incorrectly thought Louis's plan would fail
because the arguments would end up being prematurely evaluated.  This is
not the case, because procedures that form derived expressions (e.g.,
cond->if, let->combination) do not evaluate; they merely take an
expression--a list from the perspective of the underlying system--and
rewrite it to form a new list.)


PART II

We must store the environment a thunk is created in, because if the thunk
contains variables, we need to know in which environment to look up their
values.  For example:

(define x 0)
(define (foo y)
  (define x 1)
  (+ x y))

Now consider what happens when we try:

(foo x)

This SHOULD be equivalent to (foo 0), which would return 1.

Since arguments to compound procedures get delayed, when we invoke foo, y
is bound to <thunk x>.

So now when we try to evaluate (+ x y), we look up the bindings for x and
y, which results in:

(+ 1 <thunk x>)

Since we must force all arguments to primitive procedure calls, we end up
with:

(+ 1 x)

What's x?  If we try looking it up in the current environment, we'll
incorrectly find that x is 1 instead of its global value 0.  In order to
determine in which environment we need to look up x, we must store the
environment whenever we create a thunk.

(When we were dealing with delay and force in week 11, why didn't we need
to worry about these environments?)



2. depth

Here's the answer I was expecting:

(define (depth struct)
  (if (not (pair? struct))
      0
      (max (+ 1 (depth (car struct)))
           (depth (cdr struct)) ) ))

A number of people tried things like:

...
(+ (depth (car struct))
   (depth (cdr struct)) )
...

But this is wrong, because branches have independent depths.  It doesn't
make sense to find the maximum depth along one branch and to add it with
the maximum depth along another branch.

A few people tried:

...
(+ 1 (max (depth (car struct))
          (depth (cdr struct)) ))

Which is close, but it isn't quite correct.  We only "go deeper" when an
ELEMENT of a list--the car--is another list, NOT when the cdr is a list.
(Since trees are represented as lists in this problem, the cdr will ALWAYS
be a list!) Thus, for example, this would cause (depth '(a b c d e))
incorrectly to return 5.

(Note that the the incorrect version above WOULD work if we were dealing
with binary trees, where each node is merely a pair of branches instead of
a list.)

One student came up with a clever answer:

(define (depth struct)
  (if (not (pair? struct))
      0
      (+ 1 (apply max (map depth struct))) ))


Expect a tree-recursion question on the final.  So far, all of you have
escaped tree-recursion problems on the midterms (with the exceptions of
count-change and ring-print, but neither asked you to write code from
scratch), so be ready.



3. special forms

PART I

Only two people correctly identified all the special forms.

I didn't intend for this problem to be about memorization; I don't care if
you happen to remember if cons-stream is a special form or not.  What is
more important is that you can figure out and understand which operators
require special evaluation rules.

The following are special forms, along with their reasons:

BEGIN
  We must evaluate the arguments to begin sequentially in left-to-right
  order.  Ordinary procedures do not have a specified evaluation order for
  arguments.

COND
  cond expressions have special structures; each clause is of the form

    (<predicate> <exp1> <exp2> ... <expN>)

  This does NOT mean we want to pass <exp1> <exp2> ... <expN> as arguments
  to the result of the predicate. (see also IF)

CONS-STREAM
  We need to delay evaluation of the second argument.

DEFINE
  It makes no sense to evaluate the variable name.

DELAY
  We explicitly do not want to evaluate the argument; this is the whole
  point of delay.

IF
  We must conditionally evaluate either the consequent expression or the
  alternative expression based on the predicate.  We do not wish to
  evaluate both.

LAMBDA
  We never evaluate the parameters, which are only used to create bindings.
  We only evaluate the body when the resulting procedure is INVOKED.

LET
  let expressions have special structures.

    (let ((x 1))
      <body>)

  This does NOT mean that we are invoking a procedure x with the argument 1
  and then invoking the result with no arguments.  Furthermore, the body
  cannot be evaluated until after the bindings are created.

QUOTE
  (quote x) should return the symbol x; it should not evaluate x.

SET!
  (see DEFINE)

Of course, the above list is NOT complete.  There are numerous other
special forms.


Remember, almost all of the cond clauses in mc-eval are checks for special
forms!  Any special form implemented in meta-Scheme MUST be handled
specially by mc-eval.  Anything that requires special evaluation rules MUST
be a special form.

Also remember that primitive procedures are NOT the same as special forms.


The following are NOT special forms.  Each evaluates all of its arguments
in the usual fashion:

CONS, CAR, CDR
  These are typically primitive procedures.  However, recall that we can
  implement cons, car, and cdr using message-passing procedures.

SET-CAR!, SET-CDR!
  To execute (set-car! x 1), we must look up the value of x to find the
  corresponding memory structure. From there, we can perform the desired
  mutation.

  These must be primitive procedures, because otherwise we would have no
  way of mutating structures in memory.

EQ?
  This must be a primitive procedure, as otherwise we would have no way to
  compare memory pointers.

FORCE
  We WANT to evaluate thunks.  This can be accomplished with a user-defined
  procedure:

  (define (force thunk) (thunk))

STREAM-CAR, STREAM-CDR
  These can be user-defined in terms of car, cdr, and force.

EVAL, APPLY
  These must be primitive procedures. (This is analogous to how mc-eval and
  mc-apply perform the roles of eval and apply in meta-Scheme, but they're
  implemented in the underlying Scheme system.)


I neglected to ask about AND, OR, and NOT.  Which of them are special
forms?


PART II

begin evaluates each of its arguments sequentially, in left-to-right order,
and it returns the value of the last expression.