Mailing List Archive

Ken Manheimer wrote:
>
> Hokay. I *think* i have this, and i have a question to followup.

...

> In any case, one big unknown for me is the expense of continuations. Just
> how expensive is squirreling away the future, anyway? (:-)

The future costs at most to create *one* extra frame with a copy
of the original frame's local stack.
By keeping the references to all the other frames which were
intact, the real cost is of course bigger, since we keep
the whole frame path from this one up to the topmost
frame alive. As soon as we drop the handle, everything winds
up and vanishes.
I also changed the frame refcounting to guarantee exactly
that behavior. (before, unwinding was explicitly done).

> If we're deep in a call stack, seems like there can be a lot of
> lexical-bindings baggage, plus whatever i-don't-know-how-big-it-is control
> logic there is/was/will be pending. Does the size of these things
> (continuations) vary extremely, and is the variation anticipatable? I'm
> used to some surprises about the depth to which some call or other may go, i
> don't expect as much uncertainty about my objects - and it seems like
> continuations directly transform the call depth/complexity into data
> size/complexity... ??

Really, no concern necessary. The state is not saved at all
(despite one frame), it is just not dropped. :-)

Example:
You have some application running, in a nesting level of, say,
four function calls. This makes four frames.
The bottom function now decides to spawn 10 coroutines
in a loop and puts them into an array.

Your array now holds 10 continuations, where each one is just
one frame, which points back to your frame. Now assume, you
are running one of the coroutines/generators/whatever, and
this one calls another function "bottom", just to have
some scenario.

Looking from "bottom", there is just a usual frame chain,
now 4+1 frames long.

To shorten this: The whole story is nothing more than a tree,
where exactly one leaf is active at any time, and its view
of the call chain is always linear.
Continuation jumps are possible to every other frame in the tree.
It now only depends of keeping references to the leaf which
you just left or not. If the jump removes the left reference
to your current frame, then the according chain will ripple away
up to the next branch point. If you held a reference, as you
will do with a coroutine to resume it, this chain stays as
a possible jump target.

for-me-it's-a-little-like-Tarzan-ly y'rs - chris

--
Christian Tismer :^) <mailto:tismer@appliedbiometrics.com>
Applied Biometrics GmbH : Have a break! Take a ride on Python's
Kaiserin-Augusta-Allee 101 : *Starship* http://starship.python.net
10553 Berlin : PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint E182 71C7 1A9D 66E9 9D15 D3CC D4D7 93E2 1FAE F6DF
we're tired of banana software - shipped green, ripens at home

Christian wrote:

> Really, no concern necessary. The state is not saved at all
> (despite one frame), it is just not dropped. :-)

I have to say, that's not completely reassuring.-) While little or
nothing additional is created, stuff that normally would be quite
transient remains around.

> To shorten this: The whole story is nothing more than a tree,
> where exactly one leaf is active at any time, and its view
> of the call chain is always linear.

That's wonderful - i particularly like that multiple continuations from
the same frame only amount to a single retention of the stack for that
frame. My concern is not alleviated, however.

My concern is the potential, but often-realized hairiness of computation
trees. Eg, looped calls to a function amount to nodes with myriad
branches - one for each iteration - and each branch can be an arbitrary
computation. If there were a continuation retained each time around the
loop, worse, somewhere down the call stack within the loop, you could
quickly amass a lot of stuff that would otherwise be reaped immediately.
So it seems like use of continuations *can* be surprisingly expensive,
with the expense commensurate with, and as hard (or easy) to predict as
the call dynamics of the call tree.

(Boy, i can see how continuations would be useful for backtracking-style
chess algorithms and such. Of course, discretion about what parts of
the computation is retained at each branch would probably be an
important economy for large computations, while stashing the
continuation retains everything...)

(It's quite possible that i'm missing something - i hope i'm not being
thick headed.)

Note that i do not raise this to argue against continuations. In fact,
they seem to me to be at least the right conceptual foundation for these
advanced control structures (i happen to "like" stream abstractions,
which i gather is what generators are). It just seems like it may a
concern, something about which people experience with continuations
experience (eg, the scheme community) would have some lore - accumulated
wisdom...

ken
klm@digicool.com

[Tim]
> Threads can be very useful purely as a means for algorithm
> structuring, due to independent control flows.

FWIW, I've been following the coroutine/continuation/generator bit with
'academic' interest -- the CS part of my brain likes to read about them.
Prompted by Tim's latest mention of Demo/threads/Generator.py, I looked at
it (again?) and *immediately* grokked it and realized how it'd fit into a
tool I'm writing. Nothing to do with concurrency, I/O, etc -- just
compartmentalization of stateful iterative processes (details too baroque
to go over). More relevantly, that tool would be useful on thread-less
Python's (well, when it reaches usefulness on threaded Pythons =).

