Mailing List Archive

rushing@nightmare.com wrote:
>
> [.list has been quiet, thought I'd liven things up a bit. 8^)]

Well, there certainly is enough on the todo list... it's probably
the usual "ain't got no time" thing.

> I'm not sure if this has been brought up before in other forums, but
> has there been discussion of separating the Python and C invocation
> stacks, (i.e., removing recursive calls to the intepreter) to
> facilitate coroutines or first-class continuations?

Wouldn't it be possible to move all the C variables passed to
eval_code() via the execution frame ? AFAIK, the frame is
generated on every call to eval_code() and thus could also
be generated *before* calling it.

> One of the biggest barriers to getting others to use asyncore/medusa
> is the need to program in continuation-passing-style (callbacks,
> callbacks to callbacks, state machines, etc...). Usually there has to
> be an overriding requirement for speed/scalability before someone will
> even look into it. And even when you do 'get' it, there are limits to
> how inside-out your thinking can go. 8^)
>
> If Python had coroutines/continuations, it would be possible to hide
> asyncore-style select()/poll() machinery 'behind the scenes'. I
> believe that Concurrent ML does exactly this...
>
> Other advantages might be restartable exceptions, different threading
> models, etc...

Don't know if moving the C stack stuff into the frame objects
will get you the desired effect: what about other things having
state (e.g. connections or files), that are not even touched
by this mechanism ?

--
Marc-Andre Lemburg
______________________________________________________________________
Y2000: Y2000: 232 days left
Business: http://www.lemburg.com/
Python Pages: http://starship.python.net/crew/lemburg/

M.-A. Lemburg writes:

> Wouldn't it be possible to move all the C variables passed to
> eval_code() via the execution frame ? AFAIK, the frame is
> generated on every call to eval_code() and thus could also
> be generated *before* calling it.

I think this solves half of the problem. The C stack is both a value
stack and an execution stack (i.e., it holds variables and return
addresses). Getting rid of arguments (and a return value!) gets rid
of the need for the 'value stack' aspect.

In aiming for an enter-once, exit-once VM, the thorniest part is to
somehow allow python->c->python calls. The second invocation could
never save a continuation because its execution context includes a C
frame. This is a general problem, not specific to Python; I probably
should have thought about it a bit before posting...

> Don't know if moving the C stack stuff into the frame objects
> will get you the desired effect: what about other things having
> state (e.g. connections or files), that are not even touched
> by this mechanism ?

I don't think either of those cause 'real' problems (i.e., nothing
should crash that assumes an open file or socket), but there may be
other stateful things that might. I don't think that refcounts would
be a problem - a saved continuation wouldn't be all that different
from an exception traceback.

-Sam

p.s. Here's a tiny VM experiment I wrote a while back, to explain
what I mean by 'stackless':

http://www.nightmare.com/stuff/machine.h
http://www.nightmare.com/stuff/machine.c

Note how OP_INVOKE (the PROC_CLOSURE clause) pushes new context
onto heap-allocated data structures rather than calling the VM
recursively.

Sam> I'm not sure if this has been brought up before in other forums,
Sam> but has there been discussion of separating the Python and C
Sam> invocation stacks, (i.e., removing recursive calls to the
Sam> intepreter) to facilitate coroutines or first-class continuations?

I thought Guido was working on that for the mobile agent stuff he was
working on at CNRI.

Skip Montanaro | Mojam: "Uniting the World of Music" http://www.mojam.com/
skip@mojam.com | Musi-Cal: http://www.musi-cal.com/
518-372-5583

>>>>> "SM" == Skip Montanaro <skip@mojam.com> writes:

SM> I thought Guido was working on that for the mobile agent stuff
SM> he was working on at CNRI.

Nope, we decided that we could accomplish everything we needed without
this. We occasionally revisit this but Guido keeps insisting it's a
lot of work for not enough benefit :-)

-Barry

Interesting topic! While I 'm on the road, a few short notes.

> I thought Guido was working on that for the mobile agent stuff he was
> working on at CNRI.

Indeed. At least I planned on working on it. I ended up abandoning
the idea because I expected it would be a lot of work and I never had
the time (same old story indeed).

Sam also hit it on the nail: the hardest problem is what to do about
all the places where C calls back into Python.

I've come up with two partial solutions: (1) allow for a way to
arrange for a call to be made immediately after you return to the VM
from C; this would take care of apply() at least and a few other
"tail-recursive" cases; (2) invoke a new VM when C code needs a Python
result, requiring it to return. The latter clearly breaks certain
uses of coroutines but could probably be made to work most of the
time. Typical use of the 80-20 rule.

