% -*- Mode: Tex -*-

%\input /home/welg/6001mac.tex
%\input /homes/welg/6001/6001mac.tex
%\input /zu/scheme/6001ARCHIVE/fall89/6001mac.tex
\input 6001mac.tex

\def\fbox#1{%
  \vtop{\vbox{\hrule%
              \hbox{\vrule\kern3pt%
                    \vtop{\vbox{\kern3pt#1}\kern3pt}%
                    \kern3pt\vrule}}%
        \hrule}}

\def\emptybox#1#2{\fbox{\vbox to #2{\hbox to #1 {\null}}}}

\def\pscenter#1{\hbox to\hsize{\hss\psadobenomag{#1}\hss}}

\setlength{\textheight}{9.2in}

\begin{document}

\psetheader{Spring Semester, 1998}{Recitation -- Friday, March 20}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\Large\bf 1. Student Presentation}

Explain, using the environment model, how a procedure named
make-counter (which you are going to write) works. A counter is a
procedure that one calls with no arguments. On each successive call,
it returns a value that is one larger than the previous value it
returned. The procedure make-counter takes one argument, the initial
value of the counter it will create. The first time someone uses
counter, it should return the initial value plus one.

\vskip .1in

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\Large\bf 2. Counting Fibs}

Recall the function {\tt fib-1} that takes an integer {\tt n} and
computes the {\tt n}'th Fibonacci number.  

\begin{tabular}{p{3in}p{2.5in}}
\vspace{-1.25in}
\beginlisp
(define fib-1
  (lambda (n)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          (else 
           (+ (fib-1 (- n 1))
              (fib-1 (- n 2)))))))
\endlisp
&
\psfig{figure=fib1.ps,height=1.25in}
\end{tabular}

\vspace{-0.2in}

What is the Order of Growth in Time for the procedure {\tt fib-1}?
This is a tough one to figure out.  Maybe this tree will help.
Consider the number of recursive calls to {\tt fib-1} when the
following is evaluated: {\tt (fib-1 5)}

What if we want to see exactly how many times fib-1 is being called?
Recall the function {\tt make-count-proc} from last section.  How can
we use {\tt make-count-proc} to define {\tt fib-2} that will keep a
count of the number of recursive calls?

\begin{tabular}{p{3in}p{3in}}
\beginlisp
(define make-count-proc
  (lambda (f)
    (let ((count 0))
      (lambda (x)
        (cond ((eq? x 'count) count)
              ((eq? x 'reset) 
               (set! count 0)
               0)
              (else
               (set! count (+ count 1))
               (f x)))))))
\endlisp
&
\beginlisp
(define fib-2
  (make-count-proc
   (lambda (n)
     (cond ((= n 0) 0)
           ((= n 1) 1)
           (else 
            (+ (fib-2 (- n 1))
               (fib-2 (- n 2))))))))
\null
(fib-2 5)        ==>  5
\null
(fib-2 'count)   ==>  15
\endlisp
\end{tabular}

Take a look at these calls to fib-2:

\beginlisp
(fib-2 'reset)          ==> 0
(fib-2 30)              ==> 832040
(fib-2 'count)          ==> 2692537
\null
\endlisp

That's pretty inefficient!  We're recursively calling {\tt fib-2} over
and over again with the same argument and keep computing things we've
already computed before.  How can we fix this?

\newpage

{\Large\bf 3. Memoizing}

Recall that the procedure {\tt make-count-proc} takes in a procedure
and returns a very similar procedure (from the caller's point of
view), but this new procedure keeps some local state around and does
something else each time it is called.  

Consider the procedure {\tt memoize} that takes in a procedure of one
argument and returns a procedure that keeps track of the all
previously computed values.  If a value passed in was passed in
before, the procedure simply returns the saved value.  Write the
procedure {\tt memoize}:

\beginlisp
(define memoize 
  (lambda (g)
    (let ((table '()))
      (lambda (y)
        (let ((result (assoc y table)))
          (if (pair? result)
              (cadr result)
              (let ((result (g y)))
                (set! table (cons (list y result) table))
                result)))))))
\endlisp

Now define {\tt fib-3} that uses memoization and a counter.

\begin{tabular}{p{3.5in}p{2.5in}}
\vspace{-1.25in}
\beginlisp
(define fib-3
  (make-count-proc
   (memoize
    (lambda (n)
      (cond ((= n 0) 0)
            ((= n 1) 1)
            (else 
             (+ (fib-3 (- n 1))
                (fib-3 (- n 2)))))))))
\endlisp
&
\psfig{figure=fib2.ps,height=1.25in}
\end{tabular}

What is the Order of Growth in Time of {\tt fib-3}? 

\beginlisp
(fib-3 'count)		==> 0
(fib-3 30)		==> 832040
(fib-3 'count)		==> 59
\null 
\endlisp

{\bf Challenge:} Draw the Environment Diagram for the definition of
{\tt fib-3} (above) and then for the expression {\tt (fib-3 3)}.

\vskip 0.1in

\begin{tabular}{|p{6.3in}|}
\hline 
\beginlisp
\null 
\null 
\null 
\null 
\null 
\null 
\null
\null 
\null 
\null 
\null 
\null 
\null 
\null 
\null 
\null
\endlisp \\
\hline
\end{tabular}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
