Infinite loop

Last updated

In computer programming, an infinite loop (or endless loop) [1] [2] is a sequence of instructions that, as written, will continue endlessly, unless an external intervention occurs, such as turning off power via a switch or pulling a plug. It may be intentional.

Contents

There is no general algorithm to determine whether a computer program contains an infinite loop or not; this is the halting problem.

Overview

This differs from "a type of computer program that runs the same instructions continuously until it is either stopped or interrupted". [3] Consider the following pseudocode:

how_many=0whileis_there_more_data()dohow_many=how_many+1enddisplay"the number of items counted = "how_many

The same instructions were run continuously until it was stopped or interrupted . . . by the FALSE returned at some point by the function is_there_more_data.

By contrast, the following loop will not end by itself:

birds=1fish=2whilebirds+fish>1dobirds=3-birdsfish=3-fishend

birds will alternate being 1 or 2, while fish will alternate being 2 or 1. The loop will not stop unless an external intervention occurs ("pull the plug").

Details

An infinite loop is a sequence of instructions in a computer program which loops endlessly, either due to the loop having no terminating condition, [4] having one that can never be met, or one that causes the loop to start over. In older operating systems with cooperative multitasking, [5] 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.

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, [6] 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 (such as the blue screen of death), and enter an infinite loop waiting for the user to either respond to a prompt to continue, or reset the device.

Spinlocks

Spinlocks are low-level synchronization mechanisms used in concurrent programming to protect shared resources. Unlike traditional locks that put a thread to sleep when it can't acquire the lock, spinlocks repeatedly "spin" in an infinite loop until the lock becomes available. This intentional infinite looping is a deliberate design choice aimed at minimizing the time a thread spends waiting for the lock and avoiding the overhead of higher level synchronisation mechanisms such as mutexes.

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 socket/queue) and resume execution every time input is received.

Unintentional looping

A blue screen of death on Windows XP. "The device driver got stuck in an infinite loop." Infinite loop BSOD.jpg
A blue screen of death on Windows XP. "The device driver got stuck in an infinite loop."

Most often, the term is used for those situations when this is not the intended result; that is, when this is a bug. [7] Such errors are most common by 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 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. [8]

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, [9] 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), [10] Fortran (DO ... END DO), Go (for { ... }), Ruby (loop do ... end), and Rust (loop { ... }).

Examples of intentional infinite loops

A simple example (in C):

#include<stdio.h>intmain(){for(;;)// or equivalently, while (1)printf("Infinite Loop\n");return0;}

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

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

A similar example in 1980s-era BASIC:

10PRINT"INFINITE LOOP"20GOTO10

A similar example in DOS batch files:

:Aecho Infinite Loop goto:A

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

An example in Java:

while(true){System.out.println("Infinite Loop");}

The while loop never terminates because its condition is always true.

An example in Bourne Again Shell:

for((;;));doecho"Infinite Loop"done

An example in Rust:

loop{println!("Infinite loop");}

Examples of unintentional infinite loops

Mathematical errors

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

dimxasintegerdowhilex<5x=1x=x+1loop

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:

#include<stdio.h>intmain(void){inta=0;while(a<10){printf("%d\n",a);if(a=5)printf("a equals 5!\n");a++;}return0;}

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

C output on an AMD Turion processor:
x = 0.10000000149011611938
x = 0.20000000298023223877
x = 0.30000001192092895508
x = 0.40000000596046447754
x = 0.50000000000000000000
x = 0.60000002384185791016
x = 0.70000004768371582031
x = 0.80000007152557373047
x = 0.90000009536743164062
x = 1.00000011920928955078
x = 1.10000014305114746094
x = 1.20000016689300537109
...

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

