Infinite loop
Encyclopedia
An infinite 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 system
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...

s 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 misleadingly called "infinite loops". One possible cause of a computer "freezing
Hang (computing)
In computing, a hang or freeze occurs when either a single computer program, or the whole system ceases to respond to inputs. In the most commonly encountered scenario, a workstation with a graphical user interface, all windows belonging to the frozen program become static, and though the mouse...

" is an infinite loop; others include deadlock
Deadlock
A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg"...

 and access violation
Segmentation fault
A segmentation fault , bus error or access violation is generally an attempt to access memory that the CPU cannot physically address. It occurs when the hardware notifies an operating system about a memory access violation. The OS kernel then sends a signal to the process which caused the exception...

s.

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 console is powered off.

Antique punchcard-reading unit record equipment
Unit record equipment
Before the advent of electronic computers, data processing was performed using electromechanical devices called unit record equipment, electric accounting machines or tabulating machines. Unit record machines were as ubiquitous in industry and government in the first half of the twentieth century...

 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.

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
Software bug
A software bug is the common term used to describe an error, flaw, mistake, failure, or fault in a computer program or system that produces an incorrect or unexpected result, or causes it to behave in unintended ways. Most bugs arise from mistakes and errors made by people in either a program's...

. Such errors are most common among novice programmers, but can be made by experienced programmers as well, and their causes can be quite subtle.

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
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...

 of the halting problem
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...

.

The simplest example (in C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....

):


while(1) {
printf("Infinite Loop\n");
}


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

Other simple examples:
A simple example in BASIC:

DO
LOOP UNTIL 0


A similar example in X86 assembly language
X86 assembly language
x86 assembly language is a family of backward-compatible assembly languages, which provide some level of compatibility all the way back to the Intel 8008. x86 assembly languages are used to produce object code for the x86 class of processors, which includes Intel's Core series and AMD's Phenom and...

:

loop:
; Code to loop here
jmp loop


A third example is in MS DOS

START
goto :A

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

One common cause, for example, is that the programmer intends to iterate over a collection of items such as a linked list
Linked list
In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...

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

Mathematical errors

Here is one example of an infinite loop in Visual Basic
Visual Basic
Visual Basic is the third-generation event-driven programming language and integrated development environment from Microsoft for its COM programming model...

:

dim x as integer
do until 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 SET x to 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.

Variable handling errors

Unexpected behavior in evaluating the terminating condition can also cause this problem. Here is an example (in C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....

):


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
Floating point
In computing, floating point describes a method of representing real numbers in a way that can support a wide range of values. Numbers are, in general, represented approximately to a fixed number of significant digits and scaled using an exponent. The base for the scaling is normally 2, 10 or 16...

 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.

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
Integer (computer science)
In computer science, an integer is a datum of integral data type, a data type which represents some finite subset of the mathematical integers. Integral data types may be of different sizes and may or may not be allowed to contain negative values....

 as a loop index
Control flow
In computer science, control flow refers to the order in which the individual statements, instructions, or function calls of an imperative or a declarative program are executed or evaluated....

, counting the number of iterations that have been performed.

A similar problem occurs frequently in numerical analysis
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical 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
E-Mail Loop
An email loop is an infinite loop phenomenon, resulting from mail servers, scripts, or email clients that generate automatic replies or responses. If one such automatic response triggers another automatic response on the other side, an email loop is created. The process can continue until one...

.

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
For loop
In computer science a for loop is a programming language statement which allows code to be repeatedly executed. A for loop is classified as an iteration statement....

 in C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....

:

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
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...

 used. With arbitrary-precision arithmetic
Arbitrary-precision arithmetic
In computer science, arbitrary-precision arithmetic indicates that calculations are performed on numbers whose digits of precision are limited only by the available memory of the host system. This contrasts with the faster fixed-precision arithmetic found in most ALU hardware, which typically...

, 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, a special case of an infinite loop that is caused by recursion
Recursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...

. The most trivial example of this is the term Ω in the lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...

, shown below in Scheme:

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

Ω is an infinite recursion, and therefore has no normal form
Normal form (term rewriting)
In abstract rewriting, a normal form is an element of the system which cannot be rewritten any further. Stated formally, for some reduction relation ⋅ → ⋅ over X a term t in X is a normal form if there does not exist a term t′ in X such that t → t′.Consider...

. 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
Stack-based memory allocation
Stacks in computing architectures are regions of memory where data is added or removed in a last-in-first-out manner.In most modern computer systems, each thread has a reserved region of memory referred to as its stack. When a function executes, it may add some of its state data to the top of the...

, 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
Recursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...

, for an alternate explanation of infinite recursion.

while ( true ) loop

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
Return statement
In computer programming, a return statement causes execution to leave the current subroutine and resume at the point in the code immediately after where the subroutine was called, known as its return address. The return address is saved, usually on the process's call stack, as part of the operation...

, e.g.:

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

Alderson loop

An Alderson loop is a 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 error. These are most common and visible while debugging
Debugging
Debugging is a methodical process of finding and reducing the number of bugs, or defects, in a computer program or a piece of electronic hardware, thus making it behave as expected. Debugging tends to be harder when various subsystems are tightly coupled, as changes in one may cause bugs to emerge...

 user interface code. Alderson bugs are considered to be one of the most common types of software bug
Software bug
A software bug is the common term used to describe an error, flaw, mistake, failure, or fault in a computer program or system that produces an incorrect or unexpected result, or causes it to behave in unintended ways. Most bugs arise from mistakes and errors made by people in either a program's...

.

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 forgotten to add the exit condition:

while (true) {
printf("Input a number to add to the sum or 0 to quit");
i = getUserInput;
if (i != 0) { //if i is not equal to zero the number is added to the sum
sum += i;
}
//else clause for zero should be here, without it the program won't terminate.
}


The term allegedly received its name from a programmer who had coded a modal message box in Microsoft Access
Microsoft Access
Microsoft Office Access, previously known as Microsoft Access, is a relational database management system from Microsoft that combines the relational Microsoft Jet Database Engine with a graphical user interface and software-development tools. It is a member of the Microsoft Office suite of...

 without either an OK or Cancel button, thereby disabling the entire program whenever the box came up.

See also

  • Cycle detection
  • Deadlock
    Deadlock
    A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg"...

  • Divergence (computer science)
    Divergence (computer science)
    In computer science, a computation is said to diverge if it does not terminate or terminates in an exceptional state. Otherwise it is said to converge...

  • Goto (command)
  • Recursion
    Recursion (computer science)
    Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem. The approach can be applied to many types of problems, and is one of the central ideas of computer science....

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK