\documentclass[twocolumn]{article}

\usepackage{fullpage}
\usepackage{palatino}

\begin{document}

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

\section{Administrivia}
\begin{itemize}
\item Quiz 2 is tomorrow, 7:30 -- 9:30!
\item Coverage is through environment models.
\item One page of notes, both sides.
\item Review session tonight, 5:00, 4-159.
\item Office hours, tomorrow, 3-4, Stata, Gates tower, 9th floor lobby.
\end{itemize}

\section{Environments!}
\begin{verbatim}
(define (identity x) x)
(define square
  (identity (lambda (x) (* x x))))
(square 5)
\end{verbatim}

\newpage

\begin{verbatim}
(define x 3)
((lambda (x y) (+ (x 1) y))
 (lambda (z) (+ x 2))
 3)
\end{verbatim}

\vspace{2in}

\begin{verbatim}
(define (fact n)
  (if (= n 0)
      1
      (* n (fact (- n 1)))))
(fact 2)
\end{verbatim}

\newpage

\begin{verbatim}
(define x 2)
(define proc
  (let ((x (* x 5))
        (f (lambda (y) (* x y))))
    f))
(proc 3)
\end{verbatim}

\vspace{3in}

\begin{verbatim}
(define x 2)
(define proc
  (let ((x (* x 5)))
    (let ((f (lambda (y) (* x y))))
      f)))
(proc 3)
\end{verbatim}

\clearpage

\section*{Environment Model Cheat Sheet}
To evaluate an expression in an environment $e$, follow the
rule:
\begin{description}
\item[\texttt{name}] Lookup \texttt{name} in the current environment,
  moving up frames to find the \texttt{name}.  Return the value bound
  to the \texttt{name}.
\item[\texttt{(define name exp)}] Evaluate \texttt{exp} in $e$ to get
  \texttt{val}, and create or replace a binding for \texttt{name} in
  the first frame of $e$ with \texttt{name}.  Return unspecified.
\item[\texttt{(set!\ name exp)}] Evaluate \texttt{exp} in $e$ to get
  \texttt{val}, and replace the first binding you come to for
  \texttt{name} in $e$ with \texttt{val}.  Return unspecified.
\item[\texttt{(lambda args body)}] Create a double bubble whose
  environment pointer (right half) is $e$, and set the left half to
  have the parameters \texttt{args} and body \texttt{body}.  Return a
  pointer to the double bubble.
\item[\texttt{(let ((var init) ...)\ body)}] Evaluate each
  \texttt{init} in $e$ (in any order) to get \texttt{val}s, drop a
  frame that points to $e$, bind each \texttt{var} to the associated
  \texttt{val} in the new frame, evaluate the \texttt{body} in the
  newly created environment.  Return the value of the last expression
  in the \texttt{body}.
\item[\texttt{(proc arg arg arg)}] Evaluate each expression in the
  combination in $e$, in any order.  Apply the first value to the rest
  of the values.  Return the value from applying.

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.
\item Return the value of the last expression in the body.
\end{itemize}
\end{description}

\section*{Common Environment Model Mistakes}
\begin{itemize}
\item Be sure to set the parent pointer of new frames properly ---
  it's the same as the environment pointer of \emph{the procedure
  you're applying}!
\item Keep track of what expression you're evaluating, and remember
  what steps you have left to do.  For example, when you have
  \verb+(define foo bar)+, don't forget to add the binding for
  \verb+foo+ after you finish evaluating \verb+bar+!
\item Don't get ahead of yourself!  A common mistake is for people to
  evaluate a \verb+lambda+ expression, giving a double bubble, and
  then immediately evaluate the body of the lambda.  Be sure that you
  follow the rules carefully!
\end{itemize}

\section*{Number Procedures}
\begin{description}
\item[\texttt{(quotient n1 n2)}]
\item[\texttt{(remainder n1 n2)}]
\item[\texttt{(modulo n1 n2)}] These procedures ``do the right
  thing.''  \verb+remainder+ always returns a number with the sign of
  \verb+n1+, \verb+modulo+ always returns a number with the sign of
  \verb+n2+.

\item[\texttt{(gcd n ...)}]
\item[\texttt{(lcm n ...)}] These procedures return the greatest
  common divisor or least common multiple (respectively) of their
  arguments.  The result is always non-negative.