And I've just come up with a third solution: a variation on (1) where
you arrange *two* calls: one to Python and then one to C, with the
result of the first. (And a bit saying whether you want the C call to
be made even when an exception happened.)

In general, I still think it's a cool idea, but I also still think
that continuations are too complicated for most programmers. (This
comes from the realization that they are too complicated for me!)
Corollary: even if we had continuations, I'm not sure if this would
take away the resistance against asyncore/asynchat. Of course I could
be wrong.

Different suggestion: it would be cool to work on completely
separating out the VM from the rest of Python, through some kind of
C-level API specification. Two things should be possiblw with this
new architecture: (1) small platform ports could cut out the
interactive interpreter, the parser and compiler, and certain data
types such as long, complex and files; (2) there could be alternative
pluggable VMs with certain desirable properties such as
platform-specific optimization (Christian, are you listening? :-).

I think the most challenging part might be defining an API for passing
in the set of supported object types and operations. E.g. the
EXEC_STMT opcode needs to be be implemented in a way that allows
"exec" to be absent from the language. Perhaps an __exec__ function
(analogous to __import__) is the way to go. The set of built-in
functions should also be passed in, so that e.g. one can easily leave
out open(), eval() and comppile(), complex(), long(), float(), etc.

I think it would be ideal if no #ifdefs were needed to remove features
(at least not in the VM code proper). Fortunately, the VM doesn't
really know about many object types -- frames, fuctions, methods,
classes, ints, strings, dictionaries, tuples, tracebacks, that may be
all it knows. (Lists?)

Gotta run,

--Guido van Rossum (home page: http://www.python.org/~guido/)

> In general, I still think it's a cool idea, but I also still think
> that continuations are too complicated for most programmers. (This
> comes from the realization that they are too complicated for me!)

in an earlier life, I used non-preemtive threads (that is,
explicit yields) and co-routines to do some really cool
stuff with very little code. looks like a stack-less inter-
preter would make it trivial to implement that.

might just be nostalgia, but I think I would give an arm
or two to get that (not necessarily my own, though ;-)

</F>

Guido van Rossum writes:
> I've come up with two partial solutions: (1) allow for a way to
> arrange for a call to be made immediately after you return to the
> VM from C; this would take care of apply() at least and a few
> other "tail-recursive" cases; (2) invoke a new VM when C code
> needs a Python result, requiring it to return. The latter clearly
> breaks certain uses of coroutines but could probably be made to
> work most of the time. Typical use of the 80-20 rule.

I know this is disgusting, but could setjmp/longjmp 'automagically'
force a 'recursive call' to jump back into the top-level loop? This
would put some serious restraint on what C called from Python could
do...

I think just about any Scheme implementation has to solve this same
problem... I'll dig through my collection of them for ideas.

> In general, I still think it's a cool idea, but I also still think
> that continuations are too complicated for most programmers. (This
> comes from the realization that they are too complicated for me!)
> Corollary: even if we had continuations, I'm not sure if this would
> take away the resistance against asyncore/asynchat. Of course I could
> be wrong.

Theoretically, you could have a bit of code that looked just like
'normal' imperative code, that would actually be entering and exiting
the context for non-blocking i/o. If it were done right, the same
exact code might even run under 'normal' threads.

Recently I've written an async server that needed to talk to several
other RPC servers, and a mysql server. Pseudo-example, with
possibly-async calls in UPPERCASE:

auth, archive = db.FETCH_USER_INFO (user)
if verify_login(user,auth):
rpc_server = self.archive_servers[archive]
group_info = rpc_server.FETCH_GROUP_INFO (group)
if valid (group_info):
return rpc_server.FETCH_MESSAGE (message_number)
else:
...
else:
...

This code in CPS is a horrible, complicated mess, it takes something
like 8 callback methods, variables and exceptions have to be passed
around in 'continuation' objects. It's hairy because there are three
levels of callback state. Ugh.

If Python had closures, then it would be a *little* easier, but would
still make the average Pythoneer swoon. Closures would let you put
the above logic all in one method, but the code would still be
'inside-out'.

> Different suggestion: it would be cool to work on completely
> separating out the VM from the rest of Python, through some kind of
> C-level API specification.

I think this is a great idea. I've been staring at python bytecodes a
bit lately thinking about how to do something like this, for some
subset of Python.

[...]

Ok, we've all seen the 'stick'. I guess I should give an example of
the 'carrot': I think that a web server built on such a Python could
have the performance/scalability of thttpd, with the
ease-of-programming of Roxen. As far as I know, there's nothing like
it out there. Medusa would be put out to pasture. 8^)

-Sam

