<p>I have heard that smlnj uses continuation passing style and <a href="https://proofassistants.stackexchange.com/a/679">that is one reason it has been dropped from the proof assistant Isabelle</a>.</p>
<p>Makarius, the author of the answer above, also <a href="https://cs.stackexchange.com/a/10235/">gave a detailed explanation of why CPS has bad performance properties</a>.</p>
<blockquote>
<p>At first approximation, there is a difference in &quot;locality&quot; 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.</p>
</blockquote>
<p>However, it's not clear to me why continuation-passing-style implementations need to use <em>the heap</em> in the sense of using the abstraction provided by <code>malloc</code> and <code>free</code> and not some other kind of allocator.</p>
<p>My understanding is that the <code>malloc</code>/<code>free</code> 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.</p>
<p>I'm wondering whether all that flexibility is really <em>necessary</em> though, or if more efficient implementations of CPS are possible.</p>
<p>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.</p>
<p>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.</p>
<p>This makes me wonder whether there are efficient strategies for implementation CPS-y languages.</p>

<runtime><continuation-passing-style>
Are efficient implementations of continuation passing style possible?
CC BY-SA 4.0
2024-10-15T04:49:54.607Z
Have you heard of [Chicken Scheme](https://www.call-cc.org/)? 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.)
apropos
CC BY-SA 4.0
2024-10-15T04:51:26.413Z
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.
Greg Nisbet
CC BY-SA 4.0
2024-10-15T05:43:41.747Z
"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.
MisterMiyagi
CC BY-SA 4.0
2024-10-15T22:23:50.740Z
"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.
Eric Lippert
<blockquote>
<p>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.</p>
</blockquote>
<p>If you did that, then you could implement it with a stack, but your continuations would not be real continuations.  They would be <em>like</em> 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.</p>
<p>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.</p>

CC BY-SA 4.0
2024-10-15T21:37:21.250Z
2024-10-15T21:37:21.250Z
Matt Timmermans
# Are efficient implementations of continuation passing style possible?
Posted by: username_0 on 2024-10-15
I have heard that smlnj uses continuation passing style and [that is one reason it has been dropped from the proof assistant Isabelle](https://proofassistants.stackexchange.com/a/679).

Makarius, the author of the answer above, also [gave a detailed explanation of why CPS has bad performance properties](https://cs.stackexchange.com/a/10235/).

> 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.
**Tags:** runtime continuation-passing-style
> **Comments:**
> **username_1**: Have you heard of [Chicken Scheme](https://www.call-cc.org/)? 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.)  
> **username_0**: 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.  
> **username_2**: "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.  
> **username_3**: "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.  
---
## 1 answers
### Answer by username_4 on 2024-10-15. Score: 2
> 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.
---
