Filetype PDF | Posted on 31 Jan 2023 | 2 years ago
Authentication
digital resources
220x Filetype PDF File size 0.19 MB Source: people.eecs.berkeley.edu
6.001 SICP Normal Order (Lazy) Evaluation
Alternative models for computation:
Applicative Order:
Normal (Lazy) Order Evaluation evaluate all arguments, then apply operator
Memoization
Streams Normal Order:
pass unevaluated expression to function
evaluate only when needed for primitive operation
6.001 SICP 1 6.001 SICP 2
Applicative Order vs. Normal (Lazy) Order Applicative vs. Normal?
(define (foo x)
(write-line "inside foo") (define (try a b)
(+ x x)) (if (= a 0) 1 b))
(foo (begin (write-line "eval arg") 222)) (try 0 (/ 1 0))
(try 0 (pi-to-this-many-digits 10000000))
Applicative Order: Normal (Lazy) Order:
eval arg inside foo
inside foo eval arg
=> 444 eval arg
We first evaluated argument, => 444
then substituted value into the As if we substituted the
body of the procedure unevaluated expression in the
6.001 SICP body of the procedure 3 6.001 SICP 4
Exercise – Problem with Applicative Order How can we implement lazy evaluation?
Why cant we use define to define any special form? (define (l-apply procedure arguments env) ; changed
(cond ((primitive-procedure? procedure)
E.g write a procedure safe/ that only divide if b <> 0 (apply-primitive-procedure
procedure
(list-of-arg-values arguments env)))
(define (unless pred usual exc) ((compound-procedure? procedure)
(if pred exc usual)) (l-eval-sequence
(define (safe/ a b) (procedure-body procedure)
(unless (= b 0) (/ a b) 0) (extend-environment
(procedure-parameters procedure)
(define (safe/ a b) (list-of-delayed-args arguments env)
(cond ((= b 0) 0) (procedure-environment procedure))))
(else (/ a b)))) (else (error "Unknown proc" procedure))))
6.001 SICP 5 6.001 SICP 6
1
Thunks–a delayed argument Thunks–delay-it and force-it
Abstractly –a thunk is a "promise" to return a value when (define (delay-it exp env) (list 'thunk exp env))
later needed ("forced") (define (thunk? obj) (tagged-list? obj 'thunk))
(define (thunk-exp thunk) (cadr thunk))
Concretely –our (define (thunk-env thunk) (caddr thunk))
representation: (define (force-it obj)
thunk exp env (cond ((thunk? obj)
(actual-value (thunk-exp obj)
(else obj))) (thunk-env obj)))
(delay-it exp env) –promise to evalexp later (define (actual-value exp env)
(force-it exp) –evalexp now, leave no thunks (force-it (l-eval exp env)))
6.001 SICP 7 6.001 SICP 8
Exercise – Applicative vers Normal Order Memo-izing evaluation
Write a function normal-order? That returns #t if the In lazy evaluation an arg is reevaluate each time it is used
language is normal order and #f if the language is In applicative order evaluation argument is evaluated once
applicative order. Can we keep track of values once we’ve obtained them,
(define (normal-order?) and avoid cost of reevaluation?
(let ((x #t))
((lambda (x) ’())
(begin (set! x #f) ’()))
x)) thunk exp env
evaluated- result
6.001 SICP thunk 6.001 SICP
9 10
Thunks–MemoizingImplementation Laziness and Language Design
(define (evaluated-thunk? obj) We have a dilemma with lazy evaluation
(tagged-list? obj 'evaluated-thunk)) Advantage: only do work when value actually needed
(define (thunk-value evaluated-thunk) Disadvantages
(cadr evaluated-thunk)) –not sure when expression will be evaluated; can be
(define (force-it obj) very big issue in a language with side effects
(cond ((thunk? obj) –may evaluate same expression more than once
(let ((result (actual-value (thunk-exp obj)
(thunk-env obj)))) Memoization doesn't fully resolve our dilemma
(set-car! obj 'evaluated-thunk) Advantage: Evaluate expression at most once
(set-car! (cdr obj) result) Disadvantage: What if we want evaluation on each use?
(set-cdr! (cdr obj) '())
result))
((evaluated-thunk? obj) (thunk-value obj))
(else obj))) Alternative approach: give programmer control!
6.001 SICP 11 6.001 SICP 12
2
Variable Declarations: lazy and lazy-memo Syntax Extensions – Parameter Declarations
Handle lazy and lazy-memo extensions in an upward- (define (first-variable var-decls) (car var-decls))
compatible fashion.; (define (rest-variables var-decls) (cdr var-decls))
(lambda (a (b lazy) c (d lazy-memo)) ...) (define declaration? pair?)
"a", "c" are the usual kind of variables (evaluated before (define (parameter-name var-decl)
procedure application (if (pair? var-decl) (car var-decl) var-decl))
"b" is lazy, “Normal Order”: it gets (re)-evaluated each (define (lazy? var-decl)
time its value is actually needed (and (pair? var-decl) (eq? 'lazy (cadr var-decl))))
"d" is lazy-memo; it gets evaluated the first time its (define (memo? var-decl)
value is needed, and then that value is returned again (and (pair? var-decl)
any other time it is needed again. (eq? 'lazy-memo (cadr var-decl))))
6.001 SICP 13 6.001 SICP 14
Controllably Memo-izing Thunks A new version of delay-it
thunk –nevergets memoized Look at the variable declaration to do the right thing...
thunk-memo –first eval is remembered (define (delay-it decl exp env)
evaluated-thunk –memoized-thunk that has (cond ((not (declaration? decl))
already been evaluated (l-eval exp env))
((lazy? decl)
(list 'thunk exp env))
when thunk- exp env ((memo? decl)
forced memo (list 'thunk-memo exp env))
(else (error "unknown declaration:" decl))))
evaluated- result
thunk
6.001 SICP 15 6.001 SICP 16
Change to force-it Order Comparison
(define (force-it obj) (define (foo x)
(cond ((thunk? obj) ;eval, but don't remember it (write-line "inside foo")
(actual-value (thunk-exp obj) (+ x x))
(thunk-env obj)))
((memoized-thunk? obj) ;eval and remember (foo (begin (write-line "eval arg") 222))
(let ((result
(actual-value (thunk-exp obj) Applicative Normal (lazy) MemoizedNormal
(thunk-env obj)))) Order: Order: (Lazy-memo) Order:
(set-car! obj 'evaluated-thunk)
(set-car! (cdr obj) result) eval arg inside foo inside foo
(set-cdr! (cdr obj) '()) inside foo eval arg eval arg
result)) eval arg => 444
((evaluated-thunk? obj) (thunk-value obj)) => 444 => 444
(else obj)))
6.001 SICP 17 6.001 SICP 18
3
Exercise Stream Object
Given this definition of l-abs: A pair-like object, except the cdr part is lazy
(not evaluated until needed):
(define (l-abs (i lazy)) (if (< i 0) (- i) i)) cons-stream
Trace the following use of l-abs: stream-cdr
stream-car
(define (down) (begin (set! x (- x 2)) x) a a
(define x 3) value thunk-memo
(l-abs (down)) (define (cons-stream x (y lazy-memo))
(cons x y))
(define stream-car car)
(define stream-cdr cdr)
6.001 SICP 19 6.001 SICP 20
What will these print? (ex1) Decoupling computation from description
(define s (cons 5 (begin (write-line 7) 9))) Can separate order of events in computer from apparent
(car s) order of events in procedure description
(cdr s) (list-ref
(filter (lambda (x) (prime? x))
(define t (cons-stream 5 (begin (write-line 7) 9))) 100) (enumerate-interval 1 100000000))
(stream-car t) (stream-ref
(stream-filter (lambda (x) (prime? x))
(stream-cdr t) 100) (stream-interval 1 100000000))
6.001 SICP 21 6.001 SICP 22
Decoupling computation from description Decoupling computation from description
(define (stream-interval a b) (define seq (stream-interval 1 10))
(if (> a b) (define y (stream-filter even? seq))
the-empty-stream
(cons-stream a (stream-interval (+ a 1) b)))) Now! Lets do some calculation...
(define (filter-stream pred str) (stream-ref y 3) -> 8
(if (pred (stream-car str))
(cons-stream (stream-car str)
(filter-stream pred (stream-cdr str)))
(filter-stream pred (stream-cdr str))))
6.001 SICP 23 6.001 SICP 24
4
no reviews yet
Please Login to review.
