5
$\begingroup$

I have heard that smlnj uses continuation passing style and that is one reason it has been dropped from the proof assistant Isabelle.

Makarius, the author of the answer above, also gave a detailed explanation of why CPS has bad performance properties.

At first approximation, there is a difference in "locality" of memory access, when a program just runs forward on the heap in CPS style, instead of the traditional growing and shrinking of the stack.

However, it's not clear to me why continuation-passing-style implementations need to use the heap in the sense of using the abstraction provided by malloc and free and not some other kind of allocator.

My understanding is that the malloc/free abstraction is maximally flexible in the sense that no constraints at all are imposed on the lifetime of different fragments of memory, as opposed to the stack which is strictly FIFO.

I'm wondering whether all that flexibility is really necessary though, or if more efficient implementations of CPS are possible.

As a quick straw man, if we took an ordinary language without continuations like Python or C, and translated it to CPS (in an extension of the language with continuations), then we could implement that subset of the expanded language using a stack.

In other words, a CPS-y language or intermediate language that doesn't use its newfound powers in exotic ways should theoretically be able to be treated like a non-CPS language.

This makes me wonder whether there are efficient strategies for implementation CPS-y languages.

$\endgroup$
4
  • 2
    $\begingroup$ Have you heard of Chicken Scheme? If you have not, it might answer some of your questions. If you have, kindly disregard this comment. (I've only heard of it from my friends myself but have heard it referred to as the canonical extremely efficient CPS language.) $\endgroup$ Commented Oct 15, 2024 at 4:49
  • $\begingroup$ I've heard of it and some fancy trampoline thing it has in its runtime (and some quote about sometimes jumping off the Eiffel tower?), but I didn't connect it with my question until I read your comment. $\endgroup$ Commented Oct 15, 2024 at 4:51
  • $\begingroup$ "As a quick straw man …" Not sure what you are trying to say with this and the next paragraph. Most (all?) simple mechanisms are degenerate cases of more complex ones; however, implementing that degenerate case efficiently has already been done and by construction doesn’t get you the full case efficiently, only the degenerate one whose lack of features is exploited by the implementation. $\endgroup$ Commented Oct 15, 2024 at 5:43
  • 1
    $\begingroup$ "The stack" is simply a slab allocator which takes advantage of the fact that sometimes the lifetimes of newer things are known to be always shorter than the lifetimes of older things. The problem with CPS is that predicting the lifetime of a particular storage location / object accurately enough to optimize their allocation strategy is often equivalent to solving the halting problem. Lacking a solution to that problem, our recourse is to fall back on a general-purpose allocator. $\endgroup$ Commented Oct 15, 2024 at 22:23

1 Answer 1

Reset to default
2
$\begingroup$

If we took an ordinary language without continuations like Python or C, and translated it to CPS (in an extension of the language with continuations), then we could implement that subset of the expanded language using a stack.

If you did that, then you could implement it with a stack, but your continuations would not be real continuations. They would be like continuations, except you would have a bunch of rules in place about their relative lifetimes, and those kinds of things couldn't be used as continuations generally.

The reason why continuations require allocation apart from the stack is that they need to be valid after the function call/stack frame they were created in is destroyed.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.