% -*- 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\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, April 10}

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

{\Large\bf 1. Student Presentation}

Now that we can look at the implementation of the metacircular
evaluator we might expect that finally we can figure out in what order
it evaluates the sub-expressions in a combination.  The procedure that
evaluates those expressions is named list-of-values and is found on
page 367 of Section 4.1 in the textbook.  Unfortunately, it turns out
that our metacircular evaluator inherits the order of evaluation that
the underlying Scheme interpreter happens to use.  Explain this
observation to the class, and then show how to modify list-of-values
so that it always evaluates expressions left to right.

\vskip .08in

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

{\Large\bf 2. The Meta-Circular Evaluator}

The heart of the Scheme language is an interpreter, that is, a process
that evaluates legal expressions of the language.  In lecture, we saw a
Scheme interpreter built around the use of two basic procedures, which
we will call {\tt mc-eval} and {\tt mc-apply}.  Examples of these,
without data abstractions, are given below:

\beginlisp
(define (mc-eval exp env)
  (cond ((number? exp) exp)                   ;base case for numbers
        ((symbol? exp) (lookup exp env))      ;base case for variables
        ((eq? (car exp) 'quote) (car (cdr exp)))      ;special forms
        ((eq? (car exp) 'lambda) 
          (list 'procedure (cadr exp) (caddr exp) env))
        ((eq? (car exp) 'define) (eval-define (cdr exp) env))
        (else (mc-apply (mc-eval (car exp) env)       ;procedure application
                        (list-of-values (cdr exp) env)))))
\null
(define (mc-apply proc args)
   (cond ((atom? proc) (apply proc args))       ;primitive case
         ((eq? (car proc) 'procedure)           ;compound procedure
          (mc-eval (caddr proc)                         ;procedure body
                   (extend-environment (cadr proc)      ;formal parameters
                                       args             ;supplied arguments
                                       (cadddr proc)))) ;saved environment
         (else (error "Unknown procedure"))))
\null
(define (eval-define exp env)
  (define-variable! (cadr exp)
                    (mc-eval (caddr exp) env)
                    env))
\null
(define (define-variable! var val env)
  (set-car! (car env) (cons var (caar env)))
  (set-cdr! (car env) (cons val (cdar env))))
\null
(define (extend-environment vars vals base-env)
    (cons (make-frame vars vals) base-env))
\null
(define (make-frame vars vals) (cons vars vals))
\endlisp

\newpage
{\Large\bf 3. An Example using the Meta-Circular Evaluator}

Use the table below to trace what the Meta-Circular Evaluator does on
the following three expressions.  Also, use the space below the table
to draw the mc-evaluator's environment.

\beginlisp
(mc-eval '(define z (+ 1 3)) the-global-environment)
(mc-eval '(define mult (lambda (x y) (* x y))) the-global-environment)
(mc-eval '(mult z 3) the-global-environment)
\endlisp

\begin{tabular}{|p{2.7in}|p{0.3in}||p{2.1in}|p{0.4in}|}
\hline
\multicolumn{2}{|c||}{MC-Eval} & \multicolumn{2}{|c|}{MC-Apply} \\
Expression & Env & Procedure & Args \\
\hline
\hline
{\bf (define z (+ 1 3))} & GE & & \\
\hline
& & & \\ % (+ 1 3) & GE & & \\
& & & \\ % + $\Rightarrow$ \#[Prim +] & GE & & \\
& & & \\ % 1 $\Rightarrow$ 1 & GE & & \\
& & & \\ % 3 $\Rightarrow$ 3 & GE & & \\
& & & \\ % \hline
& & & \\ % & ! & \#[Prim +] $\Rightarrow$ 4 & (1 3) \\
\hline
\hline
{\bf (define mult (lambda (x y) (* x y)))} & GE & & \\
\hline
& & & \\ % (lambda (x y) (* x y)) & GE & & \\
& & & \\ % $\Rightarrow$ (procedure (x y) (* x y) GE) & ! & & \\
\hline
\hline
{\bf (mult z 3)} & GE & & \\
\hline 
& & & \\ % mult $\Rightarrow$ (procedure (x y) (* x y) GE) & GE & & \\
& & & \\ % z $\Rightarrow$ 4 & GE & & \\
& & & \\ % 3 $\Rightarrow$ 3 & GE & & \\
& & & \\ % \hline
& & & \\ % & & (procedure (x y) (* x y) GE) & (4 3) \\
& & & \\ % \hline
& & & \\ % (* x y) & E1 & & \\
& & & \\ % * $\Rightarrow$ \#[Prim *] & E1 & & \\
& & & \\ % x $\Rightarrow$ 4 & E1 & & \\
% & & & \\ % y $\Rightarrow$ 3 & E1 & & \\
% & & & \\ % \hline
% & & \#[Prim *] $\Rightarrow$ 12 & (4 3) \\
\hline
\hline
\end{tabular}

Draw the mc-evaluator's environment diagram for
evaluating the above expressions.

\begin{tabular}{|p{6.2in}|}
\hline 
\beginlisp
\null 
\null 
\null 
\null 
\null 
\null 
\null 
\null 
\null
\endlisp \\
\hline
\end{tabular}

Draw the box-and-pointer diagrams that {\bf represent} the
mc-evaluator's environment.

\begin{tabular}{|p{6.2in}|}
\hline 
\beginlisp
\null 
\null 
\null 
\null 
\null 
\null 
\null 
\null 
\null 
\null
\endlisp \\
\hline
\end{tabular}

\newpage
{\Large\bf 4. Adding let to the Meta-Circular Evaluator}

Often we will want to add a special form to our evaluator.  For
example, say we want to add {\tt let}.  In general to add a special
form, follow these steps.

\begin{enumerate}
\vspace{-0.11in}
\item Specify the syntax of the new special form
\vspace{-0.07in}
\item Define the data abstraction.
\vspace{-0.07in}
\item Write {\tt eval-foo} where {\tt foo} is your new special form
either by desugaring the expression or explicitly evalating it using
the rules defined by the special form.
\vspace{-0.07in}
\item Add a {\tt cond} clause to {\tt mc-eval} to support the new
special form.
\end{enumerate}
\vspace{-0.11in}

{\large\bf Let Form}

What is the form of a let?

\beginlisp
(let (($\langle{}var_1\rangle$ $\langle{}exp_1\rangle$) 
       ... 
      ($\langle{}var_n\rangle$ $\langle{}exp_n\rangle$)) 
   $\langle{}body\rangle$)
\endlisp

{\large\bf Let Abstractions}

You can think of {\tt let} as a {\bf data-abstraction} that holds
three things:  A list of variables, a list of expressions, and a
body.  We need to write the selectors for this abstraction.

\beginlisp
(let? '(let ((a (+ 3 4)) (b 5)) (+ a b)))           ==> \#t
(let-variables '(let ((a (+ 3 4)) (b 5)) (+ a b)))  ==> (a b)
(let-exps '(let ((a (+ 3 4)) (b 5)) (+ a b)))       ==> ((+ 3 4) 5)
(let-body '(let ((a (+ 3 4)) (b 5)) (+ a b)))       ==> (+ a b)
\endlisp

Write the code for the following three selectors:

\beginlisp
(define (let? exp)
%  (and (pair? exp) (eq? (car exp) 'let))
\null
)  
(define (let-variables let-exp) 
%  (map car (cadr let-exp))
\null
)
(define (let-exps let-exp)
%  (map cadr (cadr let-exp))
\null
)
(define (let-body let-exp)
%  (caddr let-exp)
\null
)
\endlisp

{\large\bf Writing Eval-Let (Take 1)}

Write {\tt eval-let} by desugaring:

\beginlisp
(define (eval-let exp env)
%   (mc-eval 
%    (cons 
%      (list 'lambda (let-variables exp) (let-body exp))
%      (let-values exp))
%     env)
\null
\null
\null
\null
)
\endlisp

{\large\bf Writing Eval-Let (Take 2)}

Write {\tt eval-let} without desugaring:

\beginlisp
(define (eval-let exp env)
%   (mc-eval (let-body exp)
%            (extend-environment (let-variables exp)
%                                (list-of-values (let-exps exp) env)
%                                env))
\null
\null
\null
\null
)
\endlisp

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

\end{document}
