% -*- Mode: Tex -*-

\def\AnswerSheet{1}

\input 6001mac.tex

\begin{document}

\psetheader{Spring Semester, 1999}{Recitation -- Wednesday, March 17}

{\Large\bf 0.  Administrivia}
\begin{itemize}
\itemx Don't miss lecture tomorrow!  Really.
\itemx PS \#4 is due today (in section or, for Sandia, 36-115, for
Hooman, 36-117).
\itemx PS \#5 is due on March 31st (not during spring break) 
\end{itemize}

{\Large\bf 1.  Functions Aren't Functions Anymore}

Up until now, every time we called a procedure with the same
arguments, we got the same value back.  For example, if {\lisp (foo
7)} returned {\lisp 12}, then {\bf every time} we called {\lisp (foo
7)} we would get back 12.  Consider the example below.  Draw the box
and pointer diagram and evaluate the following expressions.

\begin{tabular}{p{3.2in}p{3.2in}}
\beginlisp
(define count (list 0))
(define (counter)
  (set-car! count (+ (car count) 1))
  (car count))
\endlisp
&
\beginlisp
(counter)  \RA  {\ANSWER 1}
(counter)  \RA  {\ANSWER 2}
(counter)  \RA  {\ANSWER 3}
\endlisp
\end{tabular}

Notice that we're in danger if someone else is using the variable
count.  We'll step on each other's feet.  How can we prevent this from
happening?  

\beginlisp
(define counter
\ANSWER{
  (let ((count (list 0)))
    (lambda ()
      (set-car! count (+ (car count) 1))
      (car count)))
})
\endlisp

We'll see more tomorrow in lecture on how and why this technique of
local state works. 

{\Large\bf 2.  Buffers}

Write a function called {\lisp buffer} that takes one argument {\lisp
x} and at each call, it returns the argument of the previous call to
buffer.  For example:

\begin{tabular}{p{2in}p{4in}}
\beginlisp
(buffer 1)      \RA \#f
(buffer 7)      \RA 1
(buffer 'x)     \RA 7
(buffer '(2 5)) \RA x
(buffer +)      \RA (2 5)
\endlisp
& 
\beginlisp
(define buffer
\ANSWER{
  (let ((store (list \#f)))
    (lambda (x)
       (let ((result (car store)))
         (set-car! store x)
         result)))
})
\endlisp
\end{tabular}

{\Large\bf 3.  Remembering Values}

Write a function called {\lisp seen?} that takes one argument and
returns \#t only if that function has been called before with that
argument.  Assume you have the function {\lisp element?} that takes an
object and a list, and returns \#t if the object is in the list.

\begin{tabular}{p{2in}p{4in}}
\beginlisp
(seen? 1)  \RA \#f
(seen? 'x) \RA \#f
(seen? 1)  \RA \#t
(seen? 'y) \RA \#f
(seen? 'x) \RA \#t
(seen? 'y) \RA \#t
\endlisp
& 
\beginlisp
(define seen?
\ANSWER{
  (let ((store (list 'values)))
    (lambda (x)
       (cond ((element? x (cdr store)) \#t)
             (else (set-cdr! store (cons x (cdr store)))
                   \#f))))
})
\endlisp
\end{tabular}

{\Large\bf 4.  List Mutation -- Rings}

\begin{tabular}{p{4in}p{2in}}
\vspace{-1.5in}
Rings are circular structures similar to lists.  If we define a ring r,
{\lisp (define r (make-ring '(1 2 3 4)))}, the following is true:

\beginlisp
(nth 0 r)
\RA 1
(nth 1 r)
\RA 2
...
(nth 4 r)
\RA 1
\endlisp
& \psfig{figure=r13-1.ps,height=1.5in}
\end{tabular}

\vspace{-0.1in}

Write the function {\lisp make-ring!} that takes a list and makes a
ring out of it.  {\em Hint: It might be helpful to write a helper
function called {\lisp last-pair}.}

\beginlisp
(define (make-ring! ring-list)
\ANSWER{
   (define (last-pair lst)
      (if (null? (cdr lst)) 
          lst
          (last-pair (cdr lst))))
   (set-cdr! (last-pair ring-list) ring-list)
   ring-list
})
\endlisp

Write the procedure {\lisp rotate-left} that takes a ring and returns
a ring that has been rotated one to the right.  

\begin{tabular}{p{3.5in}p{3in}}
\beginlisp
(define (rotate-left ring)
\ANSWER{
   (cdr ring)
})
\endlisp
&
\beginlisp
(define r1 (rotate-left r))
(nth 0 r1) 
\RA 2
\endlisp
\end{tabular}

We can also rotate a ring to the right.  Rotating to the right is
harder than rotating to the left.  Define a procedure {\lisp
ring-length} that will tell us the length of the ring (which is the
length of the original list). {\em Hint: remember {\lisp eq?}}

\beginlisp
(define (ring-length ring)
\ANSWER{
   (define (helper n here)
      (if (eq? here ring)
          n
          (helper (+ 1 n) (cdr here))))
   (helper 1 (cdr ring))
})
\endlisp

Now write the procedure {\lisp rotate-right}.  If you're tired of
writing helper procedures, you can use repeated.

\begin{tabular}{p{3.5in}p{3in}}
\beginlisp
(define (rotate-right ring)
\ANSWER{
  ((repeated rotate-left 
     (- (ring-length ring) 1)) ring)
})
\endlisp
&
\beginlisp
(define r2 (rotate-right r))
(nth 0 r1) 
\RA 4
\endlisp
\end{tabular}

{\Large\bf 5.  Append!}

Recall the function {\lisp append} that takes two lists and returns a
list of the two appended.  Recall that to do this, we made a {\bf
copy} of the first list and {\lisp cons}'d it onto the second.  Now
that we had side effects, we can append two lists without creating a
copy of one of them.  Assuming you have the function {\lisp last-pair}
that we wrote above, write the function {\lisp append!}.

\beginlisp
(define (append! x y)
\ANSWER{
  (set-cdr! (last-pair x) y)
  x
})
\endlisp

\end{document}