> I know this is disgusting, but could setjmp/longjmp 'automagically'
> force a 'recursive call' to jump back into the top-level loop? This
> would put some serious restraint on what C called from Python could
> do...

Forget about it. setjmp/longjmp are invitations to problems. I also
assume that they would interfere badly with C++.

> I think just about any Scheme implementation has to solve this same
> problem... I'll dig through my collection of them for ideas.

Anything that assumes knowledge about how the C compiler and/or the
CPU and OS lay out the stack is a no-no, because it means that the
first thing one has to do for a port to a new architecture is figure
out how the stack is laid out. Another thread in this list is porting
Python to microplatforms like PalmOS. Typically the scheme Hackers
are not afraid to delve deep into the machine, but I refuse to do that
-- I think it's too risky.

> > In general, I still think it's a cool idea, but I also still think
> > that continuations are too complicated for most programmers. (This
> > comes from the realization that they are too complicated for me!)
> > Corollary: even if we had continuations, I'm not sure if this would
> > take away the resistance against asyncore/asynchat. Of course I could
> > be wrong.
>
> Theoretically, you could have a bit of code that looked just like
> 'normal' imperative code, that would actually be entering and exiting
> the context for non-blocking i/o. If it were done right, the same
> exact code might even run under 'normal' threads.

Yes -- I remember in 92 or 93 I worked out a way to emulat coroutines
with regular threads. (I think in cooperation with Steve Majewski.)

> Recently I've written an async server that needed to talk to several
> other RPC servers, and a mysql server. Pseudo-example, with
> possibly-async calls in UPPERCASE:
>
> auth, archive = db.FETCH_USER_INFO (user)
> if verify_login(user,auth):
> rpc_server = self.archive_servers[archive]
> group_info = rpc_server.FETCH_GROUP_INFO (group)
> if valid (group_info):
> return rpc_server.FETCH_MESSAGE (message_number)
> else:
> ...
> else:
> ...
>
> This code in CPS is a horrible, complicated mess, it takes something
> like 8 callback methods, variables and exceptions have to be passed
> around in 'continuation' objects. It's hairy because there are three
> levels of callback state. Ugh.

Agreed.

> If Python had closures, then it would be a *little* easier, but would
> still make the average Pythoneer swoon. Closures would let you put
> the above logic all in one method, but the code would still be
> 'inside-out'.

I forget how this worked :-(

> > Different suggestion: it would be cool to work on completely
> > separating out the VM from the rest of Python, through some kind of
> > C-level API specification.
>
> I think this is a great idea. I've been staring at python bytecodes a
> bit lately thinking about how to do something like this, for some
> subset of Python.
>
> [...]
>
> Ok, we've all seen the 'stick'. I guess I should give an example of
> the 'carrot': I think that a web server built on such a Python could
> have the performance/scalability of thttpd, with the
> ease-of-programming of Roxen. As far as I know, there's nothing like
> it out there. Medusa would be put out to pasture. 8^)

I'm afraid I haven't kept up -- what are Roxen and thttpd? What do
they do that Apache doesn't?

--Guido van Rossum (home page: http://www.python.org/~guido/)

> I'm afraid I haven't kept up -- what are Roxen and thttpd? What do
> they do that Apache doesn't?

http://www.roxen.com/

a lean and mean secure web server written in Pike
(http://pike.idonex.se/), from a company here in
Linköping.

</F>

Guido van Rossum wrote:

[setjmp/longjmp -no-no]

> Forget about it. setjmp/longjmp are invitations to problems. I also
> assume that they would interfere badly with C++.
>
> > I think just about any Scheme implementation has to solve this same
> > problem... I'll dig through my collection of them for ideas.
>
> Anything that assumes knowledge about how the C compiler and/or the
> CPU and OS lay out the stack is a no-no, because it means that the
> first thing one has to do for a port to a new architecture is figure
> out how the stack is laid out. Another thread in this list is porting
> Python to microplatforms like PalmOS. Typically the scheme Hackers
> are not afraid to delve deep into the machine, but I refuse to do that
> -- I think it's too risky.
...

I agree that this is generally bad. While it's a cakewalk
to do a stack swap for the few (X86 based:) platforms where
I work with. This is much less than a thread change.

But on the general issues:
Can the Python-calls-C and C-calls-Python problem just be solved
by turning the whole VM state into a data structure, including
a Python call stack which is independent? Maybe this has been
mentioned already.

This might give a little slowdown, but opens possibilities
like continuation-passing style, and context switches
between different interpreter states would be under direct
control.

Just a little dreaming: Not using threads, but just tiny
interpreter incarnations with local state, and a special
C call or better a new opcode which activates the next
state in some list (of course a Python list).
This would automagically produce ICON iterators (duck)
and coroutines (cover).
If I guess right, continuation passing could be done
by just shifting tiny tuples around. Well, Tim, help me :-)

[closures]

> > I think this is a great idea. I've been staring at python bytecodes a
> > bit lately thinking about how to do something like this, for some
> > subset of Python.

Lumberjack? How is it going? [to Sam]

ciao - chris

--
Christian Tismer :^) <mailto:tismer@appliedbiometrics.com>
Applied Biometrics GmbH : Have a break! Take a ride on Python's
Kaiserin-Augusta-Allee 101 : *Starship* http://starship.python.net
10553 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

>>>>> "FL" == Fredrik Lundh <fredrik@pythonware.com> writes:

FL> a lean and mean secure web server written in Pike
FL> (http://pike.idonex.se/), from a company here in
FL> Linköping.

Interesting off-topic Pike connection. My co-maintainer for CC-Mode
original came on board to add Pike support, which has a syntax similar
enough to C to be easily integrated. I think I've had as much success
convincing him to use Python as he's had convincing me to use Pike :-)

-Barry

Guido van Rossum writes:
> > If Python had closures, then it would be a *little* easier, but would
> > still make the average Pythoneer swoon. Closures would let you put
> > the above logic all in one method, but the code would still be
> > 'inside-out'.
>
> I forget how this worked :-(

[with a faked-up lambda-ish syntax]

def thing (a):
return do_async_job_1 (a,
lambda (b):
if (a>1):
do_async_job_2a (b,
lambda (c):
[...]
)
else:
do_async_job_2b (a,b,
lambda (d,e,f):
[...]
)
)

The call to do_async_job_1 passes 'a', and a callback, which is
specified 'in-line'. You can follow the logic of something like this
more easily than if each lambda is spun off into a different
function/method.

> > I think that a web server built on such a Python could have the
> > performance/scalability of thttpd, with the ease-of-programming
> > of Roxen. As far as I know, there's nothing like it out there.
> > Medusa would be put out to pasture. 8^)
>
> I'm afraid I haven't kept up -- what are Roxen and thttpd? What do
> they do that Apache doesn't?

thttpd (& Zeus, Squid, Xitami) use select()/poll() to gain performance
and scalability, but suffer from the same programmability problem as
Medusa (only worse, 'cause they're in C).

Roxen is written in Pike, a c-like language with gc, threads,
etc... Roxen is I think now the official 'GNU Web Server'.

Here's an interesting web-server comparison chart:

http://www.acme.com/software/thttpd/benchmarks.html

-Sam

> def thing (a):
> return do_async_job_1 (a,
> lambda (b):
> if (a>1):
> do_async_job_2a (b,
> lambda (c):
> [...]
> )
> else:
> do_async_job_2b (a,b,
> lambda (d,e,f):
> [...]
> )
> )
>
> The call to do_async_job_1 passes 'a', and a callback, which is
> specified 'in-line'. You can follow the logic of something like this
> more easily than if each lambda is spun off into a different
> function/method.

I agree that it is still ugly.

> http://www.acme.com/software/thttpd/benchmarks.html

I see. Any pointers to a graph of thttp market share?

--Guido van Rossum (home page: http://www.python.org/~guido/)

[GvR]
> ...
> Anything that assumes knowledge about how the C compiler and/or the
> CPU and OS lay out the stack is a no-no, because it means that the
> first thing one has to do for a port to a new architecture is figure
> out how the stack is laid out. Another thread in this list is porting
> Python to microplatforms like PalmOS. Typically the scheme Hackers
> are not afraid to delve deep into the machine, but I refuse to do that
> -- I think it's too risky.

The Icon language needs a bit of platform-specific context-switching
assembly code to support its full coroutine features, although its
bread-and-butter generators ("semi coroutines") don't need anything special.

The result is that Icon ports sometimes limp for a year before they support
full coroutines, waiting for someone wizardly enough to write the necessary
code. This can, in fact, be quite difficult; e.g., on machines with HW
register windows (where "the stack" can be a complicated beast half buried
in hidden machine state, sometimes needing kernel privilege to uncover).

Not attractive. Generators are, though <wink>.

threads-too-ly y'rs - tim

[Christian Tismer]
> ...
> But on the general issues:
> Can the Python-calls-C and C-calls-Python problem just be solved
> by turning the whole VM state into a data structure, including
> a Python call stack which is independent? Maybe this has been
> mentioned already.

The problem is that when C calls Python, any notion of continuation has to
include C's state too, else resuming the continuation won't return into C
correctly. The C code that *implements* Python could be reworked to support
this, but in the general case you've got some external C extension module
calling into Python, and then Python hasn't a clue about its caller's state.

I'm not a fan of continuations myself; coroutines can be implemented
faithfully via threads (I posted a rather complete set of Python classes for
that in the pre-DejaNews days, a bit more flexible than Icon's coroutines);
and:

> This would automagically produce ICON iterators (duck)
> and coroutines (cover).

Icon iterators/generators could be implemented today if anyone bothered
(Majewski essentially implemented them back around '93 already, but seemed
to lose interest when he realized it couldn't be extended to full
continuations, because of C/Python stack intertwingling).

> If I guess right, continuation passing could be done
> by just shifting tiny tuples around. Well, Tim, help me :-)

Python-calling-Python continuations should be easily doable in a "stackless"
Python; the key ideas were already covered in this thread, I think. The
thing that makes generators so much easier is that they always return
directly to their caller, at the point of call; so no C frame can get stuck
in the middle even under today's implementation; it just requires not
deleting the generator's frame object, and adding an opcode to *resume* the
frame's execution the next time the generator is called. Unlike as in Icon,
it wouldn't even need to be tied to a funky notion of goal-directed
evaluation.

don't-try-to-traverse-a-tree-without-it-ly y'rs - tim

Guido van Rossum wrote:
> ...
> > http://www.acme.com/software/thttpd/benchmarks.html
>
> I see. Any pointers to a graph of thttp market share?

thttpd currently has about 70k sites (of 5.4mil found by Netcraft). That
puts it at #6. However, it is interesting to note that 60k of those
sites are in the .uk domain. I can't figure out who is running it, but I
would guess that a large UK-based ISP is hosting a bunch of domains on
thttpd.

It is somewhat difficult to navigate the various reports (and it never
fails that the one you want is not present), but the data is from
Netcraft's survey at: http://www.netcraft.com/survey/

Cheers,
-g

--
Greg Stein, http://www.lyra.org/

[Christian Tismer]
> ...
> But on the general issues:
> Can the Python-calls-C and C-calls-Python problem just be solved
> by turning the whole VM state into a data structure, including
> a Python call stack which is independent? Maybe this has been
> mentioned already.

The problem is that when C calls Python, any notion of continuation has to
include C's state too, else resuming the continuation won't return into C
correctly. The C code that *implements* Python could be reworked to support
this, but in the general case you've got some external C extension module
calling into Python, and then Python hasn't a clue about its caller's state.

I'm not a fan of continuations myself; coroutines can be implemented
faithfully via threads (I posted a rather complete set of Python classes for
that in the pre-DejaNews days, a bit more flexible than Icon's coroutines);
and:

> This would automagically produce ICON iterators (duck)
> and coroutines (cover).

Icon iterators/generators could be implemented today if anyone bothered
(Majewski essentially implemented them back around '93 already, but seemed
to lose interest when he realized it couldn't be extended to full
continuations, because of C/Python stack intertwingling).

> If I guess right, continuation passing could be done
> by just shifting tiny tuples around. Well, Tim, help me :-)

Python-calling-Python continuations should be easily doable in a "stackless"
Python; the key ideas were already covered in this thread, I think. The
thing that makes generators so much easier is that they always return
directly to their caller, at the point of call; so no C frame can get stuck
in the middle even under today's implementation; it just requires not
deleting the generator's frame object, and adding an opcode to *resume* the
frame's execution the next time the generator is called. Unlike as in Icon,
it wouldn't even need to be tied to a funky notion of goal-directed
evaluation.

don't-try-to-traverse-a-tree-without-it-ly y'rs - tim

Tim Peters writes:
> I'm not a fan of continuations myself; coroutines can be
> implemented faithfully via threads (I posted a rather complete set
> of Python classes for that in the pre-DejaNews days, a bit more
> flexible than Icon's coroutines); and:

Continuations are more powerful than coroutines, though I admit
they're a bit esoteric. I programmed in Scheme for years without
seeing the need for them. But when you need 'em, you *really* need
'em. No way around it.

For my purposes (massively scalable single-process servers and
clients) threads don't cut it... for example I have a mailing-list
exploder that juggles up to 2048 simultaneous SMTP connections. I
think it can go higher - I've tested select() on FreeBSD with 16,000
file descriptors.

[...]

BTW, I have actually made progress borrowing a bit of code from SCM.
It uses the stack-copying technique, along with setjmp/longjmp. It's
too ugly and unportable to be a real candidate for inclusion in
Official Python. [.i.e., if it could be made to work it should be
considered a stopgap measure for the desperate].

I haven't tested it thoroughly, but I have successfully saved and
invoked (and reinvoked) a continuation. Caveat: I have to turn off
Py_DECREF in order to keep it from crashing.

| >>> import callcc
| >>> saved = None
| >>> def thing(n):
| ... if n == 2:
| ... global saved
| ... saved = callcc.new()
| ... print 'n==',n
| ... if n == 0:
| ... print 'Done!'
| ... else:
| ... thing (n-1)
| ...
| >>> thing (5)
| n== 5
| n== 4
| n== 3
| n== 2
| n== 1
| n== 0
| Done!
| >>> saved
| <Continuation object at 80d30d0>
| >>> saved.throw (0)
| n== 2
| n== 1
| n== 0
| Done!
| >>> saved.throw (0)
| n== 2
| n== 1
| n== 0
| Done!
| >>>

I will probably not be able to work on this for a while (baby due any
day now), so anyone is welcome to dive right in. I don't have much
experience wading through gdb tracking down reference bugs, I'm hoping
a brave soul will pick up where I left off. 8^)

http://www.nightmare.com/stuff/python-callcc.tar.gz
ftp://www.nightmare.com/stuff/python-callcc.tar.gz

-Sam

rushing@nightmare.com wrote:

[...]

> BTW, I have actually made progress borrowing a bit of code from SCM.
> It uses the stack-copying technique, along with setjmp/longjmp. It's
> too ugly and unportable to be a real candidate for inclusion in
> Official Python. [.i.e., if it could be made to work it should be
> considered a stopgap measure for the desperate].

I tried it and built it as a Win32 .pyd file, and it seems to
work, but...

> I haven't tested it thoroughly, but I have successfully saved and
> invoked (and reinvoked) a continuation. Caveat: I have to turn off
> Py_DECREF in order to keep it from crashing.

Indeed, and this seems to be a problem too hard to solve
without lots of work.
Since you keep a snapshot of the current machine stack,
it contains a number of object references which have been
valid when the snapshot was taken, but many are most
probably invalid when you restart the continuation.
I guess, incref-ing all current alive objects on
the interpreter stack would be the minimum, maybe more.

A tuple of necessary references could be used as an
attribute of a Continuation object. I will look
how difficult this is.

ciao - chris


--
Christian Tismer :^) <mailto:tismer@appliedbiometrics.com>
Applied Biometrics GmbH : Have a break! Take a ride on Python's
Kaiserin-Augusta-Allee 101 : *Starship* http://starship.python.net
10553 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

Christian Tismer wrote:
>
> rushing@nightmare.com wrote:
[...]

> > I haven't tested it thoroughly, but I have successfully saved and
> > invoked (and reinvoked) a continuation. Caveat: I have to turn off
> > Py_DECREF in order to keep it from crashing.

It is possible, but a little hard.
To take a working snapshot of the current thread's
stack, one needs not only the stack snapshot which
continue.c provides, but also a restorable copy of
all frame objects involved so far.
A copy of the current frame chain must be built, with
proper reference counting of all involved elements.
And this is the crux: The current stack pointer of the
VM is not present in the frame objects, but hangs
around somewhere on the machine stack.
Two solutions:

1) modify PyFrameObject by adding a field which holds
the stack pointer, when a function is called.
I don't like to change the VM in any way for this.
2) use the lasti field which holds the last VM instruction
offset. Then scan the opcodes of the code object
and calculate the current stack level. This is possible
since Guido's code generator creates code with the stack
level lexically bound to the code offset.

Now we can incref all the referenced objects in the frame.
This must be done for the whole chain, which is copied and
relinked during that. This chain is then held as a
property of the continuation object.

To throw the continuation, the current frame chain must
be cleared, and the saved one is inserted, together with
the machine stack operation which Sam has already.

A little hefty, isn't it?

ciao - chris

--
Christian Tismer :^) <mailto:tismer@appliedbiometrics.com>
Applied Biometrics GmbH : Have a break! Take a ride on Python's
Kaiserin-Augusta-Allee 101 : *Starship* http://starship.python.net
10553 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

[Sam]
> Continuations are more powerful than coroutines, though I admit
> they're a bit esoteric.

"More powerful" is a tedious argument you should always avoid <wink>.

> I programmed in Scheme for years without seeing the need for them.
> But when you need 'em, you *really* need 'em. No way around it.
>
> For my purposes (massively scalable single-process servers and
> clients) threads don't cut it... for example I have a mailing-list
> exploder that juggles up to 2048 simultaneous SMTP connections. I
> think it can go higher - I've tested select() on FreeBSD with 16,000
> file descriptors.

The other point being that you want to avoid "inside out" logic, though,
right? Earlier you posted a kind of ideal:

Recently I've written an async server that needed to talk to several
other RPC servers, and a mysql server. Pseudo-example, with
possibly-async calls in UPPERCASE:

auth, archive = db.FETCH_USER_INFO (user)
if verify_login(user,auth):
rpc_server = self.archive_servers[archive]
group_info = rpc_server.FETCH_GROUP_INFO (group)
if valid (group_info):
return rpc_server.FETCH_MESSAGE (message_number)
else:
...
else:
...

I assume you want to capture a continuation object in the UPPERCASE methods,
store it away somewhere, run off to your select/poll/whatever loop, and have
it invoke the stored continuation objects as the data they're waiting for
arrives.

If so, that's got to be the nicest use for continuations I've seen! All
invisible to the end user. I don't know how to fake it pleasantly without
threads, either, and understand that threads aren't appropriate for resource
reasons. So I don't have a nice alternative.

> ...
> | >>> import callcc
> | >>> saved = None
> | >>> def thing(n):
> | ... if n == 2:
> | ... global saved
> | ... saved = callcc.new()
> | ... print 'n==',n
> | ... if n == 0:
> | ... print 'Done!'
> | ... else:
> | ... thing (n-1)
> | ...
> | >>> thing (5)
> | n== 5
> | n== 4
> | n== 3
> | n== 2
> | n== 1
> | n== 0
> | Done!
> | >>> saved
> | <Continuation object at 80d30d0>
> | >>> saved.throw (0)
> | n== 2
> | n== 1
> | n== 0
> | Done!
> | >>> saved.throw (0)
> | n== 2
> | n== 1
> | n== 0
> | Done!
> | >>>