Consider me pro-generator, and still agnostic on the co* things.

--david

[Ken Manheimer]
> First, i think the crucial distinction i needed to make was the fact that
> the stuff inside the body of the call/cc is evaluated only when
> the call/cc is initially evaluated. What constitutes the "future" of the
> continuation is the context immediately following the call/cc expression.

Right! call/cc is short for call-with-current-continuation, and "current"
refers to the continuation of call/cc itself. call/cc takes a function as
an argument, and passes to it its (call/cc's) *own* continuation. This is
maximally clever and maximally confusing at first. Christian has a less
clever way of spelling it that's likely to be less confusing too.

Note that it has to be a *little* tricky, because the obvious API

k = gimme_a_continuation_for_here()

doesn't work. The future of "gimme_a_..." includes binding k to the result,
so you could never invoke the continuation without stomping on k's binding.

k = gimme_a_continuation_for_n_bytecodes_beyond_here(n)

could work, but is a bit hard to explain coherently <wink>.

> ...
> In any case, one big unknown for me is the expense of continuations.
> Just how expensive is squirreling away the future, anyway? (:-)

Christian gave a straight answer, so I'll give you the truth <wink>: it
doesn't matter provided that you don't pay the price if you don't use it. A
more interesting question is how much everyone will pay all the time to
support the possibility even if they don't use it. But that question is
premature since Chris isn't yet aiming to optimize. Even so, the answer so
far appears to be "> 0 but not much".

in-bang-for-the-buck-continuations-are-cheap-ly y'rs - tim

>> Again, though, you never want to muck with continuations directly!
>> They're too wild. You get an expert to use them in the bowels of an
>> implementation of something else.

[Christian]
> Maybe with one exception: With careful coding, you can use
> a continuation at the head of a very deep recursion and use
> it as an early break if the algorithm fails. The effect is
> the same as bailing out with an exception, despite the fact
> that no "finally" causes would be obeyed. It is just a
> incredibly fast jump out of something if you know what
> you are doing.

You don't need continuations for this, though; e.g., in Icon I've done this
often, by making the head of the deep recursion a co-expression, doing the
recursion via straight calls, and then doing a coroutine resumption of &main
when I want to break out. At that point I set the coexp to &null, and GC
reclaims the stack frames (the coexp is no longer reachable from outside)
when it feels like it <wink>.

This is a particularly simple application of coroutines that could be
packaged up in a simpler way for its own sake; so, again, while
continuations may be used fruitfully under the covers here, there's still no
reason to make a poor end user wrestle with them.

> ... Well, I admit that the continuation approach is slightly too much
> for the coroutine/generator case,

It's good that you admit that, because generators alone could have been
implemented with a 20-line patch <wink>. BTW, I expect that by far the bulk
of your changes *still* amount to what's needed for disentangling the C
stack, right? The continuation implementation has been subtle, but so far
I've gotten the impression that it requires little code beyond that required
for stacklessness.

> ...
> How about "amb"? :-)
> (see "teach youself schem in fixnum days, chapter 14 at
> http://www.cs.rice.edu/~dorai/t-y-scheme/t-y-scheme-Z-H-15.html#%_chap_14)

That's the point at which I think continuations get insane: it's an
unreasonably convoluted implementation of a straightforward (via other
means) backtracking framework. In a similar vein, I've read 100 times that
continuations can be used to implement a notion of (fake) threads, but
haven't actually seen an implementation that wasn't depressingly subtle &
long-winded despite being just a feeble "proof of concept".

These have the *feeling* of e.g. implementing generators on top of real
threads: ya, you can do it, but nobody in their right mind is fooled by it
<wink>.

> About my last problems:
> The hard decision is:
> - Either I just stop and I'm ready already, and loops are funny.

OK by me -- forgetting implementation, I still can't claim to know what's
the best semantic here.

> - Or I do the hidden register search, which makes things more
> complicated and also voidens the pushback trick partially,
> since then I would manage all stack stuff in one frame.

Bleech.

> - Or, and that's what I will do finally:
> For now, I will really just correct the loops.
>
> Well, that *is* a change to Python again, but no semantic change.
> The internal loop counter will no longer be an integer object,
> but a mutable integer box. I will just create a one-element
> integer array and count with its zero element.
> This is correct, since the stack value isn't popped off,
> so all alive stack copies share this one element.

Ah, very clever! Yes, that will fly -- the continuations will share a
reference to the value rather than the value itself. Perfect!

> As a side effect, I save the Object/Integer conversion, so
> I guess it will be faster. *and* this solution does not involve
> any other change, since the stack layout is identical to before.

Right, no downside at all. Except that Guido will hate it <wink>.

there's-a-disturbance-in-the-force-ly y'rs - tim

[Christian]
> Really, no concern necessary. The state is not saved at all
> (despite one frame), it is just not dropped. :-)

