Infinite loop

This article is about the programming term. For the street on which Apple Inc.'s campus is located, see Infinite Loop (street). For the book by Michael S. Malone, see Infinite Loop (book).

Loop constructs
Do while loop
While loop
For loop
Foreach loop
Infinite loop
Control flow

An infinite loop (or endless loop) is a sequence of instructions in a computer program which loops endlessly, either due to the loop having no terminating condition, having one that can never be met, or one that causes the loop to start over. In older operating systems with cooperative multitasking, infinite loops normally caused the entire system to become unresponsive. With the now-prevalent preemptive multitasking model, infinite loops usually cause the program to consume all available processor time, but can usually be terminated by the user. Busy wait loops are also sometimes called "infinite loops". One possible cause of a computer "freezing" is an infinite loop; others include thrashing, deadlock, and access violations.

Intended vs unintended looping

Looping is repeating a set of instructions until a specific condition is met. An infinite loop occurs when the condition will never be met, due to some inherent characteristic of the loop.

Intentional looping

There are a few situations when this is desired behavior. For example, the games on cartridge-based game consoles typically have no exit condition in their main loop, as there is no operating system for the program to exit to; the loop runs until the console is powered off.

Antique punch card-reading unit record equipment would literally halt once a card processing task was completed, since there was no need for the hardware to continue operating, until a new stack of program cards were loaded.

By contrast, modern interactive computers require that the computer constantly be monitoring for user input or device activity, so at some fundamental level there is an infinite processing idle loop that must continue until the device is turned off or reset. In the Apollo Guidance Computer, for example, this outer loop was contained in the Exec program, and if the computer had absolutely no other work to do it would loop run a dummy job that would simply turn off the "computer activity" indicator light.

Modern computers also typically do not halt the processor or motherboard circuit-driving clocks when they crash. Instead they fall back to an error condition displaying messages to the operator, and enter an infinite loop waiting for the user to either respond to a prompt to continue, or to reset the device.

Unintentional looping

Most often, the term is used for those situations when this is not the intended result; that is, when this is a bug. Such errors are most common among novice programmers, but can be made by experienced programmers as well, because their causes can be quite subtle.

One common cause, for example, is that the programmer intends to iterate over a collection of items such as a linked list, executing the loop code once for each item. Improperly formed links can create a reference loop in the list, where one list element links to one that occurred earlier in the list. This joins part of the list into a circle, causing the program to loop forever.

While most infinite loops can be found by close inspection of the code, there is no general method to determine whether a given program will ever halt or will run forever; this is the undecidability of the halting problem.

Interruption

So long as the system is responsive, infinite loops can often be interrupted by sending a signal to the process (such as SIGINT in Unix), or an interrupt to the processor, causing the current process to be aborted. This can be done in a task manager, in a terminal with the Control-C command, or by using the kill command or system call. However, this does not always work, as the process may not be responding to signals or the processor may be in an uninterruptible state, such as in the Cyrix coma bug (caused by overlapping uninterruptible instructions in an instruction pipeline). In some cases other signals such as SIGKILL can work, as they do not require the process to be responsive, while in other cases the loop cannot be terminated short of system shutdown.

Language support

Examples of intentional infinite loops

The simplest example (in C):

int main()
{
  for (;;); // or while (1);
}

The form for (;;) for an infinite loop is traditional, appearing in the standard reference The C Programming Language, and is often punningly pronounced "forever".^[2]

This is a loop that will print "Infinite Loop" without halting.

A similar example in BASIC :

10 PRINT "INFINITE LOOP"
20 GOTO 10

A similar example in X86 assembly language:

loop:
  ; Code to loop here
  jmp loop

Another example is in DOS

:A
goto :A

Here the loop is quite obvious, as the last line unconditionally sends execution back to the first.

An example in Python

while True:
    print("Infinite Loop")

An example in Bash

 $ while true; do echo "Infinite Loop"; done

An example in Perl

print "Infinite Loop\n" while 1

Examples of unintentional infinite loops

Mathematical errors

Here is one example of an infinite loop in Visual Basic:

dim x as integer
do while x < 5
  x = 1
  x = x + 1
loop

This creates a situation where x will never be greater than 5, since at the start of the loop code x is given the value of 1, thus, the loop will always end in 2 and the loop will never break. This could be fixed by moving the x = 1 instruction outside the loop. Essentially what this infinite loop does is to instruct a computer to keep on adding 1 to 1 until 5 is reached. Since 1+1 always equals 2, this will never happen.

In some languages, programmer confusion about the mathematical symbols may lead to an unintentional infinite loop. For example, here is a snippet in C:

#include <stdio.h>

int main(void)
{
   int a = 0;
   while (a < 10) {
      printf("%d\n", a);
      if (a = 5)
         printf("a equals 5!\n");
      a++;
   }
   return 0;
}

The expected output is the numbers 0 through 9, with an interjected "a equals 5!" between 5 and 6. However, in the line "if (a = 5)" above, the programmer has confused the = (assignment) with == (equality test) operators. Instead, this will assign the value of 5 to a at this point in the program. Thus, a will never be able to advance to 10, and this loop cannot terminate.

