Hacker News new | ask | show | jobs
by fao_ 3293 days ago
As far as I know, scheme's continuations are efficient. That's kind of the basis of RABBIT, Orbit, and a chunk of Appel's work, isn't it?

(See also: http://lambda-the-ultimate.org/node/2406#comment-36369)

3 comments

As far as I can tell, L2's continuations look very similar to the Cheney on the M.T.A. [0] approach to continuations.

[0] http://home.pipeline.com/~hbaker1/CheneyMTA.html

Thanks for the link. I am not sure if I see the similarity. L2 neither uses the heap nor garbage collection nor are its programs converted into continuation-passing-style. Am I missing something?
Those compilers use CPS as an intermediate language - a bit like SSA form for functional languages - which is (mostly) independent of supporting first class continuations.

Support for first class continuations is a matter of tradeoffs. It's quite reasonable for an implementation to choose 'slow' continuations (in which call/cc copies the stack) in order to be able to use the more efficient native stack for function calls.

(EDIT: and in response to the linked post, it is quite possible to efficiently compile what would be contifiable functions in direct style - see the recent paper Compiling Without Continuations in which the GHC hackers do exactly that.)

I will try to read into the details of Scheme's implementation of continuations...

The reason I made the claim about efficiency is because Scheme's continuations have an unlimited lifetime. This is in contrast to L2's continuations that can only have a dynamic lifetime. (The rules for manipulating continuations in L2 are analogous (and only analogous) to the rules for returning the addresses of local variables in C.) So I just assumed that Scheme implementations must occur an overhead for the greater generality of their continuations.

Different Scheme implementations, presumably, have different implementations of continuations.

An implementation of call/cc can be efficient provided you are willing to sacrifice the notion of a single execution stack and embrace constructs like spaghetti stacks that allow for indefinite lifetime of an execution context.