[Ken]
> I have to say, that's not completely reassuring.-) While little or
> nothing additional is created, stuff that normally would be quite
> transient remains around.

I don't think this is any different than that keeping a reference to a class
instance alive keeps all the attributes of that object alive, and all the
objects reachable from them too, despite that you may never again actually
reference any of them. If you save a continuation, the implementation *has*
to support your doing anything that's *possible* to do from the saved
control-flow state -- and if that's a whole big giant gob o' stuff, that's
on you.

> ...
> So it seems like use of continuations *can* be surprisingly expensive,
> with the expense commensurate with, and as hard (or easy) to predict as
> the call dynamics of the call tree.
>
> (Boy, i can see how continuations would be useful for backtracking-style
> chess algorithms and such.

It comes with the territory, though: backtracking searches are *inherently*
expensive and notoriously hard to predict, whether you implement them via
continuations, or via clever hand-coded assembler using explicit stacks.
The number of nodes at a given depth is typically exponential in the depth,
and that kills every approach at shallow levels.

Christian posted a reference to an implementation of "amb" in Scheme using
continuations, and that's a very cute function: given a list of choices,
"amb" guarantees to return (if any such exists) that particular list element
that allows the rest of the program to "succeed". So if indeed chess is a
forced win for white, amb(["P->KR3", "P->KR4", ...]) as the first line of
your chess program will return "the" winning move! Works great in theory
<wink>.

> Of course, discretion about what parts of the computation is retained
> at each branch would probably be an important economy for large
> computations, while stashing the continuation retains everything...)

You bet. But if you're not mucking with exponential call trees-- and,
believe me, you're usually not <wink> --it's not a big deal.

> Note that i do not raise this to argue against continuations. In fact,
> they seem to me to be at least the right conceptual foundation for these
> advanced control structures (i happen to "like" stream abstractions,
> which i gather is what generators are).

Generators are an "imperative" flavor of stream, yes, potentially useful
whenever you have an abstraction that can deliver a sequence of results
(from all the lines in a file, to all the digits of pi). A very common
occurrence! Heck, without it, Python's "for x in s:" wouldn't be any fun at
all <wink>.

how-do-i-love-thee?-let-me-generate-the-ways-ly y'rs - tim

Tim Peters wrote:
...

> This is a particularly simple application of coroutines that could be
> packaged up in a simpler way for its own sake; so, again, while
> continuations may be used fruitfully under the covers here, there's still no
> reason to make a poor end user wrestle with them.

Well.

def longcomputation(prog, *args, **kw):
return quickreturn(prog, args, kw)

# prog must be something with return function first arg
# quickreturn could be done as so:

def quickreturn(prog, args, kw):
cont = getpcc() # get parent's continuation
def jumpback(val=None, cont=cont):
putcc(cont, val) # jump to continuation
apply(prog, jumpback, args, kw)

# and if they want to jump out, they call jumpback with
# an optional return value.

Can't help it, it still is continuation-ish.

> > ... Well, I admit that the continuation approach is slightly too much
> > for the coroutine/generator case,
>
> It's good that you admit that, because generators alone could have been
> implemented with a 20-line patch <wink>. BTW, I expect that by far the bulk
> of your changes *still* amount to what's needed for disentangling the C
> stack, right? The continuation implementation has been subtle, but so far
> I've gotten the impression that it requires little code beyond that required
> for stacklessness.

Right. You will see soon. The only bit which cont's need more than
coro's is to save more than one stack state for a frame.
So, basically, it is just the frame copy operation.
If I was heading just for coroutines, then I could save
that, but then I need to handle special cases like exception,
what to do on return, and so on.
Easier to do that one stuff once right. Then I will never dump
code for an unforeseen coro-effect, since with cont's, I *may*
jump in and bail out wherever I want or don't want.
The special cases come later and will be optimized, and naturally
they will reduce themselves to what's needed.

Example: If I just want to switch to a different coro, I just
have to swap two frames. This leads to a data structure which
can hold a frame and exchange it with another one.
The cont-implementation does something like

fetch my current continuation # and this does the frame copy stuff
save into local state variable
fetch cont from other coro's local state variable
jump to new cont

Now, if the source and target frames are guaranteed to
be different, and if the source frame has no dormant
extra cont attached, then it is safe to merge the above
steps into one operation, without the need to save
local state.

