% -*- Mode: Tex -*-

\def\AnswerSheet{1}

\input 6001mac.tex

\begin{document}

\psetheader{Spring Semester, 1999}{Recitation -- Friday, April 9}

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

{\Large\bf 1. Some Meta-Circular Evaluator Code}

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:

\vspace{0.2in}

\centerline{\psfig{figure=r18c.ps,width=5in}}

\vspace{0.1in}

\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 2. 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
\ANSWERI{(+ 1 3)} & \ANSWERI{GE} & & \\
\ANSWERI{+ $\Rightarrow$ \#[Prim +]} & \ANSWERI{GE} & & \\
\ANSWERI{1 $\Rightarrow$ 1} & \ANSWERI{GE} & & \\
\ANSWERI{3 $\Rightarrow$ 3} & \ANSWERI{GE} & & \\
\hline
& \ANSWERI{!} & \ANSWERI{\#[Prim +] $\Rightarrow$ 4} & \ANSWERI{(1 3)} \\
\hline
\hline
{\bf (define mult (lambda (x y) (* x y)))} & GE & & \\
\hline
\ANSWERI{(lambda (x y) (* x y))} & \ANSWERI{GE} & & \\
\ANSWERI{$\Rightarrow$ (procedure (x y) (* x y) GE)} & \ANSWERI{!} & & \\
\hline
\hline
{\bf (mult z 3)} & GE & & \\
\hline 
\ANSWERI{mult $\Rightarrow$ (procedure (x y) (* x y) GE)} & \ANSWERI{GE} & & \\
\ANSWERI{z $\Rightarrow$ 4} & \ANSWERI{GE} & & \\
\ANSWERI{3 $\Rightarrow$ 3} & \ANSWERI{GE} & & \\
\hline
& & \ANSWERI{(procedure (x y) (* x y) GE)} & \ANSWERI{(4 3)} \\
\hline
\ANSWERI{(* x y)} & \ANSWERI{E1} & & \\
\ANSWERI{* $\Rightarrow$ \#[Prim *]} & \ANSWERI{E1} & & \\
\ANSWERI{x $\Rightarrow$ 4} & \ANSWERI{E1} & & \\
\ANSWERI{y $\Rightarrow$ 3} & \ANSWERI{E1} & & \\
\hline
& & \ANSWERI{\#[Prim *] $\Rightarrow$ 12} & \ANSWERI{(4 3)} \\
\hline
\hline
\end{tabular}

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

\vskip 0.05in

\ANSWERIS{
\centerline{\psfig{figure=r18b.ps,width=4in}}
}{
\vspace{1.4in}
}

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

\vskip 0.08in

\ANSWERIS{
\centerline{\psfig{figure=r18a.ps,height=2in}}
}{
\vspace{1in}
}

\newpage
{\Large\bf 3. Adding {\tt 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.1in}
\item Specify the syntax of the new special form
\vspace{-0.05in}
\item Define the data abstraction.
\vspace{-0.05in}
\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.05in}
\item Add a {\tt cond} clause to {\tt mc-eval} to support the new
special form.
\end{enumerate}

\vspace{-0.1in}

{\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 selectors:

\begin{tabular}{p{3in}|p{3in}}
\beginlisp
(define (let? exp)
\ANSWER{
  (and (pair? exp) (eq? (car exp) 'let))
})  
\null
(define (let-variables let-exp) 
\ANSWER{  (map car (cadr let-exp))
})
\endlisp
& 
\beginlisp
(define (let-exps let-exp)
\ANSWER{  (map cadr (cadr let-exp))
})
\null
(define (let-body let-exp)
\ANSWER{  (caddr let-exp)
})
\endlisp
\end{tabular}

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

Write {\tt eval-let} by desugaring:

\beginlisp
(define (eval-let exp env)
\ANSWER{
  (mc-eval 
   (cons 
     (list 'lambda (let-variables exp) (let-body exp))
     (let-values exp))
    env)
})
\endlisp

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

Write {\tt eval-let} without desugaring:

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

\newpage
{\Large\bf 4. Brain Teasers (I have an extra page)}

1.  Write a scheme expression that prints itself.

(Hint: Consider how a cell reproduces.  It contains its own blueprint
(the DNA strand in the nucleus); reproduction involves (a) copying the
blueprint, (b) implementing the blueprint.  That is, it uses the
blueprint twice.)

\beginlisp
\ANSWER{
((lambda (x)
   (list x (list (quote quote) x)))
 (quote (lambda (x)
          (list x (list (quote quote) x)))))
}
\null
\ANSWER{ 
Here's another solution (my favorite):
\null
(LET ((LET '`(LET ((LET ',LET))
                  ,LET)))
     `(LET ((LET ',LET))
           ,LET))
}
\endlisp

\vspace{0.2in}

2.  Write a scheme expression that goes into an infinite loop {\bf
without} using a {\tt define}, {\tt let}, or {\tt set!}

\beginlisp
\ANSWER{
((lambda (x) (x x)) (lambda (x) (x x)))
}
\endlisp

\vspace{0.2in}

3.  Write a {\tt lambda} expression that, when applied to a number,
computes the factorial of that number {\bf without} using {\tt define},
{\tt let}, or {\tt set!}  (Hint: Answer \#2 first!).

\beginlisp
\ANSWER{
(lambda (z) 
  ((lambda (x y) (if (= y 1) 1 (* y (x x (- y 1)))))
   (lambda (x y) (if (= y 1) 1 (* y (x x (- y 1)))))
   z))
}
\endlisp

\vspace{0.2in}

4.  Write the procedure {\tt list} {\bf without} using {\tt list} or
{\tt cons}.  (This should produce a real scheme list.)

\beginlisp
\ANSWER{
(define (list . args) args)
}
\endlisp

\vspace{0.2in}

5.  Write the procedure {\tt car} {\bf without} using {\tt car}.

\beginlisp
\ANSWER{
(define (car first . rest) first)
}
\endlisp

\vspace{0.2in}

6.  Write the procedure {\tt cdr} {\bf without} using {\tt cdr}.

\beginlisp
\ANSWER{
(define (cdr first . rest) rest)
}
\endlisp

\vspace{0.2in}

7.  Write {\tt map} using {\tt accumulate} (no recursion).

\beginlisp
\ANSWER{
(define (map proc x)
  (accumulate (lambda (x y) (cons (proc x) y)) nil x))
}
\endlisp

\vspace{0.2in}

8.  Write {\tt filter} using {\tt accumulate} (no recursion).

\beginlisp
\ANSWER{
(define (filter pred lst)
  (accumulate (lambda (x y) (if (pred x) (cons x y) y)) nil lst))
}
\endlisp

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


\end{document}
