in reply to Tail Recursion in Perl

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.

Replies are listed 'Best First'.
Re: Re: Tail Recursion in Perl
by dragonchild (Archbishop) on Dec 31, 2003 at 19:23 UTC
    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);

      [download]

      This produces the following output: 

      recursing
Deep recursion on subroutine "main::recurse" at /tmp/p line 7.
tailless_recursing

      [download]

      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]
Re: Re: Tail Recursion in Perl
by stvn (Monsignor) on Jan 01, 2004 at 01:42 UTC

    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);

      [download]
      ...into the proper goto syntax.
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom