Scoped Variables in a Recursive Function.

[kilinrax]

While investigating Benchmark.pm 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 ./benchmark-sort.pl 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?

[japhy]

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



$_="goto+F.print+chop;\n=yhpaj";F1:eval

[Adam]

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;

}

[japhy]

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.

$_="goto+F.print+chop;\n=yhpaj";F1:eval

[tilly]

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.

[extremely]

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.

HTH

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