In the end, two coro's will jump to each other by doing
nothing more than this. Exactly that is what Sam's
prototype does right now. WHat he's missing is treatment
of the return case. If a coro returns towards the place
where it was forked off, then we want to have a cont
which is able to handle it properly.
That's why exceptions work fine with my stuff: You can
put one exceptionhandler on top of all your coroutines
which you create. It works without special knowledge
of coroutines.
After I realized that, I knew the way to go.

>
> > ...
> > How about "amb"? :-)
> > (see "teach youself schem in fixnum days, chapter 14 at
> > http://www.cs.rice.edu/~dorai/t-y-scheme/t-y-scheme-Z-H-15.html#%_chap_14)
>
> That's the point at which I think continuations get insane: it's an
> unreasonably convoluted implementation of a straightforward (via other
> means) backtracking framework. In a similar vein, I've read 100 times that
> continuations can be used to implement a notion of (fake) threads, but
> haven't actually seen an implementation that wasn't depressingly subtle &
> long-winded despite being just a feeble "proof of concept".

Maybe this is a convoluted implementation. But the principle?
Return a value to your caller, but stay able to continue
and do this again.
Two continuations, and with the optimizations from above,
it will be nothing.

I will show you the code in a few, and you will realize that we are
discussing the empty set. The frames have to be used, and the
frames are already continuations. Only if they can be reached
twice, they will have to be armed for that.

Moving back to my new "more code - less words" principle.

[mutable ints as loop counters]

> Ah, very clever! Yes, that will fly -- the continuations will share a
> reference to the value rather than the value itself. Perfect!

Actually I'm copying some code out of Marc's counterobject
which is nothing more than a mutable integer and hide it
in ceval.c, since that doesn't introduce another module
for a thing which isn't needed elsewhere, after Guido's hint.

Better than to use the array module which doesn't publish
its internals and might not always be linked in.

> Right, no downside at all. Except that Guido will hate it <wink>.

I made sure that this is what he hates the lest.

off-for-coding-ly y'rs - chris

--
Christian Tismer :^) <mailto:tismer@appliedbiometrics.com>
Applied Biometrics GmbH : Have a break! Take a ride on Python's
Kaiserin-Augusta-Allee 101 : *Starship* http://starship.python.net
10553 Berlin : PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint E182 71C7 1A9D 66E9 9D15 D3CC D4D7 93E2 1FAE F6DF
we're tired of banana software - shipped green, ripens at home

[David Ascher]
> FWIW, I've been following the coroutine/continuation/generator bit with
> 'academic' interest -- the CS part of my brain likes to read about them.
> Prompted by Tim's latest mention of Demo/threads/Generator.py, I looked at
> it (again?) and *immediately* grokked it and realized how it'd fit into a
> tool I'm writing. Nothing to do with concurrency, I/O, etc -- just
> compartmentalization of stateful iterative processes (details too baroque
> to go over).

"stateful iterative process" is a helpful characterization of where these
guys can be useful! State captured in variables is the obvious one, but
simply "where you are" in a mass of nested loops and conditionals is also
"state" -- and a kind of state especially clumsy to encode as data state
instead (ever rewrite a hairy recursive routine to use iteration with an
explicit stack? it's a transformation that can be mechanized, but the
result is usually ugly & often hard to understand).

Once it sinks in that it's *possible* to implement a stateful iterative
process in this other way, I think you'll find examples popping up all over
the place.

> More relevantly, that tool would be useful on thread-less
> Python's (well, when it reaches usefulness on threaded Pythons =).

As Guido pointed out, the API provided by Generator.py is less restrictive
than any that can be built with the "one frame" flavor of generator
("resumable function"). Were you able to make enough sense of the long
discussion that ensued to guess whether the particular use you had in mind
required Generator.py's full power? If you couldn't tell, post the baroque
details & I'll tell you <wink>.

not-putting-too-fine-a-point-on-possible-vs-natural-ly y'rs - tim

On Sun, 11 Jul 1999, Tim Peters wrote:

> As Guido pointed out, the API provided by Generator.py is less restrictive
> than any that can be built with the "one frame" flavor of generator
> ("resumable function"). Were you able to make enough sense of the long
> discussion that ensued to guess whether the particular use you had in mind
> required Generator.py's full power? If you couldn't tell, post the baroque
> details & I'll tell you <wink>.

I'm pretty sure the use I mentioned would fit in even the simplest version
of a generator. As to how much sense I made of the discussion, let's just
say I'm glad there's no quiz at the end. I did shudder at the mention of
unmentionables (male public displays of affection -- yeaach!), yodel at
the mention of Lord Greystoke swinging among stack branches and chuckled
at the vision of him being thrown back in a traceback (ouch! ouch!
ouch!, "most painful last"...).

--david

