coroutines and continuations ( in Python? - long discussion )
Steven D. Majewski
A while ago there was a (crossposted) thread about about pipes:
most of the discussion was about Perl, but it caused me to repost my
redirect.py modules ( to show how *easy* the problem was in Python! ;-),
and also to think more about the utility of having a more general
2-way interface.
The tostring/tolines functions in redirect are able to package
the printed output from a function and return it as a python
object. This gives some of the capability of unix pipes without
having to actually pipe thru the OS - the non-trivial semantic
difference being that redirect does not produce any concurrency -
the inner function must run to completion before the redirecting
wrapper can return the collected output to the calling function.
Actual concurrency of independent threads is not required, though:
coroutine would be sufficient since the read/write is a
blocking operation that could be an implicit transfer of control.
I know Guido is not as enamored of coroutines as old Icon-ers like
Tim and I. He has (more than once, I think) stated the view that
anything you could do with coroutines, you can do with classes.
This view is certainly true from a theoretical POV - complemantarity
of the object=method+data and closure=function+environment and all
that, and coroutines are just a subset of continuations, etc., etc.
But the difference is that saving of state into an objects instance
variables has to be explicitly programmed, where coroutines and
continuation are implicit. ( And being able to turn a pair of
read/writes in a pair of functions into a coroutine return/continue,
mediated transparently by a file-like python object would seem to
be a potential big win for code-reuse. )
It is possible to program a pair of classes that cooperate with each
other, but there is no way to make a class that can link two arbitrary
functions by their read/write methods. The flow of control is not
symetrical: one of the functions must RETURN before the other can
get continue.
The fact that Python frames are (heap allocated) objects and not
just pushed on the stack, means that they can persist whether that
function is active or not. In fact, an exception passes you a link
to a whole bunch of frameobjects in it's traceback object.
A frame object appears contain all of the necessary state to serve
as a continuation except that the interpreter's stactpointer
and blockpointer are not preserved, and when a stack frame is
unwound by an exception, the stack is emptied by poping and
DECREF-ing the contents.
I looks to me that it would no be difficult to give Python
continuations: if a stackpointer and blockpointer are added
to the frameobject, all that is missing is an operation to
package a frameobject-continuation, and a 'resume' operation
( a change to ceval.c ) that takes a frame/continuation object
instead of creating a new frameobject.
I am far from a complete understanding of ceval and what happens
to frame and blocks in Python, so I may be missing some obvious
problem ( And all the details of *exactly* how to do this aren't
completely clear to me yet, either ).
Comments ?
What I initially wanted was some sort of cooperative coroutine
control between two functions mediated by a file-like object
that used it's read/write methods to alternate control on the
two functions. Except for inet servers, most of the cases where
I might want threads seem to actually fit a blocking coroutine
model better than parallel threads, and in the cases where it
doesn't, I'm quite happy to use unix processes for threading.
I would like to have threads on dos/mac, but I don't know if
any of the portable (on unix) threads packages work on those
platforms, or how much work it would be to get really portable
threads written in C to work in Python. But since the easiest
method of adding coroutine control appears to be the more
general case of adding continuations to Python, I would think
that this also gives a possible method of adding preemptive
threads to the Python interpreter in a portable manner by
coding it into the virtual machine rather than the real machine.
Comments ?
[ Encouraging or _discouraging_ comments invited! If I'm blind
to some fatal flaw or don't understand what's going on in
ceval, I'ld be happy to hear about it before I actually
waste time in trying to implement it! ]
-- Steve Majewski (804-982-0831) <sd...@Virginia.EDU> --
-- UVA Department of Molecular Physiology and Biological Physics --
-- Box 449 Health Science Center Charlottesville,VA 22908 --
[ "Cognitive Science is where Philosophy goes when it dies ...
if it hasn't been good!" - Jerry Fodor ]
Tim Peters
but complete example. Maybe someone knows a better way, or maybe someone
will find it helpful, or maybe it will help the discussion? At least it
will give people something to pick on <wink>.
Here's the example in Icon, where co-routines are a fundamental (built-
in; oodles of language support) concept, but avoiding Icon's specialized
terminology:
# "create <expr>" creates a closure (kinda) for expression expr
# "^c" create a distinct copy of closure c (kinda)
# "@c" resumes closure c (kinda)
# within a closure, "suspend <expr>" acts kinda like a resumable return;
# local state (vrbls & "the instruction counter") is preserved
procedure main()
local f1, f2
f1 := create intsfrom(5)
f2 := ^f1
write(@f1," ",@f1," ",@f2," ",@f2," ",@f2," ",@f1)
end
procedure intsfrom(i)
repeat {
suspend i
i := i + 1
}
end
That prints
5 6 5 6 7 7
In Python, when I want a "resumable function" f(*args), it goes like
this:
1) Change the function into a class:
class f:
def __init__(self, *args):
# save away the arguments, or info derived from them,
# into self. data members
2) Define a "_wrap" method in a stylized way. For an object o of class
f, o._wrap() returns a "wrapper object" that implements the resumable
function abstraction. I.e., after w = o._wrap(), doing w() returns the
function's 1st result, doing w() again returns the 2nd result, & so
on (if the function generates a finite number of results, it's often
convenient for w() to return None when it's finished).
def _wrap(self):
return _Wrapper(self,
[list of initial values for f's locals]).invoke
3) Define a "_work" method that's the body of the function, written
to take its local values from its "state" argument. Changes to the
(conceptual) local state must be written back into the state argument
before a return.
def _work(self, state):
[list of locals] = state
# do the work; do "return <expr>" where Icon has "suspend <expr>"
4) The _Wrapper class doesn't depend on any specifics of the function
body; it just knows that the function's work is done by a "_work"
method, and that the _work method wants a "state" argument:
class _Wrapper:
def __init__(self, func, initstate):
self.func = func # not used in this example
self.worker = func._work
self.state = initstate
def invoke(self):
return self.worker(self.state)
Given the little bit of _Wrapper machinery in #4, the Icon example can be
written following points #1-3 like so:
class intsfrom:
def __init__(self, n):
self.n = n
def _wrap(self):
return _Wrapper(self, [self.n]).invoke
def _work(self, state):
[i] = state
state[0] = i+1
return i
f = intsfrom(5)
f1 = f._wrap()
f2 = f._wrap()
print f1(), f1(), f2(), f2(), f2(), f1()
That also prints 5 6 5 6 7 7.
Note that while the example is trivial, the _method_ works well even in
very complex settings.
A good part of this is due to defining _wrap() as returning what "looks
like" a no-argument function: because of this, all _users_ of "resumable
functions" can invoke them in the same way, without knowing anything
about the arguments they "really need", or indeed even that they're
anything special. This makes it easy to write general higher-level
functions that can interleave result sequences from collections of
arbitrary resumable functions in arbitrary ways.
Another good part of it is due to _not_ storing execution state in an
intsfrom object itself, but in the wrapper around it. As the example
shows in a small way, this allows any number of _independent_ executable
instances to be created from a single instance of intsfrom. Alas, it's
hard to show the real advantage of that in a simple example; the short &
vague course is that it takes the teeth out of aliasing.
Notes:
1) Doing the wrapping by hand (packaging the function and its state by
hand) doesn't bother me, and to the contrary it's sometimes useful to
define derived _Wrapper classes that do a little more work in their
"invoke" method. E.g., in a package providing pattern-matching
objects, it was useful to define a wrapper class whose invoke method
itself had a bit of state, to capture the state of the global match
the first time thru, and restore that state when it saw that
self.worker(self.state) couldn't find more things to try.
2) An invocation of w = object._wrap() is itself an instance method call
(to _Wrapper.invoke), which in turn does two instance attribute
lookups (self.worker & self.state) and another instance method call
(to self.worker). Do a lot of this, & it's not cheap.
3) Rewriting the function body (_work) to take its locals out of a list,
and to store them back into the list when they're updated, is pretty
mechanical.
4) But the "preserve the 'instruction counter' across calls" bit is a
bitch. It reminds me of the days when I needed to do recursion in
Fortran or assembler "by hand": making the machinery explicit in the
code is a complex & obfuscating transformation.
Here's a relatively simple example of the last point:
class _PatAlt(_PatList):
...
def _wrap(self):
return _InfoWrapper(self, [0, self.pats[0]._wrap()]).invoke
def _work(self, state):
[i, wrap] = state
while 1:
if wrap():
state[0], state[1] = i, wrap
return 1
else:
i = i + 1
if i < len(self.pats):
wrap = self.pats[i]._wrap()
else:
return 0
The "_work" routine _started_ life in suspend-extended pseudo-Python as
def work(self):
for p in self.pats:
wrap = p._wrap()
while wrap():
suspend 1
return 0
and most of the hair is to fake the effect of resuming "in the middle" of
the nested loops.
So when Steve says:
> But the difference is that saving of state into an objects instance
> variables has to be explicitly programmed, where coroutines and
> continuation are implicit.
I agree so far as it goes, but think the "instruction counter" bit is
1000x worse. For a truly complex function, the transformation to fake
that can be truly excruciating, while preserving local variables in the
"state" argument remains pretty mechanical.
So what would I like? I'm not sure. Two things I don't want to see:
1) Changing Python at a deep level to support coroutines/closures.
2) Any scheme that shares with Icon that the _resumption_ of such beasts
requires special syntax. The technique above makes a special case out
of _creating_ a "resumable function" object, but the resumptions
themselves look and act like ordinary function calls. That has
practical value, in limiting the visibility of implementation
decisions.
OTOH, I'd very much _like_ some language help for this style of
programming, provided it can be done with little effect on the language
as a whole. E.g., I have no problem at all with having to explicitly
"wrap" a function that I want to use in coroutine fashion, and that makes
me suspect almost all of it could be achieved via a new "wrapped
function" object that doesn't affect the visible semantics of existing
objects, or the implementation of most existing objects.
BTW, the primary difference between "suspend" and "return" in Icon is
that while both return a result, "suspend" explicitly says that the
function can-- and "return" that it cannot --be resumed again. This is
nice for self-documentation and error-catching purposes, but isn't
essential.
Warning: What I called "resumable functions" above can be implemented via
coroutines, but aren't as general as the latter, as I understand them.
And if _any_ discussion needs complete examples to illustrate the
intended concepts, it's this one, because the same phrases are used by
many people with different meanings in mind.
One difference: a "resumable function" is all about preserving local
execution state across resumptins, and nothing about arbitrary (goto-
like) transfer of control. General coroutines are, I believe, about
both.
progress-is-90%-definition<wink>-ly y'rs - tim
Tim Peters t...@ksr.com
not speaking for Kendall Square Research Corp
Steven D. Majewski
Thanks for that long and thoughtful reply, Tim.
I've used the same sort of techniques, but you've clearly thought
it out into a more systematic method.
( So we're assigning you chapter 14 of "Python - The BOOK!" :-)
Skipping over the current usage example to proposed mods discussion,
On Apr 30, 1:29, Tim Peters wrote:
>
> So what would I like? I'm not sure. Two things I don't want to see:
>
> 1) Changing Python at a deep level to support coroutines/closures.
>
[ With due caveat's that I haven't worked out the implementation
and there still may be a fatal flaw in my proposed scheme... ]
Well - one of the things that excited me was that it looked like
a deep change is not necessary. Minimal change to the language,
addition of some fields to frame-objects or creation of a new
continuation object with ref to a frame-object, one more byte
code to create one of these objects, and a way to enter/resume one.
I see minimal or no impact to the rest of the language or to
programs that don't use these features. ( the pyc file magic
will have to be changed, but since it is a downwardly compatible
change, there is no reason to reject the previous compiled code.
Old compliers can and should reject newer .pyc files that may
use this feature. )
The possibility of deeper change enters if one considers
generalizing continuations to provide "restartable"
exceptions - but the way around this is to NOT change
the semantics of exceptions, but merely to allow a 'raise'
to pass a continuation object as its optional arg.
> 2) Any scheme that shares with Icon that the _resumption_ of such beasts
> requires special syntax. The technique above makes a special case out
> of _creating_ a "resumable function" object, but the resumptions
> themselves look and act like ordinary function calls. That has
> practical value, in limiting the visibility of implementation
> decisions.
One way is to make continuation objects callable, just like functions,
methods, and class creators:
result, cont = cofunc( args ) # returns a value, continuation tuple
use( result )
result, cont = cont() # re-enter
[ I'm not yet sure how or whether to fit args to the continuation into
this scheme. Or how exactly to express "capture the current
continuation" in a return statement. ... vague mumbling about
whether the thing that creates a continuation ought to be a
(pseudo)function or an expression in Python goes here ... :-) ]
> OTOH, I'd very much _like_ some language help for this style of
> programming, provided it can be done with little effect on the language
> as a whole. E.g., I have no problem at all with having to explicitly
> "wrap" a function that I want to use in coroutine fashion, and that makes
> me suspect almost all of it could be achieved via a new "wrapped
> function" object that doesn't affect the visible semantics of existing
> objects, or the implementation of most existing objects.
The type of "wrapper" I was envisioning in the pipe example would be a
class that takes two functions as args, and rebinds stdin/stdout to it
self. Its read and write methods encapsulate the coroutine control:
the called functions do no explicit save/restore of state - they
merely call obj.read or obj.write. ( Steve waves his hand magically,
here: I worked this all out BEFORE I looked at a possible implementation -
I'll go back and see if I can translate my squiggly flow-of-control drawing
into terms of my proposed solution, and see if it *STILL* makes any sense!
Once I convinced myself that coroutines were the sufficient and
necessary missing element for a solution, I stopped thinking about the
problem and started thinking about coroutines. ;-)
> BTW, the primary difference between "suspend" and "return" in Icon is
> that while both return a result, "suspend" explicitly says that the
> function can-- and "return" that it cannot --be resumed again. This is
> nice for self-documentation and error-catching purposes, but isn't
> essential.
So, what I see is no special syntax to resume a continuation, and no
built-in wrapper is required; the "special" syntax is in the return.
Maybe "suspend value" returning a value,continuation tuple is better
than "return value, current_continuation()" , in avoiding my problem
of expressing that current_continuation() really ought to refer to
the next-line after return, not the instruction immediately AFTER
the capture-continuation code ( which is going to be 'build-tuple' &
'return' )
> Warning: What I called "resumable functions" above can be implemented via
> coroutines, but aren't as general as the latter, as I understand them.
> And if _any_ discussion needs complete examples to illustrate the
> intended concepts, it's this one, because the same phrases are used by
> many people with different meanings in mind.
>
> One difference: a "resumable function" is all about preserving local
> execution state across resumptins, and nothing about arbitrary (goto-
> like) transfer of control. General coroutines are, I believe, about
> both.
Well - I started out trying to solve the "pipe" problem, but then
discovered (suprisingly!) that the simplest solution is also the
most general one.
However - what I DON'T want is scheme-like continuation syntax.
Python is ( and should continue to be ) and easy to use language.
Scheme continuation are extremely powerful, but I think they are
rather confusing to use. Icon co-routines and co-expressions, on
the other hand, give a subset of the capabilities of generalized
continuations, but that subset is quite easy to use and understand,
and captures a significant portion of those capabilities.
Exception handling capture the other sizable subset. I prefer the
functionality of exceptions and coroutines, without binding them
to any particular implementation. My use of the word continuation
in this discussion may lead you to think otherwise, but that's
just a side effect of the fact that I don't know any better way to
talk about it.
Despite scurrilous rumors to the contrary, I DO NOT want to change
Python into Scheme! :-)
[ And why I'm trying to steer clear of fork-like magic functions
that seem to return different things at different instances. ]
- Steve Majewski (804-982-0831) <sd...@Virginia.EDU>
Tim Peters
for short), with "write" corresponding to "suspend" (produce an output),
and "read" corresponding to "resume a resfunc argument or data member or
whatever" (consume an input). Here's a runnable example, using the
"intsfrom" resfunc from my previous msg as the head of a pipe:
class _Wrapper: # same as last time
def __init__(self, func, initstate):
self.worker = func._work
self.state = initstate
def invoke(self):
return self.worker(self.state)
class intsfrom: # same as last time
def __init__(self, n): # output = n, n+1, n+2, ...
self.n = n
def _wrap(self):
return _Wrapper(self, [self.n]).invoke
def _work(self, state):
[i] = state
state[0] = i+1
return i
class PipeStage: # for resfuncs in the pipe beyond the first, w/ no state
def _wrap(self, sourcewrap):
return _Wrapper(self, sourcewrap).invoke
class linear_combination(PipeStage):
def __init__(self, a, b): # output = input * a + b
self.a, self.b = a, b
def _work(self, source):
return source()*self.a + self.b
class filter_divby(PipeStage):
def __init__(self, n): # output = elts of input divisible by n
self.n = n
def _work(self, source):
while 1:
next = source()
if next % self.n == 0:
return next
def makepipe(*stages): # make a left-to-right pipeline from resfuncs
pipe = stages[0]._wrap()
for stage in stages[1:]:
pipe = stage._wrap(pipe)
return pipe
if3 = intsfrom(3)
lc31 = linear_combination(3,1)
fdb5 = filter_divby(5)
pipe1 = makepipe(if3, lc31, fdb5)
pipe2 = makepipe(if3, lc31, filter_divby(7))
for i in range(10):
print pipe1(), pipe2()
That prints
10 28
25 49
40 70
55 91
70 112
85 133
100 154
115 175
130 196
145 217
I.e., a pipe stage is just a resfunc with a resfunc argument
(corresponding to "stdin").
Notes:
+ The main pain is the same: faking the preservation of the "program
counter" can be excruciating (not really shown above; see preceding
msg).
+ This scheme produces an "output driven" pipe: no stage produces a
result until a later stage asks for one. So, as the above shows, it's
pleasant for handling unbounded streams.
+ It's even _possible_ to overload "|" so that
pipe1 = if3 | lc31 | fdb5
pipe2 = if3 | lc31 | filter_divby(7)
works. However, it's painful to do that cuz Python is picky about what
it allows as arguments to "|". Specifically, the _wrap methods have to
be changed to return class instances instead of instance method
objects, and that change propagates in icky ways throughout the scheme.
> ...
> ( So we're assigning you chapter 14 of "Python - The BOOK!" :-)
Cool, but I'd rather make that chapter unnecessary <wink>.
> ...
> The possibility of deeper change enters if one considers generalizing
> continuations to provide "restartable" exceptions
Given that the longer I use exceptions, the less places I don't regret
having used them, I've got no interest in making exceptions even more
bizarre <wink>. One advantage of resfuncs over general coroutines is
that resfunc resumptions and suspensions occur in ordinary stack-like
order, so that resfuncs don't necessarily require significant reworking
of the existing exception mechanism; could be that all it would take for
_nice_ semantics is to mark a resfunc as unresumable if an uncaught
exception passed through it while it was active.
> - but the way around this is to NOT change the semantics of exceptions,
> but merely to allow a 'raise' to pass a continuation object as its
> optional arg.
Agreed that if it must be done <wink>, that's the way to do it.
> ...
> One way is to make continuation objects callable, just like functions,
> methods, and class creators:
>
> result, cont = cofunc( args ) # returns a value, continuation tuple
> use( result )
> result, cont = cont() # re-enter
You don't want the 1st call to look different than all the others; any
concrete, specific example would convince you of that instantly <smile>.
I'd suggest this instead, where "resfunc" is a new built-in (whatever)
with the same signature as the built-in "apply":
resfuncobject = resfunc( callable_object, argument_tuple )
In Python pseudo-code, the implementation of resfunc would look something
like:
ResumeError = 'ResumeError'
class _Resfunc:
def __init__(self, args):
if len(args) != 2:
raise TypeError, 'need 2 args'
func, a = args
if not is_callable_object(func):
raise TypeError, '1st arg must be callable object'
if type(a) is not type(()):
raise TypeError, '2nd arg must be tuple'
self.func, self.args = func, a
self.frameobject = build a frame object, wave hands
self.called = 0 # function not yet called
self.resumable = 1
def invoke(self):
if not self.resumable:
raise ResumeError
if self.called:
resume self.frameobject and return its result
else:
self.called = 1
return apply(self.func, self.args) using self.frameobject
# if 'suspend' is introduced, would be nice to have
# return via 'return' set self.resumable = 0
def resfunc(*args):
return _Resfunc(args).invoke
def resfunc_fresh_copy(rf):
me = rf.im_self
if me is not a _Resfunc instance: raise TypeError, etc
return resfunc(me.func, me.args)
This gives an interface that _just_ returns a result, each time
resfuncobject is invoked. That's all I'm after. Of course there's
nothing to stop callable_object from returning a (result, continuation)
tuple if you prefer that instead. 99+% of the time the "continuation"
I'm after will simply be the ability to resume the resfunc exactly where
it left off, and the implementation sketch caters to that case by making
it a no-work-on-the-user's-part case.
Subtlety: Since resfunc resumptions and suspensions _do_ occur in a
stack-like fashion, what to do with the back-pointer in a frameobject
during a resumption is clear (you just set it to the caller's frame-- in
most respects resumption is an ordinary call! --and upon suspension the
back-pointer can be nulled-out (no need to keep a reference to the resumer
active).
Believe that life is more complicated with general co-routines:
A calls B
B calls C
C co-routine transfers to D
D contains a return: where does it go?
"C"'s a wrong answer, because D wasn't _called_ by C. "It returns to B"
is about the best answer I've seen. But then what if B co-routine
transfers to C? C never "returned", so you might think it should still
be active. OTOH, how do you implement that? Throw in some recursive
calls for some real fun <wink>. I believe resfuncs avoid all those
mysteries. E.g.,
A calls B
B calls C
C resumes a resfunc object D
D contains a return: where does it go? Back to C.
I.e. for a resumed resfunc, return/suspend always returns to the point of
resumption.
> [ I'm not yet sure how or whether to fit args to the continuation into
> this scheme.
Think I'd rarely (never?) want that. If necessary, the signature of
_Resfunc.invoke could be changed to invoke(self,*args), and rules made up
to say how invoke overwrites pieces of self.frameobject's locals based on
"args" before resuming self.func.
> Or how exactly to express "capture the current continuation" in a
> return statement.
My hope is that this would be close to a nop. I.e., so long as the
resfunc is alive, a reference to the frameobject is active in the
_Resfunc instance, so the frameobject should persist by magic. In other
words, "return" isn't enough to make the frameobject vanish. Everything
needed should survive by magic, assuming-- as you said earlier --that
frameobjects are extended to preserve enough interpreter state to
_enable_ resumption. But then I'm starting to suspect I'm after
something simpler than you're after ...
> ... vague mumbling about whether the thing that creates a
> continuation ought to be a (pseudo)function or an expression in
> Python goes here ... :-) ]
The sketch above spells "resfunc" as an ordinary function. An
implication is that it can _only_ create a resumable callable_object
object; in contrast, Icon's "create <expr>" accepts an arbitrary
expression, and a magical keyword is essential because <expr> must not be
evaluated at "create" time (else, e.g., "create func(3)" would go ahead
and _call_ func). resfunc worms around that by separating the
callable_object specification from the specification of its argument
list; both of those can be evaluated separately without harm (in fact, I
think it's clearer to evaluate them at the point of resfunc object
creation).
> The type of "wrapper" I was envisioning in the pipe example would be a
> class that takes two functions as args, and rebinds stdin/stdout to it
> self. Its read and write methods encapsulate the coroutine control:
> the called functions do no explicit save/restore of state - they
> merely call obj.read or obj.write. ( Steve waves his hand magically,
> here: ...
There seems to be an assumption here that func #1 never reads & that func
#2 never writes. Is that so? If not, you've got a hairier problem
figuring out whether obj.write is being invoked from a print in func #1
or func #2, and similarly for obj.read. E.g., your disco function both
reads and writes, so after you rebind stdout it may be a mess to separate
disco's output from the library disassembler's output.
One of the "hidden" reasons for executing func #1 to completion before
starting on func #2 is so that these complications don't come up in the
first place <wink>.
Still, assuming func #1 only writes and func #2 only reads,
+ In a language with resfuncs, the natural way to code func #1 is as a
resfunc that produces a sequence of results (via "suspend" or a moral
equivalent), and func #2 as a (ordinary) function that consumes a
sequence of inputs (obtained via repeatedly resuming an "input"
resfunc). Then hooking them together is easy & natural; it's also no
problem if either or both want to "read" and "write". Getting func #2
to read from stdin just requires passing stdin.readline as the
"resfunc" object (func #2 won't care that it's not "really" a resfunc
object, cuz stdin.readline _acts_ like one). Getting func #1 to write
to stdout isn't _that_ simple, but easy enough (it's just hooked to the
obvious "write a result sequence to stdout" function).
+ I do believe things are tougher if you want to spoof read/write: a
resfunc decides when _it_ wants to yield control, but in spoofing
read/write you want something else (namely the read/write proxies) to
decide that its _invoking_ function wants to yield control. So that
notion of resumability spills across frames.
Should have taken you at your word to begin with <wink>: you've convinced
me we're really after different things here. I'm trying to find an
easier way to write some kinds of programs to begin with, and you're
trying to find a way to trick existing programs into doing things their
authors didn't intend. How's that for a fair summary <grin>?
> ...
> Well - I started out trying to solve the "pipe" problem, but then
> discovered (suprisingly!) that the simplest solution is also the
> most general one.
For the kinds of problems I envision solving via the resfunc approach,
messing with tuple returns and explicit continuations would be painful --
although less painful than what I'm doing now. So I think of explicit
continuations as being "simplest and most general" in much the way I
think "go to" is the simplest and most general control structure <0.4
grin>.
> However - what I DON'T want is scheme-like continuation syntax.
Have a brief sketch of that handy?
> ...
> Scheme continuation are extremely powerful, but I think they are rather
> confusing to use. Icon co-routines and co-expressions, on the other
> hand, give a subset of the capabilities of generalized continuations,
> but that subset is quite easy to use and understand, and captures a
> significant portion of those capabilities.
Typical Icon co-expressions are well-behaved, and I've tried to capture
their most useful qualities in the resfunc notion. OTOH, I've found
Icon's _general_ co-routine facilities to be confusing, error-prone in
practice, and-- so far --never actually less work than clearer
alternatives.
So whatever "generalized continuations" means exactly, if it subsumes
general co-routines I bet I could learn to hate it <0.9 grin>.
> Exception handling capture the other sizable subset. I prefer the
> functionality of exceptions and coroutines, without binding them
> to any particular implementation. My use of the word continuation
> in this discussion may lead you to think otherwise, but that's
> just a side effect of the fact that I don't know any better way to
> talk about it.
Well, that's what examples are for (else we're using words without shared
referents). Writing up my examples in excruciating detail has really
helped me understand what I would want here, and I'm surprised to find
that "what I want" (resfuncs) really wouldn't give you a pleasant
solution to your examples. But I'm not sure that what you want would
give you a pleasant solution either! How about fleshing out your general
redirection problem via coding a full solution "as if" Python already had
what you want? I find a lot of things I _don't_ want that way <smile>.
grimy-handed-ly y'rs - tim
Steven D. Majewski
Since I'm at home on the modem, detailed response to your example
and some of your points will have to wait until I get a hardcopy
to study, but I'll comment on a few points now:
Re: restartable exceptions:
[ Tim on why it's not something he wants or desires... ]
sdm> - but the way around this is to NOT change the semantics of exceptions,
sdm> but merely to allow a 'raise' to pass a continuation object as its
sdm> optional arg.
tim> Agreed that if it must be done <wink>, that's the way to do it.
Restartable state after an exception was NOT one of my goals, either.
I was just commenting on the fact that it would become possible.
sdm> ...
sdm> One way is to make continuation objects callable, just like functions,
sdm> methods, and class creators:
sdm>
sdm> result, cont = cofunc( args ) # returns a value, continuation tuple
sdm> use( result )
sdm> result, cont = cont() # re-enter
tim> You don't want the 1st call to look different than all the others; any
tim> concrete, specific example would convince you of that instantly <smile>.
I think you are correct about that, but:
tim> I'd suggest this instead, where "resfunc" is a new built-in (whatever)
tim> with the same signature as the built-in "apply":
You can get around that by wrapping the first call:
cont = lambda: apply( cofunc, args )
...
while SOMETHING:
result, cont = cont()
use( result )
tim> This gives an interface that _just_ returns a result, each time
tim> resfuncobject is invoked. That's all I'm after. Of course there's
tim> nothing to stop callable_object from returning a (result, continuation)
tim> tuple if you prefer that instead. 99+% of the time the "continuation"
tim> I'm after will simply be the ability to resume the resfunc exactly where
tim> it left off, and the implementation sketch caters to that case by making
tim> it a no-work-on-the-user's-part case.
And if you don't want to explicitly handle the continuation, then that
can be wrapped up and hidden in a class.
I don't disagree with what you're after. I just think that my version
is closer to the implementation ( at least the one I have in mind ) and
thus the more primitive and builtin one. Since I don't see anything special
to be done on the initial call of the function - the difference
between a regular function and a resumable function is just that one
does a 'return' and the other does a suspend ( i.e. returns a
continuation ) I don't see the need for a special function to
create one.
But I'm all for adding things on top of that to make the typical
cases standard and easy syntax.
tim> Believe that life is more complicated with general co-routines:
Yes. ( more on that later... )
tim> I.e. for a resumed resfunc, return/suspend always returns to the point of
tim> resumption.
sdm> [ I'm not yet sure how or whether to fit args to the continuation into
sdm> this scheme.
tim> Think I'd rarely (never?) want that.
Agreed.
sdm> Or how exactly to express "capture the current continuation" in a
sdm> return statement.
tim> My hope is that this would be close to a nop. I.e., so long as the
tim> resfunc is alive, a reference to the frameobject is active in the
tim> _Resfunc instance, so the frameobject should persist by magic. In other
tim> words, "return" isn't enough to make the frameobject vanish. Everything
tim> needed should survive by magic, assuming-- as you said earlier --that
tim> frameobjects are extended to preserve enough interpreter state to
tim> _enable_ resumption. But then I'm starting to suspect I'm after
tim> something simpler than you're after ...
Yes - you're after something simpler.
Yes - what you said above should be true: as long as a reference to
the continuation object exists, it should be resumable, and a wrapper
class can keep that reference in an instance variable for you.
No - you didn't get what I meant by that sentence. i.e. I agree
but that's a different point.
sdm> ... vague mumbling about whether the thing that creates a
sdm> continuation ought to be a (pseudo)function or an expression in
sdm> Python goes here ... :-) ]
[ ... Tim on Icon's create() and his resfunc() ... ]
Again: what I was talking about was not creation of the resumable
function, but creation of a resumable frame by the 'suspend'
( or whatever syntax )
sdm> The type of "wrapper" I was envisioning in the pipe example would be a
sdm> class that takes two functions as args, and rebinds stdin/stdout to it
sdm> self. Its read and write methods encapsulate the coroutine control:
sdm> the called functions do no explicit save/restore of state - they
sdm> merely call obj.read or obj.write. ( Steve waves his hand magically,
sdm> here: ...
tim> + I do believe things are tougher if you want to spoof read/write: a
tim> resfunc decides when _it_ wants to yield control, but in spoofing
tim> read/write you want something else (namely the read/write proxies) to
tim> decide that its _invoking_ function wants to yield control. So that
tim> notion of resumability spills across frames.
Yes. Although a 'suspend value' would be a simple syntax for "return
a ( value, continuation ) tuple with the continuation causing
resumption of the function at the next statement", it doesn't give me
a way to express what I wanted to do in spoofing read/write.
( And when I figured that out last night, I figured out exactly what
you meant about resumable functions as a simpler subset of generalized
coroutines! ) What my problem requires is a swap of continuations:
read and write both save a current continuation and resume a previous
one. As you said - it's a more symetrical and complicated problem than
just a non-symetrical restart.
tim> Should have taken you at your word to begin with <wink>: you've convinced
tim> me we're really after different things here. I'm trying to find an
tim> easier way to write some kinds of programs to begin with, and you're
tim> trying to find a way to trick existing programs into doing things their
tim> authors didn't intend. How's that for a fair summary <grintim>?
I want both, but that's a fair summary, as until this problem, I was
convinced ( but, as you were, unsatisfied ;-) that Classes and some
non-trivial bookeeping could give the same results. ( And maybe I
had some hope that the problem could be generalized into a one-time
wrapper somehow - like I eventually did with my class that coerces
things into a sequence. )
sdm> ...
sdm> Well - I started out trying to solve the "pipe" problem, but then
sdm> discovered (suprisingly!) that the simplest solution is also the
sdm> most general one.
tim>
tim> For the kinds of problems I envision solving via the resfunc approach,
tim> messing with tuple returns and explicit continuations would be painful --
tim> although less painful than what I'm doing now. So I think of explicit
tim> continuations as being "simplest and most general" in much the way I
tim> think "go to" is the simplest and most general control structure <0.4
tim> grin>.
Yes. I said above: "closer to the implementation"
sdm> However - what I DON'T want is scheme-like continuation syntax.
tim> Have a brief sketch of that handy?
No. I have to reread the documentation whenever I want to use them.
Subtle and powerful.
tim> So whatever "generalized continuations" means exactly, if it subsumes
tim> general co-routines I bet I could learn to hate it <0.9 grintim>.
It subsumes general co-routines, non-local goto's and exception
handling and finally-type things. As one of the less
object-oriented of functional-programmers once put it:
"Why would you ever want objects when you have closures and
continuations."
tim> Well, that's what examples are for (else we're using words without shared
tim> referents). Writing up my examples in excruciating detail has really
tim> helped me understand what I would want here, and I'm surprised to find
tim> that "what I want" (resfuncs) really wouldn't give you a pleasant
tim> solution to your examples. But I'm not sure that what you want would
tim> give you a pleasant solution either! How about fleshing out your general
tim> redirection problem via coding a full solution "as if" Python already had
tim> what you want? I find a lot of things I _don't_ want that way <smiletim>.
I just wanted to make the point than although I'm starting from a
possible implementation ( i.e. it was seeing that implementing it
didn't look as difficult as I had initially thought ) I don't want
to bind the syntax to tightly to a particular implementation if I
can avoid it.
The problem I'm having in pseudo-coding my example is the problem
of expressing capturing a particular continuation without drawing
arrows and lines.
I think it's simple to say that:
suspend value
#### > continue HERE:
returns ( value, cont ) such that cont() resumes at the HERE label,
and the meaning doesn't get confused if I substitute any expression
of function(s) for 'value'.
What I need for my read/write problem is a "save this continuation
(insert arrow) HERE and resume that continuation THERE" syntax.
Modula has a syntax for coroutine call, though I can't recall it
offhand. ( Guido? ) I suspect that it does the sort of 'swap'
that I require, but hides the continuation as you would like.
Clearly, one of my problems here is limited exposure to
"general coroutines" , but experience with the more limited
for of Icon coexpressions, and the more general concepts of
continuation or threads. ( Not the same - I just mean that
in unix one gets used to using processes in cases where they
will often wait on each other, so they are functioning as
coroutines - just cause pipes are easy to express. )
So maybe I *will* have to give up the idea of passing, assigning,
handling, poking and otherwise prodding continuation explicitly.
However, I think this produces some OTHER problems which I won't
go into right now.
Guido.va...@cwi.nl
certainly made entertaining reading!
Here are my own ramblings about this subject:
1) Restartable functions are really "generators" in disguise.
2) Many cases where Icon or Scheme would use generators are best done
in Python by separating the two phases out and creating an explicit
list of items as an intermediate stage. This may seem odd but it
often gives clearer code than all the magic with coroutines (I read
the paper on Sather Iters that Steve recommended -- shock horror!).
The efficiency will often be adequate, especially since you don't have
all the coroutine switching overhead (and since list operations are
built in), as long as the list of intermediate results isn't too
outrageously long (as in infinite :-).
3) Tim proposes a multi-stage interface: first you wrap a function,
creating an object that stands for the sequence you have in mind
(e.g. the integers from 5); then you invoke the object to give you a
sequence generator; finally you call the generator repeatedly to give
you the successive items. My feeling is that this is trying to copy
two independent features from Icon in one Python feature: generators
and cloning (my words). Although the cloning can occasionally be
useful, I would prefer to tackle such a feature separately, and
concentrate on generators right now. Using an object-oriented
approach, maintaining the current state as data member(s) of self
greatly simplifies the implementation, e.g.:
class IntsFrom:
def __init__(self, n):
self.n = n
def next(self):
n = self.n
self.n = n + 1
return n
4) I don't think that it would be a good idea to allow exceptions to
be restarted, even if it were possible. They are generally used in
situations where there is no sensible course of action possible. If a
mending possibility exists in a particular situation I think defining
a "hook" function would be more appropriate -- the default hook could
raise the exception or the code calling the hook could raise the
exception if the hook didn't fix the problem. Anyway, most exceptions
come from C code and these are certainly almost all unmendable; the
continuation idea doesn't work there either.
5) Likewise I am horrified by the idea that there may somehow be a
possibility for a caller to make my function continue after it
returns. The return statement is often used for flow control within a
function, as in:
def fac(n):
if n <= 1: return 1
return n*fac(n-1)
6) All this notwithstanding, I can sympathesize with the difficulty of
having to "save the program counter" in certain generators (not
intsfrom()). Here's an example, adapted from Demo/scripts/pi.py,
which generates an endless stream of decimal digits of pi:
def pi():
k, a, b, a1, b1 = 2L, 4L, 1L, 12L, 4L
while 1:
# Next approximation
p, q, k = k*k, 2L*k+1L, k+1L
a, b, a1, b1 = a1, b1, p*a+q*a1, p*b+q*b1
# Print common digits
d, d1 = a/b, a1/b1
while d == d1:
==> output(int(d))
a, a1 = 10L*(a%b), 10L*(a1%b1)
d, d1 = a/b, a1/b1
The digits are passed to the output() function called at the indicated
line (not shown here -- it prints its argument).
7) Here's a proposal for a possible interface which I think can be
implemented with not too many changes to the interpreter's internal
machinery:
There's a built-in Generator class (or type or whatever fits the
bill) with get() and put() methods. To create a Generator instance,
you pass the class a function and an argument list for the function.
The function could be something like pi() above except that it is
passed the generator instance as additional argument. We could
adapt the example above like this:
def pi(g):
...
while 1:
...
while ...:
==> g.put(int(d))
...
The user would use it as follows:
g = Generator(pi, ()) # pass pi an empty argument list
while 1:
==> d = g.get()
print int(d),
Each call to g.get() resumes pi() until it calls g.put(); the
argument to g.put() is returned by g.get(). When the function
returns, get() raises an exception (we could use None but I would
prefer not to disallow for sequences containing None).
8) An implementation of this interface using threads is possible in
today's Python (if you have threads), as follows:
class Generator:
def __init__(self, func, args):
self.getlock = thread.allocate_lock()
self.putlock = thread.allocate_lock()
self.getlock.acquire()
self.putlock.acquire()
self.done = 0
thread.start_new_thread(self.start, (func, args))
def start(self, func, args):
# Set the wheels in proper motion
try:
self.putlock.acquire() # Wait for first get()
apply(func, args + (self,))
finally:
self.done = 1
self.getlock.release()
def get(self):
self.putlock.release() # Resume producer thread
self.getlock.acquire() # Wait for produced value
if self.done:
raise EOFError # Sequence finished
return self.value
def put(self, value):
self.value = value
self.getlock.release() # Resume consumer thread
self.putlock.acquire() # Wait for next get() call
9) This is probably not an ideal implementation (threads have more
power and consequential overhead than necessary to implement
coroutines), but as a proof of concept and as a tool to prototype the
interface it is good enough. The pi example is entirely compute bound
(almost all time is spent in long integer arithmetic) so it doesn't
matter so much here anyway.
10) I have also thought of an implementation in ceval.c. This would
require an extension to eval_code() to execute "continuations". The
generator state would contain a continuation of the function
(initialized with code to call it from the top). The get() method
would run the continuation and expect a particular exception from it
(say NextValue). The put() method would raise the NextValue error
with as "exception argument" the value to be returned, and store the
current frame etc in the generator object for resumption. The get()
method would catch the exception (letting any other pass unchanged)
and return the associated value. Boundary conditions to be
determined.
11) It should be possible that g.put() be called not just by the
generating function (pi() in our example) but also by any function
that it calls. For this to work, eval_code() will have to be
restructured so that calling a python function from another python
function is done using the same C stack frame. To implement this,
call_object(), call_function() and call_builtin() will have to be
inlined in the case for BINARY_CALL. Python functions called from C
(e.g. Python Xt callbacks, which are called vial call_object from the
C callback) won't be able to use this feature. Some special machinery
will be necessary to make it work across apply(). I don't know if it
is necessary to make it work for the functions passed to map(),
filter() or reduce() or other places where call_object is used from C.
Note that the version using real threads doesn't have these
restrictions since the generating function runs on a separate stack.
12) I forgot what I wanted to say here :-)
13) It is a matter of taste whether to pass the generator instance or
its put() method to the generating function. I like to pass the
generator instance, so that if in a future release generators get
additional methods or data attributes, these may be be used/inspected
by the generating function.
14) I'm sure Steve can use this interface to reach new heights of
obfuscated Python -- how about generators returning generators...
--Guido van Rossum, CWI, Amsterdam <Guido.va...@cwi.nl>
URL: <http://www.cwi.nl/cwi/people/Guido.van.Rossum.html>
Tim Peters
ones in Guido's msg for now:
> ...
> 1) Restartable functions are really "generators" in disguise.
Yes, as I understand the word, Tim's resfuncs are one way to implement
generators. But I don't know precisely what "generators" means to
anyone on any given day, so used a different name, whose meaning I could
control.
> ...
> 3) Tim proposes a multi-stage interface: first you wrap a function,
> creating an object that stands for the sequence you have in mind
> (e.g. the integers from 5); then you invoke the object to give you a
> sequence generator; finally you call the generator repeatedly to give
> you the successive items.
Wasn't proposing that, just showed code I have that actually _does_ that.
In its original context, that scheme makes good sense. Fully agree that,
when such an elaborate scheme is needed, it's better to build it out of
simpler features (provided suitable ones exist to build it from <wink>).
> Although the cloning can occasionally be useful,
In context, it was essential. Objects had two roles, a passive one in
which they recorded time-invariant information about their purpose in
life, and an active role in which they applied that information to a
time-variant backtracking search. The objects appear in large graph
structures, so sharing objects was hard to stop (nor would I have wanted
to), and in their _active_ roles each "invocation" of an object needed
its own execution environment. No amount of static duplication could
achieve that, because an object's _active_ state could cause any number
of indirect (recursive) invocations of itself.
> I would prefer to tackle such a feature separately, and concentrate on
> generators right now.
That is the key problem! "Cloning" is easily implemented when needed.
> Using an object-oriented approach, maintaining the current state as
> data member(s) of self greatly simplifies the implementation, e.g.:
>
> class IntsFrom:
> def __init__(self, n):
> self.n = n
> def next(self):
> n = self.n
> self.n = n + 1
> return n
So long as we stick to trivial examples, it is indeed tempting to think
that's good enough <0.9 grin>. As a slightly non-trivial example, note
that this implementation of IntsFrom would not work correctly in the
runnable "pipe" example I gave: an instance can be shared in its
_passive_ state (merely recording that someday it may be asked to
generate integers starting from n) fine, but sharing the _active_ state
(actually generating integers) is disastrous.
In simple examples, or simple uses, it's reasonable to tell a user "don't
do anything that will break the implementation" <wink>; in complex
settings that advice is just impossible to follow. I didn't wind up with
all the "_wrap" and "_work" machinery because I thought it was clear <grin>.
A more OO-like alternative would have been for "passive" objects to
create "active" objects on the fly, as needed, from a parallel or derived
hierarchy. Tried those too, & just didn't like 'em.
> ...
> 5) Likewise I am horrified by the idea that there may somehow be a
> possibility for a caller to make my function continue after it
> returns.
Ditto -- introducing "suspend" isn't _logically_ necessary, but the
design sucks big-time without it (the notion _was_ that, given "suspend",
a "return" would mark the resfunc as unresumable).
> ....
> 6) All this notwithstanding, I can sympathesize with the difficulty of
> having to "save the program counter" in certain generators (not
> intsfrom()).
Forget intsfrom already <grin>. The real pain indeed comes in examples
like the pi.py one, with nested loops, or other non-trivial control flow.
> ...
This is fine. Replace "Generator" with "resfunc", "put" with "suspend",
and "g=Generator(func, args); ... g.get()" with "g = resfunc(f, args); ...
g()", and it looks pretty familiar <grin>. Seriously, the functionality
is there, and the spelling is pleasant.
> 8) An implementation of this interface using threads is possible in
> today's Python (if you have threads), as follows:
Very pretty, Guido! It's enough to make me finally bring up the threads
package (busman's holiday ...).
> class Generator:
> def __init__(self, func, args):
> self.getlock = thread.allocate_lock()
> self.putlock = thread.allocate_lock()
> self.getlock.acquire()
> self.putlock.acquire()
> self.done = 0
> thread.start_new_thread(self.start, (func, args))
If, before that, you add
self.func = func
self.args = args
then you can also have
def clone(self): # return fresh version of same generator
return Generator(self.func, self.args)
> def start(self, func, args):
> # Set the wheels in proper motion
> try:
> self.putlock.acquire() # Wait for first get()
> apply(func, args + (self,))
Believe that line would be better as
apply(func, (self,) + args)
I.e., the called function surely knows it needs a Generator argument, but
other arguments may be optional.
> finally:
> self.done = 1
> self.getlock.release()
> def get(self):
> self.putlock.release() # Resume producer thread
> self.getlock.acquire() # Wait for produced value
> if self.done:
> raise EOFError # Sequence finished
> return self.value
> def put(self, value):
> self.value = value
> self.getlock.release() # Resume consumer thread
> self.putlock.acquire() # Wait for next get() call
>
> 9) This is probably not an ideal implementation (threads have more
> power and consequential overhead than necessary to implement
> coroutines),
The worst aspect is that if the caller doesn't run the generator to
completion (and it can't if the generator is modeling an infinite
sequence, and it merely won't if the caller is doing a search for a
sequence element that meets some condition -- both are common uses), the
spawned thread will hang forever at a putlock acquire; unless I'm
mistaken, the thread won't go away even if the generator is garbage-
collected. OS's are improving, but a few thousand stray threads still
give most of 'em indigestion <wink>.
Perhaps adding "self.die_early = 0" in __init__, introducing
def __del__(self):
self.die_early = 1
self.putlock.release() # let the spawned thread see it's time to die
self.getlock.acquire() # wait for it to see the flag before nuking me
adding
if self.die_early:
raise 'DieEarly' # abort thread, to the "finally" block in "start"
at the end of "put" (the point of using a string literal on the raise is
to minimize the chance that something in func will catch it, although a
perverse func could still do "try: g.put(x); except: pass" -- hmm!)
and changing start's "try:" block to
try:
self.putlock.acquire()
if not self.die_early:
apply(func, (self,) + args)
would usually suffice.
> but as a proof of concept and as a tool to prototype the interface it
> is good enough.
Absolutely!
> The pi example is entirely compute bound (almost all time is spent in
> long integer arithmetic) so it doesn't matter so much here anyway.
My experience is that real-life generators usually do little work per
invocation; their real value is that they're an achingly _natural_ way to
approach some otherwise-daunting problems. The pi example isn't horribly
atypical, though. So, as usual, every conceivable use is vital to
someone <grin/sigh>.
> 10) I have also thought of an implementation in ceval.c. This would
> require an extension to eval_code() to execute "continuations".
I saw Steve's eyes light up all the way from Boston <wink>. I'll study
this one later -- outta time.
> ...
> 11) It should be possible that g.put() be called not just by the
> generating function (pi() in our example) but also by any function
> that it calls. ... [various complications and irregularities]
I don't have a clear use in mind for this capability -- do you? Not to
say I wouldn't stumble into one if it was there.
BTW, I looked up Scheme's continuation gimmicks, and confess my head's
still spinning too fast to think straight.
> 12) I forgot what I wanted to say here :-)
Ditto my response.
> 13) It is a matter of taste whether to pass the generator instance or
> its put() method to the generating function. I like to pass the
> generator instance, so that if in a future release generators get
> additional methods or data attributes, these may be be used/inspected
> by the generating function.
Sorry, but you're dead wrong about this one: your preference is
objectively correct, so it's not a matter of taste <smile>.
OTOH, how to deal with "get()" is more troublesome. If a "consumer"
function is invoked via
g = Generator(producer, args)
consumer(g)
then it's likely to be littered with g.get(), and this stops you from
invoking it with (say)
consumer(stdin.readline)
So I'd favor calling via consumer(g.get). The similarity between
generators and file input is well worth exploiting! For that reason I
liked overloading EOFError with "generator exhausted" too.
> 14) I'm sure Steve can use this interface to reach new heights of
> obfuscated Python -- how about generators returning generators...
Well, _recursive_ generators are natural as heck -- and pretty darn
obscure until the light clicks on <wink>. E.g.
g = Generator(powerset, ([1,2,3],))
while 1:
next = g.get()
print next,
if next is None: break
print
should print
[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3], None
def powerset(g, set):
if len(set) == 0:
g.put( [] )
g.put( None )
first, rest = set[0], set[1:]
h = Generator(powerset, (rest,))
while 1:
next = h.get()
g.put( next )
g.put( [first] + next )
Will leave it as a disgusting exercise for the reader why this works even
though nothing checks for a None return inside powerset's "while" loop.
steve's-turn<grin>-ly y'rs - tim the obscure
Guido.va...@cwi.nl
>
Concluding, it was essential because of the particular example you
chose. I got confused because you actually made a point of claiming
that this was essential -- I now understand that it was essential for
the example, not for restartable functions. Maybe a simpler example
would have been in order :-)
> > I would prefer to tackle such a feature separately, and concentrate on
> > generators right now.
Yes.
> If, before that, you add
> self.func = func
> self.args = args
Actually, I first coded it like that! I should trust my intuition
more before starting to think about programs :-)
> then you can also have
>
> def clone(self): # return fresh version of same generator
> return Generator(self.func, self.args)
You don't give up easily don't you :-)
> apply(func, args + (self,))
>
> Believe that line would be better as
>
> apply(func, (self,) + args)
>
> I.e., the called function surely knows it needs a Generator argument, but
> other arguments may be optional.
On second thought I agree here -- I started writing before letting my
intuition catch up :-)
> The worst aspect is that if the caller doesn't run the generator to
> completion (and it can't if the generator is modeling an infinite
> sequence, and it merely won't if the caller is doing a search for a
> sequence element that meets some condition -- both are common uses), the
> spawned thread will hang forever at a putlock acquire; unless I'm
> mistaken, the thread won't go away even if the generator is garbage-
> collected. OS's are improving, but a few thousand stray threads still
> give most of 'em indigestion <wink>.
Agreed. See my new implementation at the bottom. Note that you can't
rely on __del__() being called since the producer still has a
reference to the object, so I added a kill() method.
> > 10) I have also thought of an implementation in ceval.c. This would
> > require an extension to eval_code() to execute "continuations".
>
> I saw Steve's eyes light up all the way from Boston <wink>. I'll study
> this one later -- outta time.
Haven't heard from him yet -- he must be VERY busy :-)
> > 11) It should be possible that g.put() be called not just by the
> > generating function (pi() in our example) but also by any function
> > that it calls. ... [various complications and irregularities]
>
> I don't have a clear use in mind for this capability -- do you? Not to
> say I wouldn't stumble into one if it was there.
If you think of get() as read(), you can surely think of put() as
write(), and then surely you can think of tons of applications for
this -- it's so natural to structure a big generator as a set of
subroutines. (Haven't any real examples yet -- sorry.)
> BTW, I looked up Scheme's continuation gimmicks, and confess my head's
> still spinning too fast to think straight.
Glad we agree on this one...
> OTOH, how to deal with "get()" is more troublesome. If a "consumer"
> function is invoked via
>
> g = Generator(producer, args)
> consumer(g)
>
> then it's likely to be littered with g.get(), and this stops you from
> invoking it with (say)
>
> consumer(stdin.readline)
>
> So I'd favor calling via consumer(g.get). The similarity between
> generators and file input is well worth exploiting! For that reason I
> liked overloading EOFError with "generator exhausted" too.
Then why doesn't this apply to producers as well? Anyway for
consumers it's a user decision -- the interface doesn't specify at all
how your consumer is called. It does specify how your producer is
called though. Anyway it's trivial to derive a class from Generator
which defines read() and write() as aliases for get() and put()...
============================ Generator.py ============================
# Generator implementation using threads
import thread
Killed = 'Generator.Killed'
class Generator:
# Constructor
def __init__(self, func, args):
self.getlock = thread.allocate_lock()
self.putlock = thread.allocate_lock()
self.getlock.acquire()
self.putlock.acquire()
self.func = func
self.args = args
self.done = 0
self.killed = 0
thread.start_new_thread(self._start, ())
# Internal routine
def _start(self):
try:
self.putlock.acquire()
if not self.killed:
try:
apply(self.func, (self,) + self.args)
except Killed:
pass
finally:
if not self.killed:
self.done = 1
self.getlock.release()
# Called by producer for each value; raise Killed if no more needed
def put(self, value):
if self.killed:
raise TypeError, 'put() called on killed generator'
self.value = value
self.getlock.release() # Resume consumer thread
self.putlock.acquire() # Wait for next get() call
if self.killed:
raise Killed
# Called by producer to get next value; raise EOFError if no more
def get(self):
if self.killed:
raise TypeError, 'get() called on killed generator'
self.putlock.release() # Resume producer thread
self.getlock.acquire() # Wait for value to appear
if self.done:
raise EOFError # Say there are no more values
return self.value
# Called by consumer if no more values wanted
def kill(self):
if self.killed:
raise TypeError, 'kill() called on killed generator'
self.killed = 1
self.putlock.release()
# Clone constructor
def clone(self):
return Generator(self.func, self.args)
def pi(g):
k, a, b, a1, b1 = 2L, 4L, 1L, 12L, 4L
while 1:
# Next approximation
p, q, k = k*k, 2L*k+1L, k+1L
a, b, a1, b1 = a1, b1, p*a+q*a1, p*b+q*b1
# Print common digits
d, d1 = a/b, a1/b1
while d == d1:
g.put(int(d))
a, a1 = 10L*(a%b), 10L*(a1%b1)
d, d1 = a/b, a1/b1
def test():
g = Generator(pi, ())
g.kill()
g = Generator(pi, ())
for i in range(10): print g.get(),
print
h = g.clone()
g.kill()
while 1:
print h.get(),
test()
========================================================================
Steven D. Majewski
>
> > > 10) I have also thought of an implementation in ceval.c. This would
> > > require an extension to eval_code() to execute "continuations".
> >
> > I saw Steve's eyes light up all the way from Boston <wink>. I'll study
> > this one later -- outta time.
>
> Haven't heard from him yet -- he must be VERY busy :-)
>
Sorry guys. I pickup up and started to read "Snow Crash" over the weekend
and got distracted... Were we talking about something? :-)
> > BTW, I looked up Scheme's continuation gimmicks, and confess my head's
> > still spinning too fast to think straight.
>
> Glad we agree on this one...
That makes three!
To quote Kent Dybvig:
( let ([x (call/cc (lambda (k) k))])
(x (lambda (ignore) "hi"))) ==> "hi"
- Steve M.
[ terminal screen disolves into white-noise "snow" ... ]
Jaap Vermeulen
>4) I don't think that it would be a good idea to allow exceptions to
>be restarted, even if it were possible. They are generally used in
>situations where there is no sensible course of action possible. If a
EXCEPT for KeyboardInterrupt, which can be triggered anywhere and is
hard to trap in such a way that you can always reenter the codeblock.
I still have no fool-proof way to ignore KeyboardInterrupt or create a
handler that terminates your program if you wish, but continues
otherwise. :-(
>mending possibility exists in a particular situation I think defining
>a "hook" function would be more appropriate -- the default hook could
>raise the exception or the code calling the hook could raise the
>exception if the hook didn't fix the problem. Anyway, most exceptions
That would be convenient, and solve the problem above. How does the
"hook" function fix the problem? By returning a special value?
I still think an exception object (as proposed a while ago) would give
a cleaner interface than all this special "hook" stuff.
-Jaap-
--
Jaap Vermeulen +--------------------------+
| Sequent Computer Systems |
Internet : ja...@sequent.com | Beaverton, Oregon |
Uucp : ...uunet!sequent!jaap +--------------------------+
Tim Peters
> > In context, it was essential. [long explanation]
> Concluding, it was essential because of the particular example you
> chose. I got confused because you actually made a point of claiming
> that this was essential -- I now understand that it was essential for
> the example, not for restartable functions. Maybe a simpler example
> would have been in order :-)
Sorry for the confusion! This is tough. Steve & I were mostly rambling,
and at least I was posting a mixture of things I've done, speculation,
and half-formed pseudo-proposals ... & in no particular order.
The actual problem is that the example I posted was _too_ simple <wink>:
it didn't show why all the supporting hair got invented to begin with,
only that it worked in a simple example.
BTW, the real point of the "cloning" in the examples was to supply each
active object its own set of (conceptual) local variables, and your
Generator class does that automatically. In other words, the Generator
class does all the "cloning" I _usually_ need even without the .clone
method.
> ...
> You don't give up easily don't you :-)
It depends. Challenge my stubbornness like this again, & I'll resume
whining about strings <wink>.
> ... Note that you can't rely on __del__() being called since the
> producer still has a reference to the object, so I added a kill()
> method.
Thanks for clearing that up! Of course I agree, now that I've been
kicked in the butt with the obvious.
> ...
> If you think of get() as read(), you can surely think of put() as
> write(), and then surely you can think of tons of applications for
> this -- it's so natural to structure a big generator as a set of
> subroutines. (Haven't any real examples yet -- sorry.)
No problem -- I'm sure they'll pop up. I'm just afraid they'll turn out
to be useful in ways that require the full power of the thread
implementation. Too soon to say!
> ...
> # Generator implementation using threads
BTW, has anyone built Python with vanilla POSIX pthreads? I see there
are some relevant #ifdef's in the relevant modules, but the Makefiles
don't seem to cater to the possibility directly.
Haven't tried it yet, just wondering whether someone already has.
echoing-the-eternal-question-ly y'rs - tim
Steven Miale
Steven D. Majewski <sd...@elvis.med.virginia.edu> wrote:
>To quote Kent Dybvig:
>
> ( let ([x (call/cc (lambda (k) k))])
> (x (lambda (ignore) "hi"))) ==> "hi"
But Dan Friedman says...
(define receiver
(lambda (continuation)
(continuation continuation)))
(define tester
(lambda (continuation)
(writeln "beginning")
(call/cc continuation)
(writeln "middle")
(call/cc continuation)
(writeln "end")))
(tester (call/cc receiver)) =>
beginning
beginning
middle
beginning
end
We call it "Mondo Bizarro."
Steve "CPS that" Miale
--
Steven Miale - smi...@cs.indiana.edu | Don't blame me -
Indiana University, Bloomington, IN | I voted Libertarian.
Guido.va...@cwi.nl
> >be restarted, even if it were possible. They are generally used in
> >situations where there is no sensible course of action possible. If a
>
> EXCEPT for KeyboardInterrupt, which can be triggered anywhere and is
> hard to trap in such a way that you can always reenter the codeblock.
> I still have no fool-proof way to ignore KeyboardInterrupt or create a
> handler that terminates your program if you wish, but continues
> otherwise. :-(
This shuld be solved by Lance's signal handling module -- the default
SIGINT handler will then raise KeyboardInterrupt. Until then, I'm not
going to change things. (Hey Lance! How's it going?)
> >mending possibility exists in a particular situation I think defining
> >a "hook" function would be more appropriate -- the default hook could
> >raise the exception or the code calling the hook could raise the
> >exception if the hook didn't fix the problem. Anyway, most exceptions
>
> That would be convenient, and solve the problem above. How does the
> "hook" function fix the problem? By returning a special value?
Hook functions would be defined with an interface that would allow
them to mend things. This depends very much on the kind of problem to
be mended. I was thinking of very specific hooks for very specific
situations -- not a general "hook" mechanism to be invoked where
currently exceptions are used.
> I still think an exception object (as proposed a while ago) would give
> a cleaner interface than all this special "hook" stuff.
I must admit I don't remember how exception objects were defined. Was
this during one of my absences?
--Guido van Rossum, CWI, Amsterdam <Guido.va...@cwi.nl>
URL: <http://www.cwi.nl/cwi/people/Guido.van.Rossum.html>
PS I junked the -k flag tonight. It felt really good cutting out
those lines of code :-)
la...@fox.com
> Date: Tue, 03 May 1994 23:02:52 +0200
>
> > >4) I don't think that it would be a good idea to allow exceptions to
> > >be restarted, even if it were possible. They are generally used in
> > >situations where there is no sensible course of action possible. If a
> >
> > EXCEPT for KeyboardInterrupt, which can be triggered anywhere and is
> > hard to trap in such a way that you can always reenter the codeblock.
> > I still have no fool-proof way to ignore KeyboardInterrupt or create a
> > handler that terminates your program if you wish, but continues
> > otherwise. :-(
>
> This shuld be solved by Lance's signal handling module -- the default
> SIGINT handler will then raise KeyboardInterrupt. Until then, I'm not
> going to change things. (Hey Lance! How's it going?)
Actually the signal module is comming very well... and yes.. once the
signal module is finished you can just assign a function like the following
to disable the KeyboardInterrupt:
def null_sigint(sig_num):
pass
and yes the default SIGINT handler does just the following:
def default_sigint(sig_num):
raise KeyboardInterrupt
I do have one question that I posted to the mailing list but never saw
it or got a response from it so I doubt it got there.
I need to add a SignalInterrupt exception and was thinking of adding it
to __builtin__ so that you could just use SignalInterrupt anywhere
without having to import signal. Does this make sense or should I just
leave it in the signal module?
Also, should I pass a second option to the signal handler routine
that is a traceback object? or a frameobject?
Or should I just pass in the signal_number?
--
Lance Ellinghouse la...@fox.com
Tim Peters
> Since I'm at home on the modem, detailed response to your example
> and some of your points will have to wait until I get a hardcopy
> to study, but I'll comment on a few points now:
The terms of the discussion have changed a lot since it started, so let's
drop it & start a new one <wink>.
Two things I took from Guido's responses:
1) Your original problem (redirecting the "write" output from one
function to the "read" input of another, in pipe-like fashion) would
be easy to solve using threads (i.e., by binding stdin & stdout to a
pair of "get" and "put" methods much like the methods of that name in
Guido's Generator class).
2) General continuations may be much harder to implement than we thought,
because the state of the _C_ runtime stack is also part of the current
continuation, and that's hard to muck with short of low-level OS- and
machine-specific hacks. I can picture an elaborate scheme to worm
around that, also using threads, but ...
Disagree with either of those? The more I see of general continuations
the less I want to see them as part of Official Python, but I do think
they'd be fascinating to play with. I've been surprised before!
> ...
> As one of the less object-oriented of functional-programmers once put
> it: "Why would you ever want objects when you have closures and
> continuations."
Indeed, given those, why would anyone ever want sex.
> ...
> What I need for my read/write problem is a "save this continuation
> (insert arrow) HERE and resume that continuation THERE" syntax.
Approaching this via "simple" coroutines, a
coroutine_transfer_to THERE
in routine HERE says exactly that. General coroutines are easier to
reason about, because you can use the name of a routine as a shorthand
for "whatever continuation was in effect the last time the routine with
that name coroutine-transferred out".
> Modula has a syntax for coroutine call, though I can't recall it
> offhand. ( Guido? ) I suspect that it does the sort of 'swap'
> that I require, but hides the continuation as you would like.
In Modula-2 it's
PROCEDURE TRANSFER(VAR p1,p2: PROCESS)
Saves the state of the current process into p1, and resumes process p2.
Chase it back far enough and p2 must initially have been created by a
call to NEWPROCESS, which creates a "process" out of a top-level
parameterless procedure and a chunk of "workspace" memory.
In an OO language, or any language that took coroutines very seriously,
it would be more natural for the transfer to name only p2.
> ...
> So maybe I *will* have to give up the idea of passing, assigning,
> handling, poking and otherwise prodding continuation explicitly.
Heck no! It's fun <smile>.
although-given-whiskey-i'm-not-sure-why-anyone-would-want-continuations-
Guido.va...@cwi.nl
> signal module is finished you can just assign a function like the following
> to disable the KeyboardInterrupt:
>
> def null_sigint(sig_num):
> pass
>
> and yes the default SIGINT handler does just the following:
>
> def default_sigint(sig_num):
> raise KeyboardInterrupt
Good! I'd love to see it in the next release!
> I do have one question that I posted to the mailing list but never saw
> it or got a response from it so I doubt it got there.
I guess the message got lost, I can't remember I saw it.
> I need to add a SignalInterrupt exception and was thinking of adding it
> to __builtin__ so that you could just use SignalInterrupt anywhere
> without having to import signal. Does this make sense or should I just
> leave it in the signal module?
I don't know what it should do but as I believe that your signal
interface will become a permanent part of Python I don't see a problem
with putting it in __builtin__.
> Also, should I pass a second option to the signal handler routine
> that is a traceback object? or a frameobject?
> Or should I just pass in the signal_number?
The frame object sounds like the proper thing to do here. Traceback
objects are only used to keep past frames alive -- when a signal
handler is called the current frame is still alive so there is no need
for a traceback yet.
Steven D. Majewski
>
> Two things I took from Guido's responses:
>
> 1) Your original problem (redirecting the "write" output from one
> function to the "read" input of another, in pipe-like fashion) would
> be easy to solve using threads (i.e., by binding stdin & stdout to a
> pair of "get" and "put" methods much like the methods of that name in
> Guido's Generator class).
However, one of my other points burried somewhere in that discussion
was that threads could be supported more portably by building
coroutines into the interpreter virtual machine. Python byte-code
instructions and builtin-C functions would then be 'atomic'. ( This
has some good and some bad implications, which I haven't thought thru
yet. ) Whether a coroutine/continuation syntax should show thru to the
Python language level is another question. I'm interested in exploring
that option, but the two questions are independent.
> 2) General continuations may be much harder to implement than we thought,
> because the state of the _C_ runtime stack is also part of the current
> continuation, and that's hard to muck with short of low-level OS- and
> machine-specific hacks. I can picture an elaborate scheme to worm
> around that, also using threads, but ...
But that's the point: because C-functions and python byte-code
instructions are atomic, the _C_ runtime stack is NOT a part of the
context or current continuation - only the Python block and argument
stacks and the current byte-code instruction pointer. We only have to
keep state for the virtual machine - that's what makes it portable.
> Disagree with either of those?
Yes. [ see above! ]
> The more I see of general continuations
> the less I want to see them as part of Official Python, but I do think
> they'd be fascinating to play with. I've been surprised before!
I've finished my sci-fi book, so my silence on these matters has been due
mostly to the fact that I'm actually tring to figure out an implementation so
I CAN play with it. If I give up on coroutines and/or continuations in
the *language*, my fall back is to try to support portable threads via
this mechanism.
- Steve Majewski (804-982-0831) <sd...@Virginia.EDU>
Tim Peters
> > ... the _C_ runtime stack is also part of the current continuation ...
> [steve]
> ... the _C_ runtime stack is NOT a part of the context or current
> continuation - only the Python block and argument stacks and the
> current byte-code instruction pointer. We only have to keep state
> for the virtual machine - that's what makes it portable.
I believe you're going to find this isn't true, at both shallow and deep
levels. Guido mentioned the "deep" level: a call to a Python routine may
end up calling an external C routine that in turn calls another Python
routine. The continuation at that point is a mess.
The "shallow" level comes up in _any_ call today. E.g., here's the whole
program:
def f():
# want to save a continuation here
return 1
f()
The byte-code for the call to f calls the C routine call_object, which
in turn calls the C routine call_function, which in turn (an indirect
recursion) calls eval_code again. So by the time we get to the comment,
we have 3 C frames stacked up as part of the continuation. The
RETURN_VALUE code doesn't currently stay within the evaluation loop: it
exits eval_code, unwinding the C stack frames until it gets back to the
call_object call in the top-level invocation of eval_code.
"resfuncs" as originally presented were defined in such a way that all
that hair was irrelevant: they always returned directly to their caller,
and so unwound all intermediate C frames, and required capturing the
state in only one Python frameobject for resumption (that's what I was
getting at with the unclear "what to do with the back pointer is clear"
bit: all the relevant state was contained in one Python frameobject, so
the _chain_ of C frames that come with a _chain_ of frameobjects wasn't a
problem).
Guido mentioned that for a non-thread implementation of the Generator
class to work, and allowing .put ("suspend") in routines called _from_
the Generator function, he'd have to do the call_object/call_function bit
(& presumably the RETURN_VALUE part too) inline, to avoid the C frame
problems (i.e., to have the common call cases handled iteratively, within
the evaluation loop, rather than via recursive invocations of the
evaluation loop: it's the latter that sucks the C stack into the
continuation).
That would take care of the "shallow" problems, and may be a Good Thing
regardless (if, as seems likely, it cut the time to do a Python call).
But the "deep" problems remain.
> ... threads could be supported more portably by building coroutines
> into the interpreter virtual machine. ... If I give up on coroutines
> and/or continuations in the *language*, my fall back is to try to
> support portable threads via this mechanism.
I don't know -- it's certainly more complicated than I thought at first,
though! Even the obvious approach of building the notion of threads
directly into the interpreter, and having it explicitly time-slice them
at the byte-code level, gets into all sorts of trouble early on, and
again in large part because the C stack gets intertwined. I actually
don't see a clean solution short of making the "evaluation loop" an
honest-to-Guido plain _loop_.
BTW, I don't know whether the following got sent to the list, but a
certain well-known Python Fan had this to say about the language he's
forced to work on to pay for all his golf carts <wink>:
> Indeed. That's one of the reasons Perl 5 was written not to keep any
> of that stuff in the C stack. That's part of what I mean when I say
> that Perl 5 has a very flat interpreter.
>
> I do keep the context info on a stack, however. But it's all pushed and
> popped with macros, so it would be relatively easy to reimplement.
>
> On the other hand, I don't particularly like continuations... :-)
looking-for-love-in-all-the-wrong-places<grin>-ly y'rs - tim
Steven D. Majewski
But 'SUSPEND' opcode would do a return from ceval just like 'RETURN' opcode,
except it would return a ( retval, cont-obj ) tuple instead of just
retval. [ Where cont-obj is an object containing the current
frameobject, plus block-pointer, stack-pointer, and last-instruction-
pointer ]. The other difference between RETURN is that SUSPEND would
not do a POP/DECREF on the contents of the python stack. That code would
have to be in the destructor for cont-obj.
Ceval would return and the C-stack would unwind, leaving behind a
"restartable" python frame. ( and ceval would have to be modified
to accept such an object, and to SKIP current_frame = newframeobject,
etc., and to restore (virtual machine) state from that object. )
So I'm not *completely* convinced yet, but you guys have raised enough
good points that you've got me worried! That's why I raised the
issue in the first place: it looked TOO EASY and I was suspicious.
( However, the LESS easy it looks, the MORE I begin to believe it! ;-)