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

betrachtet sie sogar als guten Programmierungsstil. Verschachtelte Schleifen dieser Art kommen auch in Anweisungen für die Zusammensetzung alltäglicher Dinge vor und bei Tätigkeiten wie Stricken oder Häkeln — wobei ganz kleine Schleifen mehrere Male in größeren Schleifen wiederholt werden, die ihrerseits wiederholt ausgeführt werden ... Während das Ergebnis einer Schleife auf einer tieferen Ebene vielleicht nicht mehr ist als ein paar Stiche, kann das Ergebnis einer Schleife auf hoher Ebene ein wesentlicher Teil eines Kleidungsstückes sein.
    Auch in der Musik treten häufig verschachtelte Schleifen auf — so zum Beispiel, wenn eine Tonleiter (eine kleine Schleife) verschiedene Male hintereinander gespielt wird, vielleicht jedesmal mit einer Verschiebung in der Tonhöhe. Zum Beispiel enthalten die letzten Sätze sowohl von Prokofieffs Fünftem Klavierkonzert wie von Rachmaninoffs Zweiter Symphonie ausgedehnte Passagen, in denen schmale, gemäßigte und langsame Tonleiter-Schleifen von verschiedenen Instrumentengruppen gleichzeitig gespielt werden — mit starker Wirkung. Die Tonleitern gehen bei Prokofieff nach oben, bei Rachmaninoff nach unten. Man kann auswählen.
    Ein allgemeinerer Begriff ist der des Unterprogramms oder der Prozedur, worauf wir bereits etwas eingegangen sind. Dabei ist die Grundvorstellung die, daß eine Gruppe von Operationen gebündelt und als eine einzige Einheit mit einem Namen aufgefaßt wird — so die Prozedur BLUMIGES SUBSTANTIV . Wie wir bei den RTN-Verfahren sahen, können Prozeduren einander mit Namen aufrufen und damit sehr konzis Folgen von auszuführenden Operationen ausdrücken. Das ist das Wesen der Modularität beim Programmieren. Modularität tritt natürlich bei Hi-Fi-Systemen, bei Möbeln, bei lebenden Zellen, in der menschlichen Gesellschaft auf — wo immer eine hierarchische Organisation besteht.
    Ab und an benötigt man eine Prozedur, die sich je nach dem Zusammenhang variieren läßt: Eine solche Prozedur kann entweder mit einer Möglichkeit ausgestattet werden, das im Gedächtnis Gespeicherte zu überprüfen und entsprechend zu handeln, oder man kann ihr explizit eine Liste von Parametern eingeben, die die Wahl der vorzunehmenden Handlung bestimmt. Manchmal verwendet man beide Methoden. In der RTN-Terminologie ist die Wahl der Reihenfolge der auszuführenden Handlungen gleichbedeutend mit der Wahl des einzuschlagenden Weges. Ein RTN, das mit Parametern und Bedingungen gefüttert ist, die die Wahl des Weges in seinem Inneren bestimmen, heißt „Ausgebautes“ Transitions-Netzwerk“ (ATN). Ein Gebiet, auf dem ATNs den RTNs vielleicht vorzuziehen sind, ist das der Erzeugung vernünftiger — im Gegensatz zu unsinnigen — deutscher Sätze aus nackten Wörtern gemäß der Grammatik, die in einer Anzahl von ATNs repräsentiert ist. Die Parameter und Bedingungen würden uns erlauben, verschiedene semantische Einschränkungen einzugeben, so daß rein zufällige Zusammenstellungen wie „ein undankbares Frühstück“ verboten wären. Mehr darüber in Kapitel XVIII.
Rekursion in Schachprogrammen
    Ein klassisches Beispiel für einen rekursiven Vorgang mit Parametern ist die Prozedur für die Wahl des „besten“ Zugs beim Schach. Der beste Zug ist offensichtlich der, der den Gegner in der schwierigsten Lage beläßt. Deshalb ist ein Test für die Güte eines Zugs einfach: Nimm an, du hättest den Zug ausgeführt, und beurteile dann die Stellung vom Standpunkt deines Gegners aus. Wie aber beurteilt er die Stellung? Nun, er sucht nach seinem besten Zug. Das heißt, er mustert im Geist alle möglichen Züge und beurteilt sie von dem Standpunkt aus, den er für den deinigen hält, in der Hoffnung, daß die Stellung dir jetzt schlecht vorkommt. Beachte aber, daß wir nunmehr „bester Zug“ rekursiv definiert haben, indem wir einfach von dem Grundsatz Gebrauch machten, daß was für die eine Seite das Beste, für die andere das Schlechteste ist. Die rekursive Prozedur, die nach dem besten Zug sucht, geht so vor, daß sie einen Zug ausprobiert — und dann in der Rolle des Gegners sich selbst aufruft! Als solcher versucht sie einen anderen Zug und ruft sich selbst in der Rolle des Gegners ihres Gegners auf — das heißt, sich selbst.
    Die Rekursion kann mehrere Stufen tief sein — aber irgendwo muß sie auslaufen! Wie kann man eine Stellung auf dem Brett beurteilen, ohne vorauszuschauen? Zu diesem Zweck gibt es eine Anzahl nützlicher Kriterien, wie z. B. einfach die