[Tim]
> "stateful iterative process" is a helpful characterization of where these
> guys can be useful! State captured in variables is the obvious one, but
> simply "where you are" in a mass of nested loops and conditionals is also
> "state" -- and a kind of state especially clumsy to encode as data state
> instead (ever rewrite a hairy recursive routine to use iteration with an
> explicit stack? it's a transformation that can be mechanized, but the
> result is usually ugly & often hard to understand).

This is another key description of continuations (maybe not quite
worth a hug :). The continuation captures exactly all state that is
represented by "position in the program" and no state that is
represented by variables.

But there are many hairy details. In antiquated assembly, there might
not be a call stack, and a continuation could be represented by a
single value: the program counter. But now we have a call stack, a
value stack, a block stack (in Python) and who knows what else.

I'm trying to understand whether we can get away with saving just a
pointer to a frame, whether we need to copy the frame, or whether we
need to copy the entire frame stack.

(In regular Python, the frame stack also contains local variables.
These are explicitly exempted from being saved by a continuation. I
don't know how Christian does this, but I presume he uses the
dictionary which can be shared between frames.)

Let's see... Say we have this function:

def f(x):
try:
return 1 + (-x)
finally:
print "boo"

The bytecode (simplified) looks like:

SETUP_FINALLY (L1)
LOAD_CONST (1)
LOAD_FAST (x)
UNARY_NEGATIVE
BINARY_ADD
RETURN_VALUE

L1: LOAD_CONST ("boo")
PRINT_ITEM
PRINT_NEWLINE
END_FINALLY

Now suppose that the unary minus operator saves its continuation
(e.g. because x was a type with a __neg__ method). At this point
there is an entry on the block stack pointing to L1 as the try-finally
block, and the value stack has the value 1 pushed on it.

Clearly if that saved continuation is ever invoked (called? used?
activated? What do you call what you do to a continuation?) it should
substitute whatever value was passed into the continuation for the
result of the unary minus, and the program should continue by pushing
it on top of the value stack, adding it to 1, and returning the
result, executing the block of code at L1 on the way out. So clearly
when the continuation is used, 1 should be on the value stack and L1
should be on trh block stack.

Assuming that the unary minus function initially returns just fine,
the value stack and the block stack of the frame will be popped. So I
conclude that saving a continuation must save at least the value and
block stack of the frame being saved.

Is it safe not to save the frame and block stacks of frames further
down on the call stack? I don't think so -- these are all destroyed
when frames are popped off the call stack (even if the frame is kept
alive, its value and block stack are always empty when the function
has returned).

So I hope that Christian has code that saves the frame and block
stacks! (It would be fun to try and optimize this by doing it lazily,
so that frames which haven't returned yet aren't copied yet.)

How does Scheme do this? I don't know if it has something like the
block stack, but surely it has a value stack!

Still mystified,

