delay and force in Python

Will Stuyvesant hwlgw at
Wed Jan 19 06:17:10 EST 2005

Here is a question for people who are more comfortable than
I am with new Python stuff like generators.

I am having fun implementing things from the Wizard book
(Abelson, Sussman, "Structure and Interpretation of Computer
Programs") in Python.  In chapter 3.5 it is about streams as
delayed lists.

Streams are interesting because they are to lists like
xrange is to range.  Could save a lot on memory and

Below is my straight translation from Scheme code in the
Wizard book to Python.  It works, but now I want to rewrite
the delay and force functions using Python's new stuff,
generators or iterators or what-have-you.  I have the
feeling that that is possible, can you do it?

The program below creates a stream with the numbers 1..995
and then filters the stream, keeping only the even numbers,
and then prints the second number in the stream (implemented
as the first number of the tail, just like in the 3.5
Section in the Wizard book).

. # file:
. def delay(exp): return lambda: exp
. def force(o): return o()
. def cons_stream(a,b): return [a, delay(b)]
. def stream_hd(s): return s[0]
. # we use tl for cdr
. def tl(x):
.     if len(x) == 2: return x[1]
.     else: return x[1:]
. def stream_tl(s): return force(tl(s))
. def stream_enumerate_interval(low, high):
.     if low > high:
.         return None
.     else:
.         return cons_stream(
.                  low,
.                  stream_enumerate_interval(low+1, high))
. def stream_filter(pred, s):
.     if s is None:
.         return None
.     elif pred(stream_hd(s)):
.         return cons_stream(
.                  stream_hd(s),
.                  stream_filter(pred, stream_tl(s)))
.     else:
.         return stream_filter(pred, stream_tl(s))
. def isEven(n): return n % 2 == 0
. print stream_hd(stream_tl(stream_filter(
.   isEven,
.   stream_enumerate_interval(1,995))))
. # 4

Something else: this crashes with a "maximum recursion reached"
. print stream_enumerate_interval(1,998)

while this does not crash
. print stream_enumerate_interval(1,900)
this means Python has a maximum of something like 900

More information about the Python-list mailing list