Suppose the driver were in a script instead:

thing(5) # line 1
print repr(saved) # line 2
saved.throw(0) # line 3
saved.throw(0) # line 4

Then the continuation would (eventually) "return to" the "print repr(saved)"
and we'd get an infinite output tail of:

Continuation object at 80d30d0>
n== 2
n== 1
n== 0
Done!
Continuation object at 80d30d0>
n== 2
n== 1
n== 0
Done!
Continuation object at 80d30d0>
n== 2
n== 1
n== 0
Done!
Continuation object at 80d30d0>
n== 2
n== 1
n== 0
Done!
...

and never reach line 4. Right? That's the part that Guido hates <wink>.

takes-one-to-know-one-ly y'rs - tim

Tim Peters wrote:

[to Sam]

> The other point being that you want to avoid "inside out" logic, though,
> right? Earlier you posted a kind of ideal:
>
> Recently I've written an async server that needed to talk to several
> other RPC servers, and a mysql server. Pseudo-example, with
> possibly-async calls in UPPERCASE:
>
> auth, archive = db.FETCH_USER_INFO (user)
> if verify_login(user,auth):
> rpc_server = self.archive_servers[archive]
> group_info = rpc_server.FETCH_GROUP_INFO (group)
> if valid (group_info):
> return rpc_server.FETCH_MESSAGE (message_number)
> else:
> ...
> else:
> ...
>
> I assume you want to capture a continuation object in the UPPERCASE methods,
> store it away somewhere, run off to your select/poll/whatever loop, and have
> it invoke the stored continuation objects as the data they're waiting for
> arrives.
>
> If so, that's got to be the nicest use for continuations I've seen! All
> invisible to the end user. I don't know how to fake it pleasantly without
> threads, either, and understand that threads aren't appropriate for resource
> reasons. So I don't have a nice alternative.

It can always be done with threads, but also without. Tried it
last night, with proper refcounting, and it wasn't too easy
since I had to duplicate the Python frame chain.

...

> Suppose the driver were in a script instead:
>
> thing(5) # line 1
> print repr(saved) # line 2
> saved.throw(0) # line 3
> saved.throw(0) # line 4
>
> Then the continuation would (eventually) "return to" the "print repr(saved)"
> and we'd get an infinite output tail of:
>
> Continuation object at 80d30d0>
> n== 2
> n== 1
> n== 0
> Done!
> Continuation object at 80d30d0>
> n== 2
> n== 1
> n== 0
> Done!

This is at the moment exactly what happens, with the difference that
after some repetitions we GPF due to dangling references
to too often decref'ed objects. My incref'ing prepares for
just one re-incarnation and should prevend a second call.
But this will be solved, soon.

> and never reach line 4. Right? That's the part that Guido hates <wink>.

Yup. With a little counting, it was easy to survive:

def main():
global a
a=2
thing (5)
a=a-1
if a:
saved.throw (0)