--Guido van Rossum (home page: http://www.python.org/~guido/)

[.Guido wonders about continuations -- must be a bad night for sleep <wink>]

Paul Wilson's book-in-progress has a (large) page of HTML that you can
digest quickly and that will clear up many mysteries:

ftp://ftp.cs.utexas.edu/pub/garbage/cs345/schintro-v14/schintro_142.html

Scheme may be the most-often implemented language on Earth (ask 100 Schemers
what they use Scheme for, persist until you get the truth, and 81 will
eventually tell you that mostly they putz around writing their own Scheme
interpreter <0.51 wink>); so there are a *lot* of approaches out there.

Wilson describes a simple approach for a compiler. A key to understanding
it is that continuations aren't "special" in Scheme: they're the norm.
Even plain old calls are set up by saving the caller's continuation, then
handing control to the callee.

In Wilson's approach, "the eval stack" is a globally shared stack, but at
any given moment contains only the eval temps relevant to the function
currently executing. In preparation for a call, the caller saves away its
state in "a continuation", a record which includes:

the current program counter
a pointer to the continuation record it inherited
a pointer to the structure supporting name resolution (locals & beyond)
the current eval stack, which gets drained (emptied) at this point

There isn't anything akin to Python's block stack (everything reduces to
closures, lambdas and continuations). Note: the continuation is immutable;
once constructed, it's never changed.

Then the callees' arguments are pushed on the eval stack, a pointer to the
continuation as saved above is stored in "the continuation register", and
control is transferred to the callee.

Then a function return is exactly the same operation as "invoking a
continuation": whatever is in the continuation register at the time of the
return/invoke is dereferenced, and the PC, continuation register, env
pointer and eval stack values are copied out of the continuation record.
The return value is passed back in another "virtual register", and pushed
onto the eval stack first thing after the guts of the continuation are
restored.

So this copies the eval stack all the time, at every call and every
return/invoke. Kind of. This is partly why "tail calls" are such a big
deal in Scheme: a tail call need not (*must* not, in std Scheme) create a
new continuation. The target of a tail call simply inherits the
continuation pointer inherited by its caller.

Of course many Scheme implementations optimize beyond this.

> I'm trying to understand whether we can get away with saving just a
> pointer to a frame, whether we need to copy the frame, or whether we
> need to copy the entire frame stack.

In the absence of tail calls, the approach above saves the stack on every
call and restores it on every return, so there's no "extra" copying needed
when capturing, or invoking, a continuation (cold comfort, I agree <wink>).

About Christian's code, we'd better let it speak for itself -- I'm not clear
on the details of what he's doing today. Generalities:

> ...
> So I hope that Christian has code that saves the frame and block
> stacks!

Yes, but nothing gets copied until a continuation gets captured, and at the
start of that I believe only one frame gets cloned.

> (It would be fun to try and optimize this by doing it lazily,
> so that frames which haven't returned yet aren't copied yet.)

He's aware of that <wink>.

> How does Scheme do this? I don't know if it has something like the
> block stack, but surely it has a value stack!

Stacks and registers and such aren't part of the language spec, but, you
bet -- however it may be spelled in a given implementation, "a value stack"
is there.

BTW, many optimizing Schemes define a weaker form of continuation too
(call/ec, for "escaping continuation"). Skipping the mumbo jumbo definition
<0.9 wink>, you can only invoke one of those if its target is on the path
back from the invoker to the root of the call tree (climb up tree like
Cheetah, not leap across branches like Tarzan). This amounts to a
setjmp/longjmp in C -- and may be implemented that way!

i-say-do-it-right-or-not-at-all<wink>-ly y'rs - tim

Guido van Rossum wrote:
...
> I'm trying to understand whether we can get away with saving just a
> pointer to a frame, whether we need to copy the frame, or whether we
> need to copy the entire frame stack.

You need to preserve the stack and the block stack of a frame, if
and only if it can be reached twice. I make this dependent from
its refcount. Every frame monitors itself before and after
every call_function, if a handler field in the frame "f_callguard"
has been set. If so, the callguard is called. Its task is to
see wether we must preserve the current state of the frame and to
carry this out.

The idea is to create a shadow frame "on demand". When I touch
a frame with a refcount > 1, I duplicate it at its f_back pointer.
By that is is turned into a "continuation frame" which is nothing
more than the stack copy, IP, and the block stack.

By that, the frame stays in place where it was, all pointers
are still fine. The "real" one is now in the back, and the
continuation frame's purpose when called is only to restore
the state of the "real one" and run it (after doing a new
save if necessary).

I call this technique "push back frames".

>
> (In regular Python, the frame stack also contains local variables.
> These are explicitly exempted from being saved by a continuation. I
> don't know how Christian does this, but I presume he uses the
> dictionary which can be shared between frames.)

I keep the block stack and a stack copy. All the locals are
only existing once. The frame is also only one frame. Actually
always a new one (due to push back), but virtually it is
"the frame", with multiple continuation frames pointing at it.

...
> Clearly if that saved continuation is ever invoked (called? used?
> activated? What do you call what you do to a continuation?)

I think of throwing. Mine are thrown. The executive of standard
frames is "eval_code2_loop(f, passed_retval)", where the executive
of a continuation frame is "throw_continuation(f, passed_retval)".

...
> Is it safe not to save the frame and block stacks of frames further
> down on the call stack? I don't think so -- these are all destroyed
> when frames are popped off the call stack (even if the frame is kept
> alive, its value and block stack are always empty when the function
> has returned).
>
> So I hope that Christian has code that saves the frame and block
> stacks! (It would be fun to try and optimize this by doing it lazily,
> so that frames which haven't returned yet aren't copied yet.)

:-) I have exactly that, and I do it lazily already.
Unless somebody saves a continuation, nothing special happens.
But if he does, the push back process follows his path like
a zip (? Reißverschluß) and ensures that the path can be walked
again. Tarzan has now the end of this liane in his hand.
He might use it to swing over, or he might drop it, and it ribbles
away and vanishes as if it never existed.

Give me some final testing, and you will be able to try it out
in a few days.

ciao - chris

--
Christian Tismer :^) <mailto:tismer@appliedbiometrics.com>
Applied Biometrics GmbH : Have a break! Take a ride on Python's
Kaiserin-Augusta-Allee 101 : *Starship* http://starship.python.net
10553 Berlin : PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint E182 71C7 1A9D 66E9 9D15 D3CC D4D7 93E2 1FAE F6DF
we're tired of banana software - shipped green, ripens at home

