Programming language
LOOP is a simple register language that precisely captures the primitive recursive functions.
The language is derived from the counter-machine model. Like the counter machines the LOOP language comprises a set of one or more unbounded "registers", each of which can hold a single non-negative integer. A few arithmetic instructions (like 'CleaR', 'INCrement', 'DECrement', 'CoPY', ...) operate on the registers. The only control flow instruction is 'LOOP x DO "..." END'. It causes the instructions within its scope to be repeated x times. (Changes of the content of register x during the execution of the loop do not affect the number of passes.)
History.
The LOOP language was formulated in a 1967 paper by Albert R. Meyer and Dennis M. Ritchie.
They showed the correspondence between the LOOP language and primitive recursive functions.
The language also was the topic of the unpublished PhD thesis of Ritchie.
It was also presented by Uwe Schöning, along with GOTO and WHILE.
Design philosophy and features.
In contrast to GOTO programs and WHILE programs, LOOP programs always terminate. Therefore, the set of functions computable by LOOP-programs is a proper subset of computable functions (and thus a subset of the computable by WHILE and GOTO program functions).
Meyer &amp; Ritchie proved that each primitive recursive function is LOOP-computable and vice versa.
An example of a total computable function that is not LOOP computable is the Ackermann function.
Formal definition.
Syntax.
LOOP-programs consist of the symbols codice_1, codice_2, codice_3, codice_4, codice_5 and codice_6 as well as any number of variables and constants. LOOP-programs have the following syntax in modified Backus–Naur form:
formula_1
Here, formula_2 are variable names and formula_3 are constants.
Semantics.
If P is a LOOP program, P is equivalent to a function formula_4. The variables formula_5 through formula_6 in a LOOP program correspond to the arguments of the function formula_7, and are initialized before program execution with the appropriate values. All other variables are given the initial value zero. The variable formula_8 corresponds to the value that formula_7 takes when given the argument values from formula_5 through formula_6.
A statement of the form
 xi := 0
means the value of the variable formula_12 is set to 0.
A statement of the form
 xi := xi + 1
means the value of the variable formula_12 is incremented by 1.
A statement of the form
 "P"1; "P"2
represents the sequential execution of sub-programs formula_14 and formula_15, in that order.
A statement of the form
 LOOP x DO "P" END
means the repeated execution of the partial program formula_16 a total of formula_17 times, where the value that formula_17 has at the beginning of the execution of the statement is used. Even if formula_16 changes the value of formula_17, it won't affect how many times formula_16 is executed in the loop. If formula_17 has the value zero, then formula_16 is not executed inside the LOOP statement. This allows for branches in LOOP programs, where the conditional execution of a partial program depends on whether a variable has value zero or one.
Creating "convenience instructions".
From the base syntax one create "convenience instructions". These will not be subroutines in the conventional sense but rather LOOP programs created from the base syntax and given a mnemonic. In a formal sense, to use these programs one needs to either (i) "expand" them into the code  – they will require the use of temporary or "auxiliary" variables so this must be taken into account, or (ii) design the syntax with the instructions 'built in'.
The k-ary projection function formula_24 extracts the i-th coordinate from an ordered k-tuple.
In their seminal paper Meyer &amp; Ritchie made the assignment formula_25 a basic statement.
As the example shows the assignment can be derived from the list of basic statements.
To create the formula_26 instruction use the block of code below.
formula_27 =equiv
 xj := 0;
 LOOP xi DO
 xj := xj + 1
 END
Again, all of this is for convenience only; none of this increases the model's intrinsic power.
Example Programs.
Addition.
Addition is recursively defined as:
 formula_28
Here, S should be read as "successor".
In the hyperoperater sequence it is the function formula_29
formula_30 can be implemented by the LOOP program ADD( x1, x2)
 LOOP x1 DO
 x0 := x0 + 1
 END;
 LOOP x2 DO
 x0 := x0 + 1
 END
Multiplication.
Multiplication is the hyperoperation function formula_31
formula_32 can be implemented by the LOOP program MULT( x1, x2 )
 x0 := 0;
 LOOP x2 DO
 x0 := ADD( x1, x0)
 END
The program uses the ADD() program as a "convenience instruction". Expanded, the MULT program is a LOOP-program with two nested LOOP instructions. ADD counts for one.
More hyperoperators.
Given a LOOP program for a hyperoperation function formula_33, one can construct a LOOP program for the next level
formula_34 for instance (which stands for exponentiation) can be implemented by the LOOP program POWER( x1, x2 )
 x0 := 1;
 LOOP x2 DO
 x0 := MULT( x1, x0 )
 END
The exponentiation program, expanded, has three nested LOOP instructions.
Predecessor.
The predecessor function is defined as
formula_35.
This function can be computed by the following LOOP program, which sets the variable formula_8 to formula_37.
 "/* precondition: x2 = 0 */"
 LOOP x1 DO
 x0 := x2;
 x2 := x2 + 1
 END
Expanded, this is the program
 "/* precondition: x2 = 0 */"
 LOOP x1 DO
 x0 := 0;
 LOOP x2 DO
 x0 := x0 + 1
 END;
 x2 := x2 + 1
 END
This program can be used as a subroutine in other LOOP programs. The LOOP syntax can be extended with the following statement, equivalent to calling the above as a subroutine:
 x0 := x1 ∸ 1
"Remark: Again one has to mind the side effects. The predecessor program changes the variable x2, which might be in use elsewhere. To expand the statement x0 := x1 ∸ 1, one could initialize the variables xn, xn+1 and xn+2 (for a big enough n) to 0, x1 and 0 respectively, run the code on these variables and copy the result (xn) to x0. A compiler can do this."
Cut-off subtraction.
If in the 'addition' program above the second loop decrements x0 instead of incrementing, the program computes the difference (cut off at 0) of the variables formula_5 and formula_39.
 x0 := x1
 LOOP x2 DO
 x0 := x0 ∸ 1
 END
Like before we can extend the LOOP syntax with the statement:
 x0 := x1 ∸ x2
If then else.
An if-then-else statement with if x1 ; x2 then P1 else P2:
 xn1 := x1 ∸ x2;
 xn2 := 0;
 xn3 := 1;
 LOOP xn1 DO
 xn2 := 1;
 xn3 := 0
 END;
 LOOP xn2 DO
 P1
 END;
 LOOP xn3 DO
 P2
 END;
Notes and references.
 ;templatestyles src="Reflist/styles.css" / ;
Bibliography.
 ;templatestyles src="Refbegin/styles.css" / ;