% -*- Mode: Tex -*-

\def\AnswerSheet{1}

\input 6001mac.tex

\begin{document}

\psetheader{Spring Semester, 1999}{Recitation -- Wednesday, April 28}

{\Large\bf 1. Explicit Control Evaluator: The Important Contracts}

{\footnotesize
\begin{tabular}{|p{1in}|p{2.7in}|p{2.5in}|}
Function & Assumption & Promise \\
\hline
eval-dispatch 
& 
Expression in EXP, Environment in ENV, continuation in CONT
& 
End up at CONT with result in VAL
\\
\hline
apply-dispatch
&
Procedure in PROC, list of arguments in ARGL, continuation at the top
of the stack.
&
End up at CONT with result in VAL and the stack popped
\\
\hline
eval-sequence 
& 
Sequence of expressions in UNEV, Environment in ENV, continuation at
the top of the stack.
& 
Evaluate the expressions in sequence, and end up at CONT with result
of the final expression in VAL and the stack popped. \\
\hline
\end{tabular}
}

{\Large\bf 2. Adding AND to the Explicit Control Evaluator}

We can also add {\tt and} to our explicit-control evaluator.  We
first add a clause to the evaluator dispatch

\beginlisp
eval-dispatch
  ...
  (test (op and?) (reg exp))
  (branch (label ev-and))
  ...
\endlisp

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

The key is to write register machine code to implement {\tt AND}
starting at the label {\tt EV-AND}.  Fill in the missing spots.
Assume we've got the primitives {\tt first-conjunct} and {\tt
second-conjunct}.

\beginlisp
1. ev-and
2.   (assign unev \ANSWERISR{(op second-conjunct) (reg exp)}{\emptybox{3in}{10pt}})
3.   (assign exp \ANSWERISR{(op first-conjunct) (reg exp)}{\emptybox{3in}{10pt}})
4.   (save continue)
5.   (save env)
6.   (save unev)
7.   (assign continue eval-after-first)
8.   (goto \ANSWERISR{(label eval-dispatch)}{\emptybox{3in}{10pt}})
9. eval-after-first
10.  (restore \ANSWERISR{unev}{\emptybox{3in}{10pt}})
11.  (restore \ANSWERISR{env}{\emptybox{3in}{10pt}})
12.  (test (op true?) (reg val)) 
13.  (branch (label eval-second-arg))
14.  (assign val \#f)
15.  (restore \ANSWERISR{continue}{\emptybox{3in}{10pt}})
16.  (goto (reg continue))
17. eval-second-arg
18.  (assign exp \ANSWERISR{(reg unev)}{\emptybox{3in}{10pt}})
19.  (assign continue after-second)
20.  (goto \ANSWERISR{(label eval-dispatch)}{\emptybox{3in}{10pt}})
21. after-second
22.  \ANSWERISR{(restore continue)}{\emptybox{3in}{10pt}}
23.  (goto (reg continue))
\endlisp

\newpage
{\Large\bf 3. Tail Recursion}

Does this {\tt ev-and} routine handle tail recursion?  For example,
consider the scheme code below.  What result (if any) do we get when
we evaluate {\tt (list? x)} in our regular scheme?  How about a scheme
built on top of the above explicit-control evaluator?

\beginlisp
(define (list? x)
  (or (null? x)
      (and (pair? x) (list? (cdr x)))))

(define z (list 1))
(set-cdr! z z)

(list? z)
\endlisp

\vspace{0.1in}

To see how this is working, let's evaluate the expression
{\tt (and \#t (and \#f \#t))}.

\emptybox{6.5in}{3in}

\vspace{0.1in}

How could we change the code above so that it handles tail-recursion?
Hint: remove lines 19 through 23 and add two lines in their place.

\beginlisp
19.  \ANSWERISR{(restore continue)}{\emptybox{3in}{10pt}}
20.  \ANSWERISR{(goto (label eval-dispatch))}{\emptybox{3in}{10pt}}

\endlisp

\vspace{0.1in}

Can we get rid of the new line 19 by moving another line somewhere?

\ANSWERISR{Move line 15 after line 11}{\emptybox{33pc}{.25in}}

\vspace{0.1in}

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

\ANSWERISR{Yes, if true? is defined as anything that is not \#f}{\emptybox{33pc}{.25in}}

\vspace{0.1in}

How can we get rid of line 18 by changing another line?

\ANSWERISR{Change line 10 to (restore exp)}{\emptybox{33pc}{.25in}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
