NAME¶
Sub::Recursive - Anonymous memory leak free recursive subroutines
SYNOPSIS¶
use Sub::Recursive;
# LEAK FREE recursive subroutine.
my $fac = recursive {
my ($n) = @_;
return 1 if $n < 1;
return $n * $REC->($n - 1);
};
# Recursive anonymous definition in one line, plus invocation.
print recursive { $_[0] <= 1 ? 1 : $_[0] * $REC->($_[0] - 1) } -> (5);
# Experimental interface
use Sub::Recursive qw/ mutually_recursive %REC /;
my ($odd, $even) = mutually_recursive(
odd => sub { $_[0] == 0 ? 0 : $REC{even}->($_[0] - 1) },
even => sub { $_[0] == 0 ? 1 : $REC{odd }->($_[0] - 1) },
);
DESCRIPTION¶
Recursive closures suffer from a severe memory leak. "Sub::Recursive"
makes the problem go away cleanly and at the same time allows you to write
recursive subroutines as expression and can make them truly anonymous. There's
no significant speed difference between using &recursive and writing the
simpler leaking solution.
The problem¶
The following won't work:
my $fac = sub {
my ($n) = @_;
return 1 if $n < 1;
return $n * $fac->($n - 1);
};
because of the recursive use of $fac which isn't available until after the
statement. The common fix is to do
my $fac;
$fac = sub {
my ($n) = @_;
return 1 if $n < 1;
return $n * $fac->($n - 1);
};
Unfortunately, this introduces another problem.
Because of perl's reference count system, the code above is a memory leak. $fac
references the anonymous sub which references $fac, thus creating a circular
reference. This module does not suffer from that memory leak.
There are two more reasons why I don't like to write recursive closures like
that: (a) you have to first declare it, then assign it thus requiring more
than a simple expression (b) you have to name it one way or another.
The solution¶
This module fixes all those issues. Just change "sub" for
"recursive" and use &$REC for the recursive call:
use Sub::Recursive;
my $fac = recursive {
my ($n) = @_;
return 1 if $n < 1;
return $n * $REC->($n - 1);
};
It also makes it easy to pass it directly to a subroutine,
foo(recursive { ... });
just as any other anonymous subroutine.
EXPORTED FUNCTIONS¶
If no arguments are given to the "use" statement $REC and
&recursive are exported. If any arguments are given only those given are
exported. ":ALL" exports all.
$REC - exported by default¶
$REC holds a reference to the current subroutine inside subroutines created with
&recursive. Don't ever touch $REC inside or outside the subroutine except
for the recursive call.
"recursive" - exported by default¶
&recursive takes one argument and that's an anonymous sub defined in the
same package as the call to &recursive is in. It's prototyped with
"&" so bare-block calling style is encouraged.
recursive { ... }
The return value is an anonymous closure that has &$REC working in it.
%REC¶
This is an experimental part of the API.
%REC holds the subroutine references given to &mutually_recursive, with the
same keys.
Don't ever touch %REC inside or outside the subroutines except for the recursive
calls.
"mutually_recursive"¶
This is an experimental part of the API.
&mutually_recursive works like &recursive except it takes a list of
key/value pairs where the key names are the names used for the keys in %REC
and the values are the subroutine references. The return values are the
subroutine references, ordered as given to &mutually_recursive.
my ($odd, $even) = mutually_recursive(
odd => sub { $_[0] == 0 ? 0 : $REC{even}->($_[0] - 1) },
even => sub { $_[0] == 0 ? 1 : $REC{odd }->($_[0] - 1) },
);
BUGS¶
If you follow the rest of the manual you don't have to read this section. I
include this section anyway to make debugging simpler.
$REC is a package global and as such there are some gotchas. You won't encounter
any of these bugs below if you just use
recursive { ... }
and don't mention $REC outside of such an expression. In short: it's quite
unlikely you'll get bitten by any of these bugs.
- "my" and "our"
- Don't declare $REC with "my". That'll make $REC mean your
lexical variable rather than the global that "Sub::Recursive"
uses.
Don't declare $REC with "our". In particular, problem arise the
"our" scopes over several packages. If you do
package Foo;
use Sub::Recursive;
our $REC;
...
package Bar;
my $fatal = recursive { $REC->() };
$REC in &$fatal will be using the value of $Foo::REC but
"Sub::Recursive" has no way of knowing that and will think you
use $Bar::REC.
If you for some reason need to have $REC declared you can as a last resort
get around both these issues by fully qualifying $REC to the package in
which the subroutine is created.
package Foo;
use Sub::Recursive;
my $REC; # Bad.
my $fatal = recursive { $Foo::REC->() }; # Still works.
- Subroutine reference defined in another package
- This is a really far out edge case.
If the subroutine reference given to &recursive is defined in another
package than the call to &recursive in it then it won't work.
package Foo;
my $foo = sub { $REC->() };
package Bar;
use Sub::Recursive;
my $bar = &recursive($foo); # Won't work.
The subroutine referenced by $foo is using $Foo::REC but &recursive
thinks it's using $Bar::REC. Note that you have to circumvent prototyping
in order to encounter this bug.
Why you'd want to do this escapes me. Please contact me if you find a reason
for doing this.
EXAMPLE¶
Some algorithms are perhaps best written recursively. For simplicity, let's say
I have a tree consisting of arrays of array with arbitrary depth. I want to
map over this data structure, translating every value to another. For this I
might use
my $translator = recursive { [ map {
ref() ? $REC->($_) : do {
$translate{$_}
}
} @{$_[0]} ] };
my $bar = $translator->($foo);
Now, a tree mapper isn't perhaps the best example as it's a pretty general
problem to solve, and should perhaps be abstracted but it still serves as an
example of how this module can be handy.
A similar but more specialized task would be to find all men who share their Y
chromosome.
# A person data structure look like this.
my $person = {
name => ...,
sons => [ ... ], # objects like $person
daughters => [ ... ], # objects like $person
};
my @names = recursive {
my ($person) = @_;
$person->{name},
map $REC->($_), @{$person->{sons}}
} -> ($forefather);
This particular example isn't a closure as it doesn't reference any lexicals
outside itself (and thus could've been written as a named subroutine). It's
easy enough to think of a case when it would be a closure though. For instance
if some branches should be excluded. A simple flag would solve that.
my %exclude = ...;
my @names = recursive {
my ($person) = @_;
return if $exclude{$person};
$person->{name},
map $REC->($_), @{$person->{sons}}
} -> ($forefather);
Hopefully this illustrates how this module allows you to write recursive
algorithms inline like any other algorithm.
AUTHOR¶
Johan Lodin <lodin@cpan.org>
COPYRIGHT¶
Copyright 2004-2005 Johan Lodin. All rights reserved.
This library is free software; you can redistribute it and/or modify it under
the same terms as Perl itself.
SEE ALSO¶
perlref