Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses

(Perl6) Groking Continuations

by crenz (Priest)
on Apr 08, 2003 at 14:24 UTC ( [id://248935] : perlquestion . print w/replies, xml ) Need Help??

crenz has asked for the wisdom of the Perl Monks concerning the following question:

I've been reading Dan Sugalski's excellent blog "Squawks of the Parrot. He talks about continuations in two articles (1, 2), and it is an interesting read, but I have to confess I still don't understand them. Then I super-searched and found Perl and Prolog and Continuations... oh my!, with some sample code using continuations right at the beginning. That helped me to see the light a bit, but not too much.

Can somebody provide some code samples of what continuations are and what you would want to use them for? Thanks for excusing my ignorance :)

Replies are listed 'Best First'.
Re: (Perl6) Groking Continuations (iterators)
by tye (Sage) on Apr 08, 2003 at 16:29 UTC

    You use continuations to turn call-backs into iterators.

                    - tye

      Or you use closures to turn call-backs into iterators. Here I've altered the API a smidge because the original code used chdir() during the loop which is probably an unexpected side-effect. For anyone that is interested - Dominus is writing an excellent book on iterators and it includes a section on transforming recursive calls somewhat thusly. Here's a link to the book's web page (which you must all now go out and buy (when it is published)).

      BTW - this doesn't explain continuations at all - I'm just presenting a different perl5-accessible solution to the problem that tye posed.

        Actually, this does have to do with continuations, or at least the notion of CPS (continuation-passing-style). The basic idea of CPS is to turn all non-tail recursive calls to tail calls (which is equivalent to iteration) by explicitly managing your stack. This is done by adding an additional parameter that represents the explicit continuation. The end result is that your heap allocation grows larger, but at least you won't blow up the call stack due to all those non-tail recursive calls _if_ the language you're working in 'properly' handles tail calls.
        For example, a version of factorial that becomes deeply recursive:
        sub fact { my $num = shift; return 1 unless ($num); return $num * fact($num - 1); } sub tail_fact { my ($num, $k) = @_; return $k->(1) unless ($num); return tail_fact($num - 1, sub { return $num * $k->(shift); }); }

        Here we're manually representing the rest of the computation (the continuation) as an anonymous sub that keeps growing and growing... of course, the other alternative is to just represent the actual number we've accumulated thus far, but then that'd just be accumulator-passing-style.
        Of course, none of this really matters since Perl doesn't handle tail calls properly. It'll still warn you that a "Deep recursion on xxx" unless you change it to a strictly iterative version using while or for or one of those guys.

        You've managed to lose another side effect. With your version, I can't use -x _ to see if the file that the iterator just handed to me is executable. I'd have to do another stat rather than using the results of the lstat that Perl so helpfully caches for me.

        So you compressed all of the different items from the stack into two stacks that you keep handy using a closure (rather than a more tradition Perl object). I like it.

        I agree that the chdir side-effect is problematic. Too bad Unix didn't provide an efficient way to save/restore chdir context (based on i-node instead of on a path string). I'd make the chdir optional with appropriate disclaimers in the documentation but that defeats the purpose of providing a simple example.

        I think I'll try this technique on File::KGlob::unbrac (well, using a closure would be cheating since those subroutines are still Perl4-compatible code, though). (:

        Thanks for the demonstration.

                        - tye
Re: (Perl6) Groking Continuations
by Elian (Parson) on Apr 08, 2003 at 14:35 UTC
    I've had other requests for clarification, so after I finish my rant on the inefficiencies of polling for index.rdf files, I'll try and put one together. (Though that shouldn't stop anyone from putting together a good explanation!)
Re: (Perl6) Groking Continuations
by andrewc (Acolyte) on Apr 08, 2003 at 17:14 UTC

    Well, I can't claim to great knowledge on this, but I'll give it a go. Schemers out there will probably laugh their heads off.

    Essentially, a continuation is the abstract notion of "what do do next".

    You could fake Scheme's call-cc behaviour in Perl using an eval-BLOCK/if($@){} combo. The trick is distinguishing our fake death from a real thrown error:

    sub call_cc (&) { my $clause = shift; my @fake_returns; my $fake_continuation; $fake_continuation = sub { @fake_returns = @_; die $fake_continuation; }; eval { return $clause->($fake_continuation); }; if ($@) { die $@ unless $@ == $fake_continuation; return @fake_returns; } #NOTREACHED } print STDERR call_cc { my $fred = shift; $fred->(42); return 64; # NOTREACHED }; print STDERR "\n";

    But no, it's not a real continuation.

      Hmm, I think that's basically a try/catch mechanism. That is, call_cc gives you a block which includes fred. Calling fred will pop out of the whole call_cc block, even if fred was called by a subroutine deeply nested in the calling sequence. That is, it generates a "throw" keyword for you that's specific to this "try" scope. The argument to fred is used to signal exception data back to the point after call_cc, which can use that to distinguish success from failure.


        Is the right answer. It's not a real continuation because squirreling away a copy of the sub-reference $fred in, say, a package-global variable $Jane and calling $Jane later doesn't do what a real call-cc would allow you to do.

        use vars qw{$Jane}; print call_cc { my $fred = shift; $Jane = $fred; # Squirrel away a reference $fred->(42); 64; #NOTREACHED }; print "\n"; # And then call it later, outside the call_cc block... $Jane->(101); #bang.

        Results in... you guessed it, an uncaught exception. So it's just an ersatz call-cc.

        Funnily enough, call-cc is used in Scheme-like languages a lot for early exits from deep/non-deterministic recursions despite also having a try/catch-style mechanism.

Re: (Perl6) Groking Continuations
by shotgunefx (Parson) on Apr 08, 2003 at 19:50 UTC
    One explaination that I found helpufl was from Paul Graham

    "In implementors' terms, a continuation is basically a program counter and a copy of the stack. You can invoke it like a function, and you're back where you were when the continuation was made. So you can return multiple times out the same code.

    It's not bad form to use the same continuation more than once. That happens when you use continuations to do nondeterministic search, for example.

    Another thing continuations are useful for is server-based apps, strangely enough. We used them extensively in Viaweb to fake subroutine-like behavior, though because we were using CL rather than Scheme we used fake continuations made out of closures."


    "To be civilized is to deny one's nature."
Re: (Perl6) Groking Continuations
by zby (Vicar) on Apr 08, 2003 at 16:58 UTC
    For the same reason as you I have recently tried to revived my memories of continuations with this book: Semantics with Applications(it's downloadable). But that's the hard way for sure.
Re: (Perl6) Groking Continuations
by John M. Dlugosz (Monsignor) on Apr 10, 2003 at 17:52 UTC
    The interesting part about Perl and Prolog and Continuations... oh my! is that the variables are put back to what they were after performing the continuation.

    That is, given two constructs x and y, imply x, y, xx where xx is implicit in x and is to be done after y. This is straightforward if y is a closure passed to a function x.

    But here is an idea to help eliminate so many (nested) closures.

    Have the Unify leave behind an object that goes out of scope to perform xx. As a first cut, that would look like this:

    { # extra scope (my $nameless= unify ($var, "frank")) && print "This is done if var unified with frank."; } # unbinding takes place here.
    It still needs too much extra syntax, but the point is that you don't need a closure, and can easily have more than one thing to do inside the scope of the unification, and don't need an exception to indicate success/failure and get back to ordinary procedural code.

    In Perl 6, the DESTROY can't be relied upon to be called at the close brace, but a function can add exit actions to the callers scope so that works just as well and avoids the need for $nameless and extra parens.

    In C++, which doesn't have closures, you can't declare the variable inside the parens but you don't need to give it a name either if the actions are joined together with commas or &&'s, since a temporary will be destructed at the end of the complete statement containing it.

    In C#, there is no mechanism for prompt destruction actions to be called. The scoped lock is built-in and a similar mechanism can't be written within the language (a symptom that it's incomplete).