[cryptonector]

The easiest way to think about continuations is to consider them a generalization of function returns. The continuation of a C function f() is the return address and the saved frame pointer of the calling function -- and that looks a lot like a closure, and that's because it is, except that a) you can only pass that closure one argument in C: the return value, and b) you actually can't get a value for this closure in C, and c) there's no closures as such in C anyways :)

[And what is a closure? It's a tuple of {function body pointer, data pointer}, and "callbacks" in C often look just like that, but not as a singular value combining the two parts but as two separate values. In better languages a function is indistinguishable from a closure.]

Anywhere that you see `call/cc` you can think of it as making a first-class function value (a closure) of the current location (which would be the return address of the call to `call/cc`) and then passing that closure to the function given as an argument to `call/cc`. After you parse that sentence you'll realize that's a bit crazy: how does one make a function out of... a function's return address (and saved frame pointer)? The answer is: reify that {return address, saved frame pointer} as a closure. ('Reify' means, roughly, to make a hidden thing not hidden.)

Still, it must seem crazy. Yet it's not that crazy, certainly not if you make it so you can only call it once, and only if `call/cc` hasn't returned yet. What's crazy is that in Scheme this continuation can be called repeatedly, so how? Here's one way to do it: replace the stack with allocating function call frames on the heap!, which in a language with a GC means that all those function call frames remain alive as long as closures (which a continuation is) refer to them. (Another way to do it is with copying stacks.)

One can easily (for some value of "easily") implement a language that has `call/cc` in a language that doesn't but which has a) closures, b) a powerful macro system / AST / homoiconicity. All one has to do is take a program, apply continuation passing style (CPS) conversion to it (a fairly straightforward transformation where the result is unreadable for most humans), which automatically causes all function call frames to be captured in closures (thus put on the heap), but also automatically makes continuations explicit values (closures). The `call/cc` is a trivial function that passes its now-explicit continuation argument to the function that `call/cc` is given to call.

Allocating function call frames on the heap is a performance disaster. And that's where delimited continuations come in: the goal being to allocate function call frames on mini stacks.

`call/cc` is really a bit of a parlor trick, and a very nifty one at that, but continuations are a very important concept that comes up all over the place, and one that computer scientists and software engineers ought to be at least conversant with.

[JonChesterfield]

Simpler still is to recognise that "call a function" and "return from a function" are different syntax over the same thing. They both mean "jump to somewhere with a convention about where to find state".

If you replace "call a function" with goto, and replace "return from a function" with goto, then it becomes immediately obvious that "continuation" is a name for where you're going to jump to next. It only looks complicated from the context of calls/returns/stacks.

Confusing call and return for different things is unfortunate but popular. It gives rise to things like four registers available for passing arguments and one available for returning a result, when the calling convention really should be symmetric.

"Continuation passing style" is what all function calls use - x86 writes the address of the continuation to the stack, more sensible ISA's pass it in a specific register - modulo language syntax that somewhat obfuscates control flow.

[cryptonector]

> Simpler still is to recognise that "call a function" and "return from a function" are different syntax over the same thing. They both mean "jump to somewhere with a convention about where to find state".

That's pretty much what I was saying, but pithier and better stated, so thank you.

> If you replace "call a function" with goto, and replace "return from a function" with goto, then it becomes immediately obvious that "continuation" is a name for where you're going to jump to next. It only looks complicated from the context of calls/returns/stacks.

Yes, thus "lambda is the ultimate GOTO".

> Confusing call and return for different things is unfortunate but popular. It gives rise to things like four registers available for passing arguments and one available for returning a result, when the calling convention really should be symmetric.

It's a convenient abstraction for Algol family languages.

There is a difference between function call and function return in those languages: a call pushes a frame on the stack, and a return pops a frame off the stack, but both otherwise look very similar under the covers.

In CPS the "pop a frame off the stack" part doesn't happen, but instead you get tail-call optimization (TCO) to avoid the stack blowing up with calls to functions that never return (and which anyways maybe store their real call frames on the heap to boot, thus wasting all that stack space for nothing).

[kazinator]

> like four registers available for passing arguments and one available for returning a result, when the calling convention really should be symmetric

The symmetry implies the support for multiple return values.

If the language model has single return values, then continuations take one parameter. Lots of historic papers about continuations model them that way.

Multiple values are tricky. 100% symmetry is never achieved with those things. The problem is that in many contexts, an expression is expected to produce one value. We usually want (foo (bar) (baz)) to call foo with two arguments even if bar and baz return two or more values. There may be times when we want to inerpolate all the values, or some of them, into the argument space, so we need some syntax to distinguish those situations. But if (foo (bar) (baz)) just takes one value from each function, then that means that the primary value is more of a first class citizen than the additional values. There is something special about it.

We can also go the other way: declare that functions should not only return exactly one value, but only take exactly one argument. That is also symmetric! Then currying can be used to combine functions in order to simulate multiple arguments.

[JonChesterfield]

This is tricky in the comment format but here goes.

Let us declare that a function is passed exactly one value, and that it passes exactly one value to the chosen continuation. However that does not imply that it takes exactly one named argument.

(lambda a ...)

Binds that one value to a. If you pass it a list, that's a variadic function.

(lambda (a b) ...)

Requires the argument be a list of two values and binds the elements to a, b.

(lambda (a (b c) d) ...)

Likewise, except it's now a list of three things where element 1 must be a list of two things.

The corresponding return/continuation part then looks like

(let a (foo) (b c) (bar) ...)

where the let binds whatever foo returned to a, binds a list of length 2 from bar and so forth.

This works really nicely with static typing in the absence of function currying. Destructuring bind on function arguments is somewhat common.

In lisp, you have to work out what let returns when the binding doesn't typecheck at runtime and that's a bit of a mess.

In SML the construct typechecks at compile time but I can't work out how to reconcile it with currying.

Parameter trees, the (a (b) c) idea, I first saw in kernel. I don't remember if it went as far as let binding / destructuring on the continuation invocation.

I like the destructuring syntax more than currying so haven't put as much thought into providing both as the latter might deserve.

[cryptonector]

> The symmetry implies the support for multiple return values.

Yes!

> Multiple values are tricky. 100% symmetry is never achieved with those things. The problem is that [...]

You basically need destructuring on the return values, and the syntax for that has to be fairly clean. And for the example you give where one function's return value(s) is(are) passed to another's things do get tricky: shall that use only the first value returned? or maybe the whole lot of them (as an array/list)? or both, where if the callee doesn't treat the thing as an array/list then it's the first value (implying dynamic typing)? or does what happens depend on the callee's parameter's type? or what? Yeah, it's very tricky.

Another option is to have generators, and if a function returns/yields multiple values in one go, maybe treat them as single values yielded separately. This one isn't that awesome either.

> We can also go the other way: declare that functions should not only return exactly one value, but only take exactly one argument. That is also symmetric! Then currying can be used to combine functions in order to simulate multiple arguments.

Yes :)

But then in Haskell, which does this, we end up with syntactic sugar with which to pretend there's multiple arguments, thus the 100% symmetry isn't quite.

Oh well.

[kazinator]

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.

[cryptonector]

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