\documentclass[twocolumn]{article}

\usepackage{fullpage}
\usepackage{palatino}

\begin{document}

\title{6.001 Tutorial 8}
\author{David Ziegler}
\date{November 1, 2004}
\maketitle

\section{Administrivia}
\begin{itemize}
\item Problem set 7 is due tomorrow.
\item Project 3 is due Friday.
\end{itemize}

\section{Environment Model Rules}
The environment model is an accurate way of thinking about how
computation in Scheme works --- it's not a lie!  There are five simple
rules:

\begin{description}
\item[Name rule] The value of a name $n$ in an environment $e$ is the
  binding for $n$ in the first frame of $e$ where $n$ is bound.
\item[\texttt{define} rule] A \verb+define+ expression creates or replaces a
  binding for the name in the first frame of $e$.
\item[\texttt{set!} rule] A \verb+set!+ expression changes the binding
  of $n$  in the first frame of $e$ where $n$ is bound.
\item[\texttt{lambda} rule] Create a double bubble whose environment
  pointer is $e$.
\item[Apply rule] This is the important one!  To apply a procedure $p$...
\begin{itemize}
\item Create a new frame $f$.
\item Set $f$'s parent pointer to be the same as $p$'s environment
  pointer --- they are ``handcuffed'' together.
\item In $f$, bind the parameters of $p$ to the values of the
  arguments it was applied to.
\item Evaluate the body of $p$ in the newly created environment.
\end{itemize}
\end{description}

\section{Memoization}
A useful optimization that some languages perform is
\emph{memoization}.  The idea of memoization is to figure out when a
function returns a constant answer for a given set of arguments.  If
it does, whenever we call a function, we remember the arguments and
the result.  Later, we can check if we've seen these arguments before
and return the result without doing the computation again.  For
expensive functions (lots of work), this can save a lot of time.  The
following procedure takes a single argument function and returns a
memoized version.

\begin{verbatim}
(define (memoize proc)
  (let ((vals '()))
    (lambda (arg)
      (let ((previous (assoc arg vals)))
        (if previous
            (cadr previous)
            (let ((temp (proc arg)))
              (set! vals
                (cons (list arg temp)
                      vals))
              temp))))))
\end{verbatim}

Remember that \verb+assoc+ is a procedure that operates on association
lists.  It compares the \verb+car+ of each element of the list to the
first argument and returns that element if it is. It has the
following behavior:

\begin{verbatim}
(assoc 5 '((5 25) (6 36)))
; Value: (5 25)

(assoc 3 '((5 25) (6 36)))
; Value: #f

(assoc 3 '())
; Value: #f
\end{verbatim}

\clearpage

Now imagine we memoize a simple procedure:

\begin{verbatim}
(define fast-square
  (memoize (lambda (x) (* x x))))

(fast-square 5)
\end{verbatim}

What happens in the environment?

\end{document}