\item[\texttt{(floor x)}]
\item[\texttt{(ceiling x)}]
\item[\texttt{(truncate x)}]
\item[\texttt{(round x)}] These procedures return integers.
  \verb+floor+ returns the largest integer not larger than \verb+x+.
  \verb+ceiling+ returns the smallest integer not smaller than
  \verb+x+.  \verb+truncate+ returns the integer closest to \verb+x+
  whose absolute value is not larger than the absolute value of
  \verb+x+.  \verb+round+ returns the closest integer to \verb+x+,
  rounding to even when \verb+x+ is halfway between two integers.

\item[\texttt{(random modulus)}] \verb+random+ returns a pseudo-random
  number between zero (inclusive) and \verb+modulus+ (exclusive).  The
  exactness of the result is the same as the exactness of \verb+modulus+.

\end{description}

\section*{List Procedures}
\begin{description}
\item[\texttt{(cons* obj obj ...)}] \verb+cons*+ is like \verb+list+,
  except it conses together the last two arguments rather than consing
  the last argument with the empty list.

\begin{verbatim}
(cons* 'a 'b 'c) => (a b . c)
(cons* 'a 'b '(c d)) => (a b c d)
(cons* 'a) => a
\end{verbatim}

\item[\texttt{(list-copy lst)}] \verb+list-copy+ returns a newly
  allocated copy each of the pairs comprising \verb+lst+.  It does not
  touch the elements of the list.  You can use \verb+tree-copy+ to
  make a deep copy of a list.

\item[\texttt{(list-ref lst k)}] \verb+list-ref+ returns the
  \verb+k+th element of \verb+lst+, using 0-based indexing.

\item[\texttt{(sublist lst start end)}] \verb+sublist+ returns a newly
  allocated list of the elements of \verb+lst+ beginning at index
  \verb+start+ (inclusive) and ending at \verb+end+ (exclusive).

\item[\texttt{(list-head lst k)}] \verb+list-head+ returns a newly
  allocated list of the first \verb+k+ elements of \verb+lst+.

\item[\texttt{(list-tail lst k)}] \verb+list-tail+ returns the sublist
  of \verb+lst+ obtained by omitting the first \verb+k+ elements.

\item[\texttt{(last-pair lst)}] \verb+last-pair+ returns the last pair
  in \verb+lst+.

\item[\texttt{(list-transform-positive lst pred)}]
\item[\texttt{(list-transform-negative lst pred)}] These procedures
  return a newly allocated copy of \verb+lst+ containing only those
  elements for which \verb+pred+ returns (respectively) true or false.

\item[\texttt{(delq element lst)}]
\item[\texttt{(delv element lst)}]
\item[\texttt{(delete element lst)}] Returns a newly allocated copy of
  \verb+lst+ with all elements equal to \verb+element+ removed.
  \verb+delq+ uses \verb+eq?+ to compare elements, \verb+delv+ uses
  \verb+eqv?+, and \verb+delete+ uses \verb+equal?+.

\newpage

\item[\texttt{(memq obj lst)}]
\item[\texttt{(memv obj lst)}]
\item[\texttt{(member obj lst)}] Returns the first pair of \verb+lst+
  whose car is \verb+obj+.  If \verb+obj+ does not appear in
  \verb+lst+, \verb+#f+ is returned.  \verb+memq+ uses \verb+eq?+ to
  compare \verb+obj+, \verb+memv+ uses \verb+eqv?+, and \verb+member+
  uses \verb+equal?+.

\item[\texttt{(map proc lst lst ...)}] \verb+proc+ must be a procedure
  that takes as many arguments as there are \verb+lst+s.  If there is
  more than one \verb+lst+ given, they must all be the same length.
  \verb+map+ applies \verb+proc+ element-wise to the elements of the
  \verb+lst+s, and returns a list of the results.  The order in which
  \verb+proc+ is applied is unspecified.

\item[\texttt{(for-each proc lst lst ...)}] Just like \verb+map+, but
  \verb+proc+ is applied in order, from left to right, and the result
  is unspecified.

\item[\texttt{(fold-right proc init lst)}] Combines all the elements
  of \verb+lst+ using the binary operation \verb+proc+.

\item[\texttt{(sort lst proc)}]
\item[\texttt{(merge-sort lst proc)}]
\item[\texttt{(quick-sort lst proc)}] Returns a newly allocated list
  whose elements are those of \verb+lst+, rearranged to be in the
  order specified by \verb+proc+.  \verb+sort+ is an alias for
  \verb+merge-sort+.  \verb+quick-sort+ is an alternative sorting
  implementation.

\end{description}

\section*{Miscellaneous Procedures}
\begin{description}
\item[\texttt{(apply proc obj obj ...)}] Calls \verb+proc+ with the
  elements of the list \verb+(cons* obj obj ...)+ as arguments.
\end{description}

\end{document}