in reply to (Perl6) Groking Continuations

You use continuations to turn call-backs into iterators.

Oh, you wanted more of an explanation than that? Hmm. Okay.

First, you need to understand why call-backs suck and iterators are better so read Re: Are you looking at XML processing the right way? (merge).

Now, why is a call-backs API easier to provide? Well, for once thing, you can use recursion. Take something like File::Find. Let's make one that is extremely simple:

sub find { my( $callback, $subdir, $path )= @_; $path= "" if ! defined $path; $path .= "/" if "" ne $path; $path .= $subdir; chdir $subdir or die "Can't chdir($path): $!\n"; my @files= ( glob(".*"), glob("*") ); for my $file ( @files ) { next if $file eq "." or $file eq ".."; if( ! -l $file && -d _ ) { find( $callback, $file, $path ); } $callback->( $file, $path ); } chdir("..") or die "Can't chdir out of $path: $!\n"; }
and now let's turn it into an iterator:
sub find { my( $subdir, $path )= @_; $path= "" if ! defined $path; $path .= "/" if "" ne $path; $path .= $subdir; chdir $subdir or die "Can't chdir($path): $!\n"; my @files= ( glob(".*"), glob("*") ); for my $file ( @files ) { next if $file eq "." or $file eq ".."; if( ! -l $file && -d _ ) { find( $file, $path ); } RETURN( $file, $path ); } chdir("..") or die "Can't chdir out of $path: $!\n"; }
Do you see the problem? Here I am N layers deep in recursion with lots of interesting stuff in N instances each of @files, $path, $subdir, and whatever my for loop uses to keep track of where it is, and I want to return! I not only want to return all the way up my N layers of recursion, but I want to be able to come back right where I left off with my whole call stack just the way I left it so I continue right where I left off.

Well that is what continuations let you do (so I've heard, I haven't really studied them so I could well be wrong, but if so, someone will point this out and I'll learn something).

You can certainly turn the above code into an iterator without continuations, but it means getting rid of the recursion by implementing your own stack and stuffing that into some context container that the caller has to give back to you some way (usually via OO).

                - tye

Replies are listed 'Best First'.
Re: Re: (Perl6) Groking Continuations (iterators)
by diotalevi (Canon) on Apr 08, 2003 at 20:54 UTC

    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.

        Perl can do something that closely resembles an optimized tail call, but it only does so if you tell it to.
        sub tail_fact { my ($num, $k) = @_; return $k->(1) unless ($num); @_ = ($num - 1, sub { return $num * $k->(shift); }); goto &tail_fact; }

      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
        Says tye:
        Too bad Unix didn't provide an efficient way to save/restore chdir context (based on i-node instead of on a path string).

        Many unixes now provide an fchdir call which does what you want; instead of a pathname, it accepts an open file descriptor and then sets the cwd to the directory pointed to by the descriptor. To save the old cwd, you simply open the current directory. After you've done chdir, you can fchdir to the descriptor returned by the open when you want to go back.

        You can't have a system call that simply accepts an i-number, because such a call would bypass the filesystem's permission controls.

        Mark Dominus
        Perl Paraphernalia