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 in 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.
Eigenschaften
Aufgrund ihrer Definition terminieren LOOP-Programme für alle Eingaben und definieren daher totale Funktionen. 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). Ein Beispiel für eine berechenbare, aber nicht LOOP-berechenbare totale Funktion ist die Ackermann-Funktion.
Die Menge der LOOP-berechenbaren Funktionen entspricht der Menge der primitiv-rekursiven Funktionen.
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:
Hierbei sind
Variablennamen und
Konstanten.
Semantik
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.
Beispielprogramme
Addition
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, sondern diese Unterprogramme inlined und somit ein Teil des Hauptprogramms werden. 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
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 ELSE
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-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



© biancahoegel.de
Datum der letzten Änderung: Jena, den: 21.09. 2022