% -*- Mode: Tex -*-

\def\AnswerSheet{1}

\input 6001mac.tex

\def\comment[#1]{}
\begin{document}
\comment{
\psetheader{Spring Semester, 1999}{Recitation -- Friday, February 19}

{\Large\bf 1. Abstraction using Higher Order Procedures}

Let's take a look at using abstraction on common patterns.

\begin{tabular}{p{3in}p{3in}}
{\small \tt ~~~~(* 2 5)~~~~~~~~~~~~~\ANSWER{(double 5)}}
& {\small \tt ~~~~(* 3 2)~~~~~~~~~~~~~~\ANSWER{(triple 2)}}  \\
{\small \tt ~~~~(* 2 8)~~~~~~~~~~~~~\ANSWER{(double 8)}}                
& {\small \tt ~~~~(* 3 17)~~~~~~~~~~~~~\ANSWER{(triple 17)}}  \\
{\small \tt ~~~~(* 2 54)~~~~~~~~~~~~\ANSWER{(double 54)}}       
& {\small \tt ~~~~(* 3 4.1)~~~~~~~~~~~~\ANSWER{(triple 4.1)}}  \\
\hline
\begin{tabular}{p{1.2in}p{1.5in}}
{
\beginlisp
(define double
  (lambda (x) 
    (* 2 x)))
\endlisp
} & {
\beginlisp
\ANSWER{
(define double 
  (make-mult 2))
}
\endlisp
}
\end{tabular}
&
\begin{tabular}{p{1.2in}p{1.5in}}
{
\beginlisp
(define triple
  (lambda (x) 
    (* 3 x)))
\endlisp
} & {
\beginlisp
\ANSWER{
(define triple 
  (make-mult 3))
}
\endlisp
}
\end{tabular} \\
\hline
\end{tabular}

\vspace{-0.1in}
\beginlisp
                                       (define make-mult 
                                         (lambda (n)  
                                           (lambda (x) 
                                             (* n x)))) 
\endlisp


{\Large\bf 3. Higher Order Procedures}

Write a function {\tt swap} that takes a function {\tt f}, and returns
a function, that takes two arguments, and returns {\tt f} with the
variables swapped: {\small \tt (f x y) == ((swap f) y x)} For example,
{\small \tt ((swap -) 4 5) $\Rightarrow$ 1}.

\beginlisp
(define swap 
\ANSWER{
  (lambda (f)
    (lambda (x y)
      (f y x)))
}
)
\endlisp


\vspace{0.1in}

% {\Large\bf 4. More Higher Order Procedures}
% 
% Write a function {\tt fmax} that takes two functions f and g (that
% each take a number) and returns a function, that when called with a
% number $x$, returns the max of $f(x)$ and $g(x)$.  For example,
% 
% \beginlisp
% (define max-sqr-sqrt (fmax sqr sqrt))
% (max-sqr-sqrt 3) == 9
% (max-sqr-sqrt 0.25) == 0.5
% \endlisp
% \vskip .05in
% \beginlisp
% (define fmax 
%   (lambda (f g)
%     (lambda (x)
%       (let ((fx (f x))
%             (gx (g x)))
%         (if (> fx gx) fx gx)))))
% \endlisp

{\Large\bf 2. Composing Procedures}

Now try to write the function {\tt compose} that takes two functions,
{\tt f} and {\tt g}, and returns a function, that takes one argument,
and composes {\tt f} and {\tt g} on that argument.

\beginlisp
(define compose 
\ANSWER{
  (lambda (f g)
    (lambda (x)
      (f (g x))))
})
\endlisp

Let's trace through the evaluation of the following expression:

\beginlisp
((compose double cube) 3) 
((\framebox[1.9in][l]{($\lambda$ (f g) \framebox[1.16in][l]{($\lambda$ (x) (f (g x)))})} double cube) 3) 
(\framebox[1.7in][l]{($\lambda$ (x) (double (cube x)))} 3)
(double (cube 3))
54
\endlisp

Notice that there's no magic here.  We just used the same rules for
evaluation that we've been using all along -- the substitution model!

Using {\tt compose}, define the function {\tt \^{}5/2} which takes a number
{\tt x} and computes $x^{5/2}$.

\beginlisp
(define \^{}5/2 \ANSWER{ (compose sqrt cube) }                        )
\endlisp


\vspace{0.1in}
{\Large\bf 5. Repeated Composition of Procedures}

We saw how to compose two procedures to produce another procedure.
For example, we can define the following.

\beginlisp
(define fourth-power (compose square square))
(define eight-power (compose square (compose square square)))
... and so on ...
\endlisp

Let's write a (very strange) function called {\tt repeated} that takes
a function {\tt f} and an integer {\tt n}, and composes {\tt f}, {\tt
n} times.  For example:

\beginlisp
(define fourth-power (repeated square 2))
(define eight-power (repeated square 3))
... and so on ...
\endlisp

\vspace{0.1in}

\beginlisp
(define (repeated proc n)
\ANSWER{
  (if (= n 0)
      (lambda (x) x)
      (compose proc (repeated proc (- n 1))))
}
)
\endlisp

Let's look at a simple example:

\beginlisp
(define fourth-power (repeated square 2))
\ANSWER{
(repeated square 2)
(compose square  (repeated square 1))
(compose square  (compose square  (repeated square 0)))
(compose square  (compose square  (lambda (x) x)))
...
}
\endlisp

\vspace{0.1in}
{\Large\bf 6. Iterative Repeated}

Guess what..  Now that we've written the recursive version of {\tt
repeated}, let's write the iterative version.

\beginlisp
(define (repeated proc n)
\ANSWER{
  (define (iter n ans)
     (if (= n 0) 
         ans
         (iter (- n 1) (compose f ans))))
  (iter n (lambda (x) x))
}
)
\endlisp

\vspace{0.1in}
{\Large\bf 7. More Higher-Order Procedures}

Write a function {\tt snoc} that takes two arguments {\tt a} and {\tt
b} and returns a function, that when called with {\tt \#t} returns
{\tt a} and when called with {\tt \#f} returns {\tt b}.

\begin{tabular}{p{2.5in}p{3.5in}}
{
\beginlisp
(define snoc
\ANSWER{
  (lambda (a b)
    (lambda (x)
       (if x a b)))
})
\endlisp
} & 
What do we have once we define the following?  
\beginlisp
(define (rac x) (x \#t))
(define (rdc x) (x \#f))
\endlisp
\end{tabular}


Here's an even more elegant (albeit more obscure) way of doing the
same thing.  Can you figure out how this is working?

\beginlisp
(define snoc (lambda (x y) (lambda (f) (f x y))))
(define rac (lambda (p) (p (lambda (a b) a))))
(define rdc (lambda (p) (p (lambda (a b) b))))
\endlisp


% \vspace{0.1in}
% {\Large\bf 7. Kons/Kar/Kdr as Higher-Order Procedures}
% 
% Consider the following procedures as a {\em possible} method of 
% implementing data-structures.  Trace through the expressions on the
% right. 
% 
% \begin{tabular}{p{3in}p{3in}}
% {
% \beginlisp
% (define kons
%   (lambda (a b)
%     (lambda (x)
%        (if x a b))))
% (define (kar x) (x \#t))
% (define (kdr x) (x \#f))
% \endlisp
% } & {
% \beginlisp
% (define y (kons 3 4))
% (kar y)
% (kdr y)
% \endlisp
% }
% \end{tabular}
% 
% Here's an even more elegant (albeit more obscure) way of doing it.
% Can you figure out how this is working?
% 
% \beginlisp
% (define kons (lambda (x y) (lambda (f) (f x y))))
% (define kar (lambda (p) (p (lambda (a b) a))))
% (define kdr (lambda (p) (p (lambda (a b) b))))
% \endlisp
% 
% % What would this do?
% % 
% % \beginlisp
% % (define x (kons 1 2))
% % (x +)
% % \endlisp

} % comment
\end{document}