Weird enough and needs a much better interface.
But finally I'm quite happy that it worked so smoothly
after just a couple of hours (well, about six :)

ciao - chris

--
Christian Tismer :^) <mailto:tismer@appliedbiometrics.com>
Applied Biometrics GmbH : Have a break! Take a ride on Python's
Kaiserin-Augusta-Allee 101 : *Starship* http://starship.python.net
10553 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

Tim Peters writes:
> [Sam]
> > Continuations are more powerful than coroutines, though I admit
> > they're a bit esoteric.
>
> "More powerful" is a tedious argument you should always avoid <wink>.

More powerful in the sense that you can use continuations to build
lots of different control structures (coroutines, backtracking,
exceptions), but not vice versa.

Kinda like a better tool for blowing one's own foot off. 8^)

> Suppose the driver were in a script instead:
>
> thing(5) # line 1
> print repr(saved) # line 2
> saved.throw(0) # line 3
> saved.throw(0) # line 4
>
> Then the continuation would (eventually) "return to" the "print repr(saved)"
> and we'd get an infinite output tail [...]
>
> and never reach line 4. Right? That's the part that Guido hates <wink>.

Yes... the continuation object so far isn't very usable. It needs a
driver of some kind around it. In the Scheme world, there are two
common ways of using continuations - let/cc and call/cc. [.call/cc is what
is in the standard, it's official name is call-with-current-continuation]

let/cc stores the continuation in a variable binding, while
introducing a new scope. It requires a change to the underlying
language:

(+ 1
(let/cc escape
(...)
(escape 34)))
=> 35

'escape' is a function that when called will 'resume' with whatever
follows the let/cc clause. In this case it would continue with the
addition...

call/cc is a little trickier, but doesn't require any change to the
language... instead of making a new binding directly, you pass in
a function that will receive the binding:

(+ 1
(call/cc
(lambda (escape)
(...)
(escape 34))))
=> 35

In words, it's much more frightening: "call/cc is a function, that
when called with a function as an argument, will pass that function an
argument that is a new function, which when called with a value will
resume the computation with that value as the result of the entire
expression" Phew.

In Python, an example might look like this:

SAVED = None
def save_continuation (k):
global SAVED
SAVED = k

def thing():
[...]
value = callcc (lambda k: save_continuation(k))

# or more succinctly:
def thing():
[...]
value = callcc (save_continuation)

In order to do useful work like passing values back and forth between
coroutines, we have to have some way of returning a value from the
continuation when it is reinvoked.

I should emphasize that most folks will never see call/cc 'in the
raw', it will usually have some nice wrapper around to implement
whatever construct is needed.

-Sam

Sam (& others),

I thought I understood what continuations were, but the examples of
what you can do with them so far don't clarify the matter at all.

Perhaps it would help to explain what a continuation actually does
with the run-time environment, instead of giving examples of how to
use them and what the result it?

Here's a start of my own understanding (brief because I'm on a 28.8k
connection which makes my ordinary typing habits in Emacs very
painful).

1. All program state is somehow contained in a single execution stack.
This includes globals (which are simply name bindings in the botton
stack frame). It also includes a code pointer for each stack frame
indicating where the function corresponding to that stack frame is
executing (this is the return address if there is a newer stack frame,
or the current instruction for the newest frame).

2. A continuation does something equivalent to making a copy of the
entire execution stack. This can probably be done lazily. There are
probably lots of details. I also expect that Scheme's semantic model
is different than Python here -- e.g. does it matter whether deep or
shallow copies are made? I.e. are there mutable *objects* in Scheme?
(I know there are mutable and immutable *name bindings* -- I think.)

3. Calling a continuation probably makes the saved copy of the
execution stack the current execution state; I presume there's also a
way to pass an extra argument.

4. Coroutines (which I *do* understand) are probably done by swapping
between two (or more) continuations.

5. Other control constructs can be done by various manipulations of
continuations. I presume that in many situations the saved
continuation becomes the main control locus permanently, and the
(previously) current stack is simply garbage-collected. Of course the
lazy copy makes this efficient.



If this all is close enough to the truth, I think that continuations
involving C stack frames are definitely out -- as Tim Peters
mentioned, you don't know what the stuff on the C stack of extensions
refers to. (My guess would be that Scheme implementations assume that
any pointers on the C stack point to Scheme objects, so that C stack
frames can be copied and conservative GC can be used -- this will
never happen in Python.)

Continuations involving only Python stack frames might be supported,
if we can agree on the the sharing / copying semantics. This is where
I don't know enough see questions at #2 above).

--Guido van Rossum (home page: http://www.python.org/~guido/)