LOOP (programming language)

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 (and thus a subset of the computable by WHILE and GOTO program functions).

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

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:

P := x i := x j + c | x i := x j − c | P ; P | L O O P x i D O P E N D

Here, V a r := { x 0 , x 1 , . . . } are variable names and c ∈ N are constants.

Semantics

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

A statement of the form

x₀ := x₁ + c

means the value of the constant c is added to the value of the variable x 1 , and the result is set as the value of the variable x 0 . c can have the value zero, which allows the value of one variable to be assigned to another variable:

x₀ := x₁ + 0

A statement of the form

x₀ := x₁ - c

means the value of the constant c is subtracted from the value of the variable x 1 , and the result is set as the value of the variable x 0 . Negative numbers aren't allowed, and are replaced by zeros.

Variables are allowed to be simultaneously on the left and right side of an assignment. A statement of the form:

x₁: = x₁ + c

for example, adds the value of the constant c to the variable x 1 .

A statement of the form

P₁; P₂

represents the sequential execution of sub-programs P 1 and P 2 , in that order.

A statement of the form

LOOP x DO P END

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

Addition

In the following program, the variable x 0 is set to the sum of the variables x 1 and x 2 .

x₀ := x₁ + 0; LOOP x₂ DO x₀ := x₀ + 1 END

x 0 is first assigned the value of x 1 . Then, x 0 is incremented a total of x 2 times by the LOOP statement. 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:

x₀ := x₁ + x₂

Multiplication

The following LOOP program sets the value of the variable x 0 to the product of the variables x 1 and x 2 .

LOOP x₁ DO x₀ := x₀ + x₂ 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 x 2 a total of x 1 times, storing results in x 0 .