Tail recursion optimisation considered possible

[demerphq]

A comment by one of my colleagues made me realize that now that we
have __SUB__ keyword we can do a limited form of
tail-recursion-optimization.

Basically if a subroutine qualifies as "tail recursive" we can check
to see if the __SUB__ points at the same function as the function
calls resolves to.

If they are the same we can avoid the stack manipulation and replace
the sub call by @_ munging and goto.

Yves


--
perl -Mre=debug -e "/just|another|perl|hacker/"

[Aaron Crane]

demerphq <deme...@gmail.com> wrote:
> Basically if a subroutine qualifies as "tail recursive" we can check
> to see if the __SUB__ points at the same function as the function
> calls resolves to.
>
> If they are the same we can avoid the stack manipulation and replace
> the sub call by @_ munging and goto.

Is there a way of doing that without breaking user expectations for caller()?

My suspicion is that Perl shouldn't apply any form of call-frame
merging without seeing an explicit indication (whether a pragma, or
use feature feature, or simply an additional/alternative return
builtin) that the programmer is happy for call frames to disappear
from what caller() sees.

However, given such an explicit indication, it seems to me that
comparing the resolved call target to __SUB__ would be an unnecessary
restriction on the scope of the optimisation — why not also permit
call-frame merging for a tail call to a different routine? For that
matter, __SUB__ isn't entirely free, so it's conceivable that having
every tail-position invocation compare the target routine with __SUB__
might turn out to be a net pessimisation for some programs.

--
Aaron Crane ** http://aaroncrane.co.uk/

[demerphq]

sub is_this_tail_recursive {

local *is_this_tail_recursive= sub { "move along this is not the
sub you are looking for" };

is_this_tail_recursive();

[Aaron Crane]

demerphq <deme...@gmail.com> wrote:
> sub is_this_tail_recursive {
> local *is_this_tail_recursive= sub { "move along this is not the
> sub you are looking for" };
> is_this_tail_recursive();
> }

Yes, that's just the sort of situation I meant — the fact that the
callee isn't the same as the current sub doesn't stop you deallocating
the current call frame before allocating the new one (or, put another
way, merging the new call frame into the current one without doing any
allocation).

(But the failure to preserve the user's expectations of how caller()
behaves in the callee *is* a reason to avoid the optimisation, as far
as I can tell.)

I personally avoid the term "tail-recursion optimisation", and this is
one of the reasons why: the optimisation isn't really anything to do
with recursive functions, only about calling one routine in the tail
position of another.

[David Golden]

On Fri, Jul 13, 2012 at 9:38 AM, Aaron Crane <pe...@aaroncrane.co.uk> wrote:
> My suspicion is that Perl shouldn't apply any form of call-frame
> merging without seeing an explicit indication (whether a pragma, or
> use feature feature, or simply an additional/alternative return
> builtin) that the programmer is happy for call frames to disappear
> from what caller() sees.

+1

-- David

[Jan Dubois]

On Fri, 13 Jul 2012, Aaron Crane wrote:
> My suspicion is that Perl shouldn't apply any form of call-frame
> merging without seeing an explicit indication (whether a pragma, or
> use feature feature, or simply an additional/alternative return
> builtin) that the programmer is happy for call frames to disappear
> from what caller() sees.

Don't we have that alternative return builtin already with:

@_ = (...);
goto &foo;

Or are you just talking about syntactic sugar to make this more
pleasant to read?

Cheers,
-Jan

[Jan Dubois]

On Fri, 13 Jul 2012, Jan Dubois wrote:
> On Fri, 13 Jul 2012, Aaron Crane wrote:
> Don't we have that alternative return builtin already with:
>
> @_ = (...);
> goto &foo;

I just tested it, and "goto &__SUB__" doesn't work:

Goto undefined subroutine &main::__SUB__ at /Users/jan/tmp/boom.pl line 9.

I guess it is a bug, as assigning it to a variable works:

$ cat ~/tmp/boom.pl
use 5.016;
use warnings;

sub countdown {
my $count = shift;
if ($count) {
say $count;
sleep 1;
@_ = ($count-1);
my $self = __SUB__;
goto &$self;
}
say "BOOM";
}

countdown 5;
$ perl ~/tmp/boom.pl
5
4
3
2
1
BOOM
$

Should I file a bug for "goto &__SUB__"? Or is this already fixed in blead
(I don't have a build right now to test).

Cheers,
-Jan

[Rev. Chip]

+1 ... I depend on the call stack for debugging. But if you can free
resources early from the call frames somehow since you know you're not going
back to one of the functions in it, that's great.
--
Chip Salzenberg

[Rev. Chip]

On Fri, Jul 13, 2012 at 11:08:54AM -0700, Jan Dubois wrote:
> On Fri, 13 Jul 2012, Jan Dubois wrote:
> > On Fri, 13 Jul 2012, Aaron Crane wrote:
> > Don't we have that alternative return builtin already with:
> >
> > @_ = (...);
> > goto &foo;
>
> I just tested it, and "goto &__SUB__" doesn't work:

But this does: "goto &{+__SUB__}". I think "goto __SUB__" ought to.
--
Chip Salzenberg

[Eirik Berg Hanssen]

On Fri, Jul 13, 2012 at 8:08 PM, Jan Dubois <ja...@activestate.com> wrote:

On Fri, 13 Jul 2012, Jan Dubois wrote:
> On Fri, 13 Jul 2012, Aaron Crane wrote:

> Don't we have that alternative return builtin already with:
>
>     @_ = (...);
>     goto &foo;

I just tested it, and "goto &__SUB__" doesn't work:

  Goto undefined subroutine &main::__SUB__ at /Users/jan/tmp/boom.pl line 9.

 

Should I file a bug for "goto &__SUB__"?  Or is this already fixed in blead

(I don't have a build right now to test).

  Nope.

  First, it's CORE::__SUB__, not main::__SUB__.

  Second, you don't want to goto &CORE::__SUB__.  (It'll just complain you're passing too many arguments, here.)  You want to call CORE::__SUB__ to get the sub to which you want to goto:  goto &{+__SUB__}.  Or, more completely:

sidhekin@pinklady[23:30:49]~$ /opt/perl-blead/bin/perl5.17.2

use 5.016;
use warnings;

sub countdown {
    my $count = shift;
    if ($count) {
        say $count;
        sleep 1;
        @_ = ($count-1);

        goto &{+__SUB__}
    }
    say "BOOM";
}

countdown(3);

__END__
3
2
1
BOOM
sidhekin@pinklady[23:30:56]~$


Eirik

[Eirik Berg Hanssen]

  What do you know – it does:

sidhekin@pinklady[00:19:50]~$ /opt/perl-blead/bin/perl5.17.2

use 5.016;
use warnings;

sub countdown {
    my $count = shift;
    if ($count) {
        say $count;
        sleep 1;
        @_ = ($count-1);

        goto __SUB__

    }
    say "BOOM";
}

countdown(3);

__END__
3
2
1
BOOM

sidhekin@pinklady[00:19:56]~$ 


  Nope, wasn't expecting that.  But now I see it, I like it. :)


Eirik

[Paul LeoNerd Evans]

https://metacpan.org/module/Sub::Call::Tail

--
Paul "LeoNerd" Evans

leo...@leonerd.org.uk
ICQ# 4135350 | Registered Linux# 179460
http://www.leonerd.org.uk/

[Zefram]

demerphq wrote:
>If they are the same we can avoid the stack manipulation and replace
>the sub call by @_ munging and goto.

Many Perl idioms rely on strict stack discipline. For example,
implementing cleanup code as the destructor of an object held in a
lexical variable in a particular stack frame. The result is that
implicit tail-call optimisation would break all sorts of things.
Hence tail-call semantics are only safe to invoke *explicitly*, which
is what Sub::Call::Tail provides.

The case where the caller and callee happen to be the same sub is not
special from this point of view. Any change to the stack discipline
would break reasonable code.

-zefram