% Document Type: LaTeX
\documentclass{article}

\usepackage{6001}

\usepackage{psfig}

\newcommand{\csfig}[2]  
{       \centering

         \leavevmode \epsfxsize=#1      \epsffile{#2}

%        \emptybox{1in}{1in}
}

\let\to\rightarrow
\let\union\cup
\let\cross\times
\def\SN{\mbox{Sch-\-Num}}
\def\SB{\mbox{Sch-Bool}}
\def\Empty{\mbox{Empty}}
\def\SI{\mbox{Sch-Int}}
\def\SNI{\mbox{Sch-Nonneg-Int}}

\def\fbox#1{%
  \vtop{\vbox{\hrule%
     \hbox{\vrule\kern3pt%
 \vtop{\vbox{\kern3pt#1}\kern3pt}%
 \kern3pt\vrule}}% 
 \hrule}}

\newcommand{\tlisp}[1]{\relax\ifmmode\mbox{\texttt{#1}}\else\texttt{#1}\fi}

\newcommand{\List}{\mathrm{List}}
\newcommand{\tree}{\mathrm{Tree}}

%\theoremstyle{definition}
%\newtheorem{exercise}{Exercise}

\begin{document}

\psetheader{Fall 1997}{Problem Set 8}

\medskip

\begin{flushleft}
Issued: Thursday, 13 November\\
\smallskip
Due: Friday, 21 November, in recitation.\\
\smallskip
Tutorial preparation for Week of 17 November:\\
Exercises 4.7, 4.13, 4.14, 4.27, and 4.32.\\
\smallskip
Reading: {\em SICP} Sections~4.1--4.1.6, 4.2, and attached code files {\tt
meval.scm}, {\tt evdata.scm}, and {\tt syntax.scm}.
\end{flushleft}

\medskip

\begin{center}\large
{\bf Evaluators for Extended Scheme}
\end{center}

\bigskip

You will be working with an evaluator for an extended version of Scheme as
described in {\em SICP}, Chapter 4.  Without a good understanding of how
the evaluator is structured, it is very easy to become confused between
the programs that the evaluator is interpreting, the procedures that
implement the evaluator itself, and Scheme procedures called by the
evaluator.  You will need to study Chapter 4 through subsection 4.2.2
carefully in order to do this assignment.

\section{Using the Evaluator}

The code for this Problem Set includes these files:
\begin{itemize}

\item {\tt meval.scm} is the so-called ``metacircular'' evaluator
described in Section 4.1.1 of {\em SICP}.  It has been extended to allow
declarations of lazy procedure parameters, as described in Section 4.2.2
and {\em SICP} Exercise 4.31.  In order to avoid confusing the {\tt eval}
and {\tt apply} of this evaluator with the {\tt eval} and {\tt apply} of
the underlying Scheme system, we have renamed the evaluator procedures
{\tt meval} and {\tt m-apply}.

\item {\tt evdata.scm} contains the procedures that define the
evaluator's data structures.  Note that although the definitions in this
file are very similar to those Section 4.1.3, they are not exactly the
same.

\item {\tt syntax.scm} contains the procedures that define the syntax
of expressions.    Note that although the definitions in this
file are very similar to those Section 4.1.2, they are not exactly the
same.

\end{itemize}


Here's how to use the extended evaluator:

\begin{itemize}

\item To start up, do 
\begin{lisp}
M-x load-problem-set: 8
\end{lisp}
in Edwin.  This loads the files {\tt syntax.scm}, {\tt evdata.scm},
and {\tt meval.scm}.  Then evaluate
\Code{(start-meval)} in Scheme; this starts the read-eval-print loop
for the meta-circular evaluator with a freshly initialized global
environment.

\item To evaluate an expression, you may type the expression into the
\Code{*scheme*} buffer followed by {\tt ctrl-x ctrl-e}.  (Don't use
{\tt M-z} to evaluate the expression in the \Code{*scheme*}
buffer---the presence of the evaluator prompts confuses the {\tt M-z}
mechanism.  But {\tt M-z} works fine for sending expressions to the
\Code{*scheme*} buffer from other Scheme-mode buffers.)

For example,

\begin{lisp}
MEVAL=> (+ 3 4)
;;M-value: 7
\end{lisp}
shows an interaction with the {\tt meval} evaluator.

\item
It will be helpful to keep separate files of procedure definitions you
want to run the evaluator on.  When your Edwin Scheme buffer is running
the {\tt meval} read-eval-print loop, you can then visit this file and
type {\tt M-o} to have the definitions evaluated by {\tt meval}.

\item You can interrupt {\tt meval} by typing {\tt ctrl-c ctrl-c}.
To restart it with the recent definitions still intact, evaluate {\tt
(eval-loop)}.

\item The {\tt meval} evaluator does not include much of an error system.
If you hit an error you will bounce back into ordinary Scheme.  You can
restart the current evaluator, with its global environment still intact,
by evaluating {\tt (eval-loop)}.

\item It can be instructive to trace {\tt m-eval} and/or {\tt
m-apply} during evaluator executions.  (You will also probably need to do
this while debugging your code for this assignment.)

\item  Since environments are generally complex, circular list
structures, we have set Scheme's printer so that it will not go into
an infinite loop when asked to print a circular list.  This was done by
\begin{lisp}
(set! *unparser-list-depth-limit* 7)
(set! *unparser-list-breadth-limit* 10)
\end{lisp}
at the end of the file {\tt evdata.scm}.  You may want to alter the
values of these limits to vary how much list structure will be printed as
output.

\end{itemize}


\section{Lab Work}

{\bf Lab exercise 1:}

{\bf 1A:} Start the \Code{meval} evaluator and evaluate a few simple
expressions and definitions.  It's a good idea to make an intentional
error and practice restarting the read-eval-print loop.  Notice that we
have already installed {\tt let} in the evaluator, so you can use this in
your programs.

{\bf 1B:} Now trace evaluation of the application of some simple procedure
to some argument.

\medskip

Read the definition of {\tt or} on page 19 of {\em SICP}.  Note that the
{\tt or} special form is not implemented in {\tt meval}.

\paragraph{Lab Exercise 2:}
Demonstrate how, using {\tt lazy} parameters, you can define {\em
three}-argument {\tt or} as a {\em procedure}.  Turn in the definition of
your {\tt or} procedure together with some test examples to show that it
works as required.

\paragraph{Lab Exercise 3:}
Define an {\tt or->desugared} procedure which transforms an arbitrary {\tt or}
expression, which may have a varying number of arguments as in real
Scheme, into an equivalent expression which {\tt meval} can handle.  Using
this procedure, extend {\tt meval} so {\tt or} is implemented as a derived
expression, i.e., as ``syntactic sugar.''

\medskip
{\bf Lab Exercise 4:}

{\bf PreLab 4A:} Notice that the {\tt initial-environment} procedure in
{\tt evdata.scm} binds the evaluator's variable {\tt pair?} to a special
{\tt mpair?} procedure.  Give an example of what would go wrong if the
evaluator's variable {\tt pair?} was bound to Scheme's built-in {\tt
pair?} procedure.

{\bf 4B:} {\bf Temporarily} modify {\tt initial-environment} so the
evaluator's variable {\tt pair?} is bound to to Scheme's built-in {\tt
pair?} procedure, and run the evaluator on your example.
Now restore the original definition of {\tt initial-environment} and
demonstrate that your example is handled correctly.

{\bf 4C:}  Define a predicate {\tt mproc?} which applies to any Scheme
value, $v$, and returns \verb+#f+ iff $v$ is not the {\tt meval} evaluator's
representation of a procedure.

{\bf 4D:} Add a {\tt procedure?} predicate to the {\tt meval} evaluator.
A simple way to do this is to extend the evaluator's initial environment
so that the variable {\tt procedure?} is bound to the {\tt mproc?}
procedure of 4C, just as the evaluator's variable {\tt pair?} is bound to
the {\tt mpair?} procedure.


\medskip
Section 4.2.3 develops the idea of delaying evaluation of all list
elements, so all lists wind up as ``lazy'' lists with stream-like
behavior.  Second 4.2.3 implements lazy lists as lazy procedures, which
works, but has some undesirable properties (cf. Exercise 4.33).  In the
following exercise we develop an improved implementation.

{\bf Exercise 5:}

{\bf Pre-Lab 5A:} One proposal for implementing lazy lists uses a
procedure {\tt lazy-cons} rather than {\tt cons}, where {\tt lazy-cons} is
defined as:
\begin{lisp}
(define (lazy-cons (a lazy) (b lazy))
  (cons a b))
\end{lisp}
Explain why this does not work in the current evaluator.

{\bf 5B:} Modify the evaluator so that
\begin{lisp}
(cons <expr1> <expr2>)
\end{lisp}
returns a cons-cell whose {\tt car} and {\tt cdr} are the {\em unforced}
values of {\tt <expr1>} and {\tt <expr2>}.  There are several ways to do
this, for example, by modifying the {\tt meval} procedure to handle {\tt
cons} as a new special form, or by modifying the way {\tt m-apply} applies
primitive procedures.  Try to make the fewest and simplest modifications
to accomplish the task.  Try to have your modified evaluator continue
treating {\tt car} and {\tt cdr} as the primitives built into underlying
Scheme, thereby avoiding the problems noted in {\em SICP}, Exercise 4.33.

{\bf 5C:} Check that your lazy lists in {\tt meval} work properly by
trying out the definition of the {\tt prime} stream defined on page 330 of
{\em SICP}, using the list operations {\tt cons}, {\tt car}, {\tt cdr}
(which you made behave lazily in 5B) instead of stream operations.


\paragraph{Lab exercise 6:}  In Problem Set 7, {\tt define-class} was a
procedure which took a quoted class definition as an argument.  Extend
{\tt meval} so it properly supports a {\tt define-class} special form
(whose body does not need to be quoted).  Most of the necessary code can
be yanked verbatim from the Problem Set 7 file {\tt object.scm}.  (Do {\tt
M-x load-problem-set: 7} to get this file in your Edwin buffer.)

\medskip

Even with lazy parameters, not all language
facilities can be defined as Scheme procedures.  An example is the
special form {\tt (for-list <var> <l> <body>)} where \Code{<var>} is a
variable and the value of {\tt <l>} is a list.  Evaluation of this
expression causes \Code{<body>} to be repeatedly evaluated as {\tt
<var>} is successively assigned to be the elements of the value of
{\tt <l>}.  More precisely,
\begin{lisp}
(for-list <var> <l> <body>)
\end{lisp}
would be syntactic sugar for
\begin{lisp}
(let (rest-l <l>))
  (define (iter)
    (if (null? rest-l)
        the-unspecified-value
        (begin
          (set! <var> (car rest-l))
          <body>
          (set! rest-l (cdr rest-l))
          (iter))))
  (iter))
\end{lisp}
assuming that the local variables
\Code{iter} and \Code{rest-l} are ``fresh,'' in particular, that neither
is the same as \Code{<var>} or equal to any variable free in
\Code{<body>}.

\paragraph{Lab exercise 7:}
Add the {\tt for-list} construct as a special form.  Try to do
better than simply treating it as syntactic sugar as described above.  If
you do this properly, the special form will evaluate a good deal more
efficiently than the desugared version, and no assumptions about ``fresh''
variables will be necessary.  Include some tests showing that your
implementation works properly.

\newpage
Turn in this sheet along with your answers to the questions in the problem
set:

\vspace{6ex}

How much time did you spend on this homework assignment?

\vspace{6ex}

Indicate all of the following facilities you in doing this problem set:
\begin{itemize}
\item The 6.001 lab in building 36.
\item MIT Scheme on Project Athena.
\item MIT Scheme on a Windows PC.
\item EdScheme on a PC.
\item Some other Scheme system (which one?).
\end{itemize}

\vspace{6ex}

We encourage you to work with others on problem sets as long as you
acknowledge it (see the 6.001 General Information handout).

If you cooperated with other students, LA's, or others, or found portions
of your answers for this problem set in references other than the course
text (such as some of the course archives), please indicate your
consultants' names and your references in the space below.  Also,
explicitly label all text and code you are submitting which is the same as
that being submitted by one of your collaborators.

Otherwise, write ``I worked alone using only the course reference
materials.'' and sign your statement.

 
\end{document}
