Live data from Hacker News

What Does "With Continuation" Mean? (2020)

forum.snap.berkeley.edu

11–20 of 60 posts

Re: What Does "With Continuation" Mean? (2020)

#11
post #10

I took a Scheme programming class where we did tons of stuff with continuations. I got obsessed and wrote all kinds of weird code. I even started using continuation passing style in Python. It was a dark time. Looking back, none of that code makes any sense at all. When I think back to my days of mucking around with call/cc my main emotion is relief that I’ve forgotten how it works. It’s a load off my mind

In case first-class continuations scare anyone away from Scheme: you probably will never use it directly in practice, unless you're doing something very unusual that happens to really need it. For example, say you have a really hairy AI search algorithm, capturing a continuation happens to make backtracking easier. Or you're implementing another language or DSL in Scheme, and you use first-class continuations to impl…

I’m having trouble recalling, call cc just fixes the stack, right? If you mess with the heap, that sticks around?

The backtracking example is a good one. I vaguely remember needing to be careful about global state, or visible in a given context. It’s not awful, but a little tricky.

Re: What Does "With Continuation" Mean? (2020)

#12
I don't know whether it helps, but here's another explanation that doesn't involve a visual programming language:

First, imagine that procedures (or functions) are first-class values, like in some languages are called "anonymous functions", "closures", "lambdas", etc.

Now imagine that every procedure call is effectively a goto with arguments... and the familiar part about being able to return from that procedure, to its calling point, is implemented by an implicit additional value created at calling time... which is a "continuation" procedure with argument(s) that you call to return the value(s) from the other procedure.

To make it first-class continuations, imagine that "continuation" procedure value you call to return the value(s) from another procedure... can be made accessible to the program as a first-class value. Which means you can store it in a variable or data structure like any other value. And you can call that "continuation" procedure value multiple times -- returning to that dynamic state of the calling context in the program many times.

It's one of those things that application code almost never uses directly, but that could be super useful and simplifying in the implementation of another programming language, or carefully controlled in particular libraries (e.g., you wanted to make a stateful Web backend library or DSL that made it really easy to express the logic for some kind of interaction tree responding to multiple steps of form input).

Re: What Does "With Continuation" Mean? (2020)

#14
So there’s a funny thing this doesn’t touch on: the semantics of call/cc is genuinely confusing to understand! There’s a related construct that’s much more legible and has a much easier to understand: call with delimited continuation!

Oleg K wrote a very articulate piece about this some long time ago https://okmij.org/ftp/continuations/against-callcc.html

Re: What Does "With Continuation" Mean? (2020)

#15
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.

Re: What Does "With Continuation" Mean? (2020)

#16

Required reference "Objects the poor man's Closures[continuations]" [1]. Well, the links actually say "Closures And Objects Are Equivalent", which is the point. But I'd offer a deeper point - continuations/closures are rightly considered one of the hardest things most programmers ever encounter while objects are things most programmers deal with daily. Sure, that means use continuations if you want to look like a bad…

Continuations aren't equivalent to closures.

Re: What Does "With Continuation" Mean? (2020)

#17

I took a Scheme programming class where we did tons of stuff with continuations. I got obsessed and wrote all kinds of weird code. I even started using continuation passing style in Python. It was a dark time. Looking back, none of that code makes any sense at all. When I think back to my days of mucking around with call/cc my main emotion is relief that I’ve forgotten how it works. It’s a load off my mind

For me it's the opposite: I can't forget how it works, I don't want to forget how it works, and I marvel at the beauty of it all.

When I was in school I carried one of Guy Steele's (I think, if I remember correctly) articles about continuations in my back pocket for a year, breaking it out when I was bored, until I got it.

Re: What Does "With Continuation" Mean? (2020)

#18

Required reference "Objects the poor man's Closures[continuations]" [1]. Well, the links actually say "Closures And Objects Are Equivalent", which is the point. But I'd offer a deeper point - continuations/closures are rightly considered one of the hardest things most programmers ever encounter while objects are things most programmers deal with daily. Sure, that means use continuations if you want to look like a bad…

Continuations aren't equivalent to closures.

Continuations are closures. Closures aren't continuations. Though one can build continuations out of closures by converting code into continuation passing style, which makes continuations explicit, and then `call/cc` is trivial, since all it does is pass (to its function argument) its [now-explicit, after CPS conversion] continuation, thus reifying it.

Re: What Does "With Continuation" Mean? (2020)

#19

So there’s a funny thing this doesn’t touch on: the semantics of call/cc is genuinely confusing to understand! There’s a related construct that’s much more legible and has a much easier to understand: call with delimited continuation! Oleg K wrote a very articulate piece about this some long time ago https://okmij.org/ftp/continuations/against-callcc.html

I think of `call/cc` as a parlor trick that helps introduce the concept of continuations more generally.

Threads and co-routines are on the heavy-weight end of the concurrent programming techniques spectrum because they require stacks -possibly large, with guard pages and all- and encourage smearing application state onto that stack, increasing cache pressure.

Continuation passing style (CPS) is on the light-weight end because it encourages the programmer to make application state explicit and compact rather than smearing it on a stack. Callback hell is hand-coded continuation passing style (CPS). Async/await is a compromise that gets one close to the light weight of continuations.

To understand all of that one has to understand the concept of continuations. In computer science, the cheap parlor trick that is `call/cc` is helpful in introducing the concept of continuations to students. After all, `call/cc` is shocking when one first sees it, and the curious will want to understand it.

Re: What Does "With Continuation" Mean? (2020)

#20

Earlier quoted context omitted.

Continuations aren't equivalent to closures.

Continuations are closures. Closures aren't continuations. Though one can build continuations out of closures by converting code into continuation passing style, which makes continuations explicit, and then `call/cc` is trivial, since all it does is pass (to its function argument) its [now-explicit, after CPS conversion] continuation, thus reifying it.

Ehh. I think it makes it a lot harder to understand what a continuation is if you say they’re closures.

Continuations capture the stack. Closures capture variables.

Post reply on HN