In a project I am working on, I want to implement a large list using
evaluation in Scheme. The list is large enough to be too unwieldy
to store entirely in memory, but I still want to represent it in my
program as if it was. The solution is lazy evaluation.
One use of lazy evaluation is allowing a program to have infinitely
sized data structures without going into the impossible task of
actually creating them. Instead, the structure is created on the fly
as needed. As a prototype for getting it right, I made an infinitely
long list in Scheme that contains the entire Fibonacci series.
This function, given two numbers from the series, returns the lazy
list. It uses
delay to delay evaluation of the list.
Notice the recursion here as no base case, so without lazy
evaluation it would continue along forever without halting. Now run
The rest of the list is stored as a promise, which will later
be teased out using
force. This forces evaluation of the
promise. Here is a function to traverse the list to the
nth element and return it. Notice, this does have a base
Here it is in action. It is retrieving the 30th element.
If you examine
f, it contains the first 30 numbers until
running into an unevaluated promise. This behavior is very similar to
memoization, as calculated values
are stored instead of being recalculated later.
These two functions are also behaving as coroutines. When
nth-fib reaches a promise, it yields to
which continues its non-halting definition. After producing a new
f, it yields back to
The way I called these functions above, however, can lead to
problems. We are storing all the calculated values in
which can take up a lot of memory. For example, this probably won't
We will run out of memory before it halts. Instead, we can do this,
nth-fib uses tail recursion as it traverses the
list, unneeded calculated values are tossed (which the garbage
collector will handle) and no additional function stack is used. All
Scheme implementations optimize tail recursion in this way. This will
continue along until it hits the millionth Fibonacci number, all while
using a constant amount of memory.
It turns out that Scheme calls this type of data structure a
stream, and some implementations have functions and macros
defined so that they are ready to use.
So there you go: memoization, lazy evaluation, and coroutines all
packed into one example.