Stackless Python 1.0 + Continuations 0.6
Darrell
darrell at dorb.com
Sun Jan 30 13:49:29 EST 2000
"""
Great job Christian.
It sure can speed up deep recursive functions.
I'd like to see what others have figured out about how to use
Stackless.
What are the chances this will make it into python 1.6 ?
The following is excerpts from the Stackless distribution.
With some comments and mods to help me understand.
Let me know if I'm way off or if this should have been an attachment.
"""
import continuation, time
get_caller = continuation.caller
def nS2(n):
"""
Not limited by stack depth.
"""
# Causes a GP if no parms passed.
# If given a 1 cont would point up on in the call stack/chain ?
cont=get_caller(0)
# I feel an ignorant statement coming on.
# Using "cont" instead of "call" is an optimization.
# cont assumes that when called it doesn't have to
# return to it's caller. So a deep recursion doesn't have
# to keep a stack to return to each level. The final return
# at some depth, is the final returned value.
call=cont.call
# Each call to cont arrives at this point.
# And k is assigned to the current value of n with update(n)
# If you had used n it would always be the original value.
k=cont.update(n)
if k:
# This won't return so "print msg" is never called
# if "call(k-1" had been used it would have printed the msg.
cont(k-1)
msg="""
This isn't printed when cont is used. Using cont
doesn't experience stack depth limits.
This is printed when call is used.
Using call runs slower and has the same limits
as a normal recursive function.
"""
print msg
else:
del cont.link
return k
def s1(n):
"""
Limited by stack depth
"""
if n:
n=s1(n-1)
return n
def timer(n,func):
t1=time.time()
for x in range(1000):
func(n)
print time.time()-t1
if 0:
"""
Stackless is much faster for the right recursive function
"""
timer(100,nS2)
timer(100,s1)
# ======================================================================
# coroutine
# ======================================================================
"""
This was hard to understand.
"""
class coroutine:
current = None
caller_of_this = continuation.caller
def __init__ (self, f, *a, **kw):
self.state = lambda v,f=f,a=a,kw=kw: apply (f, a, kw)
self.caller = None
def resume (self, value=None):
caller = coroutine.current
caller.state = self.caller_of_this()
self.caller=caller.state
self.caller = caller
coroutine.current = self
# If you tracing this call will runaway.
self.state (value)
def kill (self):
self.__dict__.clear()
def resume_caller (value):
me = coroutine.current
me.caller.resume (value)
def resume_main (value):
_main.resume (value)
_main = coroutine (None)
coroutine.current = _main
if __name__ == '__main__':
# counter/generator
def counter (start=0, step=1):
n = start
while 1:
print 'A:',n
resume_caller (n)
n = n + step
print 'B:', n
"""
It's surprising that cc.resume() returns a value.
Guess it's related to the lambda in the __init__ ??
Need an experiment.
Prints:
A: 0
0
B: 1
A: 1
1
B: 2
A: 2
2
The second resume takes us back to the "print 'B:'"
Then back to the "print A:"
It's as though the counter functions are in separate threads.
And resume or resume_caller is a blocking message pass.
"""
cc = coroutine(counter)
print cc.resume()
print cc.resume()
print cc.resume()
# same-fringe
def _tree_walker (t):
if type(t) is type([]):
for x in t:
_tree_walker (x)
else:
"""
Passes control back to same_fringe
tree_walker and _tree_walker are in the same pseudo thread.
"""
resume_caller (t)
def tree_walker (t):
_tree_walker (t)
print 'Returns None causing the caller to exit'
resume_caller (None)
print 'Never prints'
def same_fringe (t1, t2):
co1 = coroutine (tree_walker, t1)
co2 = coroutine (tree_walker, t2)
while 1:
leaf1 = co1.resume()
leaf2 = co2.resume()
"""
tree_walker searches finds a result and calls resume_caller(t)
which passes back the result. It's printed then cox.resume()
continues the search. tree_walker is waiting to continue the
search.
"""
print 'leaf1: %s leaf2: %s' % (leaf1, leaf2)
if leaf1 == leaf2:
if leaf1 is None:
return 1
else:
return 0
print same_fringe (
[0,1,[2,3],[4,[5,[6]],7,[[[[8]]]],9]],
[[[0,1],2,[3,[4],[5]],[[6],[7]],8],9]
)
More information about the Python-list
mailing list