(Semi-OT) Coroutine vs Continuation?

[BUU]

I've been doing some interesting reading over at Dan's blog and it has prompted a question, namely the one in the topic. Coroutines I'm pretty sure I understand, this example from Dan's What the heck is: a coroutine series seems to make it abundantly clear:

  coroutine foo {
    yield 1;
    yield 2;
    yield 3;
  }
  print foo(), "\n";
  print foo(), "\n";
  print foo(), "\n";
  print foo(), "\n";
  print foo(), "\n";
  print foo(), "\n";

prints

1
2
3
1
2
3

Thats nice and simple and I understand it. But what is the difference between this and a continuation? Dan's article on continuations makes mention of capturing the control stack and restoring it, but isn't that what a coroutine does?

[ikegami]

I found the following text in this doc

[Continuation Passing Style (CPS)] is a programming style where no function is ever allowed to return. A function "A" must emulate returning by passing its would-be-return value to a continuation function that was passed into "A" as an explicit parameter. Thus, all function calls are tail calls, which means, all function calls are instances of "goto with parameters."

What follows is my interpretation. Given the example program:

sub input    {                    ...; return $value;  }
sub process1 { my ($input ) = @_; ...; return $result; }
sub process2 { my ($input ) = @_; ...; return $result; }
sub output   { my ($result) = @_; ...;                 }

output(
   process1(
      process2(
         input()
      )
   )
);

Continuation style, it would look like:

sub input    { my (        $c) = @_; ...; &$c($value ); }
sub process1 { my ($input, $c) = @_; ...; &$c($result); }
sub process2 { my ($input, $c) = @_; ...; &$c($result); }
sub output   { my ($result   ) = @_; ...;               }

input(
   sub { process1(@_, 
      sub { process2(@_,
         \&output
      ) }
   ) }
);

Why oh why? A language and/or compiler designed to optimize function calls at the end of a sub into a goto would compile the above snippet into:

sub input    { my (        $c) = @_; ...; @_ = ($value ); goto(&$c); }
sub process1 { my ($input, $c) = @_; ...; @_ = ($result); goto(&$c); }
sub process2 { my ($input, $c) = @_; ...; @_ = ($result); goto(&$c); }
sub output   { my ($result   ) = @_; ...;                            }

input(
   sub { process1(@_, 
      sub { process2(@_,
         \&output
      ) }
   ) }
);

Update: It might even optimize it to the following. I'm deep into speculative waters, now.

goto line1;

input:    { my (        $c) = @_; ...; @_ = ($value ); goto($c); }
process1: { my ($input, $c) = @_; ...; @_ = ($result); goto($c); }
process2: { my ($input, $c) = @_; ...; @_ = ($result); goto($c); }
output:   { my ($result   ) = @_; ...;                           }

line1: { push(@_, 'line2'); goto input;    }
line2: { push(@_, 'line3'); goto process1; }
line3: { push(@_, 'line4'); goto process2; }
line4: {                    goto output;   }

Any why is that good? And what about loops and everything? I'm not exactly sure. And all that being said, I don't know how it relates to coroutines. But it was interesting to me, and I hope it helps you.

[BrowserUk]

From my (also limited) understanding, one of the benefits of the contnuation passing style is that exception handling can unwind back to any point in the call stack and continue (maybe hence the name?).

It also makes coroutines very easy to implement (I believe).

That said, there are easier, cheaper ways of achieving coroutines and implementing exception handling. The overhead in retaining snapshots of the stack at every level of continuation seems immense for very limited benefits to my eyes, but then as I said, my understanding is limited.

[Elian]

A coroutine looks exactly like a normal subroutine, and to the caller it behaves like one -- you invoke it, it does its thing, and returns some values. No continuations necessary (though they do make things easier) for them. A continuation's a somewhat more complex thing, though the fact that you can do coroutines with continuations (with some complications) makes things a bit fuzzy. I'll go into some detail on the differences at some point when I've got a bit of time.

[Thelonius]

Here's a discussion about generators, coroutines, and continuations with respect to Python. Dan's code above would be called a generator in Python (and I think that's really the standard terminology).

[Elian]

Both coroutine and generator are proper terminology. (They describe mostly the same thing, so I think generator was coined by someone unfamiliar with corotines) Generators are usually used only for simple things (iterators and such) and are normally very straightforward, and as such normally don't have a fully general coroutine implementation. Coroutines can be significantly more complex -- with proper back-end transformation you can implement a full pthreads-style threading system with coroutines, something you'd probably not want to do with generators.

[chb]

I think a coroutine manages and stores the state of a single function while a continuation is like a snapshot of your whole program, stack and everything.... but I might be horribly wrong.