You use continuations to turn call-backs into iterators.

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.

Read more... (1127 Bytes)

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); });
}
[download]


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

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";
[download]

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.

—John

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.
[download]

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.

Paul Graham also have a set of pdf slides about continuations with the scheme language.

-- stefp


---

Come to YAPC::Europe 2003 in Paris, 23-25 July 2003.

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.
[download]

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).

—John