Tim Peters wrote:
...
> BTW, many optimizing Schemes define a weaker form of continuation too
> (call/ec, for "escaping continuation"). Skipping the mumbo jumbo definition
> <0.9 wink>, you can only invoke one of those if its target is on the path
> back from the invoker to the root of the call tree (climb up tree like
> Cheetah, not leap across branches like Tarzan). This amounts to a
> setjmp/longjmp in C -- and may be implemented that way!

Right, maybe this would do enough. We will throw away what's
not needed, when we know what we actually need...

> i-say-do-it-right-or-not-at-all<wink>-ly y'rs - tim

...and at the moment I think it was right to take it all.

just-fixing-continuations-spun-off-in-an-__init__-which-
-is-quite-hard-since-still-recursive,-and-I-will-ship-it-ly y'rs

- chris

--
Christian Tismer :^) <mailto:tismer@appliedbiometrics.com>
Applied Biometrics GmbH : Have a break! Take a ride on Python's
Kaiserin-Augusta-Allee 101 : *Starship* http://starship.python.net
10553 Berlin : PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint E182 71C7 1A9D 66E9 9D15 D3CC D4D7 93E2 1FAE F6DF
we're tired of banana software - shipped green, ripens at home

Backtracking a bit:

[Guido]
> This is another key description of continuations (maybe not quite
> worth a hug :).

I suppose a kiss is out of the question, then.

> The continuation captures exactly all state that is represented by
> "position in the program" and no state that is represented by variables.

Right!

> But there are many hairy details. In antiquated assembly, there might
> not be a call stack, and a continuation could be represented by a
> single value: the program counter. But now we have a call stack, a
> value stack, a block stack (in Python) and who knows what else.
>
> I'm trying to understand whether we can get away with saving just a
> pointer to a frame, whether we need to copy the frame, or whether we
> need to copy the entire frame stack.

As you convinced yourself in following paragraphs, for 1st-class
continuations "the entire frame stack" *may* be necessary.

> ...
> How does Scheme do this?

I looked up R. Kent Dybvig's doctoral dissertation, at

ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/3imp.ps.gz

He gives detailed explanations of 3 Scheme implementations there (from
whence "3imp", I guess). The first is all heap-based, and looks much like
the simple Wilson implementation I summarized yesterday. Dybvig profiled it
and discovered it spent half its time in, together, function call overhead
and name resolution.

So he took a different approach: Scheme is, at heart, just another
lexically scoped language, like Algol or Pascal. So how about implementing
it with a perfectly conventional shared, contiguous stack? Because that
doesn't work: the advanced features (lexical closures with indefinite
extent, and user-captured continuations) aren't stack-like. Tough, forget
those at the start, and do whatever it takes later to *make* 'em work.

So he did. When his stack implementation hit a user's call/cc, it made a
physical copy of the entire stack. And everything ran much faster! He
points out that "real programs" come in two flavors:

1) Very few, or no, call/cc thingies. Then most calls are no worse than
Algol/Pascal/C functions, and the stack implementation runs them at
Algol/Pascal/C speed (if we knew of anything faster than a plain stack, the
latter would use it).

2) Lots of call/cc thingies. Then "the stack" is likely to be shallow (the
program is spending most of its time co-transferring, not recursing deeply),
and because the stack is contiguous he can exploit the platform's fastest
block-copy operation (no need to chase pointer links, etc).

So, in some respects, Dybvig's stack implementation of Scheme was more
Pythonic than Python's current implementation <wink -- Dybvig effectively
used a Python list at this level, while Python effectively uses a Lispish
cons'ed frame list>.

His third implementation was for some propeller-head theoretical "string
machine", so I won't even mention it.

worrying-about-the-worst-case-can-hurt-the-normal-cases-ly y'rs - tim

Vladimir Marangozov wrote:
...
> > too-simple-to-be-obvious?-ly y'rs - tim
>
> Yes. I'm trying to understand the following:
>
> 1. What does a generator generate?

Trying my little understanding.

A generator generates a series of results if you ask for it.
That's done by a resume call (generator, resume your computation),
and the generate continues until he either comes to a suspend
(return a value, but be prepared to continue from here) or it
does a final return.

> 2. Clearly, what's the difference between a generator and a thread?

Threads can be scheduled automatically, and they don't return
values to each other, natively.
Generators are asymmetric to their callers, they're much like
functions.
Coroutines are more symmetric. They "return" to each other
values. They are not determined as caller and callee, but
they cooperate on the same level.
Therefore, threads and coroutines look more similar, just that
coroutines usually are'nt scheduled automatically. Add a scheduler,
don't pass values, and you have threads, nearly.
(of course I dropped the I/O blocking stuff which doesn't
apply and isn't the intent of fake threads).

ciao - chris

--
Christian Tismer :^) <mailto:tismer@appliedbiometrics.com>
Applied Biometrics GmbH : Have a break! Take a ride on Python's
Kaiserin-Augusta-Allee 101 : *Starship* http://starship.python.net
10553 Berlin : PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint E182 71C7 1A9D 66E9 9D15 D3CC D4D7 93E2 1FAE F6DF
we're tired of banana software - shipped green, ripens at home

