Continuations for fun and profit (fwd from perl6-language)

[Michel Rodriguez]

[Toulouse.pm]

[toulouse-pm]
Salut,

Bon, j'ai pas pense a l'epoque a forwarder le message de Dan sur le
"currying" (si je le retrouve je le ferais passer) mais je crois que des
posts comme ca ca vaut le coup d'y jeter un oeil, au moins pour se dire
que ya pas que for/while... comme structures de controle dans la vie. Et
non, ca n'est pas la meme chose qu'un GOTO.

Et puis comme ca Thierry B. pourra nous expliquer qu'il y avait la meme
chose en Fortran 1852 (qui est aussi l'annee de sa naissance!).

Michel


---------- Forwarded message ----------
Date: Mon, 8 Jul 2002 16:54:16 -0400
From: Dan Sugalski <dan at sidhe.org>
To: perl6-language at perl.org
Subject: Continuations for fun and profit

Okay, for those of you following along at home, here's a quick
rundown of what a continuation is, and how it works. (This is made
phenomenally easier by the fact that perl has continations--try
explaining this to someone used to allocating local variables on the
system stack and get ready for frustration)

A continuation is a sort of super-closure. Like a closure it captures
its lexical variables, so every time you use it, you're referring to
the same set of variables, which live on until the continuation's
destroyed. This works because the variables for a block are kept in a
scratchpad--since each block has its own, and each scratchpad's
mostly independent (mostly).

Now, imagine what would happen if the 'stack', which we track block
entries, exits, sub calls, and so forth, was *also* done with a
linked list of scratchpads, rather than as a real stack. You could
have a sort of "super closure" that both remembered all your
scratchpads *and* your spot in the call tree. That, essentially, is
what a continuation is. We remember the scratchpads with variables in
them *and* the scratchpads with stack information in them.

When we invoke a continuation, we put in place both the variables and
call scratchpads, making it, in effect, as if we'd never really left
the spot we took the continuation at. And, like normal closures, we
can do this from wherever we like in the program.

The nice thing about continuations is you can do all the known
control-flow operations (with perhaps the exception of a forward
goto) with them, and you can use them to build new control flow
structures. For example, let's take the "while" construct:

    while ($foo) {
      $foo--;
    }

Pretty simple. (For illustrative purposes) To do that with
continuations, it'd look like:

    $cont = take_continuation();
    if ($foo) {
      $foo--;
      invoke($cont);
    }

take_continuation() returns a continuation for the current point (or
it could return one for the start of the next statement--either
works), and invoke takes a continuation and invokes it. When you
invoke a continuation you put the call scratchpads and lexical
scratchpads back to the state they were when you took the
continuation.

Presto--instant while loop. You can do for loops in a similar way, as
well as any number of other control structures.
-- 
                                         Dan

--------------------------------------"it's like this"-------------------
Dan Sugalski                          even samurai
dan at sidhe.org                         have teddy bears and even
                                       teddy bears get drunk