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 ${\mathit {LOOP}}$ bezeichnet.

Eigenschaften

Aufgrund ihrer Definition terminieren LOOP-Programme für alle Eingaben und definieren daher totale Funktionen^[1]. 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)^[2]. Ein Beispiel für eine berechenbare, aber nicht LOOP-berechenbare totale Funktion ist die Ackermann-Funktion^[3].

Die Menge der LOOP-berechenbaren Funktionen entspricht der Menge der primitiv-rekursiven Funktionen^[4].

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:

{\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}}

Hierbei sind ${\mathit {Var}}:=\{x_{0},x_{1},...\}$ Variablennamen und $c\in \mathbb {N}$ Konstanten.

Semantik

Ein Ausdruck der Form

x₀ := x₁ + c

bedeutet die Zuweisung des um $c$ erhöhten Wertes der Variablen $x_{1}$ an die Variable $x_{0}$ . Dabei ist für $c$ 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:

x₀ := x₁ + 0

Ein Ausdruck der Form

x₀ := x₁ - c

bedeutet die Zuweisung des um $c$ verminderten Wertes der Variablen $x_{1}$ an die Variable $x_{0}$ . 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 $x$ um $c$ .

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

Ein Ausdruck der Form

P₁; P₂

bedeutet die Hintereinanderausführung der Teilprogramme $P_{1}$ und $P_{2}$ in dieser Reihenfolge. Ein Ausdruck der Form

LOOP x DO P END

bedeutet die $x$ -fache Ausführung des Teilprogramms $P$ , wobei $x$ den Wert am Beginn der Abarbeitung darstellt. (Auch wenn $x$ durch die Ausführung von $P$ verändert wird, wird $P$ nur so oft ausgeführt, wie $x$ am Anfang war.) Hat $x$ dabei den Wert Null, so wird das Teilprogramm $P$ 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 $x_{0}$ die Summe der Werte der Variablen $x_{1}$ und $x_{2}$ zu.

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

Dabei bekommt zunächst $x_{0}$ den aktuellen Wert von $x_{1}$ zugewiesen und wird dann um den Wert von $x_{2}$ 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

x₀ := x₁ + x₂

beschrieben.

Dabei gilt zu beachten, dass LOOP-Programme keine Unterprogramme aufrufen können^[5], sondern diese Unterprogramme inlined und somit ein Teil des Hauptprogramms werden^[6]^[2]. 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 $x_{0}$ um den Wert des Produktes der Werte der Variablen $x_{1}$ und $x_{2}$ .

LOOP x₁ DO
  x₀ := x₀ + x₂
END

Das Programm benutzt dabei das im ersten Beispiel definierte Unterprogramm der Addition. Die ausgeführte Multiplikation wird dabei durch das $x_{1}$ -fache Addieren des Wertes von $x_{2}$ zum Wert von $x_{0}$ realisiert.

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

LOOP x₁ DO
  x₀ := x₀ + 0;
  LOOP x₂ DO
    x₀ := x₀ + 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.

x_n1:=x₁-c; x_n2:=0; x_n3:=1;
LOOP x_n1 DO
  x_n2 := 1
  x_n3 := 0
END;
LOOP x_n2 DO
  P1
END;
LOOP x_n3 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.

x_n1:=x₁-(c-1); x_n2:=x₁-c; x_n3:=1; x_n4:=1;
LOOP x_n1 DO
  LOOP x_n2 DO
     x_n3:=0;
  END;
  LOOP x_n3 DO
     P1;
     x_n4:=0;
  END
END;
LOOP x_n4 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

Einzelnachweise

↑ Uwe Schöning: Theoretische Informatik- kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1, S. 93.
↑ ^a ^b Uwe Schöning: Theoretische Informatik- kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1, S. 93,94.
↑ Uwe Schöning: Theoretische Informatik- kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1, S. 94,112.
↑ Uwe Schöning: Theoretische Informatik- kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1, S. 105.
↑ Till Tantau: Vorlesungsskript Theoretische Informatik. In: Institut für Theoretische Informatik - Universität zu Lübeck. 12. Februar 2010, S. 154–156, abgerufen am 23. Januar 2019: „Unterprogramme sind nicht erlaubt.“
↑ Uwe Schöning: Theoretische Informatik - kurz gefasst. 5. Auflage. Spektrum Akademisch Verlag, S. 102: „Die Funktion g (...) kann formal durch eine entsprechende Einsetzung definiert werden (...)“

Literatur

Uwe Schöning: Theoretische Informatik - kurzgefasst. 4. Auflage. Spektrum Akademischer Verlag, 2001, ISBN 3-8274-1099-1.

[1] Uwe Schöning: Theoretische Informatik- kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1, S. 93.

[:0-2] Uwe Schöning: Theoretische Informatik- kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1, S. 93,94.

[3] Uwe Schöning: Theoretische Informatik- kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1, S. 94,112.

[4] Uwe Schöning: Theoretische Informatik- kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1, S. 105.

[5] Till Tantau: Vorlesungsskript Theoretische Informatik. In: Institut für Theoretische Informatik - Universität zu Lübeck. 12. Februar 2010, S. 154–156, abgerufen am 23. Januar 2019: „Unterprogramme sind nicht erlaubt.“

[6] Uwe Schöning: Theoretische Informatik - kurz gefasst. 5. Auflage. Spektrum Akademisch Verlag, S. 102: „Die Funktion g (...) kann formal durch eine entsprechende Einsetzung definiert werden (...)“

[1]

[2]

[3]

[4]

[5]

[6]