|
Re: Tail Recursion in Perl
by LunaticLeo (Scribe) on Dec 31, 2003 at 17:31 UTC
|
Perl has tail recursion. It is called goto &traverse_rec. See perldoc -f goto.
Excerpt:
The "goto &NAME" form is quite different from the other forms
of "goto". In fact, it isn’t a goto in the normal sense at
all, and doesn’t have the stigma associated with other gotos.
Instead, it exits the current subroutine (losing any changes
set by local()) and immediately calls in its place the named
subroutine using the current value of @_. This is used by
"AUTOLOAD" subroutines that wish to load another subroutine and
then pretend that the other subroutine had been called in the
first place (except that any modifications to @_ in the current
subroutine are propagated to the other subroutine.) After the
"goto", not even "caller" will be able to tell that this rou-
tine was called first.
| [reply]
[d/l]
[select] |
|
|
I'm going to play newbie and ask you for an example of how you think goto &traverse_rec; is tail-recursive.
------
We are the carpenters and bricklayers of the Information Age.
Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.
| [reply]
[d/l] |
|
|
> I'm going to play newbie and ask you for an example of how you think goto &traverse_rec; is tail-recursive.
use warnings;
sub recurse {
my $i = shift;
return if $i == 0;
recurse($i-1);
}
sub tailless_recurse {
my $i = shift;
return if $i == 0;
@_ = ($i-1);
goto &tailless_recurse;
}
print "recursing\n";
recurse(200);
print "tailless_recursing\n";
tailless_recurse(200);
This produces the following output:
recursing
Deep recursion on subroutine "main::recurse" at /tmp/p line 7.
tailless_recursing
Note that the second one doesn't produce the deep recursion warning. | [reply]
[d/l]
[select] |
|
|
Tail recursion refers to a function call being completely replaced on the stack by the next function it calls. Therefor when you recurse with a tail call your stack doesn't get deeper and deeper and deeper.
This is the feature that goto &tail_call provides in perl's runtime environment.
BTW, I totally aggree with the carpenter and bricklayer comment. :)
| [reply]
[d/l] |
|
|
| [reply] |
|
|
While "goto &sub" is an interesting way to go about this, the cautiousness/conciousness needed in the twiddling of @_, and the oddity of its syntax are not what I am looking for.
I would like to find a way to do this without any actual programmer intervention. Maybe through some kind of post-compilation op-code manipulation. The more I read about the B & Opcode modules and such, it seems like it might be way to complex.
I cooked up a module a while back (after reading a book ML and a few on Erlang), while in some ways it belongs in the obsfucated code section of this site more than anywhere else, I was happy with its (sorta) simplicity/purity of design. While I have never benchmarked it, I know it would never hold up in production.
-stvn
| [reply] |
|
|
| [reply] |
|
|
While "goto &sub" is an interesting way to go about this, the cautiousness/conciousness needed in the twiddling of @_, and the oddity of its syntax are not what I am looking for.
If a change in the "goto &sub" syntax would meet your requirements, you might have a look at source filters (see also Filter::Simple). At first glance it doesn't seem like it should be too hard to make a macro (call it tail_return) which transforms something like...
tail_return sub(a,b,c);
...into the proper goto syntax.
| [reply]
[d/l]
[select] |
Re: Tail Recursion in Perl
by tilly (Archbishop) on Dec 31, 2003 at 21:10 UTC
|
You can think of the overhead of recursion as either useless overhead or useful debugging information. As soon as someone implements tail recursion optimization, the output of caller becomes massively more confusing. If you further add the complexity of continuations, good luck producing something resembling a stack backtrace which is both accurate and comprehensible.
Personally I tend not to think of the overhead of recursion. If the algorithm is more clearly coded for me recursively, I just do it and worry about optimization later if I need to. (Later usually doesn't come.)
| [reply] |
|
|
| [reply] |
Re: Tail Recursion in Perl
by Elian (Parson) on Dec 31, 2003 at 21:29 UTC
|
Note that the functionality of stackless python's been in perl 5 since the very beginning -- perl 5 is already stackless in the 'stackless python' sense. The recursion limit is entirely arbitrary, and could be changed or removed if you want. It's only in there now under the assumption that when things get that recursive it's an error, which you could, if you wanted, change. | [reply] |
|
|
Interesting.
Pray tell, how could you change it? (The recursion limit that is)
And you say that perl is stackless in the 'stackless python' sense, so am I to assume that Perl's stack is not tied to the 'C' stack?
I suppose too that stackless python maybe wasnt the best example since its unlimited recursion does not mean 'efficient' recursion.
-stvn
| [reply] |
|
|
Pray tell, how could you change it? (The recursion limit that is)
You don't change it - it's already infinite (well, up to the size of available virtual memory.) Of course, there's a warning you usually get when the recursion gets 100 deep, but that can be turned off with no warnings;
And you say that perl is stackless in the 'stackless python' sense, so am I to assume that Perl's stack is not tied to the 'C' stack?
Correct. There are a few things in Perl that can blow the C stack (such as certain pathological regexes), but mostly you're only limited by available memory.
Dave M
| [reply] |
Re: Tail Recursion in Perl
by hardburn (Abbot) on Dec 31, 2003 at 17:02 UTC
|
I haven't dug very deep myself, but I've heard that tail recursion is a lost cause in Perl5. It's one of those things that we'll have to wait for Perl6 to get.
If you're intrested in internals, search around for Parret. It's what Perl6 will run on, but porting other languages to it is an explicit goal (unlike the Java VM), and supports some really cool stuff from functional programming (unlike .NET).
----
I wanted to explore how Perl's closures can be manipulated, and ended up creating an object system by accident.
-- Schemer
: () { :|:& };:
Note: All code is untested, unless otherwise stated
| [reply]
[d/l] |
|
|
| [reply] |
Re: Tail Recursion in Perl
by belg4mit (Prior) on Jan 01, 2004 at 06:17 UTC
|
| [reply] |
Re: Tail Recursion in Perl
by Zed_Lopez (Chaplain) on Jan 01, 2004 at 18:57 UTC
|
I wanted to note that some recursive functions can be made reasonably efficient through the use of memoization, which the Memoize module makes trivial to do.
| [reply] |
Re: Tail Recursion in Perl
by oha (Friar) on Jan 03, 2004 at 14:20 UTC
|
if i remember well, tail recursion is automatically used by compilers when optimizing. At least some C compiler should. | [reply] |
|
|
Yes, that is exactly what i am thinking, using Perl to manipulate the op-code tree in the CHECK stage of the compilation process. The more I look, the less i think its possible. I guess I will have to wait for Perl 6.
-stvn
| [reply] |
Re: Tail Recursion in Perl
by BrowserUk (Patriarch) on Dec 31, 2003 at 22:26 UTC
|
Update: Ignore this post! This was true the last time I benchmarked this, but in a quick test I just did, it is not the case. Either my benchmark was crap last time, or something changed in the interpreter to speed this up. Or my memory is failing me (again).
Whilst using the special form of goto reduces the stack consumption of recursion, be aware that it is done at the penalty of speed.
If memory is the limiting factor in your application, it is a fair trade to make. But if you are hoping to improve the performance, implementing tail recursion this way will not do that.
Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
Hooray!
| [reply] |
