Re: private recursive subroutines
by friedo (Prior) on May 10, 2007 at 15:39 UTC
|
You can get around that by simply declaring $func as an undefined lexical and then re-defining it as a subroutine. Since the recursive call doesn't get executed until the sub is called for the first time, by that time, $func will contain the code reference. For example,
my $fac;
$fac = sub {
my ( $n ) = @_;
return 1 if $n == 1;
return $n * $fac->( $n - 1 );
};
print $fac->( 5 );
Yes, I know factorials are a bad example for recursion; it's just the first thing that came to mind. :) | [reply] [d/l] [select] |
|
This approach introduces a cyclic reference with $fac.
use Devel::Cycle;
my $fac;
$fac = sub {
my ( $n ) = @_;
return 1 if $n == 1;
return $n * $fac->( $n - 1 );
};
find_cycle($fac);
__END__
Cycle (1):
$A variable $fac => \&A
| [reply] [d/l] |
|
I can't say I understand much how the cycle gets introduced. Anyway, does undef $fac after the usage solve it?
| [reply] [d/l] |
|
| [reply] |
|
The F is probably the most popular, followed by fibonacci. Both are mostly demonstrated at the normal sub level. There should be some specific merit(s) to have this recursive closure. But I will keep this in mind, though, and perhaps use it someday.
Open source softwares? Share and enjoy. Make profit from them if you can. Yet, share and enjoy!
| [reply] |
Re: private recursive subroutines
by blokhead (Monsignor) on May 10, 2007 at 16:28 UTC
|
This is reminiscent of a common trick in (untyped) lambda calculus to make a function recursive -- called a Y combinator.
In fact, using a standard Y combinator, you don't have to change the public interface to the function -- you use currying to fix the extra parameter that is introduced:
my $func = sub {
my ($call_next, $param1, $param2) = @_;
do { something };
$call_next->($call_next, $newparam1, $newparam2);
};
my $nice_func = sub { $func->($func, @_) };
## now you don't have a bizarre calling convention:
$nice_func->(param1, param2);
I also like this better than your example because it doesn't use the $func variable confusingly in 2 different scopes (when I saw your original code, I had to think hard about whether you introduced a cyclic reference for $func).
Update: I should add that this won't result in a cyclic reference like the approaches in the previous replies.
See also: Re: recursive anonymous subroutines and this entry from Aristotle's use.perl journal.
| [reply] [d/l] |
Re: private recursive subroutines
by demerphq (Chancellor) on May 10, 2007 at 18:47 UTC
|
Other alternatives have been shown elsewhere in this thread, but one that Perlmonks uses (for reasons that are not worth getting into) is to do
local *foo= sub {
my ($param)= @_;
do { something };
foo($param);
};
foo(...);
This approach has the nice benefit of benefit of being a touch more readable and avoids the memory leak when using the lexically scoped var variant (as ambrus mentions elsewhere). On the other hand it spoils the method cache which can cause a general slowdown for OO. YMMV.
---
$world=~s/war/peace/g
| [reply] [d/l] |
|
In fact, it was diotalevi who taught me that my $f; $f = sub { ... &$f(...) ...}; leaks memory but the Y-combinator version my $g = sub { my $s = shift; ... &$s($s, ...) ... }; my $f = sub { &$g($g, @_) }; does not.
That was when I showed him the Y-combinatored version of a function for pureness (no side-effects). I didn't really need that because the function was global so I could have used side-effects (the memory leak wasn't an issue because it's a garbage-collected language). At that time, I didn't know that it has a practical application in perl because of the reference counting. You can find that implementation here: t2n.olv (source), t2n.pl (compiled to prolog), t2n.sml (compiled to sml), olvashato/ (link to all files).
Btw, diotalevi also claimed that this memory leak issue is described somewhere in Higher Order Perl, but I couldn't find it in that book. I'd be greatful if anyone can point me to the exact place.
| [reply] [d/l] [select] |
|
| [reply] |
|
|
|
|
| [reply] [d/l] |
|
From my limited understanding, the method cache allows Perl to remember to which function a method call resolves so it doesn't have to traverse @ISA every time.
Changing the symbol table clears the cache. the value of *foo changes twice in the snippet in your post, the explicit assignment and the implicit assignment at the end of local's scope.
$o->method(); # Normal (first call)
$o->method(); # Faster due to cache
*foo = sub {};
$o->method(); # Normal (cache cleared)
$o->method(); # Faster due to cache
| [reply] [d/l] [select] |
|
|
|
|
|
Re: private recursive subroutines
by akho (Hermit) on May 10, 2007 at 15:40 UTC
|
my $func;
$func = sub {
my ($param1, $param2) = @_;
do { something };
&{$func}($param1, $param2);
}
&{$func}($p1, $p2);
works just as well. And it is much clearer.
An anonymous recursive sub would be much more fun, though.
Upd Damn, friedo is too fast. | [reply] [d/l] |
Re: private recursive subroutines
by rlb3 (Deacon) on May 10, 2007 at 20:34 UTC
|
| [reply] |
|
Isn't this what the Y Combinator is for?
Yes, and that's what blokhead already suggested, and what my preferred solution would be.
| [reply] |
Re: private recursive subroutines
by naikonta (Curate) on May 10, 2007 at 15:36 UTC
|
Interesting. How would you escape from the recursive? Or, could you please give a real example of usage?
Open source softwares? Share and enjoy. Make profit from them if you can. Yet, share and enjoy!
| [reply] |
|
There's one here. Look for the comment saying "yay for recursive closures" :-)
| [reply] |
|
I don't think that showing my real-world example would have much point. I just had a very complicated subroutine where I wanted to refactor some code to a separate sub. I didn't want to pollute the package's namespace with another function name, so I used a my $coderef. And it turned out to be a good task for recursion, so here we go.
| [reply] |