% -*- 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, March 18}

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

{\Large\bf 1. Student Presentation}

Use the environment model to explain the stages of evaluation in the
following example:

\beginlisp
(define (make-incrementer n)
  (lambda (x) (+ x n)))
\null
(define plus-four (make-incrementer 4))
\null
(plus-four 2)
\endlisp

\vskip .1in

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

{\Large\bf 2. Environment Diagrams}

\vskip .1in

{\bf Why are we doing this? }

\begin{itemize}
\item The substitution model broke down when we added side effects!
\item In Object Oriented Programming, we need a model to represent
hierarchies, shadowing, and inheritance. 
\item {\it Looking Ahead:} We'll be writing a meta-circular evaluator
in Scheme.  You'll see that the code we write closely relates to the
rules of the environment model.
\item It's boring, but important:  There's a technical investment now,
but you'll get a lot out of it soon.
\end{itemize}

{\bf What are environment diagrams made of?}

\begin{itemize}
\item {\bf Frames:}  We draw a frame as a box. In the box go
bindings. Every frame (except the frame representing the global
environment) needs to have a link to exactly one other frame.

\item {\bf Bindings:}  A binding is an association between an
identifier (or symbol) to a value. 

\item {\bf Procedure Objects}:  These are special objects (symbolized
by the double bubble) created by evaluating a lambda expression as
described below.
\end{itemize}

\newpage

{\bf What are the rules again? }

\begin{enumerate}
\item {\bf Combination} 

     To evaluate a comibination (other than a special form), first
evaluate the subexpressions and then apply the value of the operator
subexpression to the values of the operand subexpressions.

\item {\bf Looking up an identifier} 

     Look for a value in the current frame.  

     If there is no value for that identifier in the current frame,
     follow the link from the current frame to the one that it is hung
     from. 

     Continue in this manner until we find a binding for the
     identifier we're looking up or until we run out of frames in our
     chain of links (i.e. we come to the global environment). If
     there's no binding in the global environment, the identifier
     we're looking up is an unbound variable.

\item {\bf Lambda} 

     Evaluating a lambda expression will result in a two-part
     procedure object (two circles next to each other -- the double
     bubble).

     The pointer of the left circle points down to a list of the
     parameters and the body of the procedure. 

     {\bf The pointer of the right circle points up to the environment
     frame in which the lambda expression was evaluated. }
     Note that nothing else happens until we apply the procedure. 

\item {\bf Define} 

     Define adds a binding to the frame in which it is evaluated.

\item {\bf Applying a procedure}

     Draw a new environment frame. Bind the parameters to their values
     in this new environment frame.

     Link the new environment frame to the environment frame pointed
     to {\bf by the right circle of the procedure object.}

     Evaluate the body of the procedure in this new environment frame. 

\item {\bf Set!}  \hspace{0.1in} {\tt (set! var expression)} 

     Evaluate the expression with respect to the current environment.

     Lookup the identifier in the current environment (see step \#2)

     Rebind the identifier in the frame it was found to the value of
     the expression.

\item {\bf Let}

     Just de-sugar!  (See next page)

\end{enumerate}

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

\newpage
{\Large\bf 3. Environment Diagrams: Practice}

Consider the following example.  Draw the environment diagrams
corresponding to the following expressions.

\beginlisp
(define kenny 
  (let ((status 'alive))
    (lambda (msg)
      (cond ((eq? msg 'kill)
             (set! status 'dead)
             '(they killed kenny!))
            ((eq? msg 'talk)
             (if (eq? status 'alive) '(mmm umm mmm) '()))))))
\endlisp

Wait!  We didn't say how to evaulate a let.  Well, just de-sugar the
let into a lambda.

\beginlisp
(define kenny 
  ((lambda (status)
     (lambda (msg)
       (cond ((eq? msg 'kill)
              (set! status 'dead)
              '(they killed kenny!))
             ((eq? msg 'talk)
              (if (eq? status 'alive) '(mmm umm mmm) '())))))
    'alive))
\endlisp

Now, what are the values of these expressions?

\beginlisp
(kenny 'talk)  ==>   (mmm umm mmm)
\null
(kenny 'kill)  ==>   (they killed kenny!)
\null
(kenny 'talk)  ==>   ()
\null
\null
\null
\endlisp

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


\newpage
{\Large\bf 4. More Environment Diagrams}

\begin{tabular}{|p{2.8in}|p{3.5in}|}
\hline
\beginlisp
\null
(define make-count-proc-1
  (lambda (f)
    (lambda (x)
      (let ((count 0))
        (cond ((eq? x 'count) count)
              ((eq? x 'reset) 
               (set! count 0)
               0)
              (else
               (set! count (+ count 1))
               (f x)))))))
\null
(define sqrt-c-1 
  (make-count-proc-1 sqrt))
\null
(sqrt-c-1 4)       ==>  2
(sqrt-c-1 'count)  ==>  0
\null
\endlisp
&
\\
\hline
\beginlisp
\null
(define make-count-proc-2
  (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)))))))
\null
(define sqrt-c-2 
  (make-count-proc-2 sqrt))
\null
(sqrt-c-2 4)       ==>   2
(sqrt-c-2 'count)  ==>   1
\null
\endlisp
&
\\
\hline
\beginlisp
\null
(define make-count-proc-3
  (let ((count 0))
    (lambda (f)
      (lambda (x)
        (cond ((eq? x 'count) count)
              ((eq? x 'reset) 
               (set! count 0)
               0)
              (else
               (set! count (+ count 1))
               (f x)))))))
\null
(define sqrt-c-3 
  (make-count-proc-3 sqrt))
\null
(sqrt-c-3 4)       ==>  2
(sqrt-c-3 'count)  ==>  1
\null
\endlisp
& 
\\
\hline
\end{tabular}


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

\end{document}
