PetaMem has asked for the wisdom of the Perl Monks concerning the following question:

Dear Monks,

today I spent my day bughunting a little subroutine and although it seems unlikely to me, I am about to state, that this is a Perl bug:

sub analyze {
  my $htree = shift;
  my $rul   = shift;
  my $hist  = (split /\n/, $htree->data)[0];
  my $str   = (split /\|/, $hist)[0];
  my ($k, $v);

  $hist = "|$hist";

  while(($k,$v) = each %$rul) {
    my @out = @{&proccode($str,$v)};

    for my $h (@out) {
      if($hist !~ /\|$h\|/) {
    my $new = $htree->append("$h$hist\n$k");
    &analyze($new,$rul);
    # PROBLEM: the @out loop is iterated again
    # even a 'next' does not force it to increment/end
      }
    }
  }
}

[download]
the problem of this routine is, that it seems to repeat the iteration within the for(@out) loop when returning from the recursive call to itself.

Which of course results in an endless loop for some cases. Even if I try to force it with "next" after the recursive call, it seems to be ignored.

Even if @out contains only one element, this happens.

So what is happening here? If I comment out the recursion call, the for(@out) loop behaves as it should.

sidenote: I encountered already a bug in Perl 5.8.0 when doing goto jumps within a for-loop (variables became undefined) - this was gone in 5.8.6 - which is what I'm using now.

Update: The 5.8.0 bug is ilustrated here.

Update2: Thanks to Fletch, Splinky and tlm, and because I had nothing to loose, I tried a modified version without the each iterator. Although I still do not see why it should influence the for(@out) loop, NOW IT WORKS! Instead of copying the hash, I extracted the keys into their own list. 

...
  my @rules = keys %$rul;

  for my $k (@rules) {
    my @out = @{&proccode($str,$$rul{$k})};
...

[download]

Bye
 PetaMem     All Perl:   MT, NLP, NLU

Replies are listed 'Best First'.
Re: Iterator Problem with recursion
by Fletch (Bishop) on Apr 26, 2005 at 17:09 UTC

    Not completely sure, but the fact that you're calling each on the same underlying hashref in the different scopes might be doing bad things. At least it's rasing hackles when I look at it.

[reply]
[d/l]
      You've hit the nail on the head.

      From the perlfunc documentation for each:

      There is a single iterator for each hash, shared by all each, keys, and values function calls in the program

[reply]
        Hi,

        well - I know of this restriction, and it may do bite me here sometime later. But I do not see how the each iterator, bound to %$rul should clash with the iteration of for(@out).

        Bye
         PetaMem             All Perl:   MT, NLP, NLU

[reply]
Re: Iterator Problem with recursion
by diotalevi (Canon) on Apr 27, 2005 at 04:47 UTC

    In noting your problem with re-using the same iterator on $rul over several, simultaneous calls to append(), give each call its own, separate hash and copy %$rul off before iterating over it. You then eliminate the interaction between recursive calls.

    my %rul = %$rull;

while ( my ( $k, $v ) = each %rul ) {
    ...
}

    [download]
[reply]
[d/l]
Re: Iterator Problem with recursion
by eibwen (Friar) on Apr 26, 2005 at 17:13 UTC

    I cannot say definitively what's going on, however two conceivably possible explanations could be:

    • @out contains an element with the value \@out
    • you're using next instead of last

    Possible alternatives include reducing the latter for loop:

    for my $h (@out) {
    &analyze($htree->append("$h$hist\n$k"),$rul) unless ($hist =~ /\|$
+h\|/);
}

    [download]

    If that works, it would seem to confirm that it is a bug.

    UPDATE: Looking at the provided code again, it would appear that it was provided in its entirety and that the comments were merely comments. However your reference to next as opposed to last still applies.

[reply]
[d/l]
[select]
      Hi,

      tried your code modification. Behaviour remains exactly the same. My point with "next" was, that it should not be necessary. If I'd put last instead of next after the recursion call, that'd change the semantics, because in that case, I always would look only at the first element of @out.

      OK - BUT I TRIED IT: I just hardcore put the "last" in there. Result: The same - although there is the "last" statement, the interpreter remains in the @out loop. And that IS a bug. Definitely.

      Bye
       PetaMem           All Perl:   MT, NLP, NLU

[reply]
Re: Iterator Problem with recursion
by moot (Chaplain) on Apr 26, 2005 at 17:08 UTC
    Are you sure analyze is eventually returning? Seems to me if proccode() returns anything at all that the loop over @out will be executed, calling analyze once more, and so ad infinitum.

    Update: Gah! didn't see that regexp conditional in there.. so it's unlikely that analyze() does not return at some point. In that event, is there a minimal test case that tickles this behaviour?

[reply]
      I am pretty sure, it does return. This routine (called "manal" in the system) is burried deep within a machine translation engine, I have here some log that visualizes the behaviour. The L1/L2 is a level counter I have installed to make sure I see when a level is entered and when exited.: 
      sub manal {
  my $htree = shift;
  my $rul   = shift;
  my $level = shift || 1;
  my $hist  = (split /\n/, $htree->data)[0];
  my $str   = (split /\|/, $hist)[0];
  my ($k, $v);

  $hist = "|$hist";
  &log("entering manal L$level with history: $hist\n");

  while(($k,$v) = each %$rul) {
    my @out = @{&proccode($str,$v)}

    for my $h (@out) {
      &log("debug: (out: @out - $h)/$str/$hist/$k\n");
      &manal($htree->append("$h$hist\n$k"),$rul,$level+1) if($hist !~ 
+/\|$h\|/);
 
    }
  }
  &log("exiting manal L$level for STR: $str\n");
}

      [download]
      Read more... (4 kB)

      Bye
       PetaMem           All Perl:   MT, NLP, NLU

[reply]
[d/l]

Back to Seekers of Perl Wisdom