CS 22

Clab 36: Streams (almost for free) from Lazy evaluation
More Efficient evaluation

If we make cons non-strict, we get streams from lazy for free. Of course, if we redefine cons, we have to make car and cdr work with the new cons. So try inside the driver loop:

;;; L-Eval input: (define (cons x y) (lambda (m) (m x y))) ;;; L-Eval value: ok ;;; L-Eval input: (define (car z) (z (lambda (p q) p))) ;;; L-Eval value: ok ;;; L-Eval input: (define (cdr z) (z (lambda (p q) q))) ;;; L-Eval value: ok ;;; L-Eval input: (define (intsfrom n) (cons n (intsfrom (+ 1 n)))) ;;; L-Eval value: ok ;;; L-Eval input: (car (cdr (cdr (intsfrom 1)))) ;;; L-Eval value: 3 ;;; L-Eval input: (intsfrom 1) is an infinite stream of integers starting at 1. Pretty awesome stuff.

You do pay a price. By redefining car, cons, and cdr, a lot of old stuff will not work. For example:

;;; L-Eval input: (define lis '(a b c)) ;;; L-Eval value: ok ;;; L-Eval input: lis ;;; L-Eval value: (a b c) ;;; L-Eval input: (car lis) Unknown procedure type -- APPLY (a b c) > To avoid this, you can keep the old strict primitive car, cons, cdr, and just define stream functions as suggested in SICP. We don't have to worry about delay or special forms because we will do this in a lazy evaluator where essentially everything except primitives is non-strict.

But before we do this, let's give the leval driver-loop the ability to load defintions and add them to the-global-environment. This will allow us to save repeated typing into the driver loop. While we are at it, we'll add a couple of primitives to mceval. You can get the original versions back from my pub directory. So, add

(list 'newline newline) (list 'display display) (list 'pair? pair?) to (define primitive-procedures ... in mceval.scm. I will save leval.scm as clab36.scm. Then replace the driver-loop in clab36.scm by: (define (driver-loop) (prompt-for-input input-prompt) (let ((input (read))) (if (equal? input '(quit)) "exiting-mini-eval" (begin (if (tagged-list? input 'myload) (myload (cadr input)) (let ((output (actual-value input the-global-environment))) (announce-output output-prompt) (user-print output))) (driver-loop))))) ;; load and evals in the-global-environment (define (myload fileinstr) (define inport (open-input-file fileinstr)) (define load-loop (lambda () (let ((input (read inport))) (if (eof-object? input) (begin (close-input-port inport) "exiting-load") (begin (eval input the-global-environment) (load-loop)))))) (load-loop)) I claim that once inside the leval driver loop, this will allow us to invoke an expression like (myload "finam.txt") and have the text in the file finam.txt treated as if it have been typed into the lazy evaluator at its input prompt. Note that this is designed to facilitate definitions, NOT interaction.

Let's try it. Put the following in a file calles tes.txt.

(define x 40) (define (square x) (* x x)) (define (sum-of-squares x y) (+ (square x) (square y))) (define (f a) (sum-of-squares (+ a 1) (* a 2))) (define (factorial n) (cond ((= n 1) 1) (else (* n (factorial (- n 1)))) ) ) (define (newfact n) (fact-iter 1 1 n)) (define (fact-iter product counter max-count) (cond ((> counter max-count) product) (else (fact-iter (* counter product) (+ counter 1) max-count)) )) (define (make-withdraw balance) (lambda (amount) (cond ((>= balance amount) (begin (set! balance (- balance amount)) balance)) (else 'insufficient)))) (define w1 (make-withdraw 100)) (define w2 (make-withdraw 100)) Now try the following in the clab36.scm interaction window after pressing execute: Welcome to DrScheme, version 103p1. Language: Graphical Full Scheme (MrEd) Custom. METACIRCULAR-EVALUATOR-LOADED LAZY-EVALUATOR-LOADED > (driver-loop) ;;; L-Eval input: (myload "tes.txt") ;;; L-Eval input: (square 5) ;;; L-Eval value: 25 ;;; L-Eval input: x ;;; L-Eval value: 40 ;;; L-Eval input: (factorial 5) ;;; L-Eval value: 120 ;;; L-Eval input: (w1 20) ;;; L-Eval value: 80 ;;; L-Eval input: (w1 20) ;;; L-Eval value: 60 ;;; L-Eval input: (w2 5) ;;; L-Eval value: 95 ;;; L-Eval input: (quit) This is just to show that myload seems to work. Type the-global-environment back in drscheme and you should see that the stuff in tes.txt is really defined. At least it looks like the lazy evaluator still works for stuff that doesn't need lazy to evaluate. So let's try it on stuff that does need lazy evaluation. Put the following into a file called lazy.txt

(define (try a b) (if (= a 0) 1 b)) (define (unless condition usual-value exceptional-value) (if condition exceptional-value usual-value)) (define (factorial n) (unless (= n 1) (* n (factorial (- n 1))) 1)) (define (improve guess x) (average guess (/ x guess))) (define (average x y) (/ (+ x y) 2)) (define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001)) (define (new-if predicate then-clause else-clause) (cond (predicate then-clause) (else else-clause))) (define (sqrt-iter guess x) (new-if (good-enough? guess x) guess (sqrt-iter (improve guess x) x))) (define (sqrt x) (sqrt-iter 1.0 x)) (define (square x) (* x x)) Now try doing execute again to get a fresh start and then in interaction window: Welcome to DrScheme, version 103p1. Language: Graphical Full Scheme (MrEd) Custom. METACIRCULAR-EVALUATOR-LOADED LAZY-EVALUATOR-LOADED > (driver-loop) ;;; L-Eval input: (myload "lazy.txt") ;;; L-Eval input: (try 0 'cat) ;;; L-Eval value: 1 ;;; L-Eval input: (try 1 'cat) ;;; L-Eval value: cat ;;; L-Eval input: (try 0 (/ 5 0)) ;;; L-Eval value: 1 ;;; L-Eval input: (sqrt 25) ;;; L-Eval value: 5.000023178253949 ;;; L-Eval input: (quit) "exiting-mini-eval" > 5.000023178253949 ;;; L-Eval input: (quit) "exiting-mini-eval" > Look's like Eva Lu's new-if is working and things are lazy.

At long last, we are ready to try stream stuff. Put the following in a file called streams2.txt.

;;sicp stuff (define (cons-stream x y) (lambda (m) (m x y))) (define (stream-car z) (z (lambda (p q) p))) (define (stream-cdr z) (z (lambda (p q) q))) (define the-empty-stream '()) (define stream-null? null?) ;;; If s has at least n+1 elements, returns element n in stream s ;;; counting from zero. If s has fewer elements returns (). (define (stream-ref s n) (cond ((stream-null? s) '()) ((= n 0) (stream-car s)) (true (stream-ref (stream-cdr s) (- n 1))))) (define (stream-map proc s) (if (stream-null? s) the-empty-stream (cons-stream (proc (stream-car s)) (stream-map proc (stream-cdr s))))) (define (stream-for-each proc s) (if (stream-null? s) 'done (begin (proc (stream-car s)) (stream-for-each proc (stream-cdr s))))) (define (stream-filter pred stream) (cond ((stream-null? stream) the-empty-stream) ((pred (stream-car stream)) (cons-stream (stream-car stream) (stream-filter pred (stream-cdr stream)))) (else (stream-filter pred (stream-cdr stream))))) (define (display-stream s) (stream-for-each display-line s)) (define (display-line x) (newline) (display x)) (define (stream-enumerate-interval low high) (if (> low high) the-empty-stream (cons-stream low (stream-enumerate-interval (+ low 1) high)))) (define (integers-starting-from n) (cons-stream n (integers-starting-from (+ n 1)))) (define integers (integers-starting-from 1)) (define (fibgen a b) (cons-stream a (fibgen b (+ a b)))) (define fibs (fibgen 0 1)) ;;; cfk stream->list ;;; returns a list containing the first n elements of stream s ;;; if s contains substreams, at most n top-level elements of a ;;; a substream are converted (define (stream->list n s) (cond ((stream-null? s) '()) ((not (pair? s)) s) ((= n 0) '()) (else (cons (stream->list n (stream-car s)) (stream->list (- n 1) (stream-cdr s)))))) (define (divisible? x y) (= (remainder x y) 0)) (define (sieve stream) (cons-stream (stream-car stream) (sieve (stream-filter (lambda (x) (not (divisible? x (stream-car stream)))) (stream-cdr stream))))) (define primes (sieve (integers-starting-from 2))) Now try execute and play in the interaction window with streams, including infinite streams. Here is a start: Welcome to DrScheme, version 103p1. Language: Graphical Full Scheme (MrEd) Custom. METACIRCULAR-EVALUATOR-LOADED LAZY-EVALUATOR-LOADED > (driver-loop) ;;; L-Eval input: (myload "streams2.txt") ;;; L-Eval input: integers ;;; L-Eval value: (compound-procedure (m) ((m x y)) <procedure-env>) ;;; L-Eval input: (stream-ref integers 5) ;;; L-Eval value: 6 ;;; L-Eval input: (stream->list 20 fibs) ;;; L-Eval value: (0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181) ;;; L-Eval input: Try some regular list stuff to see that we have not lost that.

Well, we have been lazy. Now let's try to be efficient.
Open aneval.scm from your week 12 directory.

This is the analyzing evaluator discussed in section 4.1.7. We'll load it and do a few evaluations and then look at the-global-environment.

metacircular-evaluator-loaded analyzing-metacircular-evaluator-loaded > (driver-loop) ;;; M-Eval input: (define x 40) ;;; M-Eval value: ok ;;; M-Eval input: (define (square x) (* x x)) ;;; M-Eval value: ok ;;; M-Eval input: (square x) ;;; M-Eval value: 1600 ;;; M-Eval input: (define (factorial n) (cond ((= n 1) 1) (else (* n (factorial (- n 1)))) ) ) ;;; M-Eval value: ok ;;; M-Eval input: (factorial 4) ;;; M-Eval value: 24 ;;; M-Eval input: q /home/cfk/cs22/week12/mceval.scm: 257.9-257.39: Unbound variable q > the-global-environment #1=(((factorial square x false true car cdr cons null? list memq member not + - * / = > >= <= < abs remainder integer? sqrt eq?) (procedure (n) #<procedure> #1#) (procedure (x) #<procedure> #1#) 40 #f #t (primitive #<primitive:car>) (primitive #<primitive:cdr>) (primitive #<primitive:cons>) (primitive #<primitive:null?>) (primitive #<primitive:list>) (primitive #<primitive:memq>) (primitive #<primitive:member>) (primitive #<primitive:not>) (primitive #<primitive:+>) (primitive #<primitive:->) (primitive #<primitive:*>) (primitive #<primitive:/>) (primitive #<primitive:=>) (primitive #<primitive:>>) (primitive #<primitive:>=>) (primitive #<primitive:<=>) (primitive #<primitive:<>) (primitive #<primitive:abs>) (primitive #<primitive:remainder>) (primitive #<primitive:integer?>) (primitive #<primitive:sqrt>) (primitive #<primitive:eq?>))) Note that fact and square are bound to the lists: (procedure (n) #<procedure> #1#) (procedure (x) #<procedure> #1#) , respectively.

The procedures embedded in these lists are drscheme procedures, that is procedures in our underlying machine language if you will. They are not mceval procedures. We can test this by using drschemes apply which mceval saved as apply-in-underlying-scheme. Recall that apply-in-underlying-scheme takes two parameters, a function and a list of arguments. It applies the function to the arguments.

> (apply-in-underlying-scheme + '(2 3)) 5 > (lookup-variable-value 'factorial the-global-environment) #2=(procedure (n) #<procedure> #4=(((factorial square x false true car cdr cons null? list memq member not + - * / = > >= <= < abs remainder integer? sqrt eq?) #2# (procedure (x) #<procedure> #4#) 40 #f #t (primitive #<primitive:car>) (primitive #<primitive:cdr>) (primitive #<primitive:cons>) (primitive #<primitive:null?>) (primitive #<primitive:list>) (primitive #<primitive:memq>) (primitive #<primitive:member>) (primitive #<primitive:not>) (primitive #<primitive:+>) (primitive #<primitive:->) (primitive #<primitive:*>) (primitive #<primitive:/>) (primitive #<primitive:=>) (primitive #<primitive:>>) (primitive #<primitive:>=>) (primitive #<primitive:<=>) (primitive #<primitive:<>) (primitive #<primitive:abs>) (primitive #<primitive:remainder>) (primitive #<primitive:integer?>) (primitive #<primitive:sqrt>) (primitive #<primitive:eq?>)))) > > (caddr (lookup-variable-value 'factorial the-global-environment)) #<procedure> > (apply-in-underlying-scheme (caddr (lookup-variable-value 'factorial the-global-environment)) (list (extend-environment '(n) '(5) the-global-environment))) 120 Now let's compare this to what mceval would have given us at the same point. > the-global-environment #1=(((factorial square x false true car cdr cons null? list memq member not + - * / = > >= <= < abs remainder integer? sqrt eq?) (procedure (n) ((cond ((= n 1) 1) (else (* n (factorial (- n 1)))))) #1#) (procedure (x) ((* x x)) #1#) 40 #f #t (primitive #<primitive:car>) (primitive #<primitive:cdr>) (primitive #<primitive:cons>) (primitive #<primitive:null?>) (primitive #<primitive:list>) (primitive #<primitive:memq>) (primitive #<primitive:member>) (primitive #<primitive:not>) (primitive #<primitive:+>) (primitive #<primitive:->) (primitive #<primitive:*>) (primitive #<primitive:/>) (primitive #<primitive:=>) (primitive #<primitive:>>) (primitive #<primitive:>=>) (primitive #<primitive:<=>) (primitive #<primitive:<>) (primitive #<primitive:abs>) (primitive #<primitive:remainder>) (primitive #<primitive:integer?>) (primitive #<primitive:sqrt>) (primitive #<primitive:eq?>))) > Here fact and square are bound to the lists: (procedure (n) ((cond ((= n 1) 1) (else (* n (factorial (- n 1)))))) #1#) (procedure (x) ((* x x)) #1#) , respectively.

The procedure bodies embedded in these (mceval) lists are source code for mceval. In mceval, every time factorial is called the body of factorial must be reanalyzed before it can be evaluated.