Loop (programming)

from Wikipedia, the free encyclopedia

A loop (also "repetition" or English loop ) is a control structure in programming languages . It repeats an instruction block - the so-called loop body or loop body  - as long as the loop condition remains valid as a run condition or does not occur as a termination condition . Loops whose loop condition always leads to continuation or which have no loop condition are endless loops .

Loops can be nested as required: Inside the loop body of the outer loop there is a loop, it lies inside or under the outer loop. Any loop can be converted to recursive or even terminal recursive form. To accelerate the program flow, loops are often unrolled by the compiler .

A loop is processed iteratively :

  1. It is checked whether the loop condition is valid; if not, the loop is ended.
  2. The entire loop body is executed. Then continue with 1..

species

A distinction is made between the following types of loops:

  • The pre-checking or head controlled loop.
    With this loop, a condition is checked before the (possible) execution of the loop body, whether the loop body (loop content) is then executed (for the first time / again) (usually with WHILE = initiated as long as this ).
  • The verification or foot operated loop.
    With this loop, after the loop body (loop content) has run through, a condition is checked whether the loop body is executed again (mostly as a construct DO ... WHILE = "execute ... as long as" or REPEAT ... UNTIL = "repeat ... until").
  • The counting loop , a special form of the pre-checking loop (mostly implemented as FOR = for loop).
  • The quantity loop , a special form of the counting loop (mostly implemented as FOREACH = "for each element of the quantity"; the order of the elements is arbitrary).

Furthermore, loops can differ with regard to their condition check:

  • Loop with running condition : The loop is run through as long as the loop condition is evaluated as "true".
  • Loop with termination condition : If the condition evaluates to "true", the loop is terminated.

An endless loop without loop condition (and without loop termination in it) can only be interrupted externally, for example by a program abort by the user, reset , interrupt , defect , switching off the device or the like.

Loop termination in special cases

In cases that are difficult to grasp as a loop condition, a loop can usually be broken off (out of the loop body).

Iteration termination

Only the current iteration is aborted: The rest of the current loop body is skipped . However, the loop continues with the next iteration. Sometimes, in nested loops, reference can also be made to a loop lying further outside - the termination of the current iteration then applies to the specified “further outside” loop; the "further inner", in whose loop body the abort instruction is, is then aborted completely.

Loop termination

Usually there is also a command to abort the loop completely, the program then continues with the first statement after the loop. Often in nested loops it is also possible to refer to a loop further outside, which then also breaks the inner loop.

Examples

The following examples in pseudocode can usually be found very similar in the respective programming languages .

Counting loop 

FOR Iterator:=Anfangszahl TO Endezahl STEP Schrittweite DO Schleifenrumpf.

In a for loop, the computer counts from a starting number to an ending number and repeats the code block (“loop body”) each time. The current number is set in a variable ("Iterator") so that it can be used in the code block if necessary. The counting loop is often limited to integers. Changing the iterator variables in the loop body is forbidden in many programming languages ​​and is considered a bad programming style, as it often leads to code that is difficult to understand - it runs counter to the way of thinking to be able to read the number of iterations directly at the loop head.

Head controlled loop

WHILE Logischer Ausdruck DO Schleifenrumpf.

In the case of a head-controlled loop, the condition is queried before the loop body is executed, i.e. at the head of the construct. A logical operation can be, for example: (x > 4)As long as this condition is true, the statements within the loop are executed. If the content of the logical operation is not changed in the body of the loop, this control structure is usually not the right one, because otherwise this loop will not be run through once or it will run infinitely long.

Foot operated loop 

DO Schleifenrumpf WHILE Logischer Ausdruck

or. 

REPEAT Schleifenrumpf UNTIL Logischer Ausdruck

In a foot-controlled loop, the condition is queried after the loop body has been executed, i.e. at the foot of the construct. A WHILErun condition follows UNTIL(German: until), a termination condition follows (German: to) . The same applies to the head-controlled loop: If the content of the logical operation is not changed in the loop body, this control structure is usually not the right one, because otherwise this loop will be run through exactly once or run forever.

Quantity loop

FOREACH Element OF Menge DO Schleifenrumpf

A set loop executes the loop body for each element of a set (e.g. array or list).

It can be replaced by a counting loop with the loop body 

FOR Iterator2 := 1 TO Mächtigkeit(Menge) DO
  BEGIN
    Element:= Iterator2-tes Element von Menge;
    Schleifenrumpf
  END

