Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options

Scoped Variables in a Recursive Function.

by kilinrax (Deacon)
on Sep 28, 2000 at 16:07 UTC ( #34361=perlquestion: print w/replies, xml ) Need Help??
kilinrax has asked for the wisdom of the Perl Monks concerning the following question:

While investigating I decided to try benchmarking different sorting algorithms, and have run into trouble with my implementation of <dfn>Merge Sort</dfn>;
sub Merge(@) { my @array = @_; MergeSort (0, $#array); return @array; sub MergeSort($$) { my $first = shift; my $last = shift; if ($last>$first) { my $mid = int(($last+$first)/2); MergeSort($first, $mid); MergeSort($mid+1, $last); my @b; @b = ( @array[$first..$mid], @array[reverse($mid+1..$last)] ); my ($i, $j, $k) = (0, $last-$first, $first); for (; $k<=$last; $k++) { $array[$k] = ($b[$i]<$b[$j]) ? $b[$i++] : $b[$j--]; } } } }
The function works perfectly, but with warnings turned on, spits out the following:
Variable "@array" will not stay shared at ./ line [x] +.
Where [x] is the first line in MergeSort() which manipulates @array.

Presumably I'm doing something naive here to do with the scoping of @array, which, in slightly different circumstances, could cause errors rather than just warnings.

So, what does the warning mean, and how should I declare @array to avoid it?

Replies are listed 'Best First'.
Re: Scoped Variables in a Recursive Function.
by japhy (Canon) on Sep 28, 2000 at 16:46 UTC
    You should not define a function inside a function. It does not behave as you'd expect. Instead, change your scoping slightly:
    { my @array; sub Merge { @array = @_; MergeSort(0, $#array); } sub MergeSort { # can see @array here... } }

      That will work, but as tilly pointed out, the problem is with the MergeSort code being named. This aught to work with the fewest changes to your code:
      sub Merge(@) { my @array = @_; local $MergeSort = sub { ### Anonymous code ref. ### my $first = shift; my $last = shift; if ($last>$first) { my $mid = int(($last+$first)/2); $MergeSort->($first, $mid); $MergeSort->($mid+1, $last); my @b; @b = ( @array[$first..$mid], @array[reverse($mid+1..$last)] ); my ($i, $j, $k) = (0, $last-$first, $first); for (; $k<=$last; $k++) { $array[$k] = ($b[$i]<$b[$j]) ? $b[$i++] : $b[$j--]; } } } $MergeSort->(0, $#array); return @array; }
        That ought to work, but it's silly, since it creates a code reference EVERY TIME you run Merge(). There's no reason to use a code reference. Define Merge() and MergeSort() in the same block, and have @array be shared between them.

Re (tilly) 1: Scoped Variables in a Recursive Function.
by tilly (Archbishop) on Sep 28, 2000 at 17:04 UTC
    For my attempt once at explaining the error, take a look at RE (3): BrainPain-Help.

    It really is a naming issue.

    Functions are given global names from which you can reach them from anywhere, any time. But only one can be available from that name at a time anywhere in the program.

    Lexical variables (declared with my) are private names that can only be reached by name from certain blocks of executing code. There may be several copies of a given lexical variable in existence at the same time, but because of how the naming works, they won't be mixed up.

    Now Perl is being asked to figure out which copy of a lexical variable will be seen when you call the globally named function and is throwing its hands up in disgust.

Re: Scoped Variables in a Recursive Function.
by extremely (Priest) on Sep 29, 2000 at 04:48 UTC

    This is the sort of code where you wish pass-by-reference was more obvious to the beginning coder.

    sub Merge(@) { my @array = @_; MergeSort (\@array, 0, $#array); return @array; } sub MergeSort($$$) { my $arrref = shift; my $first = shift; my $last = shift; if ($last>$first) { my $mid = int(($last+$first)/2); MergeSort($arrref, $first, $mid); MergeSort($arrref, $mid+1, $last); my @b; @b = ( @{$arrref}[$first..$mid], @{$arrref}[reverse($mid+1..$last) +] ); my ($i, $j, $k) = (0, $last-$first, $first); for (; $k<=$last; $k++) { $arrref->[$k] = ($b[$i]<$b[$j]) ? $b[$i++] : $b[$j--]; } } }

    As others have stated nesting subroutines Doesn't Do What You Expect. =) The enclosure method is nice but you should get used to passing references where you can. In this case Merge makes a copy of the data and then passes a reference on to MergeSort to do with as it pleases. Each recursive level of MergeSort passes the reference down to the next level. Neat and simple.


    $you = new YOU;
    honk() if $you->love(perl)

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://34361]
Approved by root
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (4)
As of 2017-04-24 19:53 GMT
Find Nodes?
    Voting Booth?
    I'm a fool:

    Results (445 votes). Check out past polls.