Infinite loop
Programming idiom
- 11 min read
- 8 chapters
Related on Lably
Through Computer programming, Computer program and Control flow
There is no general algorithm to determine whether a computer program contains an infinite loop or not; this is the halting problem.
Overview
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 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 a user. Busy wait loops are also sometimes called "infinite loops". Infinite loops are one possible cause for a computer hanging or freezing; others include thrashing, deadlock, and access violations.
Sign in to keep reading
7 more chapters are free with a Lably account.
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.
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.
Multi-threading
In multi-threaded programs some threads can be executing inside infinite loops without causing the entire program to be stuck in an infinite loop. If the main thread exits, all threads of the process are forcefully stopped, thus all execution ends and the process/program terminates. The threads inside the infinite loops can perform "housekeeping" tasks or they can be in a blocked state waiting for input (from a socket/queue) and resume execution every time input is received.
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 also, because their causes can be quite subtle.
One common cause, for example, is that a programmer intends to iterate over a sequence of nodes in a data structure such as a linked list or tree, executing the loop code once for each node. Improperly formed links can create a reference loop in the data structure, where one node links to another that occurs earlier in the sequence. This makes part of the data structure into a ring, causing naive code 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
As 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
Infinite loops can be implemented using various control flow constructs. Most commonly, in unstructured programming this is jump back up (goto), while in structured programming this is an indefinite loop (while loop) set to never end, either by omitting the condition or explicitly setting it to true, as while (true) ....
Some languages have special constructs for infinite loops, typically by omitting the condition from an indefinite loop. Examples include Ada (loop ... end loop), Fortran (DO ... END DO), Go (for { ... }), Ruby (loop do ... end), and Rust (loop { ... }).
Infinite loops can also be created using recursion. This process is called infinite recursion.
Examples of intentional infinite loops
This is a loop that will print "Infinite loop" without halting, in C:
<span id="mwfg"></span><span class="cp" id="mwfw">#include</span><span class="w" id="mwgA"> </span><span class="cpf" id="mwgQ"><stdio.h></span> <span class="kt" id="mwgg">int</span><span class="w" id="mwgw"> </span><span class="nf" id="mwhA">main</span><span class="p" id="mwhQ">()</span><span class="w" id="mwhg"> </span><span class="p" id="mwhw">{</span> <span class="w" id="mwiA"> </span><span class="k" id="mwiQ">for</span><span class="w" id="mwig"> </span><span class="p" id="mwiw">(;;)</span><span class="w" id="mwjA"> </span><span class="p" id="mwjQ">{</span> <span class="w" id="mwjg"> </span><span class="n" id="mwjw">printf</span><span class="p" id="mwkA">(</span><span class="s" id="mwkQ">"Infinite loop</span><span class="se" id="mwkg">\n</span><span class="s" id="mwkw">"</span><span class="p" id="mwlA">);</span> <span class="w" id="mwlQ"> </span><span class="p" id="mwlg">}</span> <span class="w" id="mwlw"> </span><span class="k" id="mwmA">return</span><span class="w" id="mwmQ"> </span><span class="mi" id="mwmg">0</span><span class="p" id="mwmw">;</span> <span class="p" id="mwnA">}</span>The form for (;;) for an infinite loop is traditional, appearing in the standard reference The C Programming Language, and is often pronounced "forever." However, its presence does not guarantee an infinite loop since the loop can be terminated by breaking using break, returning using return, or jumping using goto.
In C and C-derived languages, an infinite loop is perhaps more modernly expressed as while (true):
<span id="mwrA"></span><span class="cp" id="mwrQ">#include</span><span class="w" id="mwrg"> </span><span class="cpf" id="mwrw"><stdio.h></span> <span class="kt" id="mwsA">int</span><span class="w" id="mwsQ"> </span><span class="nf" id="mwsg">main</span><span class="p" id="mwsw">()</span><span class="w" id="mwtA"> </span><span class="p" id="mwtQ">{</span> <span class="w" id="mwtg"> </span><span class="k" id="mwtw">while</span><span class="w" id="mwuA"> </span><span class="p" id="mwuQ">(</span><span class="nb" id="mwug">true</span><span class="p" id="mwuw">)</span><span class="w" id="mwvA"> </span><span class="p" id="mwvQ">{</span> <span class="w" id="mwvg"> </span><span class="n" id="mwvw">printf</span><span class="p" id="mwwA">(</span><span class="s" id="mwwQ">"Infinite loop</span><span class="se" id="mwwg">\n</span><span class="s" id="mwww">"</span><span class="p" id="mwxA">);</span> <span class="w" id="mwxQ"> </span><span class="p" id="mwxg">}</span> <span class="w" id="mwxw"> </span><span class="k" id="mwyA">return</span><span class="w" id="mwyQ"> </span><span class="mi" id="mwyg">0</span><span class="p" id="mwyw">;</span> <span class="p" id="mwzA">}</span>In the descendant languages of C, such as C++, Java, and C#, it is more idiomatic to use while (true).
A similar example in 1980s-era BASIC:
<span id="mw1g"></span><span class="nl" id="mw1w">10</span><span class="w" id="mw2A"> </span><span class="kr" id="mw2Q">PRINT</span><span class="w" id="mw2g"> </span><span class="s2" id="mw2w">"INFINITE LOOP"</span> <span class="nl" id="mw3A">20</span><span class="w" id="mw3Q"> </span><span class="kr" id="mw3g">GOTO</span><span class="w" id="mw3w"> </span><span class="nl" id="mw4A">10</span>
A similar example in MS-DOS compatible batch files:
<span id="mw5Q"></span><span class="p" id="mw5g">:</span><span class="nl" id="mw5w">A</span> <span class="k" id="mw6A">echo</span> Infinite Loop <span class="k" id="mw6Q">goto</span> <span class="p" id="mw6g">:</span><span class="nl" id="mw6w">A</span>
The while loop never terminates because its condition is always true.
<span id="mw8Q"></span><span class="k" id="mw8g">for</span><span class="w" id="mw8w"> </span><span class="o" id="mw9A">((</span><span class="p" id="mw9Q">;;</span><span class="o" id="mw9g">))</span><span class="p" id="mw9w">;</span><span class="w" id="mw-A"> </span><span class="k" id="mw-Q">do</span> <span class="w" id="mw-g"> </span><span class="nb" id="mw-w">echo</span><span class="w" id="mw_A"> </span><span class="s2" id="mw_Q">"Infinite Loop"</span> <span class="k" id="mw_g">done</span>
Examples of unintentional infinite loops
Mathematical errors
Here is one example of an infinite loop in Visual Basic:
<span id="mwAQU"></span><span class="k" id="mwAQY">dim</span><span class="w" id="mwAQc"> </span><span class="n" id="mwAQg">x</span><span class="w" id="mwAQk"> </span><span class="ow" id="mwAQo">as</span><span class="w" id="mwAQs"> </span><span class="kt" id="mwAQw">integer</span> <span class="k" id="mwAQ0">do</span><span class="w" id="mwAQ4"> </span><span class="k" id="mwAQ8">while</span><span class="w" id="mwARA"> </span><span class="n" id="mwARE">x</span><span class="w" id="mwARI"> </span><span class="o" id="mwARM"><</span><span class="w" id="mwARQ"> </span><span class="mi" id="mwARU">5</span> <span class="w" id="mwARY"> </span><span class="n" id="mwARc">x</span><span class="w" id="mwARg"> </span><span class="o" id="mwARk">=</span><span class="w" id="mwARo"> </span><span class="mi" id="mwARs">1</span> <span class="w" id="mwARw"> </span><span class="n" id="mwAR0">x</span><span class="w" id="mwAR4"> </span><span class="o" id="mwAR8">=</span><span class="w" id="mwASA"> </span><span class="n" id="mwASE">x</span><span class="w" id="mwASI"> </span><span class="o" id="mwASM">+</span><span class="w" id="mwASQ"> </span><span class="mi" id="mwASU">1</span> <span class="k" id="mwASY">loop</span>
This creates a situation where x will never be greater than 5, since at the start of the loop code, x is assigned the value of 1 (regardless of any previous value) before it is changed to x + 1. Thus the loop will always result in x = 2 and will never break. This could be fixed by moving the x = 1 instruction outside the loop so that its initial value is set only once.
In some languages, programmer confusion about mathematical symbols may lead to an unintentional infinite loop. For example, here is a snippet in C:
<span id="mwATE"></span><span class="cp" id="mwATI">#include</span><span class="w" id="mwATM"> </span><span class="cpf" id="mwATQ"><stdio.h></span> <span class="kt" id="mwATU">int</span><span class="w" id="mwATY"> </span><span class="nf" id="mwATc">main</span><span class="p" id="mwATg">(</span><span class="kt" id="mwATk">void</span><span class="p" id="mwATo">)</span><span class="w" id="mwATs"> </span><span class="p" id="mwATw">{</span> <span class="w" id="mwAT0"> </span><span class="kt" id="mwAT4">int</span><span class="w" id="mwAT8"> </span><span class="n" id="mwAUA">a</span><span class="w" id="mwAUE"> </span><span class="o" id="mwAUI">=</span><span class="w" id="mwAUM"> </span><span class="mi" id="mwAUQ">0</span><span class="p" id="mwAUU">;</span> <span class="w" id="mwAUY"> </span><span class="k" id="mwAUc">while</span><span class="w" id="mwAUg"> </span><span class="p" id="mwAUk">(</span><span class="n" id="mwAUo">a</span><span class="w" id="mwAUs"> </span><span class="o" id="mwAUw"><</span><span class="w" id="mwAU0"> </span><span class="mi" id="mwAU4">10</span><span class="p" id="mwAU8">)</span><span class="w" id="mwAVA"> </span><span class="p" id="mwAVE">{</span> <span class="w" id="mwAVI"> </span><span class="n" id="mwAVM">printf</span><span class="p" id="mwAVQ">(</span><span class="s" id="mwAVU">"%d</span><span class="se" id="mwAVY">\n</span><span class="s" id="mwAVc">"</span><span class="p" id="mwAVg">,</span><span class="w" id="mwAVk"> </span><span class="n" id="mwAVo">a</span><span class="p" id="mwAVs">);</span> <span class="w" id="mwAVw"> </span><span class="k" id="mwAV0">if</span><span class="w" id="mwAV4"> </span><span class="p" id="mwAV8">(</span><span class="n" id="mwAWA">a</span><span class="w" id="mwAWE"> </span><span class="o" id="mwAWI">=</span><span class="w" id="mwAWM"> </span><span class="mi" id="mwAWQ">5</span><span class="p" id="mwAWU">)</span><span class="w" id="mwAWY"> </span><span class="p" id="mwAWc">{</span> <span class="w" id="mwAWg"> </span><span class="n" id="mwAWk">printf</span><span class="p" id="mwAWo">(</span><span class="s" id="mwAWs">"a equals 5!</span><span class="se" id="mwAWw">\n</span><span class="s" id="mwAW0">"</span><span class="p" id="mwAW4">);</span> <span class="w" id="mwAW8"> </span><span class="p" id="mwAXA">}</span> <span class="w" id="mwAXE"> </span><span class="o" id="mwAXI">++</span><span class="n" id="mwAXM">a</span><span class="p" id="mwAXQ">;</span> <span class="w" id="mwAXU"> </span><span class="p" id="mwAXY">}</span> <span class="w" id="mwAXc"> </span><span class="k" id="mwAXg">return</span><span class="w" id="mwAXk"> </span><span class="mi" id="mwAXo">0</span><span class="p" id="mwAXs">;</span> <span class="p" id="mwAXw">}</span>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 = (assignment) operator was confused with the == (equality test) operator. 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.
Rounding errors
Unexpected behavior in evaluating the terminating condition can also cause this problem. Here is an example in C:
<span id="mwAaY"></span><span class="kt" id="mwAac">float</span><span class="w" id="mwAag"> </span><span class="n" id="mwAak">x</span><span class="w" id="mwAao"> </span><span class="o" id="mwAas">=</span><span class="w" id="mwAaw"> </span><span class="mf" id="mwAa0">0.1</span><span class="p" id="mwAa4">;</span> <span class="k" id="mwAa8">while</span><span class="w" id="mwAbA"> </span><span class="p" id="mwAbE">(</span><span class="n" id="mwAbI">x</span><span class="w" id="mwAbM"> </span><span class="o" id="mwAbQ">!=</span><span class="w" id="mwAbU"> </span><span class="mf" id="mwAbY">1.1</span><span class="p" id="mwAbc">)</span><span class="w" id="mwAbg"> </span><span class="p" id="mwAbk">{</span> <span class="w" id="mwAbo"> </span><span class="n" id="mwAbs">printf</span><span class="p" id="mwAbw">(</span><span class="s" id="mwAb0">"x = %22.20f</span><span class="se" id="mwAb4">\n</span><span class="s" id="mwAb8">"</span><span class="p" id="mwAcA">,</span><span class="w" id="mwAcE"> </span><span class="n" id="mwAcI">x</span><span class="p" id="mwAcM">);</span> <span class="w" id="mwAcQ"> </span><span class="n" id="mwAcU">x</span><span class="w" id="mwAcY"> </span><span class="o" id="mwAcc">+=</span><span class="w" id="mwAcg"> </span><span class="mf" id="mwAck">0.1</span><span class="p" id="mwAco">;</span> <span class="p" id="mwAcs">}</span>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 0.1 exactly, thus introducing rounding errors on each increment (cf. box).
The same can happen in Python:
<span id="mwAdQ"></span><span class="n" id="mwAdU">x</span><span class="p" id="mwAdY">:</span> <span class="nb" id="mwAdc">float</span> <span class="o" id="mwAdg">=</span> <span class="mf" id="mwAdk">0.1</span> <span class="k" id="mwAdo">while</span> <span class="n" id="mwAds">x</span> <span class="o" id="mwAdw">!=</span> <span class="mi" id="mwAd0">1</span><span class="p" id="mwAd4">:</span> <span class="nb" id="mwAd8">print</span><span class="p" id="mwAeA">(</span><span class="n" id="mwAeE">x</span><span class="p" id="mwAeI">)</span> <span class="n" id="mwAeM">x</span> <span class="o" id="mwAeQ">+=</span> <span class="mf" id="mwAeU">0.1</span>
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
An infinite loop may be caused by several entities interacting. Consider a server that always replies with an error message if it does not understand the request. Even if there is no possibility for an infinite loop within the server itself, a system comprising two of them (A and B) may loop endlessly: if A receives a message of unknown type from B, then A replies with an error message to B; if B does not understand the error message, it replies to A with its own error message; if A does not understand the error message from B, it sends yet another error message, and so on.
One common example of such a situation is an email loop. An example of an email loop is if someone receives mail from a no-reply inbox, but their auto-response is on. They will reply to the no-reply inbox, triggering the "this is a no-reply inbox" response. This will be sent to the user, who then sends an auto-reply to the no-reply inbox, and so on and so forth.
Pseudo-infinite loops
A pseudo-infinite loop is a loop that appears infinite but is really just a very long loop.
Impossible termination condition
<span id="mwAgQ"></span><span class="k" id="mwAgU">for</span><span class="w" id="mwAgY"> </span><span class="p" id="mwAgc">(</span><span class="kt" id="mwAgg">unsigned</span><span class="w" id="mwAgk"> </span><span class="kt" id="mwAgo">int</span><span class="w" id="mwAgs"> </span><span class="n" id="mwAgw">i</span><span class="w" id="mwAg0"> </span><span class="o" id="mwAg4">=</span><span class="w" id="mwAg8"> </span><span class="mi" id="mwAhA">1</span><span class="p" id="mwAhE">;</span><span class="w" id="mwAhI"> </span><span class="n" id="mwAhM">i</span><span class="w" id="mwAhQ"> </span><span class="o" id="mwAhU">!=</span><span class="w" id="mwAhY"> </span><span class="mi" id="mwAhc">0</span><span class="p" id="mwAhg">;</span><span class="w" id="mwAhk"> </span><span class="n" id="mwAho">i</span><span class="o" id="mwAhs">++</span><span class="p" id="mwAhw">)</span><span class="w" id="mwAh0"> </span><span class="p" id="mwAh4">{}</span>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, causing an integer overflow, 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 hold i. If i was a signed integer, rather than an unsigned integer, overflow would be undefined.