Understanding (sub,partial,full,one-shot) continuations (in procedural languages)

Question

After reading almost everything I could find about continuations, I still have trouble understanding them. Maybe because all of the explanations are heavily tied with lambda calculus, which I have trouble understanding.

In general, a continuation is some representation of what to do next, after you have finished doing the current thing, i.e. the rest of the computation.

But then, it gets trickier with all the variety. Maybe some of you could help me out with my custom analogy here and point out where I have made mistakes in my understanding.

Let's say our functions are represented as objects, and for the sake of simplicity:

1. Our interpreter has a stack of function calls.
2. Each function call has a stack for local data and arguments.
3. Each function call has a queue of "instructions" to be executed that operate on the local data stack and the queue itself (and, maybe on the stacks of callers too).

^{The analogy is meant to be similar to XY concatenative language.}

So, in my understanding:

• A continuation is the rest of the whole computation (this unfinished queue of instructions + stack of all subsequent computations: queues of callers).
• A partial continuation is the current unfinished queue + some delimited part of the caller stack, up until some point (not the full one, for the whole program).
• A sub-continuation is the rest of the current instruction queue for currently "active" function.
• A one-shot continuation is such a continuation that can be executed only once, after being reified into an object.

Please correct me if I am wrong in my analogies.

Initial

You might find this QA useful: https://mcmap.net/q/150996/-what-39-s-the-difference-between-a-continuation-and-a-callback/783743 – Kataway

Seen that one. Tries to explain the general idea of the Continuation, but not all the varieties that I am struggling with – Initial

You might want to adjust your machine model to have a stack of function calls, that is when a function is called twice it can have different local data and arguments. Otherwise you get static data and non-reentrant functions. Also by "operate on the stack of callers" I hope you mean the interpreter's function (call) stack, not the local data of the caller of the function. – Fortunato

@Fortunato yea, I've meant that. Of course its a stack of unique frames. – Initial

Answer 1

A continuation is the rest of the whole computation (this unfinished queue of instructions + stack of all subsequent computations: queues of callers)

Informally, your understanding is correct. However, continuation as a concept is an abstraction of the control state and the state the process should attain if the continuation is invoked. It needs not contain the entire stack explicitly, as long as the state can be attained. This is one of the classical definitions of continuation. Refer to Rhino JavaScript doc.

A partial continuation is the current unfinished queue + some delimited part of the caller stack, up until some point (not the full one, for the whole program)

Again, informally, your understanding is correct. It is also called delimited continuation or composable continuation. In this case, not only the process needs to attain the state represented by the delimited continuation, but it also needs to limit the invocation of the continuation to the limit specified. This is in contrast to full continuation, which starts from the point specified and continues to the end of the control flow. Delimited continuation starts from this point and ends in another identified point only. It is a partial control flow and not the full one, which is precisely why delimited continuation needs to return a value (see the Wikipedia article). The value usually represents the result of the partial execution.

A sub-continuation is the rest of the current instruction queue for currently "active" function

Your understanding here is slightly hazy. Once way to understand this is to consider a multi-threaded environment. If there is a main thread and a new thread is started from it at some point, then a continuation (from the context of main or child thread), what should it represent? The entire control flow of child and main threads from that point (which in most cases does not make much sense) or just the control flow of the child thread? Sub-continuation is a kind of delimited continuation, the control flow state representation from a point to another point that is part of the sub-process or a sub-process tree. Refer to this paper.

A one-shot continuation is such a continuation that can be executed only once, after being reified into an object

As per this paper, your understanding is correct. The paper seems not to explicitly state if this is a full/classical continuation or a delimited one; however, in next sections, the paper states that full continuations are problematic, so I would assume this type of continuation is a delimited continuation.

Unbonnet

The last paper you mentioned explicitly states "delimited continuations are not part of this proposal" and the proposed "std::continuation is a one-shot continuation", so your assumption looks wrong. A reply of the author also confirms this point. (However, I believe the "full continuation" in the paper is a misnormer. "Full continuation" is constrast to "partial continuation", not the synonym of "multi-shot continuation".) – Stickler

Further, there is the traditional practical implementation of call/1cc deals one-shot continuations without delimiters (even the stack is split). Both of the implementation details (the underflow handler in the path without an explicit continuation invocation) and the call/1cc's descriptions suggest that the continuation cannot be invoked more than once even it is not applied explicitly, so "after being reified into an object" is imprecise and redundant. – Stickler

A side note (mostly to some discussions in the link referenced above): flavors of continuations are not bound to the syntaxes. For example, traditional Scheme's call/cc reifies undelimited continuations, but nowadays call/cc in Racket actually reifies delimited ones (and it fails same as the formalized semantics of the shift operator for the missing prompt). – Stickler