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? 17 2477
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()
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
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
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
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
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!
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
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
Of course I meant to put a break out of the loop after the print
statement. Duh on me. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
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...
|
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...
|
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...
|
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...
|
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?
| |
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...
|
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
|
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)
|
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...
|
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,...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
| |
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
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();...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
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
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |