LOOP-Programm

LOOP-Programme sind Programme in der Programmiersprache LOOP, einer stark eingeschränkten, modellhaften Sprache, die nur die Formulierung von Additionen, Wertzuweisungen und endlich oft durchlaufende Schleifen erlaubt. LOOP-Programme spielen in der Theoretischen Informatik eine Rolle, insbesondere im Zusammenhang mit Berechenbarkeit. Eine Funktion heißt LOOP-berechenbar, wenn sie sich als LOOP-Programm formulieren lässt. Die Menge aller LOOP-Programme wird mit <math>\mathit{LOOP}</math> bezeichnet.

Eigenschaften

Aufgrund ihrer Definition terminieren LOOP-Programme für alle Eingaben und definieren daher totale Funktionen<ref></ref>. Damit stehen sie im Kontrast zu GOTO-Programmen und WHILE-Programmen, bei denen eine Terminierung des Programms nicht garantiert ist.

Die Menge der durch LOOP-Programme berechenbaren Funktionen ist eine echte Untermenge der berechenbaren totalen Funktionen (und damit auch eine Untermenge der durch WHILE- bzw. GOTO-Programme berechenbaren Funktionen)<ref name=":0"></ref>. Ein Beispiel für eine berechenbare, aber nicht LOOP-berechenbare totale Funktion ist die Ackermann-Funktion<ref></ref>.

Die Menge der LOOP-berechenbaren Funktionen entspricht der Menge der primitiv-rekursiven Funktionen<ref></ref>.

Formale Definition

Syntax

LOOP-Programme bestehen aus den Symbolen LOOP, DO, END, :=, +, - und ; sowie einer beliebigen Anzahl von Variablen und Konstanten. LOOP-Programme haben folgende Syntax in modifizierter Backus-Naur-Form:

<math>\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} </math> Hierbei sind <math>\mathit{Var} := \{ x_0, x_1, ... \}</math> Variablennamen und <math>c \in \mathbb{N}</math> Konstanten.

Semantik

Ein Ausdruck der Form

x0 := x1 + c

bedeutet die Zuweisung des um <math>c</math> erhöhten Wertes der Variablen <math>x_1</math> an die Variable <math>x_0</math>. Dabei ist für <math>c</math> der Wert Null zulässig, so dass sich auch die direkte Zuweisung des Wertes einer Variablen an eine andere Variable mit diesem syntaktischen Konstrukt formulieren lässt:

x0 := x1 + 0

Ein Ausdruck der Form

x0 := x1 - c

bedeutet die Zuweisung des um <math>c</math> verminderten Wertes der Variablen <math>x_1</math> an die Variable <math>x_0</math>. Bei der Ausführung von Zuweisungen werden negative Werte implizit durch Nullen ersetzt.

Variablen dürfen in Zuweisungsausdrücken gleichzeitig auf der linken und auf der rechten Seite des Symbols := erscheinen. Ein Ausdruck der Form

x := x + c

erhöht beispielsweise den Wert der Variablen <math>x</math> um <math>c</math>.

Die in einem LOOP-Programm verwendeten Variablen werden vor Beginn des Programmablaufs mit vorgegebenen Initialwerten vorbelegt.

Ein Ausdruck der Form

P1; P2

bedeutet die Hintereinanderausführung der Teilprogramme <math>P_1</math> und <math>P_2</math> in dieser Reihenfolge. Ein Ausdruck der Form

LOOP x DO P END

bedeutet die <math>x</math>-fache Ausführung des Teilprogramms <math>P</math>, wobei <math>x</math> den Wert am Beginn der Abarbeitung darstellt. (Auch wenn <math>x</math> durch die Ausführung von <math>P</math> verändert wird, wird <math>P</math> nur so oft ausgeführt, wie <math>x</math> am Anfang war.) Hat <math>x</math> dabei den Wert Null, so wird das Teilprogramm <math>P</math> innerhalb des LOOP-Ausdrucks überhaupt nicht ausgeführt. Dieser Umstand erlaubt die Formulierung von Verzweigungen in LOOP-Programmen durch die bedingte Ausführung von Teilprogrammen in Abhängigkeit vom Wert einer Variablen.

Beispielprogramme

Addition

Das folgende LOOP-Programm weist der Variablen <math>x_0</math> die Summe der Werte der Variablen <math>x_1</math> und <math>x_2</math> zu.

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

Dabei bekommt zunächst <math>x_0</math> den aktuellen Wert von <math>x_1</math> zugewiesen und wird dann um den Wert von <math>x_2</math> inkrementiert.

Dieses Programm lässt sich wie ein Unterprogramm in anderen LOOP-Programmen verwenden. Solche Verwendungen werden durch eine einfache Erweiterung der ursprünglichen LOOP-Syntax in der Form

x0 := x1 + x2

beschrieben.

Dabei gilt zu beachten, dass LOOP-Programme keine Unterprogramme aufrufen können<ref>Till Tantau: In: , S. 154–156; ehemals im Vorlage:Referrer (nicht mehr online verfügbar); abgerufen :  </ref>, sondern diese Unterprogramme inlined und somit ein Teil des Hauptprogramms werden<ref></ref><ref name=":0" />. Andernfalls bestände die Möglichkeit einer zirkulären Abhängigkeit und damit einhergehend der Verlust der endlichen Laufzeit von LOOP-Programmen.

Multiplikation

Das folgende LOOP-Programm erhöht den Wert der Variablen <math>x_0</math> um den Wert des Produktes der Werte der Variablen <math>x_1</math> und <math>x_2</math>.

LOOP x1 DO
  x0 := x0 + x2
END

Das Programm benutzt dabei das im ersten Beispiel definierte Unterprogramm der Addition. Die ausgeführte Multiplikation wird dabei durch das <math>x_1</math>-fache Addieren des Wertes von <math>x_2</math> zum Wert von <math>x_0</math> realisiert.

Durch Einsetzen des LOOP-Programms für die Addition erhält man das äquivalente Programm in der ursprünglichen LOOP-Syntax.

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

IF THEN ELSE

Das folgende LOOP-Programm simuliert eine „if x₁ > c then P1 else P2“-Anweisung, wobei x₁ eine Variable, c eine Konstante und P1, P2 beliebige LOOP-Programme sind. In dem Programm werden drei neue Variablen x_n1, x_n2, x_n3 verwendet.

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;

Das folgende LOOP-Programm simuliert eine „if x₁ = c then P1 else P2“-Anweisung, wobei x₁ eine Variable, c eine Konstante und P1, P2 beliebige LOOP-Programme sind. In dem Programm werden vier neue Variablen x_n1, x_n2, x_n3, x_n4 verwendet.

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 von LOOP-Programmen durch WHILE-Programm

Ein jedes LOOP-Programm

LOOP x DO P END

kann durch das folgende WHILE-Programm simuliert werden

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

Siehe auch

• µ-Rekursion
• WHILE-Programm
• GOTO-Programm

Einzelnachweise

<references />