LOOP (programming language)


LOOP is a language that precisely captures primitive recursive functions.
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.
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.
It was also presented by Uwe Schöning, along with GOTO and WHILE.

Features

Each primitive recursive function is LOOP-computable and vice versa.
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.
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 LOOP, DO, END, :=, +, - and ; as well as any number of variables and constants. LOOP-programs have the following syntax in modified Backus–Naur form:
Here, are variable names and are constants.

Semantics

If P is a LOOP program, P is equivalent to a function. The variables through in a LOOP program correspond to the arguments of the function, and are initialized before program execution with the appropriate values. All other variables are given the initial value zero. The variable corresponds to the value that takes when given the argument values from through.
A statement of the form
xi := 0
means the value of the variable is set to 0.
A statement of the form
xi := xi + 1
means the value of the variable is incremented by 1.
A statement of the form
P1; P2
represents the sequential execution of sub-programs and, in that order.
A statement of the form
LOOP x DO P END
means the repeated execution of the partial program a total of times, where the value that has at the beginning of the execution of the statement is used. Even if changes the value of, it won't affect how many times is executed in the loop. If has the value zero, then 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 Meyer & Ritchie made the assignment 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 :
x0 := xi
This program computes the k-ary projection function, which extracts the i-th coordinate from an ordered k-tuple.

Predecessor

The predecessor function is defined as
This function can be computed by the following LOOP program, which sets the variable to.
/* 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 to 0, x1 and 0 respectively, run the code on these variables and copy the result to x0. A compiler can do this.

Addition

In the following program, the variable is set to the sum of the variables and.
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 of the variables and.
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 to the product of the variables and.
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 a total of times, storing results in.

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;