LOOP is a simple register language that precisely captures the primitive recursive functions.
[1] 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.
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.)
The LOOP language was formulated in a 1967 paper by Albert R. Meyer and Dennis M.
[2] 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.
[7] Meyer & Ritchie proved that each primitive recursive function is LOOP-computable and vice versa.
[8] LOOP-programs consist of the symbols LOOP, DO, END, :=, + and ; as well as any number of variables and constants.
in a LOOP program correspond to the arguments of the function
, and are initialized before program execution with the appropriate values.
A statement of the form means the value of the variable
A statement of the form means the value of the variable
A statement of the form represents the sequential execution of sub-programs
A statement of the form means the repeated execution of the partial program
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.
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'.
extracts the i-th coordinate from an ordered k-tuple.
In their seminal paper [2] Meyer & Ritchie made the assignment
As the example shows the assignment can be derived from the list of basic statements.
=equiv Again, all of this is for convenience only; none of this increases the model's intrinsic power.
Addition is recursively defined as: Here, S should be read as "successor".
can be implemented by the LOOP program ADD( x1, x2) Multiplication is the hyperoperation function
Expanded, the MULT program is a LOOP-program with two nested LOOP instructions.
for instance (which stands for exponentiation) can be implemented by the LOOP program POWER( x1, x2 ) The exponentiation program, expanded, has three nested LOOP instructions.
The LOOP syntax can be extended with the following statement, equivalent to calling the above as a subroutine: Remark: Again one has to mind the side effects.
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.