3 ms·

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://lam

by fao_ 9y 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 http://lambda-the-ultimate.org/node/2406#comment-36369)

shakna 9y ago
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 http://home.pipeline.com/~hbaker1/CheneyMTA.html
- murisitarusenga 9y ago
  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?
gsg 9y ago
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.)
murisitarusenga 9y ago
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.
- bitwize 9y ago
  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.

by fao_ 9y ago

shakna 9y ago

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 http://home.pipeline.com/~hbaker1/CheneyMTA.html

murisitarusenga 9y ago
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?

gsg 9y ago

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.)

murisitarusenga 9y ago

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.

bitwize 9y ago
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.