Why Are Continuations So Confusing, and What Do They Really Do? | Hacker News Reader

Why Are Continuations So Confusing, and What Do They Really Do?

idea-log.blogspot.com

19 pointsmk18 comments

His hypothetical continuations don't quite work.

  theSite = mark();
  puts "Hello, World!"
  theSite.return();

This is the first example in the post, and one which it's claimed will loop continually. Translating to Scheme (where we can actually run the pseudo-code):

  (begin
    (define theSite #f)
    (set! theSite (call/cc (lambda (c) c)))
    (print "Hello, World!") (newline)
    (theSite #f))

And we get:

  > (begin
      (define theSite #f)
      (set! theSite (call/cc (lambda (c) c)))
      (print "Hello, World!") (newline)
      (theSite #f))
  "Hello, World!"
  "Hello, World!"
  procedure application: expected procedure, given: #f; arguments were: #f

This translation to Scheme seems fair, since the definition of mark() explicitly states that it "allows you to pass information back to the original site, so that it evaluates to a different value" -- which means that the return value of mark() itself is clearly significant, and therefore that the step of "set theSite to the result of evaluating the current form" is considered part of the continuation (or "mark").

In this case, theSite gets set to #f, and the continuation is then "broken".

It might seem tedious to nitpick here, but continuations are so mysterious exactly because of these issues. mark() _can't be fixed_ without drastically changing the semantics of continuations. This is kinda non-obvious, and something that people often discover suddenly when wondering why call/cc is implemented in such a roundabout fashion.

Continuations are confusing to point where even toy examples in pedagogical blog posts are easy to mess up.

Mark can be fixed; your translation is wrong.

What Scheme are you running this with? I tried your code in DrScheme, and it prints "Hello, World!" exactly once, with no error, no infinite loop. I'm not sure why, but I expect it has something to do with the semantics of "begin" (maybe a bug in DrScheme?); you can make the code work in DrScheme as you describe if you use "let" instead of "begin":

  (let ((cont #f)) 
    (set! cont (call/cc (lambda (k) k)))
    (print "Hello, world!")
    (cont #f))

You can get an infinite loop by changing where the variable is set:

  (let ((cont #f)) 
    (call/cc (lambda (k) (set! cont k)))
    (print "Hello, world!")
    (cont #f))

A few years ago, I woke up to my alarm, really groggy, and accidentally hit alarm off when I meant to hit the snooze button. Then I thought to myself, "I think I'll stay in bed for a few more minutes. I'll just remember my current continuation and if I oversleep I'll call it back with an error".

I overslept.

Coda: however, the professor whose class I missed the first 20 minutes of was a lisper, so he got a good laugh out of my excuse.

The following article is my functional programming bible. I always refer to it when things start to get a little hazy.

http://www.defmacro.org/ramblings/fp.html

If you read it (the continuations section) you will understand continuations. I stake my HN reputation on it (whatever that's worth).

The best way to understand continuations may be to think of them as copies of the stack.

does simulating state in http with continuations scale?

Yes, dabbledb.com runs on Seaside, a continuations-based web framework running on Squeak, and Avi Bryant has posted that they're very happy with their ability to support thousands of user sessions.

It would depend on how much you used them. In News.YC I try to avoid using even closures as much as I can. In the earliest versions I made practically every link on every page be a closure. The source is so simple that way. But keeping that many closures around (in case the user hits the back button a couple times then makes another choice) soon became unwieldy. You rapidly find you have a couple hundred thousand closures in memory. So now whenever I can conveniently get all the state I need into the arguments of a url, I do that.

You can see which links need to be closures by mousing over them. If the link looks like r?fnid=hashkey, it's a reference to a closure on the server. Usually it means there is something that has to be done after whatever the link does.

Though Arc has continuations, I haven't needed to use them anywhere in News yet (except for catch and throw, which is a degenerate case). Nothing has state that complicated.

Like the blog author, I found the traditional explanation incredibly confusing: "A continuation is the remaining work to be done". I, too, found the "copies of the stack" explanation much better.

The first problem I had was understanding that the "work remaining to be done" was not measured from the point of the call/cc statement, but just after, so it was really "the work remaining to be done once you get done with this next bit here, assuming you do." It was much easier for me to think of it as an instruction pointer saved to the stack, which points to the instruction to be executed on return, not the current instruction.

Likewise, I was confused by the idea that you could save a continuation so that you could call it again and again. "Why," I thought, "would you want to execute a continuation more than once if it is just going to return the same thing each time?" It turns out I was thinking in purely functional terms, and Scheme is not a purely functional language; if you allow for side-effects, a continuation can return a different thing each time. The "work remaining to be done" explanation misses the fact that a continuation captures the state of the code and some data, but it doesn't capture all data. The stack explanation explains precisely what data is saved by the continuation and what data is subject to side-effects.

Aha, but continuations are useful even without side effects. That's the beauty!

    (let ((p (call/cc (lambda (k) (cons 1 k)))))
      (print (car p))
      (if (< (car p) 10)
        ((cdr p) (cons (+ 1 (car p)) (cdr p)))
        'finished))

Can you understand what it does? No (set!) in sight!

Bonus:

    (define (mark initial)
      (call/cc (lambda (c)
                 (define (return value)
                   (c (cons value return)))
                 (cons initial return))))

(mark x) returns a pair of values. The car is x, the cdr is a (return) function. When you call (return y), the (mark x) call returns again, this time returning y instead of x. Here's an infinite loop example:

    (let ((pair (mark 1)))
        (let ((value (car pair)) (return (cdr pair))) ; unpack the pair
          (print value)
          (return (+ value 1)))) ; jump back to the (mark 1) call, this time returning value+1

Here's a Ruby implementation of mark:

    def mark(initial)
      callcc do |c| 
        ret = lambda{|value| c.call([value,ret])}
        [initial, ret]
      end
    end

(I used ret instead of return because return is a Ruby keyword)

Example in Ruby:

    value, ret = mark 1
    puts value
    ret.call(value + 1)

I found this explanation far more confusing than a good explanation of continuations (of which I've seen several). And giving them a new name is bad mojo.

I believe the brief description being derided in this article, "the remaining work to be done", would be fine if it included the important bit: state. As he rightly points out, the work isn't the important bit...it's the state of the work+data that matters in continuations, and I didn't find his explanation really made that as clear as several other tutorials out there. Comparing it to goto was particularly uncomfortable for me (because again, it's the state that matters...and goto is effectively stateless in this context, and has the same flaw as just saying "the remaining work to be done"). The key to continuations is that you pick up where you left off with all data (the stack, as pg points out) intact.

So, pg has it right, of course, but I'm not sure very many dynamic language developers really have a very good comprehension of "the stack".

Continuations don't save "state", so his explanation is entirely right. Also, the mark() and return() operations (which are like goto) do save the environment, unlike gotos. That's why you can return() back into a procedure. You can't goto back into a procedure (well, in assembly you can but your variables will be gone).

Environment is not state? I'm afraid we have different definitions of state, then.

State genererally means the state of mutable things. Invoking a continuation will not reset the things you mutated, it will only reset the variables to their memory locations (in fact it does not "reset", the variables are still there). It's the same as with a closure:

    (let ((x 2))
      (let ((closure (lambda () (print x))))
        (set! x 4)
        (closure))) ; prints 4 not 2

The closure doesn't remember the old value of x, it just remembers the memory location.

I never said anything about resetting variables, and in fact, I emphatically mentioned copying the stack by way of clarification. I'm surprised you would misinterpret me to be saying anything about resetting variables. I'll try to refrain from using "state" in the future, when speaking to someone that could be from a functional programming background, since it seems to be so easy to misinterpret as "variables". I wasn't aware anyone used the term "state" to mean "variables", but I come from a C-derived lineage, and may have missed that memo.

I'll also try to refrain from commenting in language weenie threads. It's not my forte.

This is a very out-of-fashion confusing concept on which to write tutorials in your blog! Monads are the new continuations. Try to keep up.

Reply on news.ycombinator.com