\documentclass[twocolumn]{article}

\usepackage{fullpage}
\usepackage{palatino}

\begin{document}

\title{6.001 Tutorial 13 -- Solutions}
\author{David Ziegler}
\date{December 6, 2004}
\maketitle

\section{Administrivia}
\begin{itemize}
\item The last tutorial!
\item Last lecture is on Thursday, 10:00, 32-123!
\item Project 5 will be back at the final.
\item No office hours on Tuesday; finals week office hours to be
  arranged.
\item Problem set 10 (feedback) -- please do it, we really do care!
\item \textbf{Important} --- I'm teaching recitation on Wednesday!
\end{itemize}

\section{Lazy Evaluation}
The whole point of lazy evaluation is to put off doing work as long as
you can.  There are two ways of doing that.  One is to be explicit:

\begin{verbatim}
(delay exp)
; Returns a promise to evaluate exp
; in current environment

(force promise)
; Returns the value of exp in the
; original environment
\end{verbatim}

It's easier if everything is implicit.  In this case, all arguments to
functions are delayed, and values are forced when needed:

\begin{itemize}
\item Printing the value to screen.
\item Used as an argument to a primitive procedure.
\item Used in a conditional.
\item Used as an operator.
\end{itemize}

Lazy evaluation has a bunch of interesting applications, but the one
that we're most interested in is constructing streams, (usually)
infinite data structures.  A stream is just like a list, but the
\verb+cdr+ of each cons cell is lazy-memoized.

\begin{verbatim}
(define (cons-stream x (y lazy-memo))
  (cons x y))

(define stream-car car)

(define stream-cdr cdr)
\end{verbatim}

Some streams are very easy to construct.  For example, the stream of
infinite $1$'s:

\begin{verbatim}
(define ones (cons-stream 1 ones))
\end{verbatim}

For more complicated streams, we need some helper functions:

\begin{verbatim}
(define (add-streams s1 s2)
  (cons-stream (+ (stream-car s1)
                  (stream-car s2))
               (add-streams (stream-cdr s1)
                            (stream-cdr s2))))
\end{verbatim}

To construct a stream, think about the mathematical relationship
between successive elements in the stream.  For example, we know that
the $n$th Fibonacci number is the sum of the $n-1$st and $n-2$nd
Fibonacci numbers, and that the first and second Fibonacci numbers are
both 1.

\begin{verbatim}
(define fibs
  (cons-stream 1
    (cons-stream 1
      (add-streams fibs
                   (stream-cdr fibs)))))
\end{verbatim}

In general, to figure out how to write out code to generate a stream,
write out the numbers in the stream, and then figure out a
relationship between them.  Figure out how to express some element of
the stream in terms of other elements that preceed.

\begin{verbatim}
(define facts
  (cons-stream 1
    (mul-streams facts ints)))
\end{verbatim}

\section{Asynchronous Computing}

The whole idea of asynchronous computing is that two processes that
have shared state might interact in different ways if they are running
in parallel.

\begin{verbatim}
(define x 0)

(define (foo)
  (set! x 1))

(define (bar)
  (set! x 2))

(parallel-execute foo bar)
\end{verbatim}

So why do we care?

\section{Review}

Topics from this course:

\begin{itemize}
\item Scheme
\item Procedures and recursion
\item Orders of growth
\item Data abstractions
\item Higher-order procedures
\item Program methodology
\item Symbols and quotation
\item Abstract data types
\item Mutation
\item Environment model
\item Object-oriented systems
\item Interpretation/evaluation
\item Lazy evaluation
\item Asynchronous computing
\end{itemize}

\clearpage

\onecolumn
\thispagestyle{empty}
\section*{Final Feedback}

\begin{enumerate}
\item How have you enjoyed/tolerated/hated 6.001?
\vspace{0.9in}

\item What things have gone well?
\vspace{0.9in}

\item What things have not?
\vspace{0.9in}

\item What did you think of tutorial?  Was it useful?
\vspace{0.9in}

\item Are there any things you would have liked to have seen from me
  that would have helped?
\vspace{0.9in}

\item If you could change anything about tutorial, what would it be?
\vspace{0.9in}

\item Any other comments?
\vspace{0.9in}

\end{enumerate}

Thanks for your feedback!


\end{document}