in reply to Re: Pure Perl tail call optimization
in thread Pure Perl tail call optimization

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
}

[download]

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

Replies are listed 'Best First'.
Re: Re: Re: Pure Perl tail call optimization
by Limbic~Region (Chancellor) on Mar 09, 2004 at 19:51 UTC
    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

[reply]

      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
[reply]
[d/l]
        The deeper issue that always comes up is that tail-recursion would make caller give very different results. Which is a lot of fun when you are trying to debug a complex call. (Carp depends on caller for its output.)

        Another subtle change is different destruction mechanics. In order to do tail-recursion, you have to clean-up your current variables, etc. With reliable destruction mechanics, this may cause interesting surprises. For instance consider the technique at •Re: sub and anonymous sub. Or consider ReleaseAction. Their behaviour changes. It already changes with goto, but at least there is an easily explained cause for the change. If it is done behind the programmer's back, how do you address the confusion?

        I should also note that writing recursive routines that automatically perform iteratively makes more sense in Scheme where function calls are very cheap. When they are relatively expensive (as they are in Perl), the coolness isn't quite as compelling...

[reply]
        You'll note that the original subject was 'Tail call optimization' not 'Tail recursion optimization'. Tail call optimization comes in handy even when you're not recursing. It comes in handy when you're using lots of simple methods that simply return the results of a simple function call 
        package LeafNode;
...
sub accept {
    my($self, $visitor) = @_;
    $visitor->visit_leaf($self);
}

        [download]
        When you have tail call optimization in place, visit_leaf can return directly to accept's caller('s caller's caller's ...). Even without recursion, this can be a win because stack frames can be costly to create.
[reply]
[d/l]
[select]

In Section Meditations