# LOOP (programming language)

LOOP is a language that precisely captures primitive recursive functions.[1] The only operations supported in the language are assignment, addition, and looping a number of times that is fixed before loop execution starts.

The LOOP language was introduced in a 1967 paper by Albert R. Meyer and Dennis M. Ritchie. [2] Meyer and Ritchie showed the correspondence between the LOOP language and primitive recursive functions.

Dennis M. Ritchie formulated the LOOP language, which was also the topic of his unpublished Ph.D. thesis.[3][4]

It was also presented by Uwe Schöning, along with GOTO and WHILE.[5]

## Features

Each primitive recursive function is LOOP-computable and vice versa.[6]

In contrast to GOTO programs and WHILE programs, LOOP programs always terminate.[7] 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).[8]

An example of a total computable function that is not LOOP computable is the Ackermann function.[9]

## Formal definition

### Syntax

LOOP-programs consist of the symbols LOOP, DO, END, :=, +, - and ; as well as any number of variables and constants. LOOP-programs have the following syntax in modified Backus–Naur form:

${\displaystyle {\begin{array}{lrl}P&::=&x_{i}:=0\\&|&x_{i}:=x_{i}+1\\&|&P;P\\&|&{\mathtt {LOOP}}\,x_{i}\,{\mathtt {DO}}\,P\,{\mathtt {END}}\end{array}}}$

Here, ${\displaystyle Var:=\{x_{0},x_{1},...\}}$ are variable names and ${\displaystyle c\in \mathbb {N} }$ are constants.

### Semantics

If P is a LOOP program, P is equivalent to a function ${\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$. The variables ${\displaystyle x_{1}}$ through ${\displaystyle x_{k}}$ in a LOOP program correspond to the arguments of the function ${\displaystyle f}$, and are initialized before program execution with the appropriate values. All other variables are given the initial value zero. The variable ${\displaystyle x_{0}}$ corresponds to the value that ${\displaystyle f}$ takes when given the argument values from ${\displaystyle x_{1}}$ through ${\displaystyle x_{k}}$.

A statement of the form

xi := 0


means the value of the variable ${\displaystyle x_{i}}$ is set to 0.

A statement of the form

xi := xi + 1


means the value of the variable ${\displaystyle x_{i}}$ is incremented by 1.

A statement of the form

P1; P2


represents the sequential execution of sub-programs ${\displaystyle P_{1}}$ and ${\displaystyle P_{2}}$, in that order.

A statement of the form

LOOP x DO P END


means the repeated execution of the partial program ${\displaystyle P}$ a total of ${\displaystyle x}$ times, where the value that ${\displaystyle x}$ has at the beginning of the execution of the statement is used. Even if ${\displaystyle P}$ changes the value of ${\displaystyle x}$, it won't affect how many times ${\displaystyle P}$ is executed in the loop. If ${\displaystyle x}$ has the value zero, then ${\displaystyle P}$ 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.

## Example programs

### Assignment

The following LOOP program assigns the value of variable xi to variable xj.

xj := 0;
LOOP xi DO
xj := xj + 1
END


In their seminal paper [10] Meyer & Ritchie made the assignment ${\displaystyle x_{j}:=x_{i}}$ a basic statement. As the program above shows the assignment is redundant and can be removed from the list of basic statements. It 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:

xj := xi


Remark: One has to keep in mind that all variables are global. That the new statement is equivalent to a subroutine does not mean that it is a subroutine. Normally an activation record prevents all side effects. In this case however no other variable but xj is affected, so side effects do not occur, provided that xj, which at this point in the execution of the program might contain a nonzero value, is initialized to 0.

### Projection

A special case of the assignment program is the program (we use the extended notation):

x0 := xi


This program computes the k-ary projection function ${\displaystyle U_{i}^{k}(x_{1},...,x_{i},...,x_{k})=x_{i}}$, which extracts the i-th coordinate from an ordered k-tuple.

### Predecessor

The predecessor function is defined as

${\displaystyle \operatorname {pred} (n)={\begin{cases}0&{\mbox{if }}n=0,\\n-1&{\mbox{otherwise}}\end{cases}}}$.

This function can be computed by the following LOOP program, which sets the variable ${\displaystyle x_{0}}$ to ${\displaystyle pred(x_{1})}$.

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

In the following program, the variable ${\displaystyle x_{0}}$ is set to the sum of the variables ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$.

LOOP x1 DO
x0 := x0 + 1
END;
LOOP x2 DO
x0 := x0 + 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 + x2


### 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 ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$.

x0 := x1
LOOP x2 DO
x0 := x0 ∸ 1
END


Like before we can extend the LOOP syntax with the statement:

x0 := x1 ∸ x2


### Multiplication

The following LOOP program sets the value of the variable ${\displaystyle x_{0}}$ to the product of the variables ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$.

LOOP x1 DO
x0 := x0 + x2
END


This multiplication program uses the syntax introduced by the addition subroutine from the previous example. The multiplication is performed here by adding the value of ${\displaystyle x_{2}}$ a total of ${\displaystyle x_{1}}$ times, storing results in ${\displaystyle x_{0}}$.

### 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;