LOOP (programming language)

By Wikipedia Contributors

LOOP is a programming language designed by Uwe Schöning, along with GOTO and WHILE. The only operations supported in the language are assignment, addition and looping.

The key property of the LOOP language is that the functions it can compute are exactly the primitive recursive functions.[1]

Features

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

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

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

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:

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 {\displaystyle {\begin{array}{lrl}P&:=&x_{i}:=x_{j}+c\\&|&x_{i}:=x_{j}-c\\&|&P;P\\&|&{\mathtt {LOOP}}\,x_{i}\,{\mathtt {DO}}\,P\,{\mathtt {END}}\end{array}}} {\displaystyle {\begin{array}{lrl}P&:=&x_{i}:=x_{j}+c\\&|&x_{i}:=x_{j}-c\\&|&P;P\\&|&{\mathtt {LOOP}}\,x_{i}\,{\mathtt {DO}}\,P\,{\mathtt {END}}\end{array}}}

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

Semantics

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

A statement of the form

x0 := x1 + c

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

x0 := x1 + 0

A statement of the form

x0 := x1 - c

means the value of the constant c {\displaystyle c} c is subtracted from the value of the variable x 1 {\displaystyle x_{1}} x_{1}, and the result is set as the value of the variable x 0 {\displaystyle x_{0}} 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:

x1: = x1 + c

for example, adds the value of the constant c {\displaystyle c} c to the variable x 1 {\displaystyle x_{1}} x_{1}.

A statement of the form

P1; P2

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

A statement of the form

LOOP x DO P END

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

Addition

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

x0 := x1 + 0;
LOOP x2 DO
   x0 := x0 + 1
END

x 0 {\displaystyle x_{0}} x_{0} is first assigned the value of x 1 {\displaystyle x_{1}} x_{1}. Then, x 0 {\displaystyle x_{0}} x_{0} is incremented a total of x 2 {\displaystyle x_{2}} 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:

x0 := x1 + x2

Multiplication

The following LOOP program sets the value of the variable x 0 {\displaystyle x_{0}} x_{0} to the product of the variables x 1 {\displaystyle x_{1}} x_{1} and x 2 {\displaystyle x_{2}} 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 x 2 {\displaystyle x_{2}} x_{2} a total of x 1 {\displaystyle x_{1}} x_{1} times, storing results in x 0 {\displaystyle x_{0}} x_{0}.

If then else

An if-then-else statement with if x1 > c then P1 else P2:

xn1:=x1-c; xn2:=0; xn3:=1;
LOOP xn1 DO
  xn2 := 1
  xn3 := 0
END;
LOOP xn2 DO
  P1
END;
LOOP xn3 DO
  P2
END;

See also

Notes and references

  1. ^ Herbert Enderton (2012). Computability Theory. Academic Press.
  2. ^ Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). London: Oxford University Press. p. 105. ISBN 978-3-8274-1824-1. DNB 986529222.
  3. ^ Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). London: Oxford University Press. p. 93. ISBN 978-3-8274-1824-1. DNB 986529222.
  4. ^ Schöning, Uwe (2001). Theoretische Informatik-kurz gefasst (4 ed.). London: Oxford University Press. p. 122. ISBN 3-8274-1099-1.
  5. ^ Schöning, Uwe (2008). Theoretische Informatik-kurz gefasst (5 ed.). London: Oxford University Press. p. 112. ISBN 978-3-8274-1824-1. DNB 986529222.

External links