% -*- Mode: Tex -*-

%\input /home/welg/6001mac.tex
%\input /homes/welg/6001/6001mac.tex
%\input /zu/scheme/6001ARCHIVE/fall89/6001mac.tex
\input ./6001mac.tex

{\obeyspaces\gdef {\ }}

\def\brule#1{\vrule width#1 height -1.1pt depth 1.5pt\relax}

\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\pscenter#1{\hbox to\hsize{\hss\psadobenomag{#1}\hss}}

\setlength{\textheight}{9.2in}

\begin{document}

\psetheader{Spring Semester, 1998}{Recitation -- Friday, May 1}

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

{\Large\bf 1. Student Presentation}

Please briefly summarize the contracts for Eval and Apply in the
Explicit Control Evaluator. If possible, explain why the contents of
the Continue register are left on the stack when setting up the
dispatch to Apply.

\vskip .08in

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

{\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 self-evaluating?) (reg exp)) 
  (branch (label ev-self-eval))
  ...
  (test (op and?) (reg exp))
  (branch (label ev-and))
  (test (op application?) (reg exp)) 
  (branch (label ev-application))
  (goto unknown-expression-type-error)
\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 \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.  (test (op true?) (reg val)) 
13.  (branch (label eval-second-arg))
14.  (assign val \#f)
15.  (restore \emptybox{3in}{10pt})
16.  (goto (reg continue))
17. eval-second-arg
18.  (assign exp \emptybox{3in}{10pt})
19.  (assign continue after-second)
20.  (goto \emptybox{3in}{10pt})
21. after-second
22.  \emptybox{3in}{10pt}
23.  (goto (reg continue))
\endlisp

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.  \emptybox{3in}{10pt}
% (restore continue)
20.  \emptybox{3in}{10pt}
% (goto (label eval-dispatch))
\endlisp

\vspace{0.1in}

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

\emptybox{33pc}{.25in}

\vspace{0.1in}

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

\emptybox{33pc}{.25in}

\vspace{0.1in}

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

\emptybox{33pc}{.25in}

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

\end{document}
