Henry Baker showed that call/cc doesn't require a spaghetti stack with dynamically allocated frames. All you need is one linear stack, and never return.
Richard Stallman made similar observations in Phantom Stacks. If You Look to Hard They Aren't There.
Chicken Scheme, based on C, implements Baker's idea. Chicken Scheme's C functions never return. They take a continuation argument, and just call that instead of returning. So every logical function return is actually a new C funtion call. These all happen on the same stack, so it grows and grows. All allocations are off the stack, including lambda environments, and other objects like dynamic strings. When the stack reaches a certain limit, it is rewound back to the top, like a treadmill. During this rewinding phase, all objects allocated from the stack which are still reachable are moved to the heap.
Thus the combination of the CPS strategy (all returns are continuation invocations) and the linear stack with rewinding obviates the need for dynamically allocated frames.
I'm aware of this work, especially Chicken Scheme, but Chicken scheme basically combines the stack and the heap + compacting GC, so it's a reach to say that Chicken Scheme doesn't allocate frames on the heap... If you have to GC frames, then they are as-if on the heap. Same thing for related variants.
You can also just allocate all frames on the stack and use stack copying for `call/cc` -- this involves... a heap of stack copies :laugh: so I think I'm henceforth going to say that `call/cc` continuations always require heap allocations :)
Richard Stallman made similar observations in Phantom Stacks. If You Look to Hard They Aren't There.
Chicken Scheme, based on C, implements Baker's idea. Chicken Scheme's C functions never return. They take a continuation argument, and just call that instead of returning. So every logical function return is actually a new C funtion call. These all happen on the same stack, so it grows and grows. All allocations are off the stack, including lambda environments, and other objects like dynamic strings. When the stack reaches a certain limit, it is rewound back to the top, like a treadmill. During this rewinding phase, all objects allocated from the stack which are still reachable are moved to the heap.
Thus the combination of the CPS strategy (all returns are continuation invocations) and the linear stack with rewinding obviates the need for dynamically allocated frames.