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
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4