LOOP (programming language)

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.

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.

The following LOOP program assigns the value of variable x_i to variable x_j.

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 x_j is affected, so side effects do not occur, provided that x_j, which at this point in the execution of the program might contain a nonzero value, is initialized to 0.

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.

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 x₂, which might be in use elsewhere. To expand the statement x₀ := x₁ ∸ 1, one could initialize the variables x_n, x_n+1 and x_n+2 (for a big enough n) to 0, x₁ and 0 respectively, run the code on these variables and copy the result (x_n) to x₀. 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

If in the 'addition' program above the second loop decrements x₀ 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

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}}$.

An if-then-else statement with if x₁ > x₂ 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;