After a short vacation, I'm trying to swallow the latest discussion
about control flow management & derivatives. Could someone help me
please by answering two naive questions that popped up spontaneously
in my head:

Tim Peters wrote:

[a biased short course on generators, continuations, coroutines]
>
> ...
>
> GENERATORS
>
> Generators add two new abstract operations, "suspend" and "resume". When a
> generator suspends, it's exactly like a return today except we simply
> decline to decref the frame. That's it! The locals, and where we are in
> the computation, aren't thrown away. A "resume" then consists of
> *re*starting the frame at its next bytecode instruction, with the retained
> frame's locals and eval stack just as they were.
>
> ...
>
> too-simple-to-be-obvious?-ly y'rs - tim

Yes. I'm trying to understand the following:

1. What does a generator generate?

2. Clearly, what's the difference between a generator and a thread?

--
Vladimir MARANGOZOV | Vladimir.Marangozov@inrialpes.fr
http://sirac.inrialpes.fr/~marangoz | tel:(+33-4)76615277 fax:76615252

[Vladimir Marangozov]
> Yes. I'm trying to understand the following:
>
> 1. What does a generator generate?

Any sequence of objects: the lines in a file, the digits of pi, a postorder
traversal of the nodes of a binary tree, the files in a directory, the
machines on a LAN, the critical bugs filed before 3/1/1995, the set of
builtin types, all possible ways of matching a regexp to a string, the
5-card poker hands beating a pair of deuces, ... anything!

Icon uses the word "generators", and it's derived from that language's
ubiquitous use of the beasts to generate paths in a backtracking search
space.

In OO languages it may be better to name them "iterators", after the closest
common OO concept. The CLU language had full-blown (semi-coroutine, like
Icon generators) iterators 20 years ago, and the idea was copied &
reinvented by many later languages. Sather is probably the best known of
those, and also calls them iterators.

> 2. Clearly, what's the difference between a generator and a thread?

If you can clearly explain what "a thread" is, I can clearly explain the
similarities and differences. Well? I'm holding my breath here <wink>.

Generators/iterators are simpler than threads, whether looked at from a
user's viewpoint or an implementor's. Their semantics are synchronous and
deterministic.

Python's for/__getitem__ protocol *is* an iterator protocol already, but if
I ask you which is the 378th 5-card poker hand beating a pair of deuces, and
ask you a new question like that every hour, you may start to suspect there
may be a better way to *approach* coding enumerations in general <wink>.

then-again-there-may-not-be-ly y'rs - tim

Just so Guido doesn't feel like the quesion is being ignored <wink>:

> ...
> How does Scheme do this? [continuations]

One more reference here. Previously sketched Wilson's simple heap
implementation and Dybvig's simple stack one. They're easy to understand,
but are (heap) slow all the time, or (stack) fast most of the time but
horribly slow in some cases.

For the other extreme end of things, check out:

Representing Control in the Presence of First-Class Continuations
Robert Hieb, R. Kent Dybvig, and Carl Bruggeman
PLDI, June 1990
http://www.cs.indiana.edu/~dyb/papers/stack.ps

In part:

In this paper we show how stacks can be used to implement activation
records in a way that is compatible with continuation operations,
multiple control threads, and deep recursion. Our approach allows
a small upper bound to be placed on the cost of continuation operations
and stack overflow and underflow recovery. ... ordinary procedure calls
and returns are not adversely affected. ... One important feature of
our method is that the stack is not copied when a continuation is
captured. Consequently, capturing a continuation is very efficient,
and objects that are known to have dynamic extent can be stack­
allocated and modified since they remain in the locations in which
they were originally allocated. By copying only a small portion of the
stack when a continuation is reinstated, reinstatement costs are
bounded by a small constant.

The basic gimmick is a segmented stack, where large segments are
heap-allocated and each contains multiple contiguous frames (across their
code base, only 1% of frames exceeded 30 machine words). But this is a
complicated approach, best suited for industrial-strength native-code
compilers (speed at any cost -- the authors go thru hell to save an add
here, a pointer store there, etc).

At least at the time the paper was written, it was the approach implemented
by Dybvig's Chez Scheme (a commercial native-code Scheme compiler noted for
high speed).

Given that Python allocates frames from the heap, I doubt there's a much
faster approach than the one Christian has crafted out of his own sweat and
blood! It's worth a paper of its own.

or-at-least-two-hugs<wink>-ly y'rs - tim