Stackless Python 1.0 + Continuations 0.6
Christian Tismer
tismer at tismer.com
Tue Feb 1 07:29:33 EST 2000
Howdy,
let me try to give some hints.
Well, I see I have to build a tutorial/FAQ at some time :-)
Darrell wrote:
>
> """
> Great job Christian.
> It sure can speed up deep recursive functions.
That's for one. The real advantage is that you can switch
contexts, regardless how deeply they are nested. This
lets you write collaborating tasks which can talk to each
other without having to save/restore contexts.
In other words: You can combine algorithms as coroutines.
> What are the chances this will make it into python 1.6 ?
No idea. They are not 0 and not 1. Guido didn't definately
say no, but asked me how hard it would be to include this
version as #ifdefs. I think there is just no decision yet,
and I'll carry on improving and maintaining the code.
There is a good chance that Stackless becomes the enabling
technology for a Palm port of Python, and that is a very
good argument for at least some #ifdef solution.
I would use conditional compilation for the few involved
modules, where the changes are not so much. For ceval.c,
I wouldn't do that but provide a second file instead.
There are so many changes that #ifdefs would be very confusing.
I wrote the stuff in order to replace ceval.c while making
minimum changes, but after all I'd prefer to take the
freedom to reorganize it, in order to get it more readable.
Currently the files are still diffable. This will vanish,
in favor of readability and maybe a couple more optimizations.
> 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.
This one is solved. The GP was a bug in update which didn't check
if the frame had a node object. In your case, it doesn't exist
in the first place, and update should behave as a no-op.
Works now.
> # 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.
Right. The dfault continuation behavior on being called is to
jump. To make it into a call, it's call attribute can be used.
This is all just stuff to speed up things. Usually you don't
need these extras.
There are also jump_cv and call_cv atributes, for the common
situation that you don't only want to jump passing a value,
but passing the source continuation as well.
cont, value = contobject.jump_cv(42)
jumps to contobject's continuation, passing the continuation
at "=" and the value 42 as a tuple. We expect that at some
time someone jumps back to us, using the same protocol.
call_cv is even more useful, since for building generators
you are often asking for the current caller by continuation.caller()
or contobject.caller(), and this can be done in one step with the
call_cv trick.
> 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)
Actually, the update method is a trick to cope with continuations
in the same frame. There is no problem with continuations from
other frames since they have some useful state. But cont stems from
cont = get_caller(0)
(btw, this is now avaliable as continuation.current())
so it has the state from that assignment. This is very useless,
since we don't want to repeat the assignment of the continuation.
k = cont.update(n)
updates the state of cont to exactly this assignment of a value.
For convenience, we pass n as the start value, and it goes
directly through update into k. But when we call cont later,
this value comes from elsewhere :-)
> 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.
> """
Right, despite the fact that it can be much faster than true
recursion, since all local variables are already bound.
All recursive incarnations see the same locals, and they behave
more like fast globals. Reminds be a little of good old Fortran :-)
Well, it's a matter of taste and just a fact, not a feature.
Frame-recursion is just possible, but no recommended style,
probably. But it works and was a good stres test to push the
limits of my implementation.
<snip>
> # ======================================================================
> # coroutine
> # ======================================================================
> """
> This was hard to understand.
> """
Actually, this module is due to Sam Rushing, with minor changes of
mine. It was hard for me to understand as well, most probably
since Sam and I seem to have different points of view. I would
do it "the other way round", very similar to the generator
classes which I did (modelled after the threads generator of
Tim Peters).
But this is a matter of taste again, and the coroutines are
as fast as the generators.
This is one reason why I was reluctant to include Gen's and Co's
as C versions in the first place: There are so many possibilities
to implement them, that I'd like to collect some implementations
of other people, until "the way to do it" has settled.
Then we will make them inot permanent C versions.
Thanks for all the comments. I think it would make sense to
add this as some "examples.py" to the distribution. If you
have worked on further, can I please have a copy?
> 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]
> )
>
> --
> http://www.python.org/mailman/listinfo/python-list
--
Christian Tismer :^) <mailto:tismer at appliedbiometrics.com>
Applied Biometrics GmbH : Have a break! Take a ride on Python's
Düppelstr. 31 : *Starship* http://starship.python.net
12163 Berlin : PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint E182 71C7 1A9D 66E9 9D15 D3CC D4D7 93E2 1FAE F6DF
we're tired of banana software - shipped green, ripens at home
More information about the Python-list
mailing list