Pathologically Eclectic Rubbish Lister 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

Replies are listed 'Best First'.
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

Create A New User
Node Status?
node history
Node Type: note [id://334306]
help
Chatterbox?
 [Corion]: A good daystart to everybody! [GrandFather]: It's a good day end here Corion. The start was somewhat less than average! [Corion]: GrandFather: All's well that ends well? ;) [GrandFather]: I'm fighting with a third party device our software is to support. The documentation for the device's SDK is quite a lot less than average and most of today was spent ... [GrandFather]: discovering that one of the sensors for the device lies about the gain range it is using! [GrandFather]: However, by the end of the day I had discovered its deceptions and now have it working correctly, so yes, all's well that ends well. :-D

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (6)
As of 2017-08-24 07:04 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (365 votes). Check out past polls.

Notices?