% for yTeX
%\typesize=11pt
%\hsize=34pc
%\vsize=50pc
\parskip 6pt plus 2pt

\def\fbox#1{%
  \vtop{\vbox{\hrule%
              \hbox{\vrule\kern3pt%
                    \vtop{\vbox{\kern3pt#1}\kern3pt}%
                    \kern3pt\vrule}}%
        \hrule}}
\def\emptybox#1#2{\fbox{\vbox to #2{\hbox to #1 {\null}}}}

\def\psetheader{
\centerline{MASSACHUSETTS INSTITUTE OF TECHNOLOGY}
\centerline{Department of Electrical Engineering and Computer Science}
\centerline{6.001 Structure and Interpretation of Computer Programs}
\centerline{Spring Semester, 1989}}

%\rectoleftheader={6.001 -- Spring Semester 1989}
%\rectorightheader={Recitation -- May 17}
%\onheaders
%\onfooters

\psetheader
\begin{document}

\centerline{\bf Review}

(1) Consider the following simple heap structure:

\centerline{\begintable [l|c|c|c|c|c|c|c|c|]
Address&&0&&1&&2&&3&&4&&5&&6&&7&\cr
\midline
the-cars&&P3&&P5&&N3&&P0&&P7&&N1&&N4&&N2&\cr
\midline
the-cdrs&&P2&&P2&&P4&&P6&&E0&&P7&&N2&&E0&\cr
\botline
\endtable}

Suppose that the ROOT register contains the pointer P1.  

A.  Draw a more conventional box and pointer representation of the
list structure  pointed to by ROOT.

\emptybox{33pc}{2in}

B.  What is the printed representation for the contents of ROOT?

\emptybox{33pc}{.5in}


C. Which cells are free to be garbage collected?

\emptybox{33pc}{.5in}

(2) Consider the following sequence of expressions.

\beginlisp
(define sum 0)
\pbrk
(define (accum x)
  (set! sum (+ x sum))
  sum)
\pbrk
(define seq (map accum (enumerate-interval 1 20)))
\pbrk
(define y (filter even? seq))
\pbrk
(nth-stream 2 y)
\endlisp


What is the value of {\tt sum} after each of the above expressions is
evaluated?  What is the printed response to evaluating the {\tt
nth-stream} expression?  Would these responses have been different if
we had implemented {\tt (delay {\it exp})} simply as {\tt (lambda ()
{\it exp})} without using memoization?  Explain.

\emptybox{33pc}{2in}

(3) When the Scheme interpreter evaluates the primitive Scheme
procedure {\tt AND}, first it evaluates all of the operands, and then
it applies the {\tt AND} procedure to the values of the operands.  If
the values of all the operands are ture, {\tt AND} returns true,
otherwise it returns false.  This can be inefficient, since if the
value of any operand is false, there is no need to evaluate the
remaining ones.  We can implement a new procedure called {\tt
FAST-AND}, a procedure of two arguments, that has the following
behaviour.  First, the first operand is evaluated.  If its value is
false, then {\tt NIL} is returned as the value of {\tt FAST-AND}.
Otherwise, the second operand is evaluated and the value obtained by
this evaluation is returned as the value of the entire procedure.

Alyssa P. Hacker notes that this  means writing
\beginlisp
(fast-and f g)
\endlisp
should be equivalent to writing
\beginlisp
(if f g nil)
\endlisp

Louis Reasoner proposes the following definition.
\beginlisp
(define (fast-and a1 a2)
  (if a1 a2 nil))
\endlisp
His colleagues quickly point out that this will still result in both
operands always being evaluated.  Ben Bitdiddle offers the following
example to prove this point.
\beginlisp
(define a 2)
\pbrk
(fast-and (not (atom? a)) (car a))
\endlisp
Given Louis's proposed definition, explain what will happen when Ben's
code is evaluated. 

\emptybox{33pc}{1in}

Ben says that Louis's idea can still be salvaged.  In particular, Ben
says that we could rewrite {\tt fast-and} such that it would be used
as follows:
\beginlisp
(fast-and (lambda () f) (lambda () g))
\endlisp
What is the actual definition of {\tt fast-and} that will make this
work in the way we described?
\beginlisp
(define (fast-and a1 a2)
\endlisp

\emptybox{33pc}{1in}

Alyssa says that this is a neat idea, but that it is very cumbersome
to use.  She claims it is a better idea to build {\tt fast-and} as a
special form in the evaluator.

To do this, we first build a data abstraction for recognizing and
manipulating expressions involving {\tt fast-and}.   This means we
will need a predicate called {\tt fast-and?}, which tests whether an
expression starts with the symbol {\tt fast-and}.  We will also need
two selectors, {\tt first-conjunct} and {\tt second-conjunct}, which
when given a {\tt fast-and} expression will select the first and
second conjuncts respectively.  Given this data abstraction, we can
then just add a conditional clause to the meta-circular evaluator:
\beginlisp
(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ...
        ((fast-and? exp) (eval-fast-and (first-conjunct exp) 
                                        (second-conjunct exp)
                                        env))
        ((application? exp) (apply (eval (operator exp) env)
                                   (list-of-values (operands exp) env)))
        (else (error "Unknown expression type -- EVAL" exp))))
\endlisp
What should the definition of the {\tt fast-and?} predicate be?

\emptybox{33pc}{1in}

Define the two selectors, {\tt first-conjunct} and {\tt second-conjunct}.

\emptybox{33pc}{1.5in}

Complete the following
\beginlisp
(define (eval-fast-and a1 a2 env)
\endlisp
\emptybox{33pc}{1.5in}

We can also add {\tt fast-and} to our explicit-control evaluator.  We
first add a clause to the evaluator dispatch
\beginlisp
eval-dispatch
  (branch (self-evaluating? (fetch exp)) ev-self-eval
  ...
  (branch (fast-and? (fetch exp)) ev-and)
  (branch (application? (fetch exp)) ev-application)
  (goto unknown-expression-type-error)
\endlisp

{\tt EV-AND} presumes that the {\tt EXP} register holds the expression
to be evaluated, and the {\tt ENV} register holds the current
environment pointer.

The key is to write register machine code to implement {\tt FAST-AND}
starting at the label {\tt EV-AND}.  Fill in the missing spots.
\beginlisp
1. ev-and
2.   (assign unev \emptybox{3in}{10pt})
3.   (assign exp \emptybox{3in}{10pt})
4.   (save continue)
5.   (save env)
6.   (save unev)
7.   (assign continue eval-after-first)
8.   (goto \emptybox{3in}{10pt})
9. eval-after-first
10.  (restore \emptybox{3in}{10pt})
11.  (restore \emptybox{3in}{10pt})
12.  (branch (true? (fetch val)) eval-second-arg)
13.  (assign val '())
14.  (restore \emptybox{3in}{10pt})
15.  (goto (fetch continue))
16. eval-second-arg
17.  (assign exp \emptybox{3in}{10pt})
18.  (assign continue after-second)
19.  (goto \emptybox{3in}{10pt})
20. after-second
21.  \emptybox{3in}{10pt}
22.  (goto (fetch continue))
\endlisp

Alyssa mutters that this will work but it violates the nice notion of
tail recursion.  She claims that we can fix this so that our {\tt
fast-and} code will display tail recursion if we dro p4 lines of code
and add one new line of code.

What four lines of code should be dropped?

\emptybox{33pc}{.25in}

What is the new line of code to be added, and where should it be added?

\emptybox{33pc}{.25in}

Ben points out that we didn't have to add an instruction above, we
could have just moved an existing instruction.
Which line should we move and where should we move it to?

\emptybox{33pc}{.25in}

Could we remove line 13 without changing the value returned by the
code?  Why or why not?

\emptybox{33pc}{.25in}

\end
\end{document}
