\documentclass{article}

\usepackage{fullpage}
\usepackage{palatino}

\begin{document}

\title{6.001 Tutorial 11 -- Solutions}
\author{David Ziegler}
\date{November 22, 2004}
\maketitle

\section{Administrivia}
\begin{itemize}
\item Problem set 9 is due tomorrow.
\item Project 4 is due Wednesday (lucky you!).
\item Project 5 is coming out on Wednesday, will be due Friday of next
week.
\end{itemize}

\section{Meta-Circular Evaluator}
The meta-circulator evaluator is an implementation of a Scheme
evaluator, \emph{in Scheme}.  It's an important distinction --- we've
written Scheme code (the evaluator) that manipulates data (lists that
look like Scheme expressions) to produce values.  We could have
written the evaluator in another language (like C).  We could also
have written an evaluator for another language (like Perl).  The
language the evaluator is written in and the language the evaluator
evaluates are separate.

In our evaluator, we have expressions (lists, symbols, numbers, etc.)
and environments.  An expression is a piece of data, the same sort of
data that the reader produces in the read, eval, print loop.  An
environment is a list of name-value bindings, along with a pointer to
a parent environment.

The evaluator works by determining the type of the expression --- is
it a self-evaluating expression, a special form, etc.?  Once it
determines the type, it dispatches to an appropriate evaluation
function for that type of expression.  For most expression types, we
have an evaluation rule that tells us how to evaluate the expression
--- now you can see the environment model rules in code!

\begin{verbatim}
(define (eval-assignment exp env)
  (set-variable-value! (assignment-variable exp)
                       (m-eval (assignment-value exp) env)
                       env))

(define (set-variable-value! var val env)
  (if (eq? env the-empty-environment)
      (error "No such variable" var)
      (let* ((frame (first-frame env))
             (binding (find-in-frame var frame)))
        (if binding
            (set-binding-value! binding val)
            (set-variable-value! var val (enclosing-environment env))))))

(define (set-binding-value! binding val)
  (set-car! (cdr binding) val))
\end{verbatim}

\section{Evaluating New Expressions}
When we create new types of expressions (or change the meaning of
existing ones), we need to add code to the evaluator to evaluate those
expressions.  There are two methods of doing this -- write a new
evaluation function, and desugar the expression into something
simpler.

\subsection{Writing New Selectors}
Let's work on handling \verb+let+ expressions.  The first thing we
need whenever we add a new expression type is procedures that handle
the \emph{syntax} of the new expression.  In the case of a \verb+let+,
we've got the \emph{names}, \emph{expressions}, and \emph{body}.

\begin{verbatim}
(define (let? exp)
  (tagged-list? exp 'let))

(define (let-names exp)
  (map first (second exp)))

(define (let-exprs exp)
  (map second (second exp)))

(define (let-body exp)
  (cddr exp))

\end{verbatim}

\subsection{Creating a New Evaluation Function}
After we've got the syntax procedures, we can write the function that
actually evaluates the expression we're given.  We also need to add a
clause to the evaluator that recognizes the expression type and calls
the appropriate evaluation function.

\begin{verbatim}
...
      ((let? exp) (eval-let exp env)
...


(define (eval-let exp env)
  (let ((new-env (extend-environment (let-names exp)
                                     (map (lambda (x) (m-eval x env))
                                          (let-exprs exp))
                                     env)))
    (eval-sequence (let-body exp) new-env)))
\end{verbatim}

\subsection{Desugar the Expression}
Alternately, we can desugar the expression into another expression
that we already know how to evaluate.  In the case of a \verb+let+,
that's a \verb+lambda+ and a combination.

\begin{verbatim}
...
      ((let? exp) (m-eval (let->combination exp) env))
...


(define (let->combination exp)
  (let ((names (let-names exp))
        (exprs (let-exprs exp))
        (body (let-body exp)))
    (cons (cons 'lambda
                (cons names
                      body))
          exprs)))
\end{verbatim}

You can make your desugaring functions much simpler if you use
\verb+quasiquote+.  \verb+quasiquote+ is like \verb+quote+, except
that you can tell Scheme to evaluate parts of the quoted expression.
A few examples:

\begin{verbatim}
`(1 2 3)
; (1 2 3)

`(1 (+ 1 1) 3)
; (1 (+ 1 1) 3)

`(1 ,(+ 1 1) 3)
; (1 2 3)
\end{verbatim}

The \verb+,+ is used to tell Scheme to ``unquote'' an expression --
that is, to evaluate it.

\begin{verbatim}
`(1 2 ,(list 3 4))
; (1 2 (3 4))

`(1 2 ,@(list 3 4))
; (1 2 3 4)
\end{verbatim}

The \verb+,@+ means ``unquote'' and ``splice'' -- evaluate it, and the
thing had better be a list, and then insert the contents of the list
into the result.

Using quasiquote, we can write desugaring functions very easily.

\begin{verbatim}
(define (let->combination exp)
  (let ((names (let-names exp))
        (exprs (let-exprs exp))
        (body (let-body exp)))
    `((lambda (,@names)
        ,@body)
      ,@exprs)))
\end{verbatim}

\end{document}