Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

Re: Pure Perl tail call optimization

by abstracts (Hermit)
on Apr 25, 2002 at 22:14 UTC ( #162119=note: print w/ replies, xml ) Need Help??


in reply to Pure Perl tail call optimization

Hello,

In order to use goto to obtain true tail recursion, you need to use goto LABEL and not goto SUB because the later does just what the regular call does. Here is one way how you might do your factorial example:

printf "10 factorial is %d", scheme_procs('factorial', 1, 10); my $ls = mklist(1,5,5,7,3,6); # make a list print pair_str($ls) . "\n"; # print it my $max = scheme_procs('max', $ls); # get the max printf "Max is $max\n"; #pair_push($ls,$ls); # make a circular list!! # now do the bad thing, never terminate but monitor # memory usage #$max = scheme_procs('max', $ls); # get the max #printf "Max is $max\n"; ################################################### # call scheme_procs(proc name, args); ################################################### sub scheme_procs{ my $proc = shift; if($proc eq 'max'){ # go to the correct label goto SCM_MAX; } elsif($proc eq 'factorial'){ goto SCM_FACTORIAL; } else { die "no such proc: $proc"; } SCHEME_RP: # return the return values if(wantarray){ return(@_); } else { return $_[0]; } SCM_FACTORIAL: my ($total,$n) = @_; if($n == 0){ @_ = ($total); goto SCHEME_RP; # return } else { @_ = ($total*$n, $n - 1); goto SCM_FACTORIAL; # tail call } SCM_MAX: my $p = shift; print_resources(); if(null($p)){ die "Error"; } if(null(cdr($p))){ @_ = (car($p)); goto SCHEME_RP; # return } else { if(car($p) > (car(cdr($p)))){ @_ = (cons(car($p), cdr(cdr($p)))); goto SCM_MAX; # tail call } else { @_ = (cdr($p)); goto SCM_MAX; # tail call } } } # helper functions for our simplistic scheme subsystem sub cons{ my($a,$d) = @_; [$a,$d] } sub car{ shift->[0] } sub cdr{ shift->[1] } sub null{ not defined shift } sub set_cdr{ my ($ls, $v) = @_; $ls->[1] = $v } sub mklist{ return unless @_; return cons(shift, mklist(@_)); } sub pair_str{ my $p = shift; if(ref $p eq 'ARRAY'){ "(" . pair_str(car($p)) . " " . pair_str(cdr($p)) . ")"; } else { if(null($p)){ "()" } else { $p; } } } # this is a really bad resource monitor but works to monitor # memory growth to check for proper tail recursion sub print_resources{ my @lines = grep {$_ =~ /\s+(\d+)/ and $1 eq $$} `ps u`; print @lines; }


Comment on Re: Pure Perl tail call optimization
Download Code
Re: Re: Pure Perl tail call optimization
by pdcawley (Hermit) on Apr 26, 2002 at 05:35 UTC
    Um... goto &SUB doesn't do the same thing as a normal sub call; no new stack frame is created, which is what tail call optimization is about, only creating a new stack frame when necessary. But it's still awfully slow (actually I've not done a speed comparison between goto SUB and the approach I'm currently using, and I'm not entirely sure how I'd code the benchmark.

    The big problem with goto LABEL is that it's even more awfully slow; doing a linear search through the source file every time it's called, which is why I discounted it. And implementing continuations means using a computed goto.

    I really should try an implementation that uses goto SUB though.

      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.

        It looks like you've proven that goto &sub leaks memory, but does that mean it creates a stack frame? Not necessarily. It could be doing something else that uses memory on each call. I think you'll need to go to the source to get irrefutable proof that goto &sub creates stack frames.

        -sam

      Um, goto &SUB does create a new stack frame, but only after the old one is stripped off. (Shouldn't leak memory though.)

      And goto LABEL doesn't do a linear search through the source file. And the way the (non-linear) search is written, going from the last statement to a label at the beginning should be pretty fast. Benchmarks are the only way to tell which will be faster.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://162119]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (7)
As of 2014-11-24 06:38 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My preferred Perl binaries come from:














    Results (137 votes), past polls