473,597 Members | 2,331 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

delay and force in Python


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?

Jul 18 '05 #1
17 2455
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()

Jul 18 '05 #2
Will Stuyvesant wrote:
Streams are interesting because they are to lists like
xrange is to range. Could save a lot on memory and
computations.
I think you're looking for generators.
Below is my straight translation from Scheme code in the
Wizard book to Python. Something else: this crashes with a "maximum recursion reached"
. print stream_enumerat e_interval(1,99 8)


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
be***@benjiyork .com

Jul 18 '05 #3
Will Stuyvesant wrote:
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).
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!)
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?


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 | nc******@email. com | Brisbane, Australia
---------------------------------------------------------------
http://boredomandlaziness.skystorm.net
Jul 18 '05 #4
Will Stuyvesant wrote:
. def delay(exp): return lambda: exp


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.
import Stream
s = Stream.Item(1, lambda: Stream.Item(2, lambda: Stream.End()))
s <Stream.Item: 1, ...> s.current 1 s.next <Stream.Item: 2, ...> s.next.current 2 s.next.next <Stream.End> s.next.next.nex t Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "Stream.py" , line 37, in _fail
raise EndOfStream()
Stream.EndOfStr eam def evens(n=0): ... return Stream.Item(n, lambda: evens(n + 2))
... s = evens()
s.current 0 s.next.current 2 s.next.next.cur rent

4

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

Dave
Jul 18 '05 #5
Will Stuyvesant wrote:
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?


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
Jul 18 '05 #6

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:
o = stream_enumerat e_interval(11,1 21)
print o [11, <function <lambda> at 0x00BA8670>] f = o[1]
r = f()
print r [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
s = stream_generato r(initValue, next, stop, other_params)
stream_hd(strea m_tl(stream_fil ter(isEven,s)))


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!

Jul 18 '05 #7
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:
for i, n in enumerate(x for x in xrange(998) if x % 2 == 0):

.... if i == 1:
.... print n
....
2

Jul 18 '05 #8
On Wed, 19 Jan 2005 23:53:28 +1000, Nick Coghlan <nc******@iinet .net.au> wrote:
[...]
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?


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.

ISTM you forgot something ;-)
(I.e., that 1000 is only a default value (don't know if same on all platforms)).
import sys
help(sys.setrec ursionlimit)

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
Jul 18 '05 #9
Of course I meant to put a break out of the loop after the print
statement. Duh on me.

Jul 18 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

12
18611
by: Conrad | last post by:
Greetings, Q: Is there some way to gracefully suspend a python app for a second or so then resume? I could write the classic basic dumb loop-tenzillion-times delay, but that seems inelegant, and well, just wrong. By the way, I'm also using wxPython, if that helps any. I need to delay a python program for about a second. Googling around, it looks like most of the timer stuff has to do with thread handling, but my application is not...
0
2639
by: jacob c. | last post by:
When I request a URL using urllib2, it appears that urllib2 always makes the request using HTTP 1.0, and not HTTP 1.1. I'm trying to use the "If-None-Match"/"ETag" HTTP headers to conserve bandwidth, but if I'm not mistaken, these are HTTP 1.1 headers, so I can't reasonably expect a web server to respond correctly to my requests. (In my limited testing, it looks like some servers respond correctly with an HTTP 304 status, while some...
20
3003
by: Doug Thews | last post by:
I ran into an interesting re-pain delay after calling the Abort() method on a thread, but it only happens the very first time I call it. Every time afterward, there is no delay. I've got a delegate inside the UI that I call to update the progress meter. I use the Suspend() and Abort() methods based on button events. I can watch the progress meter increase just fine when the thread is running. When I select Start, I enable the Cancel...
7
2934
by: mfeingold | last post by:
I am working on a system, which among other things includes a server and a ..net control sitting in an html page and connected to the server. I ran into a couple of problems, you guys might have some insight about. 1) It takes 20 sec or so to open a tcp socket from the client to the server. It just sits in the TcpClient.conect waiting for something. When I run the same control from a windows application it connects right away and works...
6
7157
by: Martin | last post by:
Using javascript, I want to force a browser window to close after about 30 minutes of non-use. Can someone point me to a script that can do this? I assume I could use the setTimeout function and keep re-setting it whenever the mouse is moved. Is there a better way?
2
6008
by: ShawnD | last post by:
I'm having some issues when trying to read input off of a pipe using a python script. I'm trying to process packet data from tcpdump in real-time, so it's a filter that needs to read data while the process being piped from is still reading. On both my Linux and OSX system, it seems that there's a large delay reading from stdin if the process being read from is still running, even if it's producing output to be read. It will wait until it...
0
1601
by: Jonathan Mark | last post by:
hi all... I wrote a seemingly simple function (below) to use Popen3() and select() to run a program and capture its exit status, stdout output, and stderr output. It worked fine until the box was upgraded to Debian sarge. Now the call to select() always takes about 13 seconds before returning the first time. The delay only occurs when the function is running within a CGI program
2
1446
by: dwhall | last post by:
I have 2 python scripts: examples of a producer and a filter, respectively: #! /usr/bin/env python import sys, time if __name__ == "__main__": while True: sys.stdout.write("hello.\r\n") time.sleep(0.000001)
6
7940
by: sheldonlg | last post by:
I came across a problem and googling for an answer didn't help. What I want to do is run an AJAX script that sets a hidden variable on the form. I call the AJAX script from a javascript function. After the call, I check the value of that hidden variable and proceed according to whether it is zero or one. The problem is that the AJAX call does not complete before the test. So, I put in a delay after the call to the AJAX function. I...
0
7962
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
7884
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
1
8024
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
6681
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
5844
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5423
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
3921
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
2394
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
1
1493
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.