% Document Type: LaTeX
\documentclass{article}

\usepackage{6001}
\usepackage{amsmath}
\usepackage{array}
\usepackage{psfig}

\newcommand{\meta}[1]{\ensuremath{\langle\mathrm{#1}\rangle}}
\newcommand{\Or}{\mathbin{\mid}}

\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 9}

\medskip

\begin{flushleft}
Issued: Tuesday, 25 November\\
\smallskip
Due: Friday, 5 December, in recitation.\\
\smallskip
Tutorial preparation for Week of 1 December: Exercises 1A, 4B, 6A below\\
\smallskip
Reading: Attached code files {\tt tr-flatten.scm},
{\tt fotr-evl.scm}, {\tt fotrinit.scm}, and {\tt derived.scm}.
Review {\em SICP} Sections~4.1--4.1.6, 4.2.
\end{flushleft}

\medskip

\begin{center}\large
{\bf A Tail-Recursive First-Order Scheme Evaluator}
\end{center}

\bigskip

\section{Tail-recursive calls}
The difference between iterative procedures and more general recursive
procedures is that the number of ``things to do'' after a recursive
procedure call returns a value can grow unboundedly with the size of the
arguments.  With iterative procedure calls, the number of things to do
after the call stays bounded.

A procedure call is {\em tail-recursive} when there is {\em nothing} to do
after the call.  For example, if a call occurs as the last item in a {\tt
begin} expression, it is tail-recursive.  Or if a call occurs as a branch
of an {\tt if}, it is tail-recursive.  A call in a {\tt let} expression is
tail-recursive if it is tail-recursive in the body of the {\tt let}.  On
the other hand, a procedure call inside another procedure call, is {\em
not} tail-recursive.  For example, the call to {\tt factorial} in
\begin{lisp}
(* n (factorial (- n 1)))
\end{lisp}
occurs within the call to the primitive procedure {\tt *}; it is not
tail-recursive because there will still be a multiplication to do after
the {\tt factorial} call returns.  An expression is tail-recursive if all
the procedure calls, aside from calls to primitive procedures, are
tail-recursive.  A procedure definition is tail-recursive if the sequence
of expressions and definitions in its body are all tail-recursive.

Tail-recursive procedures are easier to simulate by hand than general
recursive procedures because at any point in an evalution, the only things
which need be recorded are the location in the procedure definition of the
subexpression currently being evaluated, and the current environment.  If
the procedure is also {\em first-order}, meaning it does not use
procedures as arguments of other procedures or as returned values, then it
isn't even necessary to keep track of the environment: it is enough to
record only the values of the parameters and global variables in the
procedure definition.  For this reason, first-order tail-recursive
procedures are also easy to translate into lower-level machine language
instructions.

In this problem set we will show you a first-order tail-recursive
intepreter for Scheme.  The step-by-step behavior of this interpreter is
much more explicit than the meta-circular interpreter of Section 4.1 or of
PS8.  It serves to explain how to implement {\em all} of Scheme in terms
of an elementary, small fragment of Scheme.

And in addition to reducing Scheme to a simpler language, the
tail-recursive interpreter will allow us to explain a variety of new
programming languages features, for example, MIT Scheme's {\tt error}
procedure.


\section{Using a stack to turn recursion into tail-recursion}
There are general techniques for rewriting recursive procedures as
tail-recursive ones.  The basic idea is to rewrite the procedures to keep
a shared, explicit, {\tt stack} of the computational ``things to do''
after a procedure call. We'll illustrate this idea with the procedure
which flattens a tree, that is, it returns a list of the leaves of the tree
in depth-first left-to-right order.

We've already seen {\tt flatten} written as a tree recursion:
\begin{lisp}
(define (flatten tree)       ;tree-recursive
  (cond ((null? tree) '())
        ((pair? tree)
         (append (flatten (car tree))
                 (flatten (cdr tree)))
        (else (list tree)))))   ;TREE is a leaf
\end{lisp}

To turn this into a tail-recursive procedure, we look at the
non-tail-recursive calls above and think of the computational task which
remains to do after each call.  We'll assume for simplicity that {\tt
append} is tail-recursive (we know how to define it so it would be).  This
leaves two remaining calls:
\begin{lisp}
(flatten (car tree))
\end{lisp}
and
\begin{lisp}
(flatten (cdr tree))
\end{lisp}
Neither of these is tail-recursive, since whatever order they are
performed in, an {\tt append} will have be done after they return.

We could rewrite {\tt flatten} tail-recursively to do either of these
calls first.  Let's pick the call to flatten the {\tt car} as the one to
do first.  Just after flattening the {\tt car} of the tree, what remains to be
done?  Looking at the definition of {\tt flatten} above, what's next is to
flatten the cdr of the tree, then append the previously computed flattened
car with the flattened cdr, and return the result.

As an aid to our memory, we'll use the string
\begin{lisp}
"(append [] (flatten (cdr tree)))"
\end{lisp}
as a tag to identify this kind of task.  Here the ``hole'', "[]",
indicates how this remaining task uses the previously computed flattened
car.  (The choice of identifying tag is arbitrary.  For example, since it
will turn out in a moment that there are only two kinds of tasks needed
for a tail-recursive {\tt flatten}, we could --- and would in a machine
implementaion --- have used a single bit as a tag instead of a long
string.)

The tag "(append [] (flatten (cdr tree)))" indicates the kind of task to
be performed, but not the exact datum to perform it on, namely, the {\tt
cdr} of the tree.  So each particular task of this kind is represented by
two items: the tag and the {\tt cdr} of the tree.

Now to process this remaining task, we have to do the second call to
flatten the {\tt cdr}.  Once that's done, the remaining task is to append
the flattened car to the just-computed value of the flattened cdr, and
return the result.  As a reminder of this, we'll use the tag
\begin{lisp}
"(append flattened-car [])"
\end{lisp}
and represent such tasks as lists of two items:
\begin{lisp}
("(append flattened-car [])" <flatcar>)
\end{lisp}
where {\tt <flatcar>} is the flattened {\tt car} of the tree obtained from
the first call.

Now we're ready to write our tail-recursive {\tt flatten}.
The idea is to write a tail-recursive procedure {\tt tr-flatten} which
acts like recursive {\tt flatten}, except that instead of {\em returning}
the flattened tree, its "contract" is to call a special {\tt return}
procedure, which is also tail-recursive, with the value of the flattened
tree:
\begin{lisp}
(define (tr-flatten tree)
  (cond ((null? tree) (RETURN '()))
        ((pair? tree) ...)
        (else (RETURN (list tree)))))   ;TREE is a leaf
\end{lisp}

The "contract" of the {\tt return} procedure is to use the value it
initially gets from {\tt tr-flatten} to carry out the next task.  The next
tasks are stored on a stack which is shared by the {\tt tr-flatten} and
{\tt return} procedures.  The {\tt return} procedure pop's the stack to
get the next task.  If the stack is empty, which means there is no next
task, then {\tt return} really returns the value it gets.

So {\tt tr-flatten} can fulfill its contract by pushing the next task
\begin{lisp}
("(append [] (flatten (cdr tree)))" CDR-OF-TREE)))
\end{lisp}
onto the stack and calling itself on the car of the tree.  Assuming {\tt
tr-flatten} fulfills its contract on the {\tt car} of the tree, the call
to itself will result in a call 
\begin{lisp}
(return <flattened-car>)
\end{lisp}
According to its contract, this call to {\tt return} will complete the
task.  So we can complete the definition of {\tt tr-flatten}:
\begin{lisp}
(define (tr-flatten tree)
  (cond ((null? tree) (return '()))
        ((pair? tree)
         (let ((next-task
                (list
                 "(append [] (flatten (cdr tree)))"
                 (cdr tree))))
           (begin
             (push next-task)
             (tr-flatten (car tree)))))
        (else
         (return (list tree)))))
\end{lisp}
Here we're regarding the stack operation {\tt push} as a primitive
procedure.  (An implementation the stack operations appears at the end of
the file {\tt fotrinit.scm}.)

Now we have to define a tail-recursive {\tt return} procedure which
carries out the two kinds of tasks.  But that's not hard since {\tt
return} can use {\tt tr-flatten}:
\begin{lisp}
(define (return val)
  (if (stack-empty?)
      val
      (let* ((next-task (pop))
             (tag (car next-task)))
        (cond
         ((string=? "(append [] (flatten (cdr tree)))" tag)
          (let ((cdr-of-tree (cadr next-task))
                (further-task
                 (list
                  "(append flattened-car [])"
                  val)))                ;VAL is the flattened car
            (begin
              (push further-task)
              (tr-flatten cdr-of-tree))))
         ((string=? "(append flattened-car [])" tag)
          (let ((flatcar (cadr next-task)))
            (return (append flatcar val)))) ;VAL is the flattened cdr
         (else (error "RETURN: unknown task" next-task))))))
\end{lisp}
Again, we're regarding the stack operations as primitive.

So finally we have tail-recursive {\tt flatten}:
\begin{lisp}
(define (flatten tree)          ;tail-recursive
  (begin
    (clear-stack!)
    (tr-flatten tree)))
\end{lisp}


The code for tail-recursive {\tt flatten} and the stack implementation is
in the file {\tt tr-flatten.scm}.  To help you see how this works, we list
the successive calls of {\tt tr-flatten} and {\tt return}, and the stack
contents after each {\tt push} in the evaluation of
\begin{lisp}
(flatten '((a b) c))
\end{lisp}

\begin{lisp}
tr-flatten: ((a b) c)
stack:
(("(append [] (flatten (cdr tree)))" (c)))

tr-flatten: (a b)
stack:
(("(append [] (flatten (cdr tree)))" (b))
 ("(append [] (flatten (cdr tree)))" (c)))

tr-flatten: a
return: (a)
stack:
(("(append flattened-car [])" (a))
 ("(append [] (flatten (cdr tree)))" (c)))

tr-flatten: (b)
stack:
(("(append [] (flatten (cdr tree)))" ())
 ("(append flattened-car [])" (a))
 ("(append [] (flatten (cdr tree)))" (c)))

tr-flatten: b
return: (b)
stack:
(("(append flattened-car [])" (b))
 ("(append flattened-car [])" (a))
 ("(append [] (flatten (cdr tree)))" (c)))

tr-flatten: ()
return: ()
return: (b)
return: (a b)
stack:
(("(append flattened-car [])" (a b)))

tr-flatten: (c)
stack:
(("(append [] (flatten (cdr tree)))" ())
 ("(append flattened-car [])" (a b)))

tr-flatten: c
return: (c)
stack:
(("(append flattened-car [])" (c))
 ("(append flattened-car [])" (a b)))

tr-flatten: ()
return: ()
(return: (c))
(return: (a b c))
;Value: (a b c)
\end{lisp}

{\bf Tutorial Exercise 1A}: What properties of the tree being flattened
determine the number of pushes and maximum stack depth?

{\bf Lab Exercise 1B}: The file {\tt tr-flatten} which loads with this
problem set contains the definitions of the flattening procedures above.
The stack operations are implemented in {\tt fotrinit.scm} which is also
loaded.

Modify the definitions of {\tt tr-flatten} and {\tt return} in the file
{\tt tr-flatten.scm}, and the definition of {\tt push} in {\tt
fotrinit.scm}, so that an application of {\tt flatten} will produce a
trace of calls and stack contents like the one above.  (Your trace needn't
be as tidy as the one above, which was hand edited.)  Hand in some
informative example traces obtained using your modified definitions.

\medskip
{\bf Exercise 2}.  Here is the usual recursive definition of {\tt
append}:
\begin{lisp}
(define (append x y)
  (if (null? x)
      y
      (cons (car x) (append (cdr x) y))))
\end{lisp}
Using the stack approach to make this tail-recursive, we might come up with
\begin{lisp}
(define (append x y)
  (clear-stack!)
  (tr-append x y))

(define (tr-append x y)
  (if (null? x)
      (return y)
      (begin
        (push (list "(cons (car x) [])" (car x)))
        (tr-append (cdr x) y))))
\end{lisp}

{\bf Pre-Lab 2A}: Write the {\tt return} procedure which goes with {\tt
tr-append}.  You should not need to have {\tt return} handle any other
kind of task than the one in {\tt tr-append}.

{\bf Pre-Lab 2B}: There are some obvious simplifications possible in the
above definitions of {\tt tr-append} and {\tt return}.  For example, since
there is only one kind of task needed, the string tag {\tt "(cons (car x)
[])"} is unnecessary.  Also, by making the stack an explicit extra
argument of both {\tt tr-append} and {\tt return}, the side-effects on the
stack can be replaced by simple list operations.  With these hints,
write a simple functional definition of a tail-recursive {\tt append}.

{\bf Lab Exercise 2C}: Show some traces of the procedure calls and stack
contents of the tail-recursive procedures of {\bf 2a}.  Compare them to
the traces of the functional versions you wrote for {\bf 2b}.


\section{Using the Evaluator}

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

\item {\tt fotr-evl.scm} is the code for the tail-recursive interpreter.
It handles self-evaluating and quoted data, variables, lambda expressions,
{\tt if}, sequences, {\tt define} and {\tt set!} directly, and {\tt and},
{\tt or}, {\tt cond}, and {\tt let} as derived expressions.  It uses the
essentially the same environment/frame and compound procedure
representations as the basic metacircular evaluator described in Section
4.1.1 of {\em SICP}, except that it does not use abstract syntax.

\item {\tt fotrinit.scm} contains the procedures that define and
initialize the evaluator's representation of environments.  It also
contains the procedures defining the evaluator's read-eval-print loop.

\item {\tt derived.scm} contains the procedures which allow
{\tt and}, {\tt or}, {\tt cond}, and {\tt let} to be treated by the
evaluator as derived expressions.

\end{itemize}

You use the evaluator in the same way as the one for Problem Set 8.

\begin{itemize}
\item To start up, do 
\begin{lisp}
M-x load-problem-set: 9
\end{lisp}
in Edwin.  This loads the files {\tt fotr-evl.scm}, {\tt fotrinit.scm},
and {\tt derived.scm}.  Then evaluate \Code{(start-fotr-eval)} in Scheme;
this starts the read-eval-print loop for the tail-recursive evaluator with
a freshly initialized global environment, which then prompts for an
expression to evaluate.

\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}
fotr-eval>> (+ 3 4)
;;fotr-value:
7
\end{lisp}
shows an interaction with the {\tt fotr-eval} 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 fotr-eval} read-eval-print loop, you can then visit this file and
type {\tt M-o} to have the definitions evaluated by {\tt fotr-eval}.

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

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

\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 fotrinit.scm}.  You may want to alter the
values of these limits to vary how much list structure will be printed as
output.

\end{itemize}

{\bf Lab exercise 3}: Extend the {\tt fotr-eval} evaluator to handle {\tt
let*} as a derived expression.  You should do this by defining a
tail-recursive procedure {\tt let*->}\emph{<some-other-form>}{\tt \&eval}
similar to those in {\tt derived.scm} and adding a {\tt let*} clause to
the {\tt fotr-eval} procedure.

{\bf Lab Exercise 4A}: Several useful procedures that are built into
Scheme, such as {\tt map}, have been omitted from {\tt fotr-eval}.  Add a
{\tt map} procedure to the evaluator so it is available at the initial
{\tt fotr-eval>>} prompt.  (There are several ways to do this.  Any one is
ok, as long as the interpreter remains first-order and tail-recursive.)

{\bf Tutorial Exercise 4B:} Be prepared to discuss some of the other ways
to pre-install {\tt map} into the evaluator.

\medskip
You may notice that this evaluator responds to errors in different
ways: for some errors, like attempting to evaluate an undefined variable,
it displays an error message and returns to its own read-eval-print loop.
For others, it bounces back into Scheme, sometimes with its own error
message and sometimes not.

{\bf Lab Exercise 5}

{\bf 5A}: Find examples of each of these kinds of error behavior by the
evaluator.

{\bf 5B}: Modify the evaluator so that it returns to its own
read-eval-print loop with a sensible error message instead of bouncing
back to Scheme, for at least one of your examples in {\bf 5A}.


{\bf Tutorial Exercise 6A}: We have used Scheme's {\tt error} procedure
throughout the course without much comment.  (If you're not sure about how
it behaves, look it up in the MIT Scheme Manual (not R$^4$RS).)  Explain
how it would be possible, but cumbersome, to add an {\tt error} procedure
to the part of Scheme which {\tt meval} of {\em SICP} 4.1 or PS8 could
interpret.  This procedure should return to the {\tt meval}
read-eval-print loop, {\em not} that of the underlying Scheme, so you
can't simply bind the meval variable {\tt error} to Scheme's underlying
{\tt error} procedure.

{\bf Lab Exercise 6B}: On the other hand, it's easy to add {\tt error} to
the fotr-evaluator: all the procedure need do is to display and/or return
a message, set the stack to the read-eval-print task, {\tt ("repl")}, and
call {\tt return}.

A {\tt *builtin-error*} procedure can be added to {\tt fotr-eval}
in a way similar to {\tt *builtin-apply*}.  Namely, add a special clause
for {\tt *builtin-error*} to the {\tt apply-dispatch} procedure in {\tt
fotr-evl.scm}.  Also, the variable {\tt error} will have to be bound to
{\tt *builtin-error*} in the {\tt fotr-eval} global environment.

Add an {\tt error} procedure to {\tt fotr-eval}.  Try it on
some examples which demonstrate that it behaves properly.  For example,
\begin{lisp}
fotr-eval>>
(begin (newline) (display 1) (error 'jumped-out) (display 2))
1
;;fotr-value:
jumped-out

fotr-value>>
\end{lisp}
displays {\tt 1}, but {\em not} {\tt 2}, and returns to the {\tt
fotr-eval} loop, not underlying Scheme.


{\bf Lab Exercise 7}: (Optional) Define a predicate {\tt tail-recursive}
which takes a Scheme expression as an argument and determines whether it
is tail-recursive.  Run your procedure on the definitions and expressions
in {\tt fotr-evl.scm} and {\tt fotrinit.scm} to determine which ones are
really tail-recursive.  (Not all are, because it was convenient to treat
some non-tail-recursive Scheme procedures as primitives.)



\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}
