delay and force in Python

[Will Stuyvesant]

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
computations.

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: teststreams.py
..
.. 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_enumerat e_interval(low, high):
.. if low > high:
.. return None
.. else:
.. return cons_stream(
.. low,
.. stream_enumerat e_interval(low+ 1, high))
..
.. def stream_filter(p red, s):
.. if s is None:
.. return None
.. elif pred(stream_hd( s)):
.. return cons_stream(
.. stream_hd(s),
.. stream_filter(p red, stream_tl(s)))
.. else:
.. return stream_filter(p red, stream_tl(s))
..
.. def isEven(n): return n % 2 == 0
..
.. print stream_hd(strea m_tl(stream_fil ter(
.. isEven,
.. stream_enumerat e_interval(1,99 5))))
.. # 4



Something else: this crashes with a "maximum recursion reached"
.. print stream_enumerat e_interval(1,99 8)

while this does not crash
.. print stream_enumerat e_interval(1,90 0)
this means Python has a maximum of something like 900
recursions?

[floydophone@gmail.com]

Re: delay and force in Python

Check this out:

def mygen():
for i in xrange(0, 10):
print "about to yield",i
yield i

g = mygen()
print "calling next()", g.next()
print "calling next()", g.next()
print "calling next()", g.next()

[Benji York]

Re: delay and force in Python

Will Stuyvesant wrote:[color=blue]
> Streams are interesting because they are to lists like
> xrange is to range. Could save a lot on memory and
> computations.[/color]

I think you're looking for generators.
[color=blue]
> Below is my straight translation from Scheme code in the
> Wizard book to Python.[/color]
[color=blue]
> Something else: this crashes with a "maximum recursion reached"
> . print stream_enumerat e_interval(1,99 8)[/color]

Unlike Scheme, Python isn't designed for heavily recursive algorithms.
Here's a more Pythonic equivalent of your code:

def count(start, stop):
i = start
while i < stop:
yield i
i += 1

def even(gen):
for x in gen:
if x % 2 == 0:
yield x

numbers = even(count(1, 999))
first = numbers.next()
second = numbers.next()

print second
--
Benji York
benji@benjiyork .com

[Nick Coghlan]

Re: delay and force in Python

Will Stuyvesant wrote:[color=blue]
> 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).[/color]

How's this:

Py> from itertools import islice
Py> print islice((x for x in xrange(1, 996) if x % 2 == 0), 1, 2).next()
4

Breaking it into pieces:

Py> from itertools import islice
Py> stream = (x for x in xrange(1, 996) if x % 2 == 0)
Py> second_item = islice(stream, 1, 2).next()
Py> print second_item
4

And most of the stream hasn't been consumed yet:
Py> print stream.next()
6
Py> unconsumed = list(stream)
Py> len(unconsumed)
494

And this version has no problem with recursion limits:
Py> print islice((x for x in xrange(1, sys.maxint) if x % 2 == 0), 1, 2).next()
4

(xrange can't handle Python longs, unfortunately, so we *are* constrained by
sys.maxint. However, since my machine only has half a gig of RAM, the above is
still a damn sight quicker than the equivalent list comprehension would be!)
[color=blue]
> Something else: this crashes with a "maximum recursion reached"
> . print stream_enumerat e_interval(1,99 8)
>
> while this does not crash
> . print stream_enumerat e_interval(1,90 0)
> this means Python has a maximum of something like 900
> recursions?[/color]

The CPython implementation is limited by the stack size allocated by the C
runtime library. The exact recursion limit is platform dependent, but something
around 1000 sounds fairly normal.

Cheers,
Nick.

--
Nick Coghlan | ncoghlan@email. com | Brisbane, Australia
---------------------------------------------------------------

http://boredomandlaziness.skystorm.net

[Dave Benjamin]

Re: delay and force in Python

Will Stuyvesant wrote:[color=blue]
> . def delay(exp): return lambda: exp[/color]

If you look at the definition of "delay" in SICP, you'll notice that
it's defined as "syntax sugar", in other words, a macro. Since Python
does not have macros, you'll have to just use "lambda", because by
defining "delay" as a function, you're forcing the expression "exp" to
evaluate immediately. In other words, theres a crucial difference between::