Variable handling errors

Unexpected behavior in evaluating the terminating condition can also cause this problem. Here is an example (in C):

float x = 0.1;
while (x != 1.1) {
  printf("x = %f\n", x);
  x = x + 0.1;
}

On some systems, this loop will execute ten times as expected, but on other systems it will never terminate. The problem is that the loop terminating condition (x != 1.1) tests for exact equality of two floating point values, and the way floating point values are represented in many computers will make this test fail, because they cannot represent the value 1.1 exactly.

The same can happen in Python:

x = 0.1
while x != 1:
    print x
    x += 0.1

Because of the likelihood of tests for equality or not-equality failing unexpectedly, it is safer to use greater-than or less-than tests when dealing with floating-point values. For example, instead of testing whether x equals 1.1, one might test whether (x <= 1.0), or (x < 1.1), either of which would be certain to exit after a finite number of iterations. Another way to fix this particular example would be to use an integer as a loop index, counting the number of iterations that have been performed.

A similar problem occurs frequently in numerical analysis: in order to compute a certain result, an iteration is intended to be carried out until the error is smaller than a chosen tolerance. However, because of rounding errors during the iteration, the specified tolerance can never be reached, resulting in an infinite loop.

Multi-party loops

Although infinite loops in a single program are usually easy to predict, a loop caused by several entities interacting is much harder to foresee. Consider a server that always replies with an error message if it does not understand the request. Apparently, there is no possibility for an infinite loop in the server, but if there are two such servers (A and B), and A receives a message of unknown type from B, then A replies with an error message to B, B does not understand the error message and replies to A with its own error message, A does not understand the error message from B and sends yet another error message, and so on ad infinitum. One common example of such situation is an e-mail loop.

Pseudo-infinite loops

A pseudo-infinite loop is a loop that appears infinite but is really just a very long loop.

Impossible termination condition

An example for loop in C:

unsigned int i;
for (i = 1; i != 0; i++) {
  /* loop code */
}

It appears that this will go on indefinitely, but in fact the value of i will eventually reach the maximum value storable in an unsigned int and adding 1 to that number will wrap-around to 0, breaking the loop. The actual limit of i depends on the details of the system and compiler used. With arbitrary-precision arithmetic, this loop would continue until the computer's memory could no longer contain i. If i was a signed integer, rather than an unsigned integer, overflow would be undefined. In this case, the loop could be optimized into an infinite loop.

Infinite recursion

Infinite recursion is a special case of an infinite loop that is caused by recursion. The most trivial example of this is the term Ω in the lambda calculus, shown below in Scheme:

(define Ω
  (let ([ω (lambda (f) (f f))])
    (ω ω)))

Ω is an infinite recursion, and therefore has no normal form. When using structural recursion, infinite recursions are usually caused by a missing base case or by a faulty inductive step. An example of such a faulty structural recursion:

(define (sum-from-1-to n)
  (+ n (sum-from-1-to (sub1 n))))

The function sum-from-1-to will run out of stack space, as the recursion never stops — it is infinite. To correct the problem, a base case is added.

(define (sum-from-1-to' n)
  (cond
    [(= n 1) 1]
    [else (+ n (sum-from-1-to' (sub1 n)))]))

This revised function will only run out of stack space if n is less than 1 or n is too large; error checking would remove the first case. For information on recursive functions which never run out of stack space, see tail recursion.

See also: Recursion, for an alternate explanation of infinite recursion.

Break statement

A "while (true)" loop looks infinite at first glance, but there may be a way to escape the loop through a break statement or return statement. Example in PHP:

while (true) {
   if ($foo->bar()) {
      return;
   }
}

Alderson loop

Alderson loop is a rare slang or jargon term for an infinite loop where there is an exit condition available, but inaccessible in the current implementation of the code, typically due to programmer's error. These are most common and visible while debugging user interface code.

A C-like pseudocode example of an Alderson loop, where the program is supposed to sum numbers given by the user until zero is given, but where the programmer has used the wrong operator:

sum = 0;
while (true) {
   printf("Input a number to add to the sum or 0 to quit");
   i = getUserInput();
   if (i * 0) { // if i times 0 is true, add i to the sum
      sum += i; // sum never change because (i * 0) is 0 for any i; it would change if we had != in the condition instead of *
   }
   if (sum > 100) {
      break;    // terminate the loop; exit condition exists but is never reached because sum is never added to
   }
}

The term allegedly received its name from a programmer who had coded a modal message box in Microsoft Access without either an OK or Cancel button, thereby disabling the entire program whenever the box came up.^[3]

External links

Make an infinite loop in several languages, on programming-idioms.org.

References

↑ Ada Programming: Control: Endless Loop
↑ Endless loop in C/C++
↑ Alderson Loop The Jargon File, Version 4.4.7. Accessed 5/21/2006. (public domain)

This article is issued from Wikipedia - version of the Wednesday, January 06, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.