In section 3.5.1, we showed how to
implement streams as delayed lists.
We introduced special forms delay and
cons-stream, which allowed us
We used a
lambda expression
to construct a
promise
to compute the
cdr
tail
of a stream, without actually fulfilling that promise until later.
| Original | JavaScript | |
| We could use this general technique of introducing special forms whenever we need more control over the evaluation process, but this is awkward. For one thing, a special form is not a first-class object like a procedure, so we cannot use it together with higher-order procedures.[1] Additionally, we were forced to create streams as a new kind of data object similar but not identical to lists, and this required us to reimplement many ordinary list operations (map, append, and so on) for use with streams. | We were forced to create streams as a new kind of data object similar but not identical to lists, and this required us to reimplement many ordinary list operations (map, append, and so on) for use with streams. |
With lazy evaluation, streams and lists can be identical, so there is no need for special forms or for separate list and stream operations. All we need to do is to arrange matters so that cons pair is non-strict. One way to accomplish this is to extend the lazy evaluator to allow for non-strict primitives, and to implement cons pair as one of these. An easier way is to recall (section 2.1.3) that there is no fundamental need to implement cons pair as a primitive at all. Instead, we can represent pairs as proceduresfunctions:[2]
| Original | JavaScript |
| (define (cons x y) (lambda (m) (m x y))) (define (car z) (z (lambda (p q) p))) (define (cdr z) (z (lambda (p q) q))) | function pair(x, y) { return m => m(x, y); } function head(z) { return z((p, q) => p); } function tail(z) { return z((p, q) => q); } |
In terms of these basic operations, the standard definitions of the list operations will work with infinite lists (streams) as well as finite ones, and the stream operations can be implemented as list operations. Here are some examples:
| Original | JavaScript |
| (define (list-ref items n) (if (= n 0) (car items) (list-ref (cdr items) (- n 1)))) (define (map proc items) (if (null? items) '() (cons (proc (car items)) (map proc (cdr items))))) (define (scale-list items factor) (map (lambda (x) (* x factor)) items)) (define (add-lists list1 list2) (cond ((null? list1) list2) ((null? list2) list1) (else (cons (+ (car list1) (car list2)) (add-lists (cdr list1) (cdr list2)))))) (define ones (cons 1 ones)) (define integers (cons 1 (add-lists ones integers))) | function list_ref(items, n) { return n === 0 ? head(items) : list_ref(tail(items), n - 1); } function map(fun, items) { return is_null(items) ? null : pair(fun(head(items)), map(fun, tail(items))); } function scale_list(items, factor) { return map(x => x * factor, items); } function add_lists(list1, list2) { return is_null(list1) ? list2 : is_null(list2) ? list1 : pair(head(list1) + head(list2), add_lists(tail(list1), tail(list2))); } const ones = pair(1, ones); const integers = pair(1, add_lists(ones, integers)); |
| Original | JavaScript |
| ;;; L-Eval input: (list-ref integers 17) ;;; L-Eval value: 18 | L-evaluate input: list_ref(integers, 17); L-evaluate value: 18 |
Note that these lazy lists are even lazier than the streams of chapter 3: The car head of the list, as well as the cdr, tail, is delayed.[3] In fact, even accessing the car head or cdr tail of a lazy pair need not force the value of a list element. The value will be forced only when it is really needed—e.g., for use as the argument of a primitive, or to be printed as an answer.
Lazy pairs also help with the problem that arose with streams in section 3.5.4, where we found that formulating stream models of systems with loops may require us to sprinkle our programs with explicit delay operations, beyond the ones supplied by cons-stream. additional lambda expressions for delays, beyond the ones required to construct a stream pair. With lazy evaluation, all arguments to procedures functions are delayed uniformly. For instance, we can implement procedures functions to integrate lists and solve differential equations as we originally intended in section 3.5.4:
| Original | JavaScript |
| (define (integral integrand initial-value dt) (define int (cons initial-value (add-lists (scale-list integrand dt) int))) int) (define (solve f y0 dt) (define y (integral dy y0 dt)) (define dy (map f y)) y) ;;; L-Eval input: (list-ref (solve (lambda (x) x) 1 0.001) 1000) ;;; L-Eval value: 2.716924 | function integral(integrand, initial_value, dt) { const int = pair(initial_value, add_lists(scale_list(integrand, dt), int)); return int; } function solve(f, y0, dt) { const y = integral(dy, y0, dt); const dy = map(f, y); return y; } |
lazierlazy lists described in this section. How can you take advantage of this extra laziness?
| Original | JavaScript |
| (car '(a b c)) | head(list("a", "b", "c")); |
listsobtained by reading in quoted expressions from the primitive list function are different from the lists manipulated by the new definitions of cons, pair, car, head, and cdr. tail. Modify the evaluator's treatment of quoted expressions so that quoted lists the evaluator such that applications of the primitive list function typed at the driver loop will produce true lazy lists.
lazy trees.