% -*- Mode: Tex -*-

\def\AnswerSheet{1}

\input 6001mac.tex

\begin{document}

\psetheader{Spring Semester, 1999}{Recitation -- Friday, March 19}

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

{\Large\bf 1. Environment Diagrams}

{\bf Why are we doing this? }

\vspace{-.1in}

\begin{itemize}
\itemx The substitution model broke down when we added side effects!
\itemx In Object Oriented Programming, we need a model to represent
hierarchies, shadowing, and inheritance. 
\itemx {\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.
\itemx It's boring, but important:  It's a technical investment now,
but you'll get a lot out of it soon.
\end{itemize}

{\bf What are environment diagrams made of?}
\vspace{-0.1in}


\begin{itemize}
\itemx {\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.

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

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

\vspace{-0.1in}

{\bf What are the rules again? }

\begin{enumerate}
\itemx {\bf Combination} 

     To evaluate a comibination with respect to an environment, first
     evaluate the subexpressions with respect to the environment and
     then apply the value of the operator subexpression to the values
     of the operand subexpressions.

\itemx {\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
     linked 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.

\itemx {\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. 

\itemx {\bf Define} 

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

\itemx {\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. 

\itemx {\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.

\itemx {\bf Let}

     Just de-sugar!  (See examples, below)

\end{enumerate}

{\Large\bf 2. A Simple Example}

Evaluate the expressions below, following the rules of the environment
model.  Draw the cooresponding environment diagram in the box.

\beginlisp
(define (fact n)
  (if (= n 1) 
      1   
      (* n (fact (- n 1)))))
\null
(define n 6)
(fact 3)
\null
\null
\null
\endlisp

\begin{tabular}{|p{6.5in}|}
\hline 
\beginlisp
\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 3. Let}

We haven't defined the rule for {\tt let}.  Well, let's just desugar
it:

\begin{tabular}{p{2in}p{4in}}
\vspace{-0.5in}
\beginlisp
(let ((x (+ 2 5))
      (y 7))
  (* x y))
     $\Leftarrow\Rightarrow$
((lambda (x y) (* x y)) 
  (+ 2 5) 7)
\endlisp
&
\begin{tabular}{|p{4.0in}|}
\hline 
\beginlisp
\null
\null 
\null
\null 
\null 
\endlisp
\\
\hline 
\end{tabular}
\end{tabular}

{\tt Let} just creates another frame linked from the current frame.
The bindings in that frame are {\tt let}-variables bound to the result
of evaluating the {\tt let}-expressions with respect to the original
environment.  

{\Large\bf 4. Another Example}

Consider the example below using higher order procedures.  Use the
environment model to evaluate the following expressions.

\beginlisp
(define make-counter
  (lambda () 
    (let ((count 0))
      (lambda () 
        (set! count (+ 1 count))
        count))))
\null
(define days (make-counter))
(define dollars (make-counter))
\null
(days)    \RA \ANSWER{1}
(days)    \RA \ANSWER{2}
(dollars) \RA \ANSWER{1}
(dollars) \RA \ANSWER{2}
\null
\endlisp

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


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

\end{document}



