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.van.Rossum@cwi.nl>
URL: <http://www.cwi.nl/cwi/people/Guido.van.Rossum.html>