CS 22

Clab 35: Lazy evaluation

Last clab, we looked at adding tracing to our own version of the meta-circular evaluator. Now let's take a look at the standard SICP evaluator together. If you copied my pub/cs22/week12 stuff, you should have it in your week12 subdirectory as mceval.scm. Use drscheme to open mceval.scm. We'll take a quick look at it together, try it on a few normal things from last clab, and then try it on: (define (try a b) (if (= a 0) 1 b)) (try 0 'cat) (try 1 'cat) (try 0 (/ 5 0)) (define (unless condition usual-value exceptional-value) (if condition exceptional-value usual-value)) (define (factorial n) (unless (= n 1) (* n (factorial (- n 1))) 1)) (factorial 5) Now open leval.scm (the lazy evaluator). We'll try the lazy evaluator together on all those above comparing and contrasting the behavior of leval to mceval. Then we'll look at the code for leval together. > (driver-loop) ;;; L-Eval input: (define (try a b) (if (= a 0) 1 b)) ;;; L-Eval value: ok ;;; 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: (define (unless condition usual-value exceptional-value) (if condition exceptional-value usual-value)) ;;; L-Eval value: ok ;;; L-Eval input: (define (factorial n) (unless (= n 1) (* n (factorial (- n 1))) 1)) ;;; L-Eval value: ok ;;; L-Eval input: (factorial 5) ;;; L-Eval value: 120 ;;; more when we do Eva Lu's new-if As your author's say: "The basic idea is that, when applying a procedure, the interpreter must determine which arguments are to be evaluated and which are to be delayed. The delayed arguments are not evaluated; instead, they are transformed into objects called thunks. The thunk must contain the information required to produce the value of the argument when it is needed, as if it had been evaluated at the time of the application. Thus, the thunk must contain the argument expression and the environment in which the procedure application is being evaluated.

The process of evaluating the expression in a thunk is called forcing. In general, a thunk will be forced only when its value is needed: when it is passed to a primitive procedure that will use the value of the thunk; when it is the value of a predicate of a conditional; and when it is the value of an operator that is about to be applied as a procedure."

Keep this in mind as we look at leval.
We'll take a quick look at a trace of apply on an evaluation of try. Remember you need to execute:

(require-library "trace.ss") If you mess up your files, you can always get what we started with from my pub/cs22 directory.

You get the idea. We really have lazy evaluation. If we have time, we'll do this sqrt together in clab. Otherwise, try the sqrt below that uses new-if at home. Sometimes lazy is good. :-)

(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)) (sqrt 25) Sometimes lazy is good. :-)

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 new lcar, lcons, lcdr. Of course, if you want this to be really useful, then you have to define ways to print things constructed from lcons in a meaningful way.