delay(sys.stdou t.write('evalua ted\n'))

and::

lambda: sys.stdout.writ e('evaluated\n' )

If you type in those two snippets, you'll see what I mean.

Coincidentally, I attempted a similar experiment just a couple of days
ago, and here's what I came up with::

# Stream.py - Stream class inspired by SICP

class Stream(object):
pass

class EndOfStream(Exc eption):
pass

class Item(Stream):
def __init__(self, current, nextf):
self.current = current
self.nextf = nextf

next = property(lambda self: self.nextf())

def fold(self, f, init):
return f(self.current, self.next.fold( f, init))

def __getitem__(sel f, n):
if n == 0:
return self.current
else:
return self.next[n - 1]

def __str__(self):
return '<Stream.Item: %s, ...>' % self.current
__repr__ = __str__

class End(Stream):
def fold(self, f, init):
return init

def __getitem__(sel f, n):
raise EndOfStream()

def _fail(self):
raise EndOfStream()

current = property(_fail)
next = property(_fail)

def __str__(self):
return '<Stream.End>'
__repr__ = __str__

Here's how it works::

Python 2.4 (#1, Dec 4 2004, 20:10:33)
[GCC 3.3.3 (cygwin special)] on cygwin
Type "help", "copyright" , "credits" or "license" for more information.[color=blue][color=green][color=darkred]
>>> import Stream
>>> s = Stream.Item(1, lambda: Stream.Item(2, lambda: Stream.End()))
>>> s[/color][/color][/color]
<Stream.Item: 1, ...>[color=blue][color=green][color=darkred]
>>> s.current[/color][/color][/color]
1[color=blue][color=green][color=darkred]
>>> s.next[/color][/color][/color]
<Stream.Item: 2, ...>[color=blue][color=green][color=darkred]
>>> s.next.current[/color][/color][/color]
2[color=blue][color=green][color=darkred]
>>> s.next.next[/color][/color][/color]
<Stream.End>[color=blue][color=green][color=darkred]
>>> s.next.next.nex t[/color][/color][/color]
Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "Stream.py" , line 37, in _fail
raise EndOfStream()
Stream.EndOfStr eam[color=blue][color=green][color=darkred]
>>> def evens(n=0):[/color][/color][/color]
... return Stream.Item(n, lambda: evens(n + 2))
...[color=blue][color=green][color=darkred]
>>> s = evens()
>>> s.current[/color][/color][/color]
0[color=blue][color=green][color=darkred]
>>> s.next.current[/color][/color][/color]
2[color=blue][color=green][color=darkred]
>>> s.next.next.cur rent[/color][/color][/color]
4

I don't know if this is useful or not, but it was an interesting
exercise nonetheless.

Dave

[Dave Benjamin]

Re: delay and force in Python

Will Stuyvesant wrote:[color=blue]
> Something else: this crashes with a "maximum recursion reached"
> . print stream_enumerat e_interval(1,99 8)
>
> while this does not crash
> . print stream_enumerat e_interval(1,90 0)
> this means Python has a maximum of something like 900
> recursions?[/color]

See "sys.getrecursi onlimit()" and "sys.setrecursi onlimit()". The lack of
tail-call optimization means you probably won't get very far with this
approach (nor with mine). ;)

Dave

[Will Stuyvesant]

Re: delay and force in Python


Yes you are right, if you just want to carry an expression
around then lambda does it; but delay was not intended as a
top-level function. Perhaps you think that my silly stream
implementation in the original post builds the whole list,
but it does not:
[color=blue][color=green][color=darkred]
>>> o = stream_enumerat e_interval(11,1 21)
>>> print o[/color][/color][/color]
[11, <function <lambda> at 0x00BA8670>][color=blue][color=green][color=darkred]
>>> f = o[1]
>>> r = f()
>>> print r[/color][/color][/color]
[12, <function <lambda> at 0x00BA86B0>]

instead it builds a list of lambda's, and that is so
desirable <wink>


