MASSACHVSETTS INSTITVTE OF TECHNOLOGY
Department of Electrical Engineering and Computer Science
6.001---Structure and Interpretation of Computer Programs
Spring Semester, 1999
Recitation -- Wednesday, April 21
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:
(define (memoize proc) (let ((run? #f) (result #f)) (lambda () (cond ((not run?) (set! result (proc)) (set! run? #t) result) (else result)))))
Consider now what happens if we change the definition of delay
as follows.
(delay s) <==> (memoize (lambda () s))
Draw the environment diagrams for the following expressions with and
without stream memoization.
(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))
Let's take a look at our old friend make-acct:
(define make-acct (lambda (balance) (lambda (msg . args) (case msg ((BALANCE) balance) ((DEPOSIT) (set! balance (+ balance (cadr args))))))))
(define a (make-acct 100)) (a 'balance) ==> 100
(define b (let ((balance 1000)) a)) (b 'balance) ==> 100
Why does b have a balance of 100 and not 1000? Quickly sketch the environment diagram for the above expressions to see why.
Consider a new special form called 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 c by rescoping a (instead of by calling make-acct).
(define c (let ((balance 1000)) (rescope a))) (c 'balance) ==> 1000
Let's add the special form rescope to the mc-evalutator.
(1) Define Data Abstraction
HiddenAnswer (define (rescope? exp) (tagged-list? exp 'rescope)) (define (rescope-exp exp) (cadr exp)) EndOfAnswer
(2) Add the appropriate cond clause to mc-eval
HiddenAnswer ((rescope? exp) (eval-rescope exp env)) EndOfAnswer
(3) Write eval-rescope
(define (eval-rescope exp env) HiddenAnswer (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"))) EndOfAnswer)
Consider a new special form called inscope that takes a procedure and an expression and then evaluates the expression with respect to the procedure's environment. For example
(define d (inscope a (lambda () (set! balance 'loser))))
(a 'balance) ==> 100 (d) (a 'balance) ==> loser
Let's add the special form inscope to the mc-evalutator.
(1) Define Data Abstraction
HiddenAnswer (define (inscope? exp) (tagged-list? exp 'inscope)) (define (inscope-procedure exp) (cadr exp)) (define (inscope-body exp) (caddr exp)) EndOfAnswer
(2) Add the appropriate cond clause to mc-eval
HiddenAnswer ((inscope? exp) (eval-inscope exp env)) EndOfAnswer
(3) Write eval-inscope
(define (eval-inscope exp env) HiddenAnswer (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"))) EndOfAnswer)