Since the sequence of processing in the set loop is arbitrary, it is up to the compiler how to proceed. Due to the fact that an iteration cannot be dependent on the "previous" one, a compiler can most easily parallelize set loops automatically .

Iteration termination

CONTINUE

or. 

CONTINUE Schleifenbezeichner

The first variant aborts the current iteration; the next iteration is to check the running condition. The second variant ends all inner loops in nested loops and has the same effect as the first variant for the outer loop that is addressed by the loop identifier . Often either a name similar to a jump label is used here; In counting loops, identification is sometimes made using the name of the iterator.

Loop termination

BREAK

or. 

BREAK Schleifenbezeichner

The first variant aborts the current loop; the process continues with the first statement after the loop. The second variant ends all inner loops completely in nested loops, as well as the outer loop that is addressed by the loop identifier . Often either a name similar to a jump label is used here; In counting loops, identification is sometimes made using the name of the iterator.

Implementation with jump instructions

In the past, unconditional jumps ( Goto commands ) were often used in high-level language programs . Languages ​​that use jump instructions allow the insertion of a label . Such a mark can then serve as the target of a Goto instruction .

According to today's programming paradigms, namely structured programming , it is not advisable to use Goto jumps, as these result in the notorious “ spaghetti code ”. In principle, however, any loop shape can be mapped with jump commands.

For loop

There are several alternatives to implementing for loops using simpler commands. Normally these alternatives behave the same, but there are differences in some special situations. Examples of special situations are:

  • The step size is 0 (not possible in all variants of the For loop).
  • The start value or the end value are the smallest or largest possible number that can be displayed.

A more detailed description of the variants can be found in the article For Loop .

While-do loop

WHILE Logischer Ausdruck DO Befehlssequenz.

corresponds to: 

Marke1:
IF NOT Logischer Ausdruck GOTO Marke2 (bedingter Vorwärtssprung)
Befehlssequenz
GOTO Marke1 (Rückwärtssprung)
Marke2:

The command sequence is never run through if the logical expression is wrong at the beginning.

Do-while loop

DO Befehlssequenz WHILE Logischer Ausdruck

corresponds to: 

Marke1:
Befehlssequenz
IF Logischer Ausdruck GOTO Marke1

Here the loop is run through once in each case. The do-while loop is thus verifying.

Repeat-until loop

REPEAT Befehlssequenz UNTIL Logischer Ausdruck

corresponds to: 

Marke1:
Befehlssequenz
IF NOT Logischer Ausdruck GOTO Marke1 (bedingter Rückwärtssprung)

So it is just a Do-While-Loop with a termination condition instead of a run condition.

Instructions in assembly language

Assembly code usually does not offer the for / while / repeat constructs known from high-level programming languages. However, since loops have to be used here too (delay due to active waiting (see below), serial addressed processing of data), simple jump commands for unconditional and conditional jumps are available.

The latter use a status flag of the CPU (e.g. zero flag) to decide whether to jump. If the requirement does not apply, the program counter (PC) is simply increased by one. The next step is to execute the command after the conditional jump command.

Example of code for an AVR microcontroller that uses a loop to delay a total of 5000 cycles by actively waiting: 

                ; delaying 4998 clocks in 2 loops
    ldi R0, $07 ; initialisiere äußeren Schleifenzähler mit '7'
Label0:
                ; innere Schleife
    ldi R1, $ed ; initialisiere inneren Schleifenzähler mit 237 (dezimal)
Label1:
    dec R1      ; Vermindert Inhalt in R1 um 1
    brne Label1 ; Sprung nur, wenn R1 nun nicht 0 ist. („BRanch if Not Equal to zero“)
    dec R0      ; äußeren Schleifenzähler um 1 verringern
    brne Label0
                ; delaying additional 2 clocks
    nop
    nop

There are often adapted assembler commands that combine several actions ("Check iterator for is-equals- ..., if not equal jump to ...", "Count iterator 1 down, if it is still greater than 0, jump to ..."). Often these require that a counting iterator z. B. is located in a certain register.

literature

  • Gert Smolka: Programming - an introduction to computer science with Standard ML. Oldenbourg Verlag, Munich 2005, ISBN 978-3-486-58601-5 .
  • Thomas Rauber, Gudula Rünger: Parallel programming. 3. Edition. Springer Verlag, Berlin 2012, ISBN 978-3-642-13603-0 .

Web links

Remarks

  1. ↑ A run condition must be fulfilled / true for a loop to continue.