% -*- Mode: Tex -*-

\def\AnswerSheet{1}

\input 6001mac.tex

\begin{document}

\psetheader{Spring Semester, 1999}{Recitation -- Friday, February 5}

{\Large\bf 1. Practice with Scheme}

Write down what Scheme will print in response to the following:

\begin{tabular}{p{3in}p{3in}}
{
\beginlisp
$\Rightarrow$ (define four 4)
\ANSWER{;Value: "four --> 4"}
$\Rightarrow$ four
\ANSWER{;Value: 4}
$\Rightarrow$ (define six (lambda () 6))
\ANSWER{;Value: "six --> \#[compound procedure]"}
$\Rightarrow$ six
\ANSWER{;Value: \#[compound procedure]}
$\Rightarrow$ (+ four 1)
\ANSWER{;Value: 5}
$\Rightarrow$ (+ (four) 1)
\ANSWER{;Error: The object 4 is not applicable}
$\Rightarrow$ (+ six 1)
\ANSWER{;Error: Compound procedure passed to add}
$\Rightarrow$ (+ (six) 1)
\ANSWER{;Value: 7}
$\Rightarrow$ (define f-add 
     (lambda (x y) 
        (+ (x) (y))))
\ANSWER{;Value: "f-add --> \#[compound procedure]"}
$\Rightarrow$ (f-add six (lambda () four))
\ANSWER{;Value: 10}
\endlisp
} & {
\beginlisp
$\Rightarrow$ (define a 5)
\ANSWER{;Value: "a --> 5"}
$\Rightarrow$ (define b (+ 1 a))
\ANSWER{;Value: "b --> 6"}
$\Rightarrow$ (+ 2 (if (> b a) b a))
\ANSWER{;Value: 8}
$\Rightarrow$ (if \#t 5 (/ 1 0))
\ANSWER{;Value: 5}
$\Rightarrow$ ((if (< a b) + -) a b)
\ANSWER{;Value: 11}
$\Rightarrow$ (if (if + \#f 2) 3 6)
\ANSWER{;Value: 6}
$\Rightarrow$ (if 0 1 2)
\ANSWER{;Value: 1}
$\Rightarrow$ (define n 4)
\ANSWER{;Value: "n --> 4"}
$\Rightarrow$ (define increment (lambda (x) (+ x 1)))
\ANSWER{;Value: "increment --> \#[compound proc]"}
$\Rightarrow$ (increment n)
\ANSWER{;Value: 5}
$\Rightarrow$ n
\ANSWER{;Value: 4}
\endlisp
}
\end{tabular}

\vspace{0.1in}
{\Large\bf 2. Writing Simple Procedures}

Write a procedure {\tt max} of two arguments that returns the larger
one.

\beginlisp
\ANSWER{
(define max 
  (lambda (x y)
    (if (> x y) 
        x
        y)))
}
\endlisp

\vspace{0.05in}

Write a procedure {\tt sign} that takes a number as its argument and
returns $-1$ if it is negative, $1$ if it is positive and $0$ if the
argument is zero.

\beginlisp
\ANSWER{
(define sign
  (lambda (x)
    (if (> x 0) 
        1
        (if (< x 0)
            -1 
            0))))
}
\endlisp

\newpage

{\Large\bf 3. Scoping of Variables}

Consider the example below.  Notice that {\tt x} is used in multiple
places.  When do we substitute for {\tt x} and when don't we?  

\beginlisp
$\Rightarrow$ (define x-y*y
    (lambda (x y)
      (- x ((lambda (x) (* x x)) y))))
\endlisp

Use the substitution model to evaluate the following expression:

\beginlisp
$\Rightarrow$ (x-y*y 11 3)
\ANSWER{$\Rightarrow$ ([proc (- x (($\lambda$ (x) (* x x)) y))] 11 3)}
\ANSWER{$\Rightarrow$ (- 11 (($\lambda$ (x) (* x x)) 3))}
\ANSWER{$\Rightarrow$ (- 11 (* 3 3))}
\ANSWER{$\Rightarrow$ (- 11 9)}
\ANSWER{;Value: 2}
\endlisp

\vspace{0.1in}

Let's examine the function below to try to better understand Scheme's
scoping rules.

\beginlisp
(define scope
  (lambda (x y z)
    (define add-to-y
       (lambda (x) (+ x y)))
    (add-to-y z)))
\null
$\Rightarrow$ (scope 1 2 3)
\ANSWER{;Value: 5}
\endlisp

\vspace{0.1in}
{\Large\bf 4. Syntactic Sugar}

Notice that we use {\tt lambda} a lot -- in fact {\em every} time we
write a function.  To save us all from writing (and possibly
mispelling) {\tt lamda} so much, there's a short-cut.

The following two expressions are equivalent.

\begin{tabular}{p{2.7in}p{0.5in}p{3in}}
{
\beginlisp
(define <proc> 
  (lambda (<arg1> <arg2> ... <argn>)
     <body>))
\endlisp
} & {\LARGE $\Leftarrow\Rightarrow$} &
{
\beginlisp
(define (<proc> <arg1> <arg2> ... <argn>)
     <body>)
\endlisp
} \\
For example, instead of writing: & & we can write: \\
{
\beginlisp
(define average 
  (lambda (x y) 
    (/ (+ x y) 2)))
\endlisp
} & {\LARGE $\Leftarrow\Rightarrow$} & {
\beginlisp
(define (average x y) 
    (/ (+ x y) 2))
\endlisp
}
\end{tabular}

\vspace{-0.1in}
They are the same, so feel free to use either one.  If the syntactic
sugar is confusing, then stick with the original for now.  The
important thing to realize is that in both cases, {\bf the lambda
expression is evaluated and then bound to the name}, even if {\tt
lambda} isn't written anywhere.

\vspace{0.1in}
{\Large\bf 5. A Recursive Procedure}

Consider the mathematical definition of factorial: 
\begin{tabular}{ll}
$n! = 1$  & for $n = 0$ \\
$n! = n (n-1)!$ & for $n > 0$ \\
\end{tabular}

Let's write the function {\tt factorial} in Scheme (using the
``Syntactic Sugar'' as described above):

\beginlisp
(define (factorial n)
\ANSWER{     (if (= n 0)
        1
        (* n (factorial (- n 1))))
}
\null
)
\endlisp


\end{document}

