Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change

Re: Re: Re: (Perl6) Groking Continuations (iterators)

by oylee (Pilgrim)
on Apr 08, 2003 at 23:17 UTC ( #249118=note: print w/replies, xml ) Need Help??

in reply to Re: Re: (Perl6) Groking Continuations (iterators)
in thread (Perl6) Groking Continuations

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.

Replies are listed 'Best First'.
Re^4: (Perl6) Groking Continuations (iterators)
by Anonymous Monk on Oct 23, 2010 at 04:58 UTC
    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; }

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://249118]
[1nickt]: Wow. I had heard about the chips on HP cartriddges but not that issue. I rejected HP's equivalent laptop becuase of build quality, very plasticky keyboard. And I believe HP is the champon of bloatware, too.
[stevieb]: Perhaps my experience with HP is a bit different as I always bought the highest end models through business.
[Corion]: 1nickt: At least the machines that $work is introducing to replace the Lenovo T60 here do not inspire confidence with me

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (14)
As of 2017-03-27 13:29 GMT
Find Nodes?
    Voting Booth?
    Should Pluto Get Its Planethood Back?

    Results (320 votes). Check out past polls.