Others suggested generators indeed, and I can imagine now a
usage pattern like
[color=blue][color=green][color=darkred]
>>> s = stream_generato r(initValue, next, stop, other_params)
>>> stream_hd(strea m_tl(stream_fil ter(isEven,s)))[/color][/color][/color]

where the idea is to pass a generator to a function all the
time. What I don't like though is that I then, as I
understand it, have to code some for-loop inside that
function, I try to avoid for-loops. But a functional form
defined with a for-loop does not seem all that bad. Anyway
I have some reading-up to do, about things some posters use
and I forgot to keep up with since I have been coding Python
1.5.2 style for ages now: properties, itertools, ...printed
some stuff already, thanks!

[infidel]

Re: delay and force in Python

It took me a while to figure out what the "translated " code was trying
to do. Here's a quick example that I think accomplishes the same
thing:
[color=blue][color=green][color=darkred]
>>> for i, n in enumerate(x for x in xrange(998) if x % 2 == 0):[/color][/color][/color]
.... if i == 1:
.... print n
....
2

[Bengt Richter]

Re: delay and force in Python

On Wed, 19 Jan 2005 23:53:28 +1000, Nick Coghlan <ncoghlan@iinet .net.au> wrote:
[...][color=blue][color=green]
>> Something else: this crashes with a "maximum recursion reached"
>> . print stream_enumerat e_interval(1,99 8)
>>
>> while this does not crash
>> . print stream_enumerat e_interval(1,90 0)
>> this means Python has a maximum of something like 900
>> recursions?[/color]
>
>The CPython implementation is limited by the stack size allocated by the C
>runtime library. The exact recursion limit is platform dependent, but something
>around 1000 sounds fairly normal.
>[/color]
ISTM you forgot something ;-)
(I.e., that 1000 is only a default value (don't know if same on all platforms)).
[color=blue][color=green][color=darkred]
>>> import sys
>>> help(sys.setrec ursionlimit)[/color][/color][/color]
Help on built-in function setrecursionlim it in module sys:

setrecursionlim it(...)
setrecursionlim it(n)

Set the maximum depth of the Python interpreter stack to n. This
limit prevents infinite recursion from causing an overflow of the C
stack and crashing Python. The highest possible limit is platform-
dependent.

Regards,
Bengt Richter

[infidel]

Re: delay and force in Python

Of course I meant to put a break out of the loop after the print
statement. Duh on me.

[Will Stuyvesant]

Re: delay and force in Python

Just for the record, an implementation without using generators,
somewhat like in Sect. 3.5 of the Wizard book, and without recursion
limit problems.
..
.. def stream_hd(s): # the head of the stream
.. return s[0]
..
.. def stream_tl(s): # the tail of the stream
.. return s[1]()
..
.. ##
.. # The low argument is required: the first element of the stream.
.. # You either use high= or stop_f= to define the end of the
.. # stream. Omit both for an infinite stream. stop_f is a function
.. # that takes low as argument and returns True or False.
.. # The next_f function takes one argument (an element of the stream,
.. # same type as the low argument has)
.. # The stop_f function takes one argument (same type as low)
.. # @param low object
.. # @param high object
.. # @param next_f function
.. # @param stop_f function
.. # @return list, a stream
.. def make_stream(low , high=None, next_f=None, stop_f=None):
.. if next_f is None: next_f = lambda x: x + 1
.. if high is not None: # using high
.. if low > high:
.. return None
.. else:
.. return [low, lambda: make_stream(
.. next_f(low), high=high, next_f=next_f)]
.. elif stop_f is not None: # using stop_f
.. if low > stop_f(low):
.. return None
.. else:
.. return [low, lambda: make_stream(
.. next_f(low), next_f=next_f, stop_f=stop_f)]
.. else: # infinite stream
.. return [low, lambda: make_stream(
.. next_f(low), next_f=next_f)]
..
.. ##
.. # iterative version of filter
.. # @param pred function, (stream-element) -> bool
.. # @param s list, a stream
.. # @return list, a stream
.. def stream_filter(p red, s):
.. if s is None: return []
.. while True:
.. elem = stream_hd(s)
.. if pred(elem):
.. return [elem, lambda: stream_filter(p red, stream_tl(s))]
.. else:
.. s = stream_tl(s)
.. if s is None: return []
..
..
.. if __name__ == '__main__':
..
.. def is100some(x): return x % 100 == 0
.. assert(stream_h d(stream_tl(str eam_tl(stream_f ilter(
.. is100some,
.. make_stream(1, 11111111111111) )))) == 300)
..
.. def add_33(x): return x + 33
.. assert(stream_h d(stream_tl(str eam_filter(
.. is100some,
.. # stream 1,34,67,100,...
.. make_stream(1,9 99999999, next_f = add_33)))) == 3400)
..
.. assert(stream_h d(stream_tl(str eam_filter(
.. is100some,
.. # infinite stream 1,2,...
.. make_stream(1)) )) == 200)
..
.. def mod_20000(x): return x % 20000 == 0
.. # this will need more evaluations than the recursion limit count
.. infinite_filter = stream_filter(m od_20000, make_stream(1))
.. assert( stream_hd(strea m_tl(infinite_f ilter)) == 40000 )
..

[Nick Coghlan]

Re: delay and force in Python

Nick Coghlan wrote:[color=blue]
> Will Stuyvesant wrote:
>[color=green]
>> 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).[/color]
>
>
> How's this:
>
> Py> from itertools import islice
> Py> print islice((x for x in xrange(1, 996) if x % 2 == 0), 1, 2).next()
> 4[/color]

Wouldn't it be nice if this could be spelt:

print (x for x in xrange(1, 996) if x % 2 == 0)[2]

Well, I just put a patch on SF to enable exactly that:

http://www.python.org/sf/1108272

Cheers,
Nick.

--
Nick Coghlan | ncoghlan@email. com | Brisbane, Australia
---------------------------------------------------------------

http://boredomandlaziness.skystorm.net

[Fredrik Lundh]

Re: delay and force in Python

Nick Coghlan wrote:
[color=blue][color=green]
>> How's this:
>>
>> Py> from itertools import islice
>> Py> print islice((x for x in xrange(1, 996) if x % 2 == 0), 1, 2).next()
>> 4[/color]
>
> Wouldn't it be nice if this could be spelt:
>
> print (x for x in xrange(1, 996) if x % 2 == 0)[2][/color]

as I've always said, the sooner we can all use the itertools goodies without
even noticing, the better.

</F>

[Peter Otten]

Re: delay and force in Python

Nick Coghlan wrote:
[color=blue][color=green]
>> Py> print islice((x for x in xrange(1, 996) if x % 2 == 0), 1, 2).next()
>> 4[/color]
>
> Wouldn't it be nice if this could be spelt:
>
> print (x for x in xrange(1, 996) if x % 2 == 0)[2]
>
> Well, I just put a patch on SF to enable exactly that:
> http://www.python.org/sf/1108272[/color]

I like it. Of course you always have to bear in mind that one giant leap for
a list could be _many_ small steps for an iterator.

Peter

[Nick Coghlan]

Re: delay and force in Python

Peter Otten wrote:[color=blue]
> Nick Coghlan wrote:
>
>[color=green][color=darkred]
>>>Py> print islice((x for x in xrange(1, 996) if x % 2 == 0), 1, 2).next()
>>>4[/color]
>>
>>Wouldn't it be nice if this could be spelt:
>>
>>print (x for x in xrange(1, 996) if x % 2 == 0)[2]
>>
>>Well, I just put a patch on SF to enable exactly that:
>>http://www.python.org/sf/1108272[/color]
>
>
> I like it. Of course you always have to bear in mind that one giant leap for
> a list could be _many_ small steps for an iterator.[/color]

Indeed. The main cases I am thinking of involve picking off the first few items
of an iterator (either to use them, or to throw them away before using the rest).

And if an app actually *needs* random access, there's a reason lists still exist ;)

Cheers,
Nick.

--
Nick Coghlan | ncoghlan@email. com | Brisbane, Australia
---------------------------------------------------------------

http://boredomandlaziness.skystorm.net