% -*- Mode: Tex -*-

\def\AnswerSheet{1}

\input 6001mac.tex

\begin{document}

\psetheader{Spring Semester, 1999}{Recitation -- Wednesday, April 21}

{\Large\bf 1. Memoization and Streams}

Memoization is a technique to improve performance by recording
previously computed values. Whenever a computation is repeated, the
recorded result is used instead of performing the same work a second
time.  Today, we will look at a simple example of how to memoize a
procedure:

\beginlisp
(define (memoize proc)
  (let ((run? \#f) (result \#f))
    (lambda ()
      (cond ((not run?)
             (set! result (proc))
             (set! run? \#t)
             result)
            (else result)))))
\endlisp

Consider now what happens if we change the definition of {\tt delay}
as follows.   \\
{\tt (delay s) <==> (memoize (lambda () s))} \\
Draw the environment diagrams for the following expressions with and
without stream memoization.

\beginlisp
(define a 5)
(define flip (cons-stream a (cons-stream (- a) flip)))
(stream-car (stream-cdr a))
(set! a 7)
(stream-car (stream-cdr a))
\endlisp

\vspace{1in}

{\Large\bf 2.  Playing with Scope}

Let's take a look at our old friend {\tt make-acct}:

\beginlisp
(define make-acct 
  (lambda (balance)
    (lambda (msg . args)
      (case msg 
        ((BALANCE) balance)
        ((DEPOSIT) (set! balance (+ balance (cadr args))))))))
\null
(define a (make-acct 100))
(a 'balance)            ==> 100
\null
(define b
  (let ((balance 1000))
    a))
(b 'balance)            ==> 100
\endlisp

Why does {\tt b} have a balance of 100 and not 1000?  Quickly sketch
the environment diagram for the above expressions to see why.

% Dynamic vs. Static Scoping.

\newpage
{\Large\bf 3. Re-scoping a procedure}

Consider a new special form called {\tt rescope} that takes a
procedure and returns a procedure with the same parameters and body,
but whose environment pointer points to the current environment.
Consider defining another account {\tt c} by rescoping {\tt a}
(instead of by calling {\tt make-acct}).

\beginlisp
(define c
  (let ((balance 1000))
    (rescope a)))
(c 'balance)            ==> 1000
\endlisp

Let's add the special form {\tt rescope} to the mc-evalutator.

{\bf (1) Define Data Abstraction}

\beginlisp
\ANSWER{
(define (rescope? exp) (tagged-list? exp 'rescope))
(define (rescope-exp exp) (cadr exp))
}
\endlisp

{\bf (2) Add the appropriate {\tt cond} clause to {\tt mc-eval}}

\vspace{-0.1in}
\beginlisp
\ANSWER{        ((rescope? exp) (eval-rescope exp env))}
\endlisp

{\bf (3) Write {\tt eval-rescope}}

\beginlisp
(define (eval-rescope exp env)
\ANSWER{
  (let ((proc (mc-eval (rescope-exp exp) env)))
    (if (compound-procedure? proc)
        (make-procedure (procedure-parameters proc)
                        (procedure-body proc)
                        env)
        (error "Bad argument to rescope")))
})
\endlisp

\vskip 0.1in

{\Large\bf 4. Grabbing procedure's scope}

Consider a new special form called {\tt inscope} that takes a
procedure and an expression and then evaluates the expression with
respect to the procedure's environment. 
For example

\beginlisp
(define d
  (inscope a (lambda () (set! balance 'loser))))
\null
(a 'balance)            ==> 100
(d)
(a 'balance)            ==> loser
\endlisp

Let's add the special form {\tt inscope} to the mc-evalutator.

{\bf (1) Define Data Abstraction}

\beginlisp
\ANSWER{
(define (inscope? exp) (tagged-list? exp 'inscope))
(define (inscope-procedure exp) (cadr exp))
(define (inscope-body exp) (caddr exp))
}
\endlisp

{\bf (2) Add the appropriate {\tt cond} clause to {\tt mc-eval}}

\vspace{-0.1in}
\beginlisp
\ANSWER{
        ((inscope? exp) (eval-inscope exp env)) 
}
\endlisp

{\bf (3) Write {\tt eval-inscope}}

\beginlisp
(define (eval-inscope exp env)
\ANSWER{
  (let ((proc (mc-eval (rescope-exp exp) env)))
    (if (compound-procedure? proc)
        (mc-eval (inscope-body exp)       
              (procedure-environment proc))
        (error "Bad procedure to inscope")))
})
\endlisp

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



\end{document}
