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 bezeichnet.

EigenschaftenBearbeiten

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 DefinitionBearbeiten

SyntaxBearbeiten

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:

 

Hierbei sind   Variablennamen und   Konstanten.

SemantikBearbeiten

Ein Ausdruck der Form

x0 := x1 + c

bedeutet die Zuweisung des um   erhöhten Wertes der Variablen   an die Variable  . Dabei ist für   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   verminderten Wertes der Variablen   an die Variable  . 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   um  .

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   und   in dieser Reihenfolge. Ein Ausdruck der Form

LOOP x DO P END

bedeutet die  -fache Ausführung des Teilprogramms  , wobei   den Wert am Beginn der Abarbeitung darstellt. (Auch wenn   durch die Ausführung von   verändert wird, wird   nur so oft ausgeführt, wie   am Anfang war.) Hat   dabei den Wert Null, so wird das Teilprogramm   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.

BeispielprogrammeBearbeiten

AdditionBearbeiten

Das folgende LOOP-Programm weist der Variablen   die Summe der Werte der Variablen   und   zu.

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

Dabei bekommt zunächst   den aktuellen Wert von   zugewiesen und wird dann um den Wert von   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[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.

MultiplikationBearbeiten

Das folgende LOOP-Programm erhöht den Wert der Variablen   um den Wert des Produktes der Werte der Variablen   und  .

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  -fache Addieren des Wertes von   zum Wert von   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 ELSEBearbeiten

Das folgende LOOP-Programm simuliert eine if x1 > c then P1 else P2 Anweisung, wobei x1 eine Variable, c eine Konstante und P1, P2 beliebige LOOP-Programme sind. In dem Programm werden drei neue Variablen xn1, xn2, xn3 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 x1 = c then P1 else P2 Anweisung, wobei x1 eine Variable, c eine Konstante und P1, P2 beliebige LOOP-Programme sind. In dem Programm werden vier neue Variablen xn1, xn2, xn3, xn4 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-ProgrammBearbeiten

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 auchBearbeiten

EinzelnachweiseBearbeiten

  1. Uwe Schöning: Theoretische Informatik- kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1, S. 93.
  2. 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.
  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. Prof. Dr. 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 (...)“

LiteraturBearbeiten