\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\begin{document}

\newcommand{\evaluatesto}{\ensuremath{\implies}}
\newcommand{\keyword}[1]{\hbox{\texttt{#1}}}
\newcommand{\mytilde}{\ensuremath{\tilde{\ }}}
\newcommand{\url}[1]{\texttt{#1}}

This will be a small review sheet that covers the first few topics of
CS3S.  However, to tell the truth, you might find the SPC web site
more helpful.  We highly recommend you to the SPC web site --- there's
a great online review on the bottom of
\url{http://www-inst.eecs.berkeley.edu/\mytilde selfpace/}.  This
will try to cover misconceptions and problems that people have
been running into.


%%%
\section{Expressions}
Scheme programs are built out of expressions.  For example:
%
\begin{verbatim}
    42
    (* 5 6)
    'i-am-a-quoted-symbol
    (= a b)
\end{verbatim}
%
are all considered expressions.  You might not expect it, but
\keyword{+} and the other math symbols are also valid expressions:
\begin{verbatim}
STk> +
#[subr +]
STk> *
#[subr *]
STk> /
#[subr /]
\end{verbatim}

We find that numbers are ``self-evaluating'' --- the value of
\keyword{42} is \keyword{42}.  Simple enough.  It's sorta like a
mathematician who starts off saying $0 = 0$, but we find that this
rule keeps Scheme's evaluation system simple.

Let's take a slightly detailed look at what happens when we have
parentheses.  In the case of \texttt{(* 5 6)}, Scheme will take the
following steps to evaluate this expression:
\begin{itemize}
  \item  Evaluate the value of \keyword{*}, \keyword{5}, and
  \keyword{6}.  \keyword{5} and \keyword{6} are self evaluating, so we
  stop there.  \keyword{*} is a primitive function that Scheme picks
  up.  Scheme now knows about these three elements.

  \item Assume the first item is a function, and apply it on the rest
  of the list.  This means that \keyword{*} will be applied on
  \keyword{5} and \keyword{6}.
\end{itemize}

You should notice that there's something weird happening; isn't this
definition circular?  We're defining evaluation in terms of
evaluation!

This rule is necessary though.  What happens here?
\begin{verbatim}
    (* 2 (+ 1 20))
\end{verbatim}
In order to compute this expression, we need to apply evaluation on
\keyword{*}, \keyword{2}, and \keyword{(+ 1 20)}.  Ok, let's look at
\keyword{(+ 1 20)}.  \keyword{1} and \keyword{20} evaluate to themselves,
and \keyword{+} evaluates to a primitive function.  Eventually, we
``hit rock bottom'' at Scheme primitives.  If we follow the rules of
evaluation long enough, we'll eventually get an answer.
%\begin{verbatim}
%(* 2 (+ 1 20)) <==>
%(* 2 21) <==>
%42
%\end{verbatim}


% commented out --- We're assuming that they know this already.
% \section{Composing functions}
%
% Whenever Scheme see parentheses in an expression

Note --- wrapping expressions with regular parentheses in attempts to
get it into a list doesn't quite work:
\begin{verbatim}
STk> ( (list 1 2) )  

*** Error:
eval: bad function in : ((list 1 2))
\end{verbatim}
This is because of the rules above on evaluation: \keyword{(list 1 2)}
evaluates to the list, and then the outer pair of parentheses tells
Scheme to apply a function with no arguments.  The next section will
elaborate on this.

\section{Quotation}
% work on this hard
Now that we've talked about evaluation, it's time to bend its rules
with quotation.  You can quote something using the quote symbol
(\keyword{'}) or with \keyword{quote}.

Let's say we want to make a function, \keyword{greeting}, that takes a
name and returns a nice greeting:
\begin{verbatim}
(define (greeting name)
  (list 'hello name))
\end{verbatim}

Let's try it out:
\begin{verbatim}
STk> (greeting 'carol)         
(hello carol)
STk> (greeting 'clancy)
(hello clancy)
\end{verbatim}

Let's try something else:
\begin{verbatim}
STk> (greeting ernie)      

*** Error:
unbound variable: ernie
\end{verbatim}
Ah!  According to evaluation rules, Scheme will try to figure out
what \keyword{greeting} and \keyword{ernie} are.  It knows about
\keyword{greeting}, since we just defined it, but gets lost at
\keyword{ernie}.


What happens if we change the definition of \keyword{greeting} like
this?
\begin{verbatim}
(define (bad-greeting name)
  '(hello name))
\end{verbatim}

\begin{verbatim}
STk> (bad-greeting 'voldemort)
(hello name)
\end{verbatim}
Ooops.


\begin{itemize}
\item When we quote an atom (symbol or number), Scheme will evaluate
it as itself.
\item When we quote a list, Scheme will return a list with each
element itself quoted.
\end{itemize}

Another example:
\begin{verbatim}
STk> '(enumerate and (list (a (b) c)))   
(enumerate and (list (a (b) c)))
\end{verbatim}
This actually deals with some issues.  First, you can make nested
lists very easily with quotation.  Next, since Scheme isn't really
looking up the value of things, we can use words like \keyword{list}.
Because we quote \keyword{list}, Scheme will treat it just like any
other quoted symbol.

This brings up the question: what happens when we do this?
\begin{verbatim}
STk> ('list 1 2 3)

*** Error:
eval: bad function in : ((quote list) 1 2 3)
\end{verbatim}
We find out two things here --- \keyword{'list} is just shorthand for
the longer expression, \keyword{(quote list)}.  Second of all,
\keyword{'list} evaluates to the symbol ``list'', and not the list
function, which is why this breaks.\footnote{However, it \emph{is}
possible to force evaluation of a symbol with the \keyword{eval}
function: \keyword{(eval '(list 1 2))} does work. We won't cover this
in 3S, but it's nice to know that it works.}


%%%
\section{List manipulation}
% work on this hard
Let's talk about list manipulation a little bit.  You might have heard
that Scheme is a Lisp-like language.  What does this mean?  A small
excerpt from the Jargon file (\url{http://www.tuxedo.org/\mytilde esr/jargon}):
\begin{quote}
LISP n.  [from `LISt Processing language', but mythically from `Lots
of Irritating Superfluous Parentheses'] AI's mother tongue, a language
based on the ideas of (a) variable-length lists and trees as
fundamental data types, and (b) the interpretation of code as data and
vice-versa.
\end{quote}
So Scheme makes it easy to do stuff with lists.  What sort of stuff?
Obviously, we'd like to look at individual elements.  Let's look at
the two primary functions for getting at list elements, \keyword{car}
and \keyword{cdr}.

The \keyword{car} of a list will give us its \emph{first} element:
\begin{verbatim}
STk> car     
#[subr car]
STk> (car '(Jack and Jill))
jack
STk> (car '((Herimone) and Ron))
(herimone)
STk> (car '((Batman (and (Robin)))))
(batman (and (robin)))
\end{verbatim}

The \keyword{cdr} of a list will give us the \emph{rest} of the list.
\begin{verbatim}
STk> (cdr '(Donald E Knuth))
(e knuth)
STk> (cdr '((William Richard) Stevens))
(stevens)
STk> (cdr '((John McCarthy)))
()
\end{verbatim}
Notice that if a list has one element, \keyword{cdr} will still give
us the rest of the list --- the empty list.

With these two functions, we can define convenient functions to reach
the first, second, and third elements of a list:
\begin{verbatim}
(define (first l) (car l))
(define (second l) (car (cdr l)))
(define (third l) (car (cdr (cdr l))))
\end{verbatim}
\ldots and so on.\footnote{Scheme does provide these functions:
\keyword{cadr}, and \keyword{caddr} to do the same thing as our
\keyword{second} and \keyword{third}.}

Other important functions include \keyword{list}, \keyword{cons}, and
\keyword{append}, which are list building functions.  Other useful
functions include \keyword{reverse} and \keyword{length}, which have
obvious and not-so-obvious uses.

The two functions that seems to catch people off guard are
\keyword{cons} and \keyword{append}.  \keyword{cons} takes in 2
elements.  For 3S, we'll assume that the second element is always a
list.  Take a look:
\begin{verbatim}
STk> (cons 'la '(vals))    
(la vals)
STk> (cons '(le) '((miserables)))
((le) (miserables))
\end{verbatim}
We can imagine the first argument squeezing into the second element.

Now let's look at \keyword{append}.  \keyword{append} only works with
lists.  Take a look:

\begin{verbatim}
STk> (append 'foo '(bar))

*** Error:
append: argument is not a list: foo
STk> (append 'foo 'bar)    

*** Error:
append: argument is not a list: foo


STk> (append '(foo) '(bar))
(foo bar)
\end{verbatim}
Append will put two lists together, and breaks otherwise.
%
\footnote{We are sorta lying through our teeth: \keyword{(append
'(foo) 'bar) \evaluatesto (foo . bar)} doesn't technically break!
(Neither does \keyword{(cons 'foo 'bar)}!)  However, this is CS61A
material --- you don't need to worry about it for now.}
%

Using \keyword{list} is pretty simple: it takes in one or more
arguments, and makes a list of those elements.
\begin{verbatim}
STk> (list 'olympic 'gold)
(olympic gold)
\end{verbatim}

What catches people, initially, is the fact that it's perfectly legal
to make a list with one element:
\begin{verbatim}
STk> (list 'supercalifragilistexpialidocious)
(supercalifragilistexpialidocious)
STk> (list '(list))
((list))
\end{verbatim}

Time to start plugging advertisements.  If you have any questions, you
can always contact us through the newsgroup, \keyword{ucb.class.cs3s}.
Details on doing this are on the SPC url above.  However, if you like
human contact, come by to the SPC, and we'll be glad to talk with you.
Also, do come by and get the work done as quickly as you can --- you
do \emph{not} want to be at the SPC during the last few weeks.  Trust
us: it's not fun.

Let's end with a nice quote by the late Richard Stevens:
\begin{quote}
``This process of digging up details and learning how things work
leads down many side streets and to many dead ends, but it is
fundamental (I think) to understanding something new.  Many times in
my books I have set out to write how something works, thinking I know
how it works, only to write some test programs that lead me to things
that I never knew.  I try to convey some of these missteps in my
books, as I think seeing the wrong solution to a problem (and
understanding why it is wrong is often as informative as seeing the
correct solution.''
\end{quote}

Good luck!

\end{document}