floatx=0.1;while(x!=1.1){printf("x = %22.20f\n",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 0.1 exactly, thus introducing rounding errors on each increment (cf. box).

The same can happen in Python:

x=0.1whilex!=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

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

Very large numbers

An example in bash:

forxin$(seq1000000000);do#loop codedone

Impossible termination condition

An example for loop in C:

unsignedinti;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 hold i. If i was a signed integer, rather than an unsigned integer, overflow would be undefined. In this case, the compiler could optimize the code into an infinite loop.

Infinite recursion

Infinite recursion is a special case of an infinite loop that is caused by recursion.

The following example in Visual Basic for Applications (VBA) returns a stack overflow error:

SubTest1()CallTest1EndSub

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 an implementation of the code, typically due to a programmer 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 wrong operator is used:

intsum=0;inti;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. Note: ZERO means FALSE, Non-Zero means TRUE. "i * 0" is ZERO (FALSE)!sum+=i;// sum never changes 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 (last name Alderson) who in 1996 [12] had coded a modal dialog box in Microsoft Access without either an OK or Cancel button, thereby disabling the entire program whenever the box came up. [13]

See also

Related Research Articles

In programming language theory, lazy evaluation, or call-by-need, is an evaluation strategy which delays the evaluation of an expression until its value is needed and which also avoids repeated evaluations.

In computer science, control flow is the order in which individual statements, instructions or function calls of an imperative program are executed or evaluated. The emphasis on explicit control flow distinguishes an imperative programming language from a declarative programming language.

In computer programming, the scope of a name binding is the part of a program where the name binding is valid; that is, where the name can be used to refer to the entity. In other parts of the program, the name may refer to a different entity, or to nothing at all. Scope helps prevent name collisions by allowing the same name to refer to different objects – as long as the names have separate scopes. The scope of a name binding is also known as the visibility of an entity, particularly in older or more technical literature—this is in relation to the referenced entity, not the referencing name.

<span class="mw-page-title-main">OpenMP</span> Open standard for parallelizing

OpenMP is an application programming interface (API) that supports multi-platform shared-memory multiprocessing programming in C, C++, and Fortran, on many platforms, instruction-set architectures and operating systems, including Solaris, AIX, FreeBSD, HP-UX, Linux, macOS, and Windows. It consists of a set of compiler directives, library routines, and environment variables that influence run-time behavior.

<span class="mw-page-title-main">C syntax</span> Set of rules defining correctly structured programs

The syntax of the C programming language is the set of rules governing writing of software in C. It is designed to allow for programs that are extremely terse, have a close relationship with the resulting object code, and yet provide relatively high-level data abstraction. C was the first widely successful high-level language for portable operating-system development.

<span class="mw-page-title-main">While loop</span> Control flow statement for repeating execution until a condition is met

In most computer programming languages, a while loop is a control flow statement that allows code to be executed repeatedly based on a given Boolean condition. The while loop can be thought of as a repeating if statement.

<span class="mw-page-title-main">For loop</span> Control flow statement for repeated execution

In computer science, a for-loop or for loop is a control flow statement for specifying iteration. Specifically, a for-loop functions by running a section of code repeatedly until a certain condition has been satisfied.

In computer science, a generator is a routine that can be used to control the iteration behaviour of a loop. All generators are also iterators. A generator is very similar to a function that returns an array, in that a generator has parameters, can be called, and generates a sequence of values. However, instead of building an array containing all the values and returning them all at once, a generator yields the values one at a time, which requires less memory and allows the caller to get started processing the first few values immediately. In short, a generator looks like a function but behaves like an iterator.

<span class="mw-page-title-main">Foreach loop</span> Control flow statement for traversing items in a collection

In computer programming, foreach loop is a control flow statement for traversing items in a collection. foreach is usually used in place of a standard for loop statement. Unlike other for loop constructs, however, foreach loops usually maintain no explicit counter: they essentially say "do this to everything in this set", rather than "do this x times". This avoids potential off-by-one errors and makes code simpler to read. In object-oriented languages, an iterator, even if implicit, is often used as the means of traversal.

In computer science and software engineering, busy-waiting, busy-looping or spinning is a technique in which a process repeatedly checks to see if a condition is true, such as whether keyboard input or a lock is available. Spinning can also be used to generate an arbitrary time delay, a technique that was necessary on systems that lacked a method of waiting a specific length of time. Processor speeds vary greatly from computer to computer, especially as some processors are designed to dynamically adjust speed based on current workload. Consequently, spinning as a time-delay technique can produce inconsistent or even unpredictable results on different systems unless code is included to determine the time a processor takes to execute a "do nothing" loop, or the looping code explicitly checks a real-time clock.

In computer programming, conditional loops or repetitive control structures are a way for computer programs to repeat one or more various steps depending on conditions set either by the programmer initially or real-time by the actual program.

In many computer programming languages, a do while loop is a control flow statement that executes a block of code and then either repeats the block or exits the loop depending on a given boolean condition.

Cilk, Cilk++, Cilk Plus and OpenCilk are general-purpose programming languages designed for multithreaded parallel computing. They are based on the C and C++ programming languages, which they extend with constructs to express parallel loops and the fork–join idiom.

Loop unrolling, also known as loop unwinding, is a loop transformation technique that attempts to optimize a program's execution speed at the expense of its binary size, which is an approach known as space–time tradeoff. The transformation can be undertaken manually by the programmer or by an optimizing compiler. On modern processors, loop unrolling is often counterproductive, as the increased code size can cause more cache misses; cf. Duff's device.

<span class="mw-page-title-main">Recursion (computer science)</span> Use of functions that call themselves

In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.

setjmp.h is a header defined in the C standard library to provide "non-local jumps": control flow that deviates from the usual subroutine call and return sequence. The complementary functions setjmp and longjmp provide this functionality.

In the C and C++ programming languages, the comma operator is a binary operator that evaluates its first operand and discards the result, and then evaluates the second operand and returns this value ; there is a sequence point between these evaluations.

Secure coding is the practice of developing computer software in such a way that guards against the accidental introduction of security vulnerabilities. Defects, bugs and logic flaws are consistently the primary cause of commonly exploited software vulnerabilities. Through the analysis of thousands of reported vulnerabilities, security professionals have discovered that most vulnerabilities stem from a relatively small number of common software programming errors. By identifying the insecure coding practices that lead to these errors and educating developers on secure alternatives, organizations can take proactive steps to help significantly reduce or eliminate vulnerabilities in software before deployment.

In computing, a hang or freeze occurs when either a process or system ceases to respond to inputs. A typical example is when computer's graphical user interface no longer responds to the user typing on the keyboard or moving the mouse. The term covers a wide range of behaviors in both clients and servers, and is not limited to graphical user interface issues.

In the C programming language, operations can be performed on a bit level using bitwise operators.

References

  1. ↑ "Endless loop dictionary definition". Archived from the original on 2020-08-01. Retrieved 2020-01-22.
  2. ↑ "What is infinite loop (endless loop)". Archived from the original on 2019-07-15. Retrieved 2020-01-22.
  3. ↑ Caruso, Denise (August 16, 1999). "Overload of Hangers-On Creates Bumpy Ride for Internet Stocks". The New York Times . Archived from the original on December 27, 2019. Retrieved December 27, 2019.
  4. ↑ "Codes and Modes: The Character of Documentary Culture". Flow Journal. November 2014. Archived from the original on 2020-08-01. Retrieved 2020-01-23. an infinite loop is one that lacks .. an exit condition
  5. ↑ also known as non-preemptive-multitasking: "Non-preemptive Multitasking". PC Magazine . Archived from the original on July 26, 2019. Retrieved February 7, 2024.
  6. ↑ David Hoag (September 1976). "The History of Apollo On-board Guidance, Navigation, and Control" (PDF). Charles Stark Draper Laboratory. Archived (PDF) from the original on 2016-11-05. Retrieved 2020-01-23.
  7. ↑ "New York Times Crossword Answers". October 13, 2013. Archived from the original on August 2, 2020. Retrieved January 22, 2020. computing .. a defect .. which .. to loop
  8. ↑ "Halting Problem in Theory of Computation". 3 October 2018. Archived from the original on 9 August 2020. Retrieved 22 January 2020.
  9. ↑ "A Buffer Overflow Exploit Against the DameWare Remote Control software". December 19, 2003. Archived from the original on July 24, 2020. Retrieved January 22, 2020. As soon as the command shell is closed with a control-c combination ...
  10. ↑ Ada Programming: Control: Endless Loop
  11. ↑ "Endless loop in C/C++". Archived from the original on 2016-08-03.
  12. ↑ Lee Dohm (May 24, 2013). "Alderson loop". Archived from the original on June 19, 2020. Retrieved January 22, 2020.
  13. ↑ "Alderson Loop". The Jargon File, Version 4.4.7. Archived from the original on 2006-05-15. Retrieved 2006-05-21.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.