Mailman 3 - Python-Dev

How stackless can Python be?
by Christian Tismer May 23, 1999

May 23, 1999

Hi, 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 … [View More]

1 1

RE: [Python-Dev] 'stackless' python?
by rushing＠nightmare.com May 21, 1999

May 21, 1999

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 … [View More]

5 30

A "real" continuation example
by rushing＠nightmare.com May 20, 1999

May 20, 1999

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 … [View More]average Scheme > programmer. 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) ((list? x) (looper (car x)) (looper (cdr x))) (else (call/cc (lambda (here) (set! getnext (lambda () (here 'keep-going))) (produce-value x)))))) (define (getnext) (looper x) (produce-value #f)) (lambda () (call/cc (lambda (k) (set! produce-value k) (getnext)))))) (define (display-fringe x) (let ((g (list->generator x))) (let loop ((elt (g))) (if elt (begin (display elt) (display " ") (loop (g))))))) (define test-case '((1 ((2 3))) (4) () (((5)) 6))) (display-fringe test-case) > 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) class list_generator: 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.walk (item) else: self.item = x # call self.suspend() with a continuation # that will continue walking the tree call_cc (self.suspend) 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 if self.k_suspend: # resume the suspended walk self.k_suspend (None) else: self.walk (self.x) def suspend (self, k_suspend): self.k_suspend = k_suspend # return a value for __call__ self.k_produce (self.item) 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. -Sam [View Less]

3 3

continuations and C extensions?
by Aaron Watters May 19, 1999

May 19, 1999

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 embedding and extensions, and this is generally one of the … [View More]

1 0

Is there another way to solve the continuation problem?
by rushing＠nightmare.com May 19, 1999

May 19, 1999

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 … [View More]handlers using the information > from exceptions. > [... code ...] Well, you just re-invented the 'Reactor' pattern! 8^) http://www.cs.wustl.edu/~schmidt/patterns-ace.html > 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. -Sam [View Less]

1 0

Is there another way to solve the continuation problem?
by Skip Montanaro May 18, 1999

May 18, 1999

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 … [View More]

2 1

Re: [Python-Dev] 'stackless' python?
by rushing＠nightmare.com May 18, 1999

May 18, 1999

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 Programming Languages": 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 … [View More]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. Yup. > 2. A continuation does something equivalent to making a copy of the > entire execution stack. Yup. > 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. Yup. > 4. Coroutines (which I *do* understand) are probably done by swapping > between two (or more) continuations. Yup. Here's an example in Scheme: http://www.nightmare.com/stuff/samefringe.scm 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 ...] [View Less]

2 1

coroutines vs. continuations vs. threads
by Aaron Watters May 18, 1999

May 18, 1999

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 don't. 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 … [View More]

5 7

another good motivation
by rushing＠nightmare.com May 18, 1999

May 18, 1999

"Escaping the event loop: an alternative control structure for multi-threaded GUIs" http://cs.nyu.edu/phd_students/fuchs/ http://cs.nyu.edu/phd_students/fuchs/gui.ps -Sam

1 0

Re: [Python-Dev] coroutines vs. continuations vs. threads
by rushing＠nightmare.com May 18, 1999

May 18, 1999

Jeremy Hylton writes: > I have to admit that I'm a bit unclear on the motivation for all > this. As Gordon said, the state machine approach seems like it would > be a good approach. For simple problems, state machines are ideal. Medusa uses state machines that are built out of Python methods. But past a certain level of complexity, they get too hairy to understand. A really good example can be found in /usr/src/linux/net/ipv4. 8^) -Sam

1 0