BlooP und FlooP - BlooP and FlooP
BlooP und FlooP sind einfache Programmiersprachen, die von Douglas Hofstadter entworfen wurden , um einen Punkt in seinem Buch Gödel, Escher, Bach zu veranschaulichen . BlooP ist eine nicht Turing-vollständige Programmiersprache, deren Hauptsteuerungsflussstruktur eine begrenzte Schleife ist (dh eine Rekursion ist nicht zulässig). Alle Programme in der Sprache müssen beendet werden, und diese Sprache kann nur primitive rekursive Funktionen ausdrücken .
FlooP ist identisch mit BlooP, außer dass es unbegrenzte Schleifen unterstützt. Es ist eine Turing-vollständige Sprache und kann alle berechenbaren Funktionen ausdrücken . Zum Beispiel kann es die Ackermann-Funktion ausdrücken , die (nicht primitiv rekursiv) nicht in BlooP geschrieben werden kann. In Anlehnung an die Standardterminologie der mathematischen Logik nennt Hofstadter die unbegrenzten Schleifen von FlooP MU-Schleifen. Wie alle Turing-vollständigen Programmiersprachen leidet FlooP unter dem Problem des Anhaltens : Programme werden möglicherweise nicht beendet, und es ist im Allgemeinen nicht möglich, zu entscheiden, welche Programme dies tun.
BlooP und FlooP können als Berechnungsmodelle angesehen werden und wurden manchmal beim Unterrichten der Berechenbarkeit verwendet.
BlooP Beispiele
Die einzigen Variablen sind OUTPUT (der Rückgabewert der Prozedur) und (eine unbegrenzte Folge von Variablen mit natürlichen Zahlen, die durch Konstanten indiziert sind, wie in der Unlimited Register Machine ). Die einzigen Operatoren sind ( Zuweisung ), (Addition), (Multiplikation), (kleiner als), (größer als) und (gleich).
CELL(i)⇐+×<>=
Jedes Programm verwendet nur eine endliche Anzahl von Zellen, aber die Zahlen in den Zellen können beliebig groß sein. Datenstrukturen wie Listen oder Stapel können behandelt werden, indem die Nummer in einer Zelle auf bestimmte Weise interpretiert wird, dh indem Gödel die möglichen Strukturen nummeriert .
Kontrollflusskonstrukte umfassen begrenzte Schleifen, bedingte Anweisungen , ABORT Sprünge aus Schleifen und QUIT Sprünge aus Blöcken. BlooP erlaubt keine Rekursion, uneingeschränkte Sprünge oder andere Dinge, die den gleichen Effekt haben würden wie die unbegrenzten Schleifen von FlooP. Benannte Prozeduren können definiert werden, diese können jedoch nur zuvor definierte Prozeduren aufrufen.
Faktorielle Funktion
VERFAHREN FAKTORFAKTORIAL [N]:
BLOCK 0: BEGINNEN
AUSGANG ⇐ 1;
CELL (0) ≤ 1;
SCHLEIFE ZU DEN MEISTEN N MALEN:
BLOCK 1: BEGINNEN
AUSGANG ⇐ AUSGANG × ZELLE (0);
CELL (0) ⇐ CELL (0) + 1;
BLOCK 1: ENDE;
BLOCK 0: ENDE.
Subtraktionsfunktion
Dies ist keine eingebaute Operation und führt (definiert auf natürlichen Zahlen) niemals zu einem negativen Ergebnis (z. B. 2 - 3: = 0). Beachten Sie, dass dies OUTPUT wie alle CELL s bei 0 beginnt und daher keine Initialisierung erfordert.
VERFAHREN MINUS DEFINIEREN [M, N]:
BLOCK 0: BEGINNEN
WENN M <N, DANN:
BLOCK BEENDEN 0;
SCHLEIFE AM MEISTEN M + 1 MAL:
BLOCK 1: BEGINNEN
WENN AUSGANG + N = M, DANN:
ABORT LOOP 1;
AUSGANG ⇐ AUSGANG + 1;
BLOCK 1: ENDE;
BLOCK 0: ENDE.
FlooP Beispiel
Das folgende Beispiel, das implementiert die Funktion Ackermann , einen Stapel unter Verwendung von Simulation beruht auf gödelnummer : das, auf die zuvor definierte numerische Funktionen ist PUSH , POP und TOP erfüllt PUSH [N, S] > 0 , TOP [PUSH [N, S]] = N und POP [PUSH [N, S]] = S . Da ein unbegrenztes MU-LOOP Programm verwendet wird, handelt es sich nicht um ein legales BlooP-Programm. Die QUIT BLOCK Anweisungen in diesem Fall springen zum Ende des Blocks und wiederholen die Schleife im Gegensatz zu der ABORT , die die Schleife verlässt.
VERFAHREN DEFINIEREN ACKERMANN [M, N]: BLOCK 0: BEGINNEN ZELLE (0) ≤ M; AUSGANG ⇐ N; ZELLE (1) ≤ 0; MU-LOOP: BLOCK 1: BEGINNEN WENN ZELLE (0) = 0, DANN: BLOCK 2: BEGINNEN AUSGANG ⇐ AUSGANG + 1; WENN CELL (1) = 0, DANN: ABORT LOOP 1; CELL (0) ⇐ TOP [CELL (1)]; CELL (1) ⇐ POP [CELL (1)]; BLOCK 1 BEENDEN; BLOCK 2: ENDE WENN AUSGANG = 0, DANN: BLOCK 3: BEGINNEN AUSGANG ⇐ 1; CELL (0) ⇐ MINUS [CELL (0), 1]; BLOCK 1 BEENDEN; BLOCK 3: ENDE AUSGANG ⇐ MINUS [AUSGANG, 1]; CELL (1) ⇐ PUSH [MINUS [CELL (0), 1], CELL (1)]; BLOCK 1: ENDE; BLOCK 0: ENDE.