Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

private recursive subroutines

by Sixtease (Friar)
on May 10, 2007 at 15:30 UTC ( #614658=perlmeditation: print w/replies, xml ) Need Help??

Say you have a complicated method and you want to have an embedded subroutine there, that won't be visible elsewhere - like Pascal or D allow. No problem - you make a lexical code reference:

my $func = sub { my ($param1, $param2) = @_; do { foo }; return $bar; }

Then you call this subroutine like this:

$func->($something, $otherthing);

But what if you want this subroutine to be recursive? Inside its body, the $func variable isn't defined yet (right hand side of assignment is evaluated first), so you can't just say

my $func = sub { do { something }; $func->($param1, $param2); }

The solution is obvious - you have to add a parameter to the function where you'll pass itself:

my $func = sub { my ($func, $param1, $param2) = @_; do { something }; $func->($func, $param1, $param2); }

Of course you'll then have to adapt the first call as well:

$func->($func, $something, $otherthing);

Replies are listed 'Best First'.
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. :)

      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

      blokhead

        I can't say I understand much how the cycle gets introduced. Anyway, does undef $fac after the usage solve it?

      Wow this is cool and so much better than my solution! Thanks, I'll use it right away.

      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!

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.

    blokhead

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

      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.

        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.

        No. MJD ignored the problem and hoped p5p would solve it. That's not entirely unreasonable since this usage is common but it doesn't seem like its fix is immanent.

        ⠤⠤ ⠙⠊⠕⠞⠁⠇⠑⠧⠊

      local *foo= sub { my ($param)= @_; do { something }; foo($param); };

      ... On the other hand it spoils the method cache which can cause a general slowdown for OO.

      demerphq, would you mind explaining this a bit?

      • How does the method cache work?
      • Which part of the above spoils it?
      • And what effect does it have on the cache?
      thanks

      clint

        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
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.

Re: private recursive subroutines
by rlb3 (Deacon) on May 10, 2007 at 20:34 UTC

    Isn't this what the Y Combinator is for? Recursive anon subs.

      Isn't this what the Y Combinator is for?
      Yes, and that's what blokhead already suggested, and what my preferred solution would be.
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!

      There's one here. Look for the comment saying "yay for recursive closures" :-)

      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.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlmeditation [id://614658]
Approved by friedo
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (9)
As of 2022-12-02 15:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Notices?