\documentclass[twocolumn]{article}

\usepackage{fullpage}
\usepackage{palatino}

\begin{document}

\title{6.001 Tutorial 7}
\author{David Ziegler}
\date{October 25, 2004}
\maketitle

\section{Administrivia}
\begin{itemize}
\item Problem set 6 is due tomorrow.
\end{itemize}

\section{Feedback}
\begin{itemize}
\item I can't move lab to west campus.
\item I can't add a check button to quizzes.
\item I won't give out solutions to projects.
\item Solutions to tutorial problems are online. \\ \verb+http://david.ziegler.ws/6.001/+
\item If you bring in cookies/cake/coffee, I know everyone would be
  happy to eat it.
\end{itemize}

\section{Mutation}
Up to this point, everything we have done in Scheme has been
\emph{functional programming} -- each function we write is a
\emph{function}; that is, a procedure that always returns the same
value(s) for any set of inputs.

Mutation changes all that, specifically by giving us functions that
can change things.  Specifically, we have \verb+set!+, \verb+set-car!+
and \verb+set-cdr!+.

\begin{description}
\item[\texttt{(set!\ name exp)}] \verb+set!+ evaluates the \verb+exp+,
  and \emph{replaces} the binding of \verb+name+ with the new value.
\item[\texttt{(set-car!\ p exp)}] \verb+set-car!+ evaluates \verb+p+
  to get a pair, and the \verb+exp+, and replaces the car of \verb+p+
  with the value of \verb+exp+.
\item[\texttt{(set-cdr!\ p exp)}] \verb+set-cdr!+ evaluates \verb+p+
  to get a pair, and the \verb+exp+, and replaces the cdr of \verb+p+
  with the value of \verb+exp+.
\end{description}

\section{Examples}
\begin{verbatim}
;; This function takes one argument
;; and returns the value of the argument
;; the LAST time it was called:
;; (buffer 1) => #f
;; (buffer 'foo) => 1
;; (buffer '(1 2 3)) => foo
(define buffer





\end{verbatim}

\begin{verbatim}
;; This function takes one argument
;; and returns #t if it has ever seen
;; that argument before
(define seen?







\end{verbatim}

\begin{verbatim}
;; This function does destructive
;; append -- it changes the cdr of
;; the last pair to point to the
;; second list
;; Don't worry about empty x
(define (append! x y)



\end{verbatim}

\clearpage

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










\end{verbatim}

A little hint -- 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}

Now imagine we memoize a simple procedure:

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

(fast-square 5)
\end{verbatim}

What happens?

\end{document}