CSSE 304 Day 20
Highlights of Day 19 interpreter code.
Add let, if, lambda to the interpreted language (if time) Memoization
For reference during today’s discussion
SOME HIGHLIGHTS OF INTERPRETER STARTING CODE
1
representing procedures
(define-datatype proc-val proc-val?
[prim-proc ; primitive procedure
(name symbol?)])
; Datatype for procedures.
; At first we have only one kind of procedure,
; but more kinds will be added later.
; First kind that we will add:
; closures created by execution of lambda
apply-prim-proc
; Usually an interpreter must define each
; built-in (primitive) procedure
; individually.
(define apply-prim-proc
(lambda (prim-proc args)
(case prim-proc
[(+) (+ (1st args) (2nd args))]
; better?: (apply + args)
[(-) (- (1st args) (2nd args))]
[(*) (* (1st args) (2nd args))]
[(add1) (+ (1st args) 1)]
[(sub1) (- (1st args) 1)]
[(cons) (cons (1st args) (2nd args))]
[(=) (= (1st args) (2nd args))]
[else (eopl:error ‘apply-prim-proc
“Bad primitive procedure name:”
prim-op)])))
2
build the initial environment
(define *prim-proc-names* ‘(+ – * add1 sub1 cons =))
(define init-env ; initial environment
(extend-env ; only contains
; primitive procedures.
*prim-proc-names* ; Recall that an
; environment
; associates values
(map prim-proc ; (not expressions)
; with variables.
*prim-proc-names*)
(empty-env)))
Add let, if, lambda
ENHANCE THE INTERPRETER
3
top-level-eval
(modified to support local envs)
(define global-env init-env)
(define top-level-eval
(lambda (form)
(eval-exp form
(empty-env))))
So eval-exp now takes a second argument, which is the current environment.
eval-exp code
(modified to support local envs)
(define eval-exp
(let ([identity-proc (lambda (x) x)])
(lambda (exp env)
(cases expression exp
[lit-exp (datum) datum]
[var-exp (id) ; look up its value.
(apply-env env
id
identity-proc ; procedure to call if id is in env (lambda () ; procedure to call if id is not in env
(apply-env global-env ; was init-env
id
identity-proc ; call if id is in global-env (lambda () ; call if id not in global-env
(error ‘apply-env
“variable ~s is not bound”
id)))))]
;; more cases on next slide
4
eval-exp code
(modified to support local envs)
(define eval-exp
(lambda (exp env)
(cases expression exp
;…
; cases from the previous slide ;…
[app-exp (rator rands)
(let ([proc-value (eval-exp rator env)]
[args (eval-rands rands env)])
(apply-proc proc-value args))]
[else (error ‘eval-exp
“Bad abstract syntax: ~a” exp)])))
eval-rands and apply-proc
(define eval-rands
(lambda (rands env)
(map (lambda (e)
(eval-exp e env)) rands)))
; Apply a procedure to its arguments.
; At this point, we only have primitive procedures.
; User-defined procedures will be added later.
(define apply-proc ; should we add an env argument? (lambda (proc-value args)
(cases proc-val proc-value
[prim-proc (op) (apply-prim-proc op
args)]
[else (error ‘apply-proc
“Attempt to apply bad procedure:”
proc-value)])))
Add let, if, lambda (on the whiteboard)
(define-datatype expression expression? [let-exp
(vars (list-of symbol?))
(exps (list-of expression?))
(bodies (list-of expression?))] . . .)
5
memoization call-with-values
(both of these topics are part of A15)
MEMOIZATION (A BRIEF DIVERSION ABOUT EFFICIENCY)
6
Background: the assoc family
• A list of 2-lists, is called an association list.
Each 2-list is treated as a key-value pair.
• The assoc procedure finds a key and its
associated value (along with the rest of the list).
• > (assoc ‘c ‘((a 1) (b 2) (c 3) (d 4) (e 5))) (c 3)
• assoc uses equal? when testing the keys. assq uses eq? assv uses eqv?
Example of a Memoizing (Caching) Function
Without caching:
(define fibonacci
(lambda (n)
(if (or (zero? n) (= n 1))
1
(+ (fibonacci (- n 2))
(fibonacci (- n 1))))))
Very simple to define, but it has a problem!
7
Timing the fibonacci function
>(define time-fib
(lambda (n)
(collect)
(time
(fibonacci n))))
>(time-fib 30)
no collections
770 ms elapsed cpu time 770 ms elapsed real time 0 bytes allocated
1346269
> (time-fib 31) (time (fibonacci n))
no collections
1220 ms elapsed cpu time
1220 ms elapsed real
time
0 bytes allocated
2178309
> (time-fib 32) (time (fibonacci n))
no collections
2010 ms elapsed cpu
time
2020 ms elapsed real
time
0 bytes allocated
3524578
> (time-fib 33) (time (fibonacci n))
no collections
3240 ms elapsed cpu
time
3240 ms elapsed real
time
0 bytes allocated
5702887
fibonacci with caching (memoization)
(define fib-memo (let ([max 1]
[sofar ‘((1 . 1) (0 . 1))])
(lambda (n)
(if (<= n max)
(cdr (assq n sofar))
(let* ([v1 (fib-memo (- n 1))]
[v2 (fib-memo (- n 2))]
[v3 (+ v2 v1)])
(set! max n)
(set! sofar (cons
(cons n v3) sofar))
v3)))))
max and sofar are used to cache previously computed values of fib-memo
8
Timing the fib-memo function
>(define time-memo
(lambda (n)
(collect)
(time (fib-memo n))))
> (time-memo 30)
(time (fib-memo n))
no collections
0 ms elapsed cpu time
0 ms elapsed real time
464 bytes allocated
1346269
> (time-memo 120) (time (fib-memo n))
no collections
0 ms elapsed cpu time
0 ms elapsed real time
2704 bytes allocated
8670007398507948658051921
> (time-memo 480)
(time (fib-memo n))
no collections
10 ms elapsed cpu time
10 ms elapsed real time
18168 bytes allocated
149131696402327401278275120573021480 636486507112094019661502199265467 79697987984279570098768737999681
> (time-memo 1920)
(time (fib-memo n))
no collections
0 ms elapsed cpu time
0 ms elapsed real time
201096 bytes allocated
130548509585974025289403903399342332 195533153264149057012466373585260 855440922729886517665791348772431 832647927017501018894903833887134 985970384628647382836605175649149 276410087245331524919858263915987 811572358836471880641113736192407 569546597943636025003714415011830 903968180799768315063395136835768 779659490153054076902321531244169 951765324840758127291467883962057 798767411224848804669073085015870 721
Wouldn’t it be nice …
• if a procedure could return multiple values? • Like in Python:
9