Re: coroutines and continuations ( in Python? - long discussion )

Tim Peters (tim@ksr.com)
Sat, 30 Apr 94 01:29:09 -0400

I'll explain how I do "this kind of stuff" in Python today via a trivial
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 tim@ksr.com
not speaking for Kendall Square Research Corp