RE: Fake threads (was [Python-Dev] ActiveState & fork & Perl)
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
[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
participants (2)
-
Ken Manheimer -
Tim Peters