After my last post about Sub::Call::Tail melo and jrockway both asked me whether I was aware of Clojure's recur form. I wasn't. Shortly afterwords I wrote Sub::Call::Recur, which implements that form in Perl.
The recur operation is a tail call to the current subroutine. It's a bit like Perl's redo builtin, but for functions instead of blocks.
Here is a tail recursive factorial implementation:
sub fact {
my ( $n, $accum ) = @_;
$accum ||= 1;
if ( $n == 0 ) {
return $accum;
} else {
recur( $n - 1, $n * $accum );
}
}
The difference between this and using Sub::Call::Tail to modify simple recursion is that recur is almost as fast as an iterative loop. The overhead of destroying and recreating the stack frame for the subroutine invocation is avoided.
I may end up combining the two modules so that a tail call resolving to the current subroutine is automatically optimized like recur, but I'm not sure if that's a good idea yet (the semantics are a little different; Sub::Call::Tail reuses the goto opcode, whereas recur is like a customized reimplementation of the redo opcode).
Posts
3 comments:
A little benchmark to prove how useful this can be:
http://gist.github.com/224094
I like that your syntax is cleaner, but you can just do the following:
sub fact {
my ( $n, $accum ) = @_;
...
} else {
@_ = ($n - 1, $n * $accum)
&fact;
}
}
The & sigil/operator/whatever, when used without trailing (), will start the subroutine without altering the stack - ie. the current @_ will be used.
You can use that same approach for optimising tail recursive calls as well.
You need to use 'goto' when you do that
Post a Comment