6.001 Recitation – 11 April,
2003
RI: Konrad
Tollmar
• Eval / Apply revisit
• Lazy evaluation
1. Break
Implement a special-form break that allow you to stop your code and inspect the environment
(define (tag-check e sym) (and (pair? e) (eq? (car
e) sym)))
(define (break? e) (tag-check e ’break*))
(define (meval exp env)
(cond
((self-evaluating? exp) exp)
((variable? exp) (lookup-variable-value exp env))
((quoted? exp) (text-of-quotation exp))
((assignment? exp) (eval-assignment exp env))
((definition? exp) (eval-definition exp env))
((break? exp) (eval-break exp env))
(define (eval-break exp env)
(prompt-for-input input-prompt)
(let
((input (read)))
(let
((output (meval input env)))
(display output))))
2. Normal vers
Applicative Order
Given:
(define
(try a b)
(if (= a 0) 1 b))
What
happen if we try:
(try
0 (/ 1 0))
(try
0 (pi-to-this-many-digits 10000000))
In Normal vers Applicative Order
?
0 and 0 vers error
and a loooong wait.
3. Eval in Normal Order
(define count 0)
(define p
( (begin (set! count (+ count 1)) (* x 3)) lazy-memo))(define x 5)
count => 0
p => #[promise 54]
(force p) => 15
p => #[promise 54]
count => 1
(force p) => 15
count => 1
4. Test Normal vers Applicative Order
Write a function normal-order? That returns #t if the language is normal order and #f if the language is applicative order.
(define
(normal-order?)
(let ((x #t))
((lambda
(x) ’())
(begin (set! x #f) ’()))
x))
5. Lazy Lists
What will happen when we evaluate the following?
(define ones (cons 1 ones))
(1 1 1 ………)
How can we use this to produce sequences of number?
(define (add-list list1 list2)
(cond
((null? list1 list2)
((null? list2 list1)
(else
(cons (+ (car list1) (car list2))
(add-list (cdr list1) (cdr list2))))))
(define intergers (cons 1 (add-list (ones
integers)))
6. Create Infinite
Streams
(define
(cons-stream x (y lazy-memo))
(cons x y))
(define
stream-car car)
(define stream-cdr cdr)
(define
(stream-interval a b)
(if (> a b)
the-empty-stream
(cons-stream a (stream-interval (+ a 1)
b))))
(define seq
(stream-interval 1 10))
Show how we could create a stream of integers in an alternative way, given the stream ones (1 1 1 1 ….) and the procedure add-streams.
(define
ones (cons-streams 1 ones))
(define
(add-streams s1 s2)
(cons-stream (+ (stream-car s1) (stream-car
s2))
(add-streams
(stream-cdr s1) (stream-cdr s2)))))
(define
integers
(cons-stream 1
(add-streams ones integers))
7. Define Fibonacci
numbers with stream.
Write a procedure, (fibs), that returns a stream of Fibonacci numbers. The Fibonacci series goes
(0 1 1 2 3 5 8
13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 ...)
It starts with two 1's, then each successive value is the sum of the previous two.
Hint:
use add-streams
F(n)
= F(n-2) + F(n-1)
(define fibs
(cons-stream
0
(cons-stream
1
(add-stream (stream-cdr fibs)
fibs))))