Gödel, Escher, Bach - ein Endloses Geflochtenes Band

werden wir bald merken, daß wir eine Kontrollstruktur einschließen müssen, d. h. eine Beschreibung der Reihenfolge, in der die Dinge zu tun sind, wann wir zurückgehen und etwas von neuem versuchen, wann wir eine Anzahl von Schritten überspringen, wann wir anhalten sollen usw.
    Es ist für jeden Algorithmus — das ist eine spezifische Beschreibung, wie eine Aufgabe auszuführen ist — typisch, daß er eine Mischung von 1) spezifisch durchzuführenden Operationen und 2) Kontrollbefehlen enthält. Bei der Entwicklung unserer Sprache, um voraussagbar lange Rechnungen auszudrücken, werden wir deshalb gleich zu Anfang Kontrollstrukturen einbeziehen müssen. Tatsächlich ist das Merkmal von BlooP die beschränkte Anzahl von Kontrollstrukturen. Es erlaubt nicht, zu irgendeinem Schritt zu springen oder Gruppen von Schritten unbeschränkt oft zu wiederholen. In BlooP ist im wesentlichen die einzige Kontrollstruktur die begrenzte Schleife („bounded loop“): eine Gruppe von Befehlen, die immer wieder bis zu einer im voraus definierten Maximalanzahl, die man Obergrenze der Schleife nennt, ausgeführt werden kann. Wenn die Obergrenze 300 wäre, dann könnte die Schleife 0,7- oder 300mal ausgeführt werden, nicht aber 301mal .
    Nun brauchen die genauen Werte aller Obergrenzen in einem Programm vom Programmierer nicht numerisch eingegeben zu werden — vielleicht kennt man sie gar nicht im voraus. Dafür kann jede Obergrenze rechnerisch bestimmt werden, bevor man in die Schleife eintritt. Will man z. B. den Wert von 2 3 n berechnen, brauchte man zwei Schleifen. Zuerst berechnet man 3 n , was n Multiplikationen erfordert. Darauf nimmt man 2 hoch diese Zahl, was 3 n Multiplikationen erfordert. So ist also die Obergrenze für die zweite Schleife das Ergebnis der Berechnung der ersten Schleife.
    Im BlooP-Programm würde man das so ausdrücken:
    PROZEDURDEFINITION „ZWEI-HOCH-DREI-HOCH“ [N]:
    BLOCK 0: ANFANG
    ZELLE (0)1;
    SCHLEIFE N MAL:
    BLOCK 1: ANFANG
    ZELLE (0)3 x ZELLE (0)
    BLOCK 1: ENDE
    ZELLE (1)1;
    SCHLEIFE ZELLE (0) MAL:
    BLOCK 2: ANFANG
    ZELLE (1)2 x ZELLE (1);
    BLOCK 2: ENDE
    OUTPUT1 ZELLE (1);
    BLOCK 0: ENDE.
BlooP-Konventionen
    Nun gehört ein wenig Erfahrung dazu, sich einen in einer Computersprache abgefaßten Algorithmus anzusehen und sich ein Bild davon zu machen, was er bewirkt. Indessen hoffe ich, daß dieser Algorithmus einfach genug ist, um ohne viel Nachprüfung verständlich zu sein. Es wird eine Prozedur definiert, die einen Input-Parameter besitzt, N ; der Output ist dann der gesuchte Wert.
    Diese Definition der Prozedur besitzt eine sogenannte Block-Struktur, und das bedeutet, daß gewisse Teile als Einheiten oder Blöcke zu betrachten sind. Alle Befehle in einem Block werden als Einheit ausgeführt. Jeder Block hat eine Nummer (der äußerste ist BLOCK 0 ) und wird abgegrenzt durch ANFANG und ENDE . In unserem Beispiel enthalten BLOCK 1 und BLOCK 2 je einen Befehl — aber wir werden in Kürze längere Blöcke zu Gesicht bekommen. Ein SCHLEIFE -Befehl bedeutet immer, daß der unmittelbar darunterstehende Block wiederholt auszuführen ist. Wie aus dem Obigen ersichtlich, können Blöcke verschachtelt sein.
    Die Strategie des vorstehenden Algorithmus haben wir schon früher beschrieben. Man beginnt damit, daß man eine Hilfsvariable, genannt ZELLE (0) nimmt. Man setzt sie zu Beginn gleich 1, und dann multipliziert man sie in einer Schleife wiederholt mit 3, bis man das genau N mal getan hat. Als nächstes führt man das Analoge für ZELLE (1) aus, setzt sie gleich 1, multipliziert genau ZELLE (0) mal mit 2, und hört auf. Schließlich nimmt man ZELLE (1) als Wert von OUTPUT . Dies ist der Wert, der an die Außenwelt geht — das einzige äußerlich sichtbare Verhalten der Prozedur.
    Hier wäre noch etwas zur Notation zu sagen. Zunächst einmal bedeutet der nach links weisende Pfeil „“:
    Berechne den Ausdruck rechts vom Pfeil, dann nimm das Ergebnis
und setze diesen Wert für ZELLE (oder OUTPUT ) links vom Pfeil ein.
    So ist die Bedeutung eines Befehls wie etwa ZELLE (1) 3 × ZELLE (1) einfach, den in ZELLE (1) gespeicherten Wert im Speicher zu verdreifachen. Man kann sich jede ZELLE als separates Wort im Gedächtnis von irgendeinem Computer vorstellen. Der einzige Unterschied zwischen einer ZELLE und einem Wort ist eigentlich bloß der, daß das letztere nur ganze Zahlen bis zu einer endlichen Grenze enthalten kann, während eine ZELLE eine beliebige Zahl, so groß sie auch sein mag, enthalten