Algorithmische Sprache und Programmentwicklung

Muhammed ibn Musa abu Djafar al-Choresmi (auch Al Khwarizmi, al-Khowârizmĭ, al-Hwârazmî geschrieben), geboren etwa 780, gestorben etwa 850, aus dem südöstlich des Aral-Sees gelegenen Choresmien in der heutigen Sowjetrepublik Usbekistan stammend, lebte in Bagdad, im „Haus der Weisheit” des Kalifen al-Mamun, zu den Zeiten, als die Hauptwerke der griechischen Mathematiker ins Arabische übertragen wurden. Sein Werk „Aufgabensammlung für Kaufleute und Testamentvollstrecker” zeigt in Bezeichnungen und in der algebraisierenden Tendenz auch indischen Einfluß. Die lateinische Übersetzung wurde später liber algorithmi genannt. Der im 15. Jh. aufkommende Gegensatz zwischen den mit Ziffern rechnenden Algorithmikern (ihre Kunstfertigkeit stammte aus den algorismus-Schriften der Scholastiker, aus Übersetzungen und Bearbeitungen aus dem Arabischen) und den Abacisten, die, vom (römischen) Abacus herkommend, das Rechnen „auf den Linien“ lehrten und sich bis ins 17. Jh. hielten (in Rußland bis heute), ist auf zeitgenössischen Holzschnitten abgebildet (Abb. 0.1).

In diesem Kapitel sollen, einen allgemeinen Algorithmenbegriff naiv voraussetzend, Rechenvorschriften eingeführt und in ihrem Aufbau untersucht werden. Besondere Beachtung erfordern dabei rekursive Rechenvorschriften und Systeme. Es ist zunächst wenig erheblich, von welcher Art und Sorte die Objekte solcher Rechenvorschriften sind, sie werden als primitive Objektmengen zusammen mit gewissen, ihnen eigentümlichen primitiven Operationen vorausgesetzt (Tab. 1.3.1). Erst im nächsten (und übernächsten) Kapitel wird auf den Aufbau von Objektmengen und auf die eventuelle innere Struktur von Objekten eingegangen.

Dieses Kapitel geht von den Begriffen Objekt und Objektmenge aus. Es werden insbesondere strukturierte Objekte eingeführt, wobei die Strukturierung auch rekursiv sein kann. Wichtige Beispiele wie Sequenzen und Kaskaden werden ausführlicher behandelt.

Die Kellermaschine benötigt Protokollkeller und Wertekeller, um „hängende” Operationen und dazugehörige Operanden aufzunehmen. Bei repetitiven Rechenvorschriften und Systemen entfällt diese Notwendigkeit, die Kellermaschine kann zu einer Babbage-Zuse-Maschine entarten. In diesem Kapitel werden Methoden und Ansätze besprochen, die der Überführung gewisser rekursiver Rechenvorschriften in repetitive Form dienen können. Die Überlegungen schließen trivialerweise hierarchisch-gestufte Systeme von Rechenvorschriften ein.

Die ersten vier Kapitel dieses Buches kamen ohne Programmvariable aus. Mindestens auf drei begrifflich voneinander unabhängigen Wegen kann man zu Programmvariablen kommen. In 5.1.1 charakterisieren wir (zusammengesetzte) Programmvariable als verkümmerte Wertekeller für den Fall, daß die Kellermaschine nur repetitive Programme verarbeitet. In 5.1.2 wird die Wertverlaufsmaschine eingeführt, eine nicht-universelle Maschine, die auf die Berechnung von primitiv rekursiven Funktionen beschränkt ist. In einem gewissen Spezialfall (der n-gliedrigen Rekursion) entsteht eine Verkümmerung, die Schiebe-Variable, für n = 2 insbesondere die gewöhnliche Programmvariable. Programmvariable können ferner aufgefaßt werden als begriffliche Erweiterungen von Resultatparametern (1.14.2), mit sequentialisierter, „variabler” Zuordnung. In diesem Sinne werden wir in 5.2 auf einem Programmvariablenbegriff aufbauen, der auf dem Gedanken der „Einsparung von Objektbezeichnungen” beruht.

Die Einführung von Variablen im vorigen Kapitel erlaubt nun, den Ablauf rekursiver Systeme freizulegen. In diesem Kapitel werden Hilfsmittel zur expliziten Beschreibung von Abläufen eingeführt. Dabei braucht man sich nicht auf sequentielle Abläufe zu beschränken. Zur Illustration koordinierter Abläufe werden Petri-Netze herangezogen.

In diesem Kapitel wird Programmvariablen ein gewisser Objektcharakter zugebilligt: sie können beispielsweise als Bestandteile von Zusammensetzungen auftreten (‚organisierte Speicher‘). Die sich damit ergebenden Notwendigkeiten — etwa „Erzeugung” von Variablen —, Besonderheiten hinsichtlich der Identität wie auch die Möglichkeiten der Implementierung rekursiv definierter Objektstrukturen mittels organisierter Speicher werden erörtert. Die Bildung von Nexen von Variablen führt nach Übergang zu einem anderen semantischen Modell zur Einführung von Zeigern und der Bildung von Geflechten. Schließlich wird der Übergang zu Adressen diskutiert. Diese Begriffe führen an eine Grenze heran, hinter der die eigentliche Domäne der maschinennahen (System-)Programmierung erst beginnt. Für Weiterführungen und Ergänzungen siehe: G. Seegmüller, „Einführung in die Systemprogrammierung” (Mannheim 1974). Es kommt uns hier jedoch darauf an, zu zeigen, daß man zunächst keine spezielle Maschinenorganisation an die Spitze der Darlegung stellen muß.

Um ein kompliziertes Problem zu lösen, kann man zwei extreme Wege einschlagen: Man benutzt eine hinreichend komplizierte Maschine und hat dann die Aussicht, eine „einfache” Lösung zu finden, oder man benutzt eine einfache Maschine und muß mit einer „komplizierten” Lösung rechnen.