% -*- 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 -- Wednesday, April 7}

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

{\Large\bf 1. Student Presentation}

Explain to the class, using box and pointer diagrams, what the
following procedure does:

\beginlisp
(define (make-ring x)
  (set-cdr! (last x) x)
  "The dirty deed is done!")
\endlisp

when applied to the list letters {\tt (define letters (list 'a 'b
'c))}.  (Last is a procedure that returns the last element of a list).
An interesting way to approach this explanation is to write the two
procedures and the list on the board, and then ask the class what
happens when you type {\tt (make-ring letters)}.

\vskip .08in

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

{\Large\bf 2. Review of Environment Diagrams}

Define a one-parameter procedure {\tt prev} that returns as its value
the argument that was passed to it the previous time it was called.
The first time {\tt prev} is called it should return {\tt nil}.

\beginlisp
(prev 'a)       ==>  ()
(prev 3)        ==>  a
(prev (+ 1 5))  ==>  3
\endlisp

\beginlisp
(define prev
  (let ((lastval '()))
    (lambda (x)
      (let ((return lastval))
        (set! lastval x)
        return))))
\endlisp

Now define a procedure {\tt make-prev} that can be used to create the
procedure {\tt prev}.  {\tt Make-prev} should take as an argument the
value that should be returned by the first call to {\tt prev}.  Then
draw the environment diagram for the following expressions:

\begin{tabular}{p{2.2in}p{4in}}
\vspace{-0.8in}
\hbox{
\beginlisp
(define make-prev
  (lambda (lastval)
    (lambda (x)
      (let ((return lastval))
        (set! lastval x)
        return))))
\null
(define prev (make-prev 0)) 
(prev 1) ==> 0
(prev 2) ==> 1
\endlisp
}
&
\hbox{
\begin{tabular}{|p{3.6in}|}
\hline 
\beginlisp
\null 
\null 
\null 
\null 
\null 
\null 
\null 
\null 
\null 
\null 
\null
\endlisp \\
\hline
\end{tabular}
} \\
\end{tabular}

Finally, write the procedure {\tt make-n-prev} that causes a ``delay''
of {\tt n} where the first {\tt n} calls to the procedure return {\tt
val}:  (Hint: {\tt compose} calls to {\tt make-prev})

\begin{tabular}{p{3in}p{3.5in}}
\beginlisp
(define prev-2 (make-n-prev 2 0))
(prev-3 1)      ==> 0
(prev-3 2)      ==> 0
(prev-3 3)      ==> 1
\endlisp
&
\beginlisp
(define (make-n-prev n val)
  (if (= n 0) identity
      (compose (make-prev val) 
               (make-n-prev (- n 1) val))))
\endlisp
\end{tabular}

\newpage
{\Large\bf 3. Review of Object Oriented Programming}

Below is the object oriented system from the March 19th Lecture Notes
(just included for reference):

\beginlisp
(define (get-method object message)
  (object message))
\null
(define (no-method name)
  (list 'no-method name))
\null
(define (no-method? x)
  (if (pair? x)
      (eq? (car x) 'no-method)
      false))
\null
(define (method? x)
  (not (no-method? x)))
\null
(define (ask object message . args)
  (let ((method (get-method object message)))
    (if (method? method)
        (apply method (cons object args))
        (error "No method" message (cadr method)))))
\endlisp

\vskip 0.1in
{\Large\bf 4. Object Oriented Stacks}

Using this object oriented style, write the function {\tt
create-stack} that will create a stack object.  Recall that stacks are
data structures that include the operations {\tt push}, {\tt pop},
{\tt peek}, and {\tt clear}.  Objects get {\tt push}ed on and {\tt
pop}ped off the stack in a last-in-first-out manner.  For example:

\beginlisp
(define s (create-stack))
(ask s 'push 5)
(ask s 'push 3)
(ask s 'pop)            ==> 3
(ask s 'push 1)
(ask s 'pop)            ==> 1
(ask s 'pop)            ==> 5
\endlisp

Complete the function {\tt create-stack}, below:

\beginlisp
(define (create-stack)
  (let ((value '()))
    (lambda (message)
      (case message
        ((PUSH)
         (lambda (self new)
           (set! value (cons new value))))
        ((PEEK)
         (lambda (self) (car value)))
        ((CLEAR)
         (lambda (self) (set! value '())))
        ((POP)
         (lambda (self)
           (let ((return (ask self 'peek)))
             (set! value (cdr value))
             return)))))))
\endlisp

\newpage
{\Large\bf 5. Object Oriented Variables}

Next, let's write an abstraction for variables in the object oriented
style.  We do this so that in addition to the {\tt get} (lookup) and
{\tt set!} operations that we have in scheme, we also want to
implement an {\tt undo!} method that un-does the last {\tt set!}ing of
the variable.  We want to store an arbitrary number of undos.  For
example:

\beginlisp
(define a (create-var 1))
(ask a 'get)                    ==> 1
(ask a 'set! 2)                 
(ask a 'get)                    ==> 2
(ask a 'undo!)
(ask a 'get)                    ==> 1
\endlisp

How can we use stacks to help us with this {\tt undo!}?  Complete the
code for {\tt create-var}, below:

\beginlisp
(define (create-var value)
  (define undo (create-stack))
  (ask undo 'push value)
  (lambda (message)
    (case message
      ((SET!)
       (lambda (self new)
         (ask undo 'push new)))
      ((GET)
        (lambda (self)
          (ask undo 'peek)))
      ((UNDO!)
       (lambda (self)
         (ask undo 'pop))))))
\endlisp

{\Large\bf 6. Object Oriented Pairs}

Well, we wrote it for one variable, now let's write it for pairs.
Consider the function {\tt create-pair} that generates a pair of
variables (the car and the cdr) that you can get or set.  When the
message {\tt undo!} is sent, the last setting gets undone (be it a
{\tt set-car!} or {\tt set-cdr!}.  Consider the following example:

\beginlisp
(define p (create-pair 1 2))
(ask p 'print)                  ==> (1 . 2)
(ask p 'set-car! 3)
(ask p 'print)                  ==> (3 . 2)
(ask p 'set-cdr! 4)
(ask p 'print)                  ==> (3 . 4)
(ask p 'set-car! 5)
(ask p 'print)                  ==> (5 . 4)
(ask p 'undo!)
(ask p 'print)                  ==> (3 . 4)
(ask p 'undo!)
(ask p 'print)                  ==> (3 . 2)
(ask p 'undo!)
(ask p 'print)                  ==> (1 . 2)
\endlisp

Complete the code for {\tt create-pair}, below:

\beginlisp
(define (create-pair car-val cdr-val)
  (define last-change (create-var '()))
  (define the-car (create-var car-val))
  (define the-cdr (create-var cdr-val))
;; Continued on next page
\endlisp

\beginlisp
  (lambda (message)
    (case message
      ((SET-CAR!)
       (lambda (self new)
         (ask last-change 'set! 'car)
         (ask the-car 'set! new)))
      ((SET-CDR!)
       (lambda (self new)
         (ask last-change 'set! 'cdr)
         (ask the-cdr 'set! new)))
      ((CAR)
       (lambda (self) (ask the-car 'get)))
      ((CDR)
       (lambda (self) (ask the-cdr 'get)))
      ((PRINT)
       (lambda (self)
         (newline)
         (display (cons (ask self 'car) (ask self 'cdr)))
         (newline)))
      ((UNDO!)
       (lambda (self)
         (case (ask last-change 'undo!)
           ((CAR) (ask the-car 'undo!))
           ((CDR) (ask the-cdr 'undo!))))))))
\endlisp

{\Large\bf 7. Object Oriented Variables with Redo!}

Now we have the ability to {\tt undo!} the results to set, let's add a
{\tt redo!} feature, such that successive calls to {\tt undo!} and be
taken back using a call to {\tt redo!}.  For example,

\beginlisp
(define a (create-var 1))
(ask a 'set! 2)
(ask a 'undo!)
(ask a 'get)    ==> 2
(ask a 'undo!)
(ask a 'get)    ==> 1
(ask a 'redo!)
(ask a 'get)    ==> 2
\endlisp

Complete the code for {\tt create-var}, below:

\beginlisp
(define (create-var value)
  (define undo (create-stack))
  (define redo (create-stack))
  (ask undo 'push value)
  (lambda (message)
    (case message
      ((SET!)
       (lambda (self new)
         (ask redo 'clear)
         (ask undo 'push new)))
      ((GET)
        (lambda (self)
          (ask undo 'peek)))
      ((UNDO!)
       (lambda (self)
         (ask redo 'push (ask undo 'pop))))
      ((REDO!)
       (lambda (self)
         (ask undo 'push (ask redo 'pop)))))))
\endlisp

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

\end{document}
