% -*- 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)))
\null
\null
\null
\null
\null
)
\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
\null
\null
\null
\null
)
\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)))
\null
\null
\null
)
\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
        ((PEEK) (lambda (self) (car value)))
        ((CLEAR) (lambda (self) (set! value '())))
        ((PUSH)
%         (lambda (self new)
%           (set! value (cons new value)))
\null
\null
        )
        ((POP)
%         (lambda (self)
%           (let ((return (ask self 'peek)))
%             (set! value (cdr value))
%             return))
\null
\null
\null
\null
        )))))
\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)
\null
\null
  (lambda (message)
    (case message
      ((SET!)
%        (lambda (self new)
%          (ask undo 'push new))
\null
\null
        )
      ((GET)
%         (lambda (self)
%           (ask undo 'peek))
\null
\null
        )
      ((UNDO!)
%       (lambda (self)
%         (ask undo 'pop)))
\null
\null
        )))
\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 the-car (create-var car-val))
  (define the-cdr (create-var cdr-val))
%  (define last-change (create-var '()))
\null
;; Continued on next page
\endlisp

\beginlisp
  (lambda (message)
    (case message
      ((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)))
      ((SET-CAR!)
       (lambda (self new)
%         (ask last-change 'set! 'car)
%         (ask the-car 'set! new))
\null
\null
        )
      ((SET-CDR!)
       (lambda (self new)
%         (ask last-change 'set! 'cdr)
%         (ask the-cdr 'set! new))
\null
\null
        )
      ((UNDO!)
       (lambda (self)
%         (case (ask last-change 'undo!)
%           ((CAR) (ask the-car 'undo!))
%           ((CDR) (ask the-cdr 'undo!)))
\null
\null
        )))))
\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))
\null
  (ask undo 'push value)
  (lambda (message)
    (case message
      ((GET) (lambda (self) (ask undo 'peek)))
      ((SET!) 
        (lambda (self new) 
         (ask redo 'clear)
         (ask undo 'push new)))
      ((UNDO!)
       (lambda (self)
%         (ask redo 'push (ask undo 'pop))
\null
        ))
      ((REDO!)
       (lambda (self)
%         (ask undo 'push (ask redo 'pop))
\null
        )))))
\endlisp

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

\end{document}
