Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re: Pure Perl tail call optimization

by Limbic~Region (Chancellor)
on Mar 05, 2004 at 18:12 UTC ( #334306=note: print w/ replies, xml ) Need Help??


in reply to Pure Perl tail call optimization

pdcawley,
Eager to try my tail recursion, I tried your example and was bummed when it didn't work. I figured out that to make it work you had to do something like:

print tail_factorial(1, 8);
Where you had to supply an initial total for it to work. Here is a slightly modified version.
sub tail_factorial { my ($n, $total) = @_; $total = 1 if ! $total; return $total if ! $n; @_ = ($n - 1, $total * $n); goto &tail_factorial; }
To verify that it works I tested it for a value of 150 - no deep recursion errors - yeah. Thanks for the p6 weekly summaries too.

Cheers - L~R


Comment on Re: Pure Perl tail call optimization
Select or Download Code
Re: Re: Pure Perl tail call optimization
by demerphq (Chancellor) on Mar 09, 2004 at 19:48 UTC

    Your code is better written as

    sub loop_factorial { my ($n, $total) = @_; $total = 1 unless $total; while ($n) { ($n,$total) = ($n - 1, $total * $n); } return $total }

    Which is more efficient, and is IMO a better example of what a compiler that optimizes tail recursion would convert it to.


    ---
    demerphq

      First they ignore you, then they laugh at you, then they fight you, then you win.
      -- Gandhi


      demerphq,
      Sure - but then it would not be recursive anymore. That is an iterative solution. I wanted to play with avoiding the deep recursion limit by using tail recursion. This is pdcawley's code, not mine.

      Cheers - L~R

        Note to other monks: This sub thread starting with my original reply to L~R is a little bit out of context. The subject of tail optimization came up in the CB and L~R's post was referenced (by L~R) and I replied to follow up on a paoint from the CB. Sorry about that if it appears out of place.

        I think the important thing to remember is the the whole hype around "tail recursion" and is really about "optimized tail recursion" is due to a fundamental equivelency between a tail recursive subroutine and its iterative equivelent. Its a very useful equivelency for language designers because it means that you don't need to supply any form of iterative control structures explicitly if you provide for automatic transparent optimization of tail recursive routines. But in languages with rich loop constructs like Perl there isnt much need to exploit it.

        In short whenever I hear people talking about how wonderful it is that they have found another weird way to emulate the normal tail recursion optimization in Perl I get a bit disdainful. The language comes with such a tool built in and reinventing it in kludgy ways like with goto is IMO not particularly impressive.

        Having said that its a pity Perl doesnt automatically optimize tail recursion, as it can involve a notational elegance that can be quite useful. My understanding is it should be a failry straightforward optimization so I wonder why it is that it hasnt happened. It could be just simply lack of tuits to do an optimization that isnt really needed I guess but it would be interesting to know if there are deeper issues.


        ---
        demerphq

          First they ignore you, then they laugh at you, then they fight you, then you win.
          -- Gandhi


Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://334306]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (11)
As of 2014-09-30 15:14 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (375 votes), past polls