cLive ;-) has asked for the wisdom of the Perl Monks concerning the following question:

Is there a standard, efficient way of catching an infinite loop? Eg, 
my $count = time;

$_ = 'hello there';

while (/e/) {
  print "ooo, looping\n";
  die ('infinite loop') if ($count + 2 > time);
}

[download]
This is a silly example, because it always loops. But the point is, it only loops for 2 seconds then quits.

In real life, I'll be doing dynamic s/earch/replace/ on dynamic vars, where the match differs from the replace (amongst other things), and wondered what the most efficient way was of catching this very rare, but possible, issue.

I suppose, the question I want answered is "What kind of failsafe's do you use to catch possible infinite loops?"

cLive ;-)

Replies are listed 'Best First'.
Re: Catching Infinite Loops
by tadman (Prior) on Apr 20, 2001 at 08:43 UTC
    Apart from the obvious strategy of coding carefully so as to not create them, you can always take the precaution of throwing an alarm call in there just in case things get out of whack. The alarm will always go off, even if your logic is blown to heck. If you put the code inside an eval, you can contain the damage, such as terminating a block of code instead of the entire program.

    Or, like you have done there, you can throw in a condition which you know will trigger at some point in the reasonable future. Base it on time, or a theoretical limit on the maximum number of loops you should take. As in, if you had a 1000 byte file and were trying to find all the 'e's, the loop should terminate by the 1001th iteration, since there aren't that many letters.

    In fact, that is the basic strategy employed by some algorithms that can, under some circumstances, end up in an infinite loop because of unusual but valid input data.

    Random Observation: Apple Computer is at 1 Infinite Loop in Cupertino, California.
[reply]
      Ditto but with some code... 
      local $SIG{ALRM} = sub { die 'what happened?' };
eval {
  alarm 2;  # about two seconds
  1 while 1;
};
if( $@ ){
  print "Whew!  Glad that timed out!\n";
}

      [download]
[reply]
[d/l]
Re: catching infinite loops
by larsen (Parson) on Apr 20, 2001 at 12:48 UTC
    I know I'm pedantic :), but I remember that the halting problem is not solvable.
[reply]
Re: catching infinite loops
by kal (Hermit) on Apr 20, 2001 at 12:36 UTC

    It depends on how you write things. For example, rather than writing a function iteratively (i.e., using the loop structure), write it recursively. Catching loops is then a matter of making sure you're not trying to calculate something you've previously tried to calculate - unless there's some random stuff in your function (making it a not-function :) if you've visited the same place twice, you're in a loop.

    The only thing to catch then is infinite diversions - such as, "Sum of all numbers to N" could be written:

    sum nums_to_n {
   my $n = shift;
   if ($n==0) return 0;
   else return $n + nums_to_n ($n-1);
}

    [download]

    This obviously loops indefinitely for $n < 0, which is not good. Usually, the answer is to make sure that your base case always occurs - that is, you can guarantee that there are certain values you can always calculate, and that you only accept values which rely, ultimately, on those values you can calculate.

    updated: changed a < into &lt; .. duh..

[reply]
[d/l]
      Random note.

      In Perl deep recursion leaks a lot of memory and is a lot slower than you would ever suspect. These two facts are connected.

      I have not tested with the current version, but also note that tail recursion with goto &my_sub does not get the performance you would hope for with a long argument list (there is adjusting of the stack), and appears to have a memory leak somewhere.

      Don't let this scare you off of recursion as a technique, but do be aware that you don't just want to blindly turn iterative loops into recursion.

[reply]
Re: catching infinite loops
by virtualsue (Vicar) on Apr 20, 2001 at 15:58 UTC
    I have never put in any gimmicks to catch an (unintended) infinite loop, though I have put them in place to catch when an infinite loop has stopped.

    As has already been pointed out, the customary method is to ask the OS to send you an alarm signal and wake you up. But... are you absolutely certain that you need to do this? I sense a possible design problem here, though I have no idea what your project entails.

[reply]
      replace $x with $y, both of which are externally input to script from config file. When you have tested it works, infinite loop can't happen. But, if an external developer decides to add their own config file, if they make a typo, the replace loop could go on forever.

      eg, ee -> e is OK, but would need to be looped until it fails. eeeee -> eee -> ee -> e -> done.

      But, say they entered these the other way round by mistake. eee -> eeeeee -> eeeeeeeeeeee ....

      Not the exact case, but that should give you an idea...

      cLive ;-)

[reply]
        In that case a time-based catch is going to be rather inadequate. A fast memory leak doesn't take long to hurt.

        Instead I would suggest either setting a maximum number of iterations, or looking into what your OS supplies in the way of things like ulimit...

[reply]
Re: catching infinite loops
by cLive ;-) (Prior) on Apr 20, 2001 at 08:23 UTC
    oops, should be: 
    die ('infinite loop') if ($count + 2 < time);

    [download]
    cLive ;-)
[reply]
[d/l]

Back to Seekers of Perl Wisdom