LOOP program

LOOP programs are programs in the programming language LOOP , a highly restricted, model-like language that only allows the formulation of additions , value assignments and loops that run through a finite number of times . LOOP programs play a role in theoretical computer science , especially in connection with predictability . A function is called LOOP-calculable if it can be formulated as a LOOP program. The set of all LOOP programs is denoted by. ${\displaystyle {\mathit {LOOP}}}$

properties

Due to their definition, LOOP programs terminate for all inputs and therefore define total functions . This is in contrast to GOTO programs and WHILE programs , in which a termination of the program is not guaranteed.

The set of functions that can be calculated using LOOP programs is a real subset of the total functions that can be calculated (and thus also a subset of the functions that can be calculated using WHILE or GOTO programs). The Ackermann function is an example of a total function that can be calculated but cannot be calculated as a LOOP .

The set of LOOP-computable functions corresponds to the set of primitive-recursive functions .

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

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

semantics

An expression of form

x0 := x1 + c

means the assignment of the increased value of the variable to the variable . It is for permissible value of zero, then the direct assignment of the value that a variable to another variable with this syntactic construct can be formulated: ${\displaystyle c}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{0}}$ ${\displaystyle c}$

x0 := x1 + 0

An expression of form

x0 := x1 - c

means the assignment of the value of the variable reduced by the variable . When executing assignments, negative values ​​are implicitly replaced by zeros. ${\displaystyle c}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{0}}$

Variables can appear in assignment expressions on the left and on the right side of the symbol at the same time :=. An expression of form

x := x + c

for example increases the value of the variable by . ${\displaystyle x}$ ${\displaystyle c}$

The variables used in a LOOP program are pre-assigned with specified initial values ​​before the program is started.

An expression of form

P1; P2

means the execution of the program units one after the other and in this order. An expression of form ${\displaystyle P_{1}}$ ${\displaystyle P_{2}}$

LOOP x DO P END

means the multiple execution of the program unit , where represents the value at the start of processing. (Even if changes are made by executing, execution is only carried out as often as was at the beginning.) If this has the value zero, the program unit within the LOOP expression is not executed at all. This fact allows the formulation of branches in LOOP programs through the conditional execution of program units depending on the value of a variable. ${\displaystyle x}$ ${\displaystyle P}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle P}$

Sample programs

addition

The following LOOP program assigns the sum of the values ​​of the variables and to the variable . ${\displaystyle x_{0}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$

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

The current value of is initially assigned and is then incremented by the value of . ${\displaystyle x_{0}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$

This program can be used like a subroutine in other LOOP programs. Such uses are made possible by a simple extension of the original LOOP syntax in the form

x0 := x1 + x2

described.

It should be noted that LOOP programs cannot call subprograms, but rather these subprograms are inlined and thus become part of the main program. Otherwise, there would be the possibility of a circular dependency and the associated loss of the finite runtime of LOOP programs.

multiplication

The following LOOP program increases the value of the variable by the value of the product of the values ​​of the variables and . ${\displaystyle x_{0}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$

LOOP x1 DO
  x0 := x0 + x2
END

The program uses the addition subroutine defined in the first example. The executed multiplication is realized by adding the value of to the value of . ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{0}}$

By using the LOOP program for the addition, you get the equivalent program in the original LOOP syntax.

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

IF THEN ELSE

The following LOOP program simulates an if x ₁ > c then P1 else P2 statement, where x _{1 is} a variable, c is a constant and P1, P2 are any LOOP programs. Three new variables x _n1 , x _n2 , x _n3 are used in the program.

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;

The following LOOP program simulates an if x ₁ = c then P1 else P2 statement, where x _{1 is} a variable, c is a constant and P1, P2 are any LOOP programs. Four new variables x _n1 , x _n2 , x _n3 , x _n4 are used in the program.

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

Simulation of LOOP programs using the WHILE program

Every LOOP program

LOOP x DO P END

can be simulated by the following WHILE program

y := x
WHILE y != 0 DO y := y-1; P END

See also

• µ recursion
• WHILE program
• GOTO program

Individual evidence

1. ↑ Uwe Schöning : Theoretical Computer Science - in short . 5th edition. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1 , p. 93 .
2. ↑ ^{a b} Uwe Schöning : Theoretical Computer Science - in short . 5th edition. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1 , p. 93.94 .
3. ↑ Uwe Schöning : Theoretical Computer Science - in short . 5th edition. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1 , p. 94.112 .
4. ↑ Uwe Schöning : Theoretical Computer Science - in short . 5th edition. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1 , p. 105 .
5. ↑ Prof. Dr. Till Tantau: Theoretical Computer Science lecture notes. In: Institute for Theoretical Computer Science - University of Lübeck. February 12, 2010, pp. 154–156 , accessed on January 23, 2019 : "Sub-programs are not permitted." 
6. ↑ Uwe Schöning: Theoretical Computer Science - in brief . 5th edition. Spektrum Akademisch Verlag, p. 102 : "The function g (...) can be formally defined by an appropriate substitution (...)"

literature

• Uwe Schöning : Theoretical Computer Science - in a nutshell . 4th edition. Spectrum Academic Publishing House, 2001, ISBN 3-8274-1099-1 .