Comment by sillysaurus3 | Hacker News Reader

Comment by sillysaurus3 | Hacker News Reader

It took a long time to grok continuations. There's an easy way to explain what they are:

Imagine running a program in a VM. You know how you can take a snapshot and then restore to it later? That snapshot is equivalent to a continuation.

Another way of phrasing it is, it's your program frozen in time. You can snapshot your program and restore to that point later.

To put it technically, step through each call stack frame, serialize all the local variables, and you have yourself a continuation. To invoke it, call those functions in order and set the local variables to those values, then set the program counter to wherever it was. (You don't literally do this, but maybe that makes it easier to understand what's going on with it.)

The confusion: What about a database connection? Or a network connection of any kind? An open file handle? Etc. The answer is that those things can't be saved in a continuation.

The way that this works in Scheme is that there's a special primitive called "dynamic wind". It takes three callback functions: "before", "during", and "after". It invokes those callback functions in order. If execution leaves "during" for any reason whatsoever, then "after" is invoked.

Here's the kicker: If execution goes back into "during", then "before" is invoked. I.e. if you save a continuation inside "during," then "before" is the place that you'd put the code to re-initiate a database connection or re-open a file handle. Or fail.

And of course, no discussion of continuations would be complete without the argument for why call/cc is generally an anti-pattern: http://okmij.org/ftp/continuations/against-callcc.html

Yet "On Lisp" presents several interesting ways to use them, and they are extremely powerful. One particular use is that you can implement cut, fail, and mark for non-deterministic backtracking. If you've used emacs lisp and you've ever written an edebug specification for how to debug a macro (https://www.gnu.org/software/emacs/manual/html_node/elisp/Sp...), some of the more complex features require backtracking: https://github.com/emacs-mirror/emacs/blob/0648edf3e05e224ee...

That's an area where continuations really shine, because the implementation can be just a few dozen lines compared to hundreds.

(elisp doesn't actually use continuations -- this is just an example of the territory they're useful in.)

Another example of the power and usefulness of continuations comes from pg, who wrote years ago that a key reason why Viaweb was routinely able to launch new features faster than the competition back in the 1990's is because they wrote their code in continuation-passing style -- they were generating closures on the fly that would be called when users clicked on specific links on web pages, whereas the competition was using HTML pages with CGI scripts:

http://ep.yimg.com/ty/cdn/paulgraham/bbnexcerpts.txt

It's worth noting that the argument against call/cc is specifically against undelimited continuations. Delimited continuations, such as those created by the `shift` and `reset` control operators, do not suffer from the problems of call/cc.

Do you find this explanation better or worse than the one that uses shift/reset and expressions with holes in them?

I think everyone learns differently, and personally I'm a fan of the shotgun method: just explain it ten different ways till one of them clicks.

I'm not OP, but my functional teacher (Matthew Flatt) taught continuations using the "holes". I really didn't get it at first; it was just a little too abstract for me.

He had us implementing an interpreter, and step-by-step we were adding more features. Eventually we added continuations (building a CEK machine). It wasn't until I actually used the interpreter and played with it after finishing the homework that continuations started to make sense.

But they really solidified for me a year later when I took a course in operational semantics from him. We walked through the evolution of semantics in various languages through history, and had to write out the evaluations of expressions step-by-step (by hand, on paper). Then continuations really made sense.

> Imagine running a program in a VM. You know how you can take a snapshot and then restore to it later? That snapshot is equivalent to a continuation.

More or less, but a continuation really only captures the PC and the stack, not the entire state of the system.

When discussing call/cc with friends, I like to liken it to Tracer's Recall ability from Overwatch, which rewinds Tracer's state -- including location, health, and ammo -- to a point in the past, while leaving everybody else's alone.

The only place I've ever used 'call/cc' is in a theorem prover I'm working on, where it's been essential. Interestingly, delimited continuations don't work for what I'm doing; I need classical undelimited continuations.

> It takes three callback functions: "before", "during", and "after".

Does this remind anyone of MonadBaseControl from the Haskell package monad-control?

So continuations are like the yield statement? They are basically a state machine?

Or are they like tail calls?

Well, neither. It's sort of like a yield statement for the whole stack. But that metaphor is more confusing than helpful.

It basically just saves the whole call stack and lets you restore exactly that stack anytime you want. So it's like a longjmp, but also "jumps" to whatever function return chain was in progress at the time the continuation was saved.

If it seems weird, it is. But with weirdness comes power.

Yeah, this is wrong. continuations close over the heap. set! will have visible effects.

---------- original -----------

They save the state of your whole program. It's just like a checkpoint in a video game. (call/cc try-the-left-door) is like doing a quick save before doing something crazy.

Say you've got a big complicated data structure, and you need to make a bunch of destructive changes to it like a stack of 3d model transformations. You have a user sitting there watching a progress bar fill up. One approach is to just go for it, and make the changes. If the user clicks cancel, you have to undo all the work you've done so far.

Another approach is to deep copy the structure, and do your changes on the copy. If the user clicks cancel, you just throw away the modified copy.

the call/cc approach let's you skip doing the whole copy manually. The underlying system will save the state of your whole program, so you can change whatever you want. If the user clicks cancel, you call/cc and it'll restore the state of your program.

Perhaps you have two libraries. in a very dynamic language like ruby, you could call/cc, load up a library, monkey patch it, use it, see it didn't parse the way you wanted it to, and then call the continuation. You jump back to your last save point. It's as though you never loaded or modified the library, and then try the other library.

they get weird, because after you tried that first library, but before you gave up, you could take another quicksave of your program from that point. you can have as many save points as you want. so you try out the second library, decide to try one more thing back in the world where you'd tried out the first approach.

It's kinda sorta like, if some of your character's inventory was preserved across saves. save the game, go down the left hall and get the key. load the game go down the right hall and use the key (because you get to keep some things across savepoints). save again and grab the mystic idol. load up that first save, and use the idol.

They're really really neat. they're not really tricky, but you kind of have to know everything your program is doing.

Well, a call/cc saves the stack, but not the state. (My "VM snapshot" explanation was very bad in this regard.) If you allocate some memory and set it to a value, then save a continuation and change that value, it won't rewind to the old value when you invoke the continuation since the value isn't a part of the stack.

Your points are true if you save that complicated data structure as local variables on the stack, though.

Sounds extremely dangerous/volatile, honestly.

In what way specifically? Setjmp and longjmp have been in the C standard library forever. How do you think exception handling is implemented?

While 'setjmp' does capture something like a continuation, it's not a full firstclass continuation because it can't be invoked more than once.

A very good explanation.

See these two in order:

// source: https://en.wikipedia.org/wiki/Call-with-current-continuation

Criticism: Oleg Kiselyov, author of a delimited continuation implementation for OCaml and designer of an API for delimited stack manipulation for the implementation of control operators, advocates the use of delimited continuations instead of the full-stack continuations that call/cc manipulates: "Offering call/cc as a core control feature in terms of which all other control facilities should be implemented turns out a bad idea. Performance, memory and resource leaks, ease of implementation, ease of use, ease of reasoning all argue against call/cc"[3]

Delimited Continuation: https://en.wikipedia.org/wiki/Delimited_continuation

Reply on news.ycombinator.com