Here is a bit of an idea that I first came up with some years ago. Guido's
response at the time was "sounds reasonable as long as we dont slow the
normal case down".
To cut a long story short, I would like eval and exec to be capable of
working with arbitrary mapping objects rather than only dictionaries. The
general idea is that I can provide a class with mapping semantics, and pass
this to exec/eval.
This would give us 2 seriously cool features (that I want <wink>), should
anyone decide to write code that enables them:
* Case insensitive namespaces. This would be very cool for COM, and as far
as I know would please the Alice people. May open up more embedding
opportunities that are lost if people feel strongly about this issue.
* Dynamic name lookups. At the moment, dynamic attribute lookups are
simple, but dynamic name lookups are hard. If I execute code "print foo",
foo _must_ pre-exist in the namespace. There is no reasonable way I can
some up with so that I can fetch "foo" as it is requested (raising the
NameError if necessary). This would also be very cool for some of the COM
work - particularly Active Scripting.
Of course, these would not be enabled by standard Python, but would allow
people to create flexible execution environments that suit their purpose.
Any comments on this? Is it a dumb idea? Anyone have a feel for how deep
these changes would cut? Its not something I want to happen soon, but it
does seem a reasonable mechanism that can provide very flexible
All this talk about stack frames and manipulating them at runtime has
reminded me of one of my biggest gripes about Python. When I say "biggest
gripe", I really mean "biggest surprise" or "biggest shame".
That is, Python is very interactive and dynamic. However, when I am
debugging Python, it seems to lose this. There is no way for me to
effectively change a running program. Now with VC6, I can do this with C.
Although it is slow and a little dumb, I can change the C side of my Python
world while my program is running, but not the Python side of the world.
Im wondering how feasable it would be to change Python code _while_ running
under the debugger. Presumably this would require a way of recompiling the
current block of code, patching this code back into the object, and somehow
tricking the stack frame to use this new block of code; even if a first-cut
had to restart the block or somesuch...
Any thoughts on this?
to make the core interpreter stackless is one thing.
Turning functions which call the interpreter
from some deep nesting level into versions,
which return a frame object instead which is
to be called, is possible in many cases.
Internals like apply are rather uncomplicated to convert.
CallObjectWithKeywords is done.
What I have *no* good solution for is map.
Map does an iteration over evaluations and keeps
state while it is running. The same applies to reduce,
but it seems to be not used so much. Map is.
I don't see at the moment if map could be a killer
for Tim's nice mini-thread idea. How must map work,
if, for instance, a map is done with a function
which then begins to switch between threads,
before map is done? Can one imagine a problem?
Maybe it is no issue, but I'd really like to
know wether we need a stateless map.
(without replacing it by a for loop :-)
ciao - chris
Christian Tismer :^) <mailto:firstname.lastname@example.org>
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:
> 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
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
| >>> saved
| <Continuation object at 80d30d0>
| >>> saved.throw (0)
| n== 2
| n== 1
| n== 0
| >>> saved.throw (0)
| n== 2
| n== 1
| n== 0
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^)
Tim Peters writes:
> The Scheme solution was the hardest to write, but is a largely
> mechanical transformation of a recursive fringe-lister that
> constructs the entire fringe in one shot. Continuations are used
> twice: to enable the recursive routine to resume itself where it
> left off, and to get each leaf value back to the caller. Getting
> that to work required rebinding non-local identifiers in delicate
> ways. I doubt the intent would be clear to an average Scheme
It's the only way to do it - every example I've seen of using call/cc
looks just like it.
I reworked your Scheme a bit. IMHO letrec is for compilers, not for
people. The following should be equivalent:
(define (list->generator x)
(let ((produce-value #f))
(define (looper x)
(cond ((null? x) 'nada)
(looper (car x))
(looper (cdr x)))
(set! getnext (lambda () (here 'keep-going)))
(set! produce-value k)
(define (display-fringe x)
(let ((g (list->generator x)))
(let loop ((elt (g)))
(display " ")
(define test-case '((1 ((2 3))) (4) () (((5)) 6)))
> So what would this look like in Continuation Python?
Here's my first hack at it. Most likely wrong. It is REALLY HARD to
do this without having the feature to play with. This presumes a
function "call_cc" that behaves like Scheme's. I believe the extra
level of indirection is necessary. (i.e., call_cc takes a function as
an argument that takes a continuation function)
def __init__ (x):
self.x = x
self.k_suspend = None
self.k_produce = None
def walk (self, x):
if type(x) == type():
for item in x:
self.item = x
# call self.suspend() with a continuation
# that will continue walking the tree
def __call__ (self):
# call self.resume() with a continuation
# that will return the next fringe element
return call_cc (self.resume)
def resume (self, k_produce):
self.k_produce = k_produce
# resume the suspended walk
def suspend (self, k_suspend):
self.k_suspend = k_suspend
# return a value for __call__
Variables hold continuations have a 'k_' prefix. In real life it
might be possible to put the suspend/call/resume machinery in a base
class (Generator?), and override 'walk' as you please.
the immutable GvR intones:
> 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).
What if there are native C calls mixed in (eg, list.sort calls back to
myclass.__cmp__ which decides to do a call/cc). One of the really
big advantages of Python in my book is the relative simplicity of
and extensions, and this is generally one of the failings of lisp
I understand lots of scheme implementations purport
to be extendible and embeddable, but in practice you can't do it with
*existing* code -- there is always a show stopper involving having to
change the way some Oracle library which you don't have the source for
does memory management or something... I've known several grad students
who have been bitten by this... I think having to unroll the C stack
might be one problem area.
With, eg, a netscape nsapi embedding you can actually get into netscape
code calls my code calls netscape code calls my code... suspends in a
continuation? How would that work? [my ignorance is torment!]
Threading and extensions are probably also problematic, but at least
better understood, I think. Just kvetching. Sorry.
-- Aaron Watters
ps: Of course there are valid reasons and excellent advantages
to having continuations, but it's also interesting to consider the
There ain't no free lunch.
Skip Montanaro writes:
> Can exceptions be coerced into providing the necessary structure
> without botching up the application too badly? Seems that at some
> point where you need to do some I/O, you could raise an exception
> whose second expression contains the necessary state to get back to
> where you need to be once the I/O is ready to go. The controller
> that catches the exceptions would use select or poll to prepare for
> the I/O then dispatch back to the handlers using the information
> from exceptions.
> [... code ...]
Well, you just re-invented the 'Reactor' pattern! 8^)
> One thread, some craftiness needed to construct things. Seems like
> it might isolate some of the statefulness to smaller functional
> units than a pure state machine. Clearly not as clean as
> continuations would be. Totally bogus? Totally inadequate? Maybe
> Sam already does things this way?
What you just described is what Medusa does (well, actually, 'Python'
does it now, because the two core libraries that implement this are
now in the library - asyncore.py and asynchat.py). asyncore doesn't
really use exceptions exactly that way, and asynchat allows you to add
another layer of processing (basically, dividing the input into
logical 'lines' or 'records' depending on a 'line terminator').
The same technique is at the heart of many well-known network servers,
including INND, BIND, X11, Squid, etc.. It's really just a state
machine underneath (with python functions or methods implementing the
'states'). As long as things don't get too complex. Python
simplifies things enough to allow one to 'push the difficulty
envelope' a bit further than one could reasonably tolerate in C. For
example, Squid implements async HTTP (server and client, because it's
a proxy) - but stops short of trying to implement async FTP. Medusa
implements async FTP, but it's the largest file in the Medusa
distribution, weighing in at a hefty 32KB.
The hard part comes when you want to plug different pieces and
protocols together. For example, building a simple HTTP or FTP server
is relatively easy, but building an HTTP server *that proxied to an
FTP server* is much more difficult. I've done these kinds of things,
viewing each as a challenge; but past a certain point it boggles.
The paper I posted about earlier by Matthew Fuchs has a really good
explanation of this, but in the context of GUI event loops... I think
it ties in neatly with this discussion because at the heart of any X11
app is a little guy manipulating a file descriptor.
Okay, from my feeble understanding of the problem it appears that
coroutines/continuations and threads are going to be problematic at best for
Sam's needs. Are there other "solutions"? We know about state machines.
They have the problem that the number of states grows exponentially (?) as
the number of state variables increases.
Can exceptions be coerced into providing the necessary structure without
botching up the application too badly? Seems that at some point where you
need to do some I/O, you could raise an exception whose second expression
contains the necessary state to get back to where you need to be once the
I/O is ready to go. The controller that catches the exceptions would use
select or poll to prepare for the I/O then dispatch back to the handlers
using the information from exceptions.
"""maintains exception raise info and selects one to go to next"""
waiters = WaveHands()
r, w, e = select([...], [...], [...])
# using r,w,e, select a waiter to call
func, place = waiters.choose_one(r,w,e)
except IOSetup, info:
if place == "spam":
# whatever I/O we needed to do is ready to go
bytes = read(some_fd)
# need to read some more from some_fd. args are:
# function, target, fd category (r, w), selectable object,
raise IOSetup, (spam_func, "eggs" , "r", some_fd)
elif place == "eggs":
# that next chunk is ready - get it and proceed...
elif yadda, yadda, yadda...
One thread, some craftiness needed to construct things. Seems like it might
isolate some of the statefulness to smaller functional units than a pure
state machine. Clearly not as clean as continuations would be. Totally
bogus? Totally inadequate? Maybe Sam already does things this way?
Skip Montanaro | Mojam: "Uniting the World of Music" http://www.mojam.com/
skip(a)mojam.com | Musi-Cal: http://www.musi-cal.com/
Guido van Rossum writes:
> 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?
This helped me a lot, and is the angle used in "Essentials of
Usually when folks refer to a 'stack', they're refering to an
*implementation* of the stack data type: really an optimization that
assumes an upper bound on stack size, and that things will only be
pushed and popped in order.
If you were to implement a language's variable and execution stacks
with actual data structures (linked lists), then it's easy to see
what's needed: the head of the list represents the current state. As
functions exit, they pop things off the list.
The reason I brought this up (during a lull!) was that Python is
already paying all of the cost of heap-allocated frames, and it didn't
seem to me too much of a leap from there.
> 1. All program state is somehow contained in a single execution stack.
> 2. A continuation does something equivalent to making a copy of the
> entire execution stack.
> I.e. are there mutable *objects* in Scheme?
> (I know there are mutable and immutable *name bindings* -- I think.)
Yes, Scheme is pro-functional... but it has arrays, i/o, and set-cdr!,
all the things that make it 'impure'.
I think shallow copies are what's expected. In the examples I have,
the continuation is kept in a 'register', and call/cc merely packages
it up with a little function wrapper. You are allowed to stomp all
over lexical variables with "set!".
> 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.
Yup. Here's an example in Scheme:
Somewhere I have an example of coroutines being used for parsing, very
elegant. Something like one coroutine does lexing, and passes tokens
one-by-one to the next level, which passes parsed expressions to a
compiler, or whatever. Kinda like pipes.
> 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.
Yes... I think backtracking would be an example of this. You're doing
a search on a large space (say a chess game). After a certain point
you want to try a previous fork, to see if it's promising, but you
don't want to throw away your current work. Save it, then unwind back
to the previous fork, try that option out... if it turns out to be
better then toss the original.
> 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.)
I think you're probably right here - usually there are heavy
restrictions on what kind of data can pass through the C interface.
But I know of at least one Scheme (mzscheme/PLT) that uses
conservative gc and has c/c++ interfaces. [... dig dig ...]
The illustrious Sam Rushing avers:
>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.
Frankly, I think I thought I understood this once but now I know I
How're continuations more powerful than coroutines?
And why can't they be implemented using threads (and semaphores etc)?
...I'm not promising I'll understand the answer...
-- Aaron Watters
I taught I taw a putty-cat!