In section 3.5.1, we showed how to
implement streams as delayed lists.
We used a function definition expression
to construct a promise

to compute
the
`tail`
of a stream, without actually fulfilling that promise
until later.
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
separate list and stream operations.
All we need to do is to arrange matters so that
`pair`
is non-strict. One way to accomplish this is to extend the lazy
evaluator to allow for non-strict primitives, and to implement
`pair`
as one of these. An easier way is to recall
(section 2.1.3) that there is no fundamental
need to implement
`pair`
as a primitive at all. Instead, we can represent
pairs as
functions:[1]

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:

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)); list_ref(integers, 17); // returns 18

Note that these lazy lists are even lazier than the streams of
chapter 3: The
`head`
of the list, as well as the
`tail`,
is delayed.[2]
In fact, even accessing the
`head`
or
`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 additional delayed function definitions, beyond the ones required to construct a stream pair. With lazy evaluation, all arguments to functions are delayed uniformly. For instance, we can implement functions to integrate lists and solve differential equations as we originally intended in section 3.5.4:

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; } list_ref(solve(x => x, 1, 0.001), 1000);

lazierlazy lists described in this section. How can you take advantage of this extra laziness?

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

head(list(a, b, c));

listsobtained by reading in quoted expressions are different from the lists manipulated by the new definitions of

[1] This
is the
functional
representation described in
exercise 2.4. Essentially any
functional
representation
(e.g., a message-passing implementation) would do as well. Notice
that we can install these definitions in the lazy evaluator simply by
typing them at the driver loop. If we had originally included
`pair`,
`head`,
and
`tail`
as primitives in the global environment, they will be redefined. (Also see
exercises 4.25
and 4.26.)

[2] This permits us to create delayed versions of more
general kinds of
list structures, not just sequences.
Hughes 1990
discusses some
applications of

lazy trees.

4.2.3
Streams as Lazy Lists