Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
Okay, you say that goto &SUB doesn't create a new stack frame, so let's test it shall we:
#!/usr/bin/perl -w my $method = shift or usage(); if($method eq 'tail'){ $0 = 'tail'; tail_inf(); } elsif($method eq 'nontail'){ $0 = 'nontail'; nontail_inf(); } else { usage(); } sub tail_inf{ L1: print_resources(); goto L2; L2: goto L1; } sub nontail_inf{ goto &T1; sub T1{ print_resources(); goto &T2; } sub T2{ goto &T1; } } { my $i=0; my $j=0; sub print_resources{ $i++; $i = $i % 100000; return unless $i == 0; my @lines = grep {$_ =~ /\s+(\d+)/ and $1 eq $$} `ps u`; print @lines; $j++; exit if $j == 10; } } sub usage{ print "Usage: $0 tail|nontail\n"; exit(-1); }
Run the code twice, one with tail as an arg, and one with nontail, here is what I get on Perl 5.6.1:
[334]: ./tail.pl tail abstract 5843 0.0 0.2 2324 1052 pts/0 S 01:00 0:00 tail abstract 5843 99.9 0.2 2328 1100 pts/0 S 01:00 0:01 tail abstract 5843 99.9 0.2 2328 1100 pts/0 S 01:00 0:01 tail abstract 5843 99.9 0.2 2328 1100 pts/0 S 01:00 0:02 tail abstract 5843 83.6 0.2 2328 1100 pts/0 S 01:00 0:02 tail abstract 5843 99.9 0.2 2328 1100 pts/0 S 01:00 0:03 tail abstract 5843 88.0 0.2 2328 1100 pts/0 S 01:00 0:03 tail abstract 5843 99.9 0.2 2328 1100 pts/0 S 01:00 0:04 tail abstract 5843 90.6 0.2 2328 1100 pts/0 S 01:00 0:04 tail abstract 5843 83.8 0.2 2328 1100 pts/0 S 01:00 0:05 tail [335]: ./tail.pl nontail abstract 5854 86.0 0.9 6300 5040 pts/0 S 01:00 0:00 nontail abstract 5854 85.5 1.7 10276 9056 pts/0 S 01:00 0:01 nontail abstract 5854 85.3 2.5 14244 13024 pts/0 S 01:00 0:02 nontail abstract 5854 85.7 3.3 18212 16996 pts/0 S 01:00 0:03 nontail abstract 5854 86.0 4.0 22184 20964 pts/0 S 01:00 0:04 nontail abstract 5854 85.8 4.8 26148 24928 pts/0 S 01:00 0:05 nontail abstract 5854 85.8 5.6 30116 28900 pts/0 S 01:00 0:06 nontail abstract 5854 85.7 6.3 34084 32868 pts/0 S 01:00 0:06 nontail abstract 5854 85.7 7.1 38056 36836 pts/0 S 01:00 0:07 nontail abstract 5854 85.9 7.9 42024 40808 pts/0 S 01:00 0:08 nontail
Clearly, the nontail calls (goto &SUB) creates new stack frames while the goto LABEL doesn't.

So, to *correctly* implement tail calls, I think goto &SUB is improper.

As for speed, and carrying this example, one can see that the tail call is faster than the nontail call:

[340]: time ./tail.pl tail > /dev/null real 0m6.079s user 0m5.450s sys 0m0.620s [341]: time ./tail.pl nontail > /dev/null real 0m10.423s user 0m9.530s sys 0m0.890s
However, in this example we have two functions calling each other, so perl might not optimize that.

As for using computed values for goto (ie goto "label value", you can do a jump table. Basically, you have a segment of the code that looks something like this:

SCM_BRANCH: if($br eq 'SCM_F1'){ goto SCM_F1; } elsif ($br eq 'SCM_F2'){ goto SCM_F2; } ... SCM_F1: # before doing a call, set $rv to where you wanna go # and pass the name of where you want to return as first arg # ie: call F2 with args $a,$b; @_ = ('RET1', $a, $b); $br = 'SCM_F2'; goto SCM_BRANCH; # here we go RET1: # here we return my @returned_vals = @_; ... $br = $rp; goto SCM_BRANCH;

Update: I agree with samtregar that the reason might not be a creation of a new stack frame. I don't know if this is by design or a bug. However, goto LABEL does not leak: it can run forever juggeling from label to another and *can* be used to create proper tail recursion.


In reply to Re: Re: Re: Pure Perl tail call optimization by abstracts
in thread Pure Perl tail call optimization by pdcawley

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others lurking in the Monastery: (10)
    As of 2014-12-19 10:24 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      Is guessing a good strategy for surviving in the IT business?





      Results (77 votes), past polls