Charakteristische Bestandteile der Begriffswelt von LISP

 

Einleitung

Um zu einem tieferen Verständnis der konkreten Gestalt einer Programmiersprache zu gelangen, mu\ssman sie in Zusammenhang mit anderenWissenschaftsgebieten betrachten. Man stellt gegenwärtig fast ausschließlich semantische und syntaktische Fragen, um das Beschreibungsproblem anzugehen; pragmatische Überlegungen sindbisher nahezu völlig übergangen worden.

Auch die eleganteste Beschreibungsmethode kann nicht sichern, daß die Objektsprache überhaupt benutzt werden wird. Hier sind neben Fragen der Ästhetik, solchen der Verfügbarkeit, Bequemlichkeit, nicht zuletzt solchen der Firmenpolitik, auch unbedingt die nach der Verknüpfung der Sprachkonzepte mit dem Vorwissen der Programmierer zu beantworten. Eine Sprache paßt sich durch ihre Entwickler, mehr (durch Betonung von ``modernen'' Konzeptionen) oder weniger gewollt, in eine Tradition von Notationsweisen ein. Für diese sind die Hintergründe der Ideen wesentlich, auf die sich der Entwickler bezog. Das gilt ganz stark für LISP mit seiner Bezugnahme auf theoretische Konzepte der Mathematik.

Neben diesen begrifflichen Verschränkungen durch die Anknüpfung an die Begriffswelt des Entwerfers der Sprache enthalten die meisten Programmiersprachen neuartige Lösungsansätze zurBewältigung programmtechnischer Probleme. Diese sind oft zurZeit der Sprachentwicklung nur unklar wissenschaftlich erfaßt worden und müssen daher zu zeitlich späteren Analysen und Verallgemeinerungen in dem betreffenden Bereich in Beziehungen gesetzt werden.

Dabei hat man zwei Aspekte zu beachten: Einmal stellt die Programmiersprache als Notationsmittel in jeden Fall insgesamt eine Antwort auf die methodischen Probleme der Programmierung dar. Ob eine Anweisungs- oder eine Ausdruckssprache vorliegt, ob Sprünge zu allen möglichen Stellen bzw. Zugriffe zu Variablen beliebiger Ebenen gestattet werden, ist hier zu sichten und zu werten. Zum zweiten waren die frühen Programmiersprachen (und ist jede wesentlich neue) mit neuartigen Implementierungsproblemen verknüpft. Blockkonzept und Felder mit variablen Grenzen erzwingen Kellerspeicher und zweifache Verkettung der Variablenbereiche (activation records) zur korrekten Führung des Programmablaufs und zur richtigen Adressierung erreichberer Variabler (dynamische und statische Kette). Rekursive Funktionen erzwingen ebenfalls den Kellerspeicher. Listen oder ähnliche Strukturen mit schwer vorhersehbaren Umfängen erfordern dynamische Speicherplatzverwaltung. Parallelverarbeitbare Anweisungsfolgen führen zu Lösungsversuchen für die Synchronisation usw. usf.

Für LISP ist eine Reihe von Beziehungen zur mathematischen Logik, genauer gesagt, zur Algorithmentheorie, wesentlich, weil J.McCarthy, der Schöpferdieser Programmiersprache, auf gewisse Teilresultate bzw. spezielle Ausformungen von Kalkülen auf diesem Bereich bewußt aufgebaut hatte. Wenn auch ein guter Teil des heute benutzten LISP durch einen Zufall in der Entwicklungsgeschichte (vgl. Kapitel 4) einige der {\sc McCarthy}schen Ideen in völlig veränderter Gestalt präsentiert, steht die Sprache immer noch in engem Zusammenhang zu diesen Basisbegriffen.

Im einzelnen werden diese Verknüpfungen mit Begriffen der Algorithmentheorie deutlich in der Betonung der (potentiellen) Rekursivität der LISP-Funktionen, der Verwendung deslambda-Operators für die Bezeichnung funktionaler Ausdrücke undder Auswahl von Ausdrücken (Termen) als Grundbestandteile der Sprache stattvon Anweisungen (statements). Um diesen Herkunftsbeziehungen gerecht zu werden, sollen in diesem Kapitel die Begriffe {\em rekursive Funktionen}, lambda-Kalkül und Ausdrucksspracheerläutert werden.

Neben den Elementen der Begriffswelt von LISP, die aus Bereichen der mathematischen Theorie stammen, sind in ihr eine ganze Reihe von (seinerzeit höchst aktuellen) Begriffen aus der Programmierungstechnik enthalten. Da LISP eine Sprache zur Symbolverarbeitung (im Gegensatz zu numerischen Rechnungen) sein sollte, lag es zum damaligen Zeitpunkt (1957-58) nahe, auf der Listenverarbeitung aufzubauen -- eine noch heutefolgenreiche (im positiven Sinne) Entscheidung. McCarthysVorliebe für interaktive Arbeit im Dialog mit dem Rechner (die für die Entwicklung der Time-Sharing-Systeme wichtige Impulse geliefert hat) führte im Zusammenhang mit dem besagten historischen Zufall in der LISP-Geschichte zur Betonung der Charakteristika Dialogsprache, interpretative Abarbeitung und der Besonderheit, da\ss{\em Programme alsDaten} auffaßbar sind. Obwohl 1960 noch niemand den Begriff der virtuellen Maschine benutzte, stellte die Orientierung von LISP auf diefreie Verfügbarkeit und einfache Neudefinierbarkeit von Funktionen praktisch eine Vorwegnahme dieser wesentlichen Ideen der strukturierten Programmierung dar. Da\ssein Programmierer durch Aufbau einer geeignetenMengen von Funktionen eine Gesamtheit von Basisoperationen für andere zur Verfügung stellen kann, mit der diese dann umgehen, als seien es die implementierten Grundfunktionen, ist in LISP-Kreisen immer bekannt gewesen und bewußt gepflegt worden.

Mit der Weiterentwicklung von LISP sind an die Sprache neue Forderungen (vgl. [BO73b]) herangetragen worden, die mittels des Ausbausangelegter Möglichkeiten befriedigt werden konnte. Dazu gehören das Verlangen nach allgemeineren Steuerungsmöglichkeiten des Rechenablaufs (globale Exits u. dgl.), nach allgemeineren Parameterübergabemechanismen (statt Wertübergabe (call by value)) und nach Zeichenkettenverarbeitung. Andere Erweiterungen, wie Mustervergleichsmittel, zielorientierte Funktionsaufrufe usw., sind bisher nur in überlagernden höheren Sprachen {\tx(MLISP2, QLISP)} verwirklicht worden. Dies liegt hauptsächlich an dem Fehlen einer allgemein akzeptierten, harmonischen und effizienten Lösung.

Die angegebenen Begriffe werden nun der Reihe nach besprochen.

 

Rekursive Funktionen

 

Rekursive Funktionen in der Informationsverarbeitung

\footnote{Vgl. auch R.Peter [PE76} und W.H.Burge [BER75].]

 

LISP ist eine Programmiersprache, die hauptsächtlich für Probleme der nichtnumerischen Informationsverarbeitung gedacht ist. Diese erfordert im Wesentlichen die Verarbeitung symbolischer Datenstrukturen. Das sind Objekte, die innerhalb von Kalkülen der mathematischen Logik gewöhnlich formale Ausdrücke genannt werden. Als allgemeinbekanntes Beispiel sollen hier die mathematischen Ausdrücke (arithmetischen Ausdrücke) erwähnt werden. Schon bei ihrer Einführung in solch einem Kalkül treffen wir auf die Rekursivität, den Selbstbezug der Definitionsklauseln:

(A1) Alle Variablen und Zahlen sind arithmetische Ausdrücke.
(A2) Sind a und b arithmetische Ausdrücke, so giltdies auch für (a + b),   (a - b), (a * b) und (a/b).(A3) Jeder arithmetische Ausdruck ist durch Anwendung der Regel (A1) und
  (A2) definiert.

In der Klausel (A2) kommt diese Rekursivität zum Ausdruck. Die Einfachheit, mit der mittels rekursivem Bezug diese Ausdrucksklasse eingeführt werden kann, bewog Hoare [HOA73],auch in Programmiersprachen für Datenstrukturdefinitionen rekursive Methoden vorzuschlagen.

Ausdrücke mit ähnlicher Struktur haben eine wichtige und einleuchtende Eigenschaft: Jeder Operand eines zweistelligenOperators kann im Prinzip {\em ein beliebig komplizierterAusdruck sein}; im Spezialfall kann dieser wiederum den gleichen Operator und zwei Operanden enthalten.

\vspace{3mm}

\begin{center}$A = A_{1} + A_{2}$

$A_{1} = A_{11} + A_{12}$.\end{center}

\vspace{3mm}

Aus dieser Möglichkeit folgt, da\ssbei der Analyse bzw.Verarbeitung solcher Ausdrücke sehr oft die potentiell gleiche Analyse auch für Teilausdrücke durchzuführen ist.

Mögen etwa arithmetische Ausdrücke einer Transformation {\bsl T} zu unterziehen sein, dann wird diese erreicht, indem man sie auf die Operanden anwendet und die so erzielten Teilergebnisse in einer Art zusammenfügt, die vom Operator des Ausdrucks abhängig ist:

\vspace{3mm}

\begin{center}{\bsl T}$(A) = komp\{op\}(${\bsl T}$(A_{1}), ${\bsl T}$(A_{2}))$.\end{center}

\vspace{3mm}

Ein überschaubares Beispiel für eine derartige Problematik stellt das Problem des symbolischen Differenzierung eines arithmetischen Ausdrucks dar. Neben den Grundregeln für die Differentiation von einfachen Operanden (z.B. die Ableitung einer Konstanten ist 0) stehen die rekursiven Regeln für die zusammengesetzten Ausdrücke. Im Fall der Summenregel werden die Teile durch Summation zusammengefügt:

\vspace{3mm}

\begin{center}$(S1 + S2)'= S1'+ S2'$ (d.h. $komp\{+\}$ ist $+$).\end{center}

\vspace{3mm}

Ähnlich werden Produktregel und Kettenregel formuliert:

\vspace{3mm}

\begin{center}$(S2 * S2)'= S1'* S2 + S1 * S2',$

$F(S)' = F'(S) * S'.$\end{center}

\vspace{3mm}

Problemsituationen, die der bei der symbolischen Differentiation vergleichbar sind, treten in der nichtnumerischen Informationsverarbeitung überall auf. In allen diesen Fällen benutzt man mit Vorteil rekursiven Methoden.

Daneben sind rekursive Verfahren auch an Stellen sinnvoll, wo man dies zunächst nicht vermuten würde. Bei Barron [BARR67]findet man eine Reihe Beispiele (vgl. Abschnitt 1.5). ``Rekursiv'' bedeutet ja zunächst nicht viel mehr als ``Zurückführen auf Bekanntes bzw. Gegebenes bzw. Errechnetes''. In der Mathematik und in der Informatik benutzt man den Begriff meist für die Bezeichnung von Funktionen (bzw. Verfahren), die dadurch gekennzeichnet sind, da\ssmanWerte einer Funktion (Ergebnisse eines Verfahrens) berechnet, indem man andere, meist leichter zu ermittelnde Werte derselben Funktion (frühere Verfahrensresultate) benutzt (bzw. stufenweise durch Anwendung des Verfahrens auf vorher mit demselben Verfahren ermittelte Ergebnisse vorgeht).

Die Einfachheit einer solchen Vorschrift und ihre effektive Ausführbarkeit haben die rekursiven Funktionen zu einem Forschungsobjekt der Mathematik gemacht.

 

Historische Bemerkungen

Die rekursive Denkweise ist in der Mathematik lang erprobt, auch wenn man sich mit den theoretischen Grundlagen erst in unserem Jahrhundert befaßte. Die induktive Definition bzw. die Arbeit mit ``rekurrenten'' Folgen der Zahlentheorie kann schon bei Archimedes (Berechnung der Zahl$\pi$) gefunden werden; später haben unter anderen Fibonacci undEuler rekurrente Folgen zur Lösung spezieller Probleme benutzt[PE5][S.166].

In die Grundlagenforschung fand der Begriff der Rekursion Eingang, als man sich von dem Gedanken trennen mußte, da\sseine Grundlegung(d.h. Deduktion von einer nachweislich sicheren, widerspruchfreien Basis) der Mathematik auf der Basis der Mengenlehre einfach zu erreichen sei. Es gibt ja bis heute keinen Beweis der Widerspruchfreiheit für die Mengenlehre. Statt die bewährten ``harmloseren'' [PE51][ebd.] Gebiete der Mathematik auf die Mengelehrezu gründen, versuchte man, neue Basisbegriffe zu finden, um völlig ohne Mengen auszukommen.

Skolem [SK23] war einer der ersten, die dies für dieZahlentheorie versuchten. Bei seiner Begründung der Zahlentheorie spielte die Rekursion eine wichtige Rolle als Definitionsmöglichkeit für Funktionen über Zahlen.

Wie Peter [PE51][S.167] bemerkt, hatte auch Peano[PEA91] in seinem Axiomensystem für die natürlichen Zahlen an dieDefinierbarkeit durch Rekursion gedacht, habe allerdings diese Eigenschaft als im Induktionsaxiom enthalten angenommen. Ein Beweis der Zuverlässigkeit dieser Definitionsart kann aber auch schon bei {\sc Dedekind} [DE93] gefunden werden.

Die Forschungen im Bereich der Grundlagen der Mathematik haben sich für die Theorie der rekursiven Funktionen als äußerst förderlich erwiesen, weil dem Begriff der rekursiven Funktionen eine Schlüsselrolle zufiel. So hoffte D.Hilbert [HIL4] im Rahmenseines Programms der Neubegründung der Mathematik, das auf eine Formalisierung der einzelnen Zweige der Mathematik und ihre dann mögliche Beweisbarkeit der Widerspruchsfreiheit abzielte, auch eines der bekanntesten ungelösten Probleme der Mengenlehre, das sogenannte Kontinuumsproblem, zu lösen (inzwischen ist die Unabhängigkeit dieser Aussage von den Axiomen der Mengenlehre durch Gödel(1935) und Cohen (1963) nachgewiesen worden). Bei dem Beweissollten Rekursionsarten höherer Stufe (transfinite Rekursion)verwendet werden. So wurden die rekursiven Funktionen ein aktuelles Forschungsobjekt.

Die Bemühungen um den Beweis der Widerspruchsfreiheit für die Zahlentheorie führten zur ersten klaren Definition der rekursiven Funktionen durch Herbrand [HERB31]. Gödel entwickelteden Herbrandschen Gedanken weiter [GO34], nachdem erzunächst eine engere Begriffsbestimmung vorgeschlagen hatte [GO31].In Anlehnung an eine Bezeichnung von Hilbert und Bernays[HIL34] (primitive Rekursion) führte Kleene dann denBegriff primitiv rekursive Funktionen für den engeren undallgemein rekursive Funktionen für den umfassenden Begriffein [KLE36].

In den zwanziger Jahren gab es ständig heftige Diskussionen zwischen den Mathematikern, die in der Nachfolge Hilberts daranglaubten, da\ssdas Hilbertsche Programm durch Axiomatisierungund Formalisierung durchführbar sei und vollzogen werden solle, und den sogenannten Intuitionisten, die dieses Programm bezweifelten und neben anderem (z.B. das Tertium non datur, d.i. der Satz vom ausgeschlossenen Dritten in der Aussagenlogik) insbesondere Existenzbeweise, die kleinerlei Konstruktionsvorschriften für das zur Debatte stehende Objekt enthielten, ablehnten. Es ist klar, da\ssfürdiese Gruppe, die unter der Führung von Brouwer [BROU8,BROU28],Heyting [HEY34] und Weyl [WEYL18] stand, die rekursivenFunktionen und die mit ihnen gegebenen klaren Berechnungsvorschriften besonders interessant sein mußten.

Auch durch den Streit mit den Intuitionisten wurde so die Frage nach dem Begriff des Verfahrens zu einer zentralen Thematik der Grundlagenforschung jener Zeit. Sie war ohnehin schon aktuell durch die Versuche, für logische Kalküle Verfahren zum Beweis wichtiger Eigenschaften wie Widerspruchsfreiheit, oder Vollständigkeit zu finden bzw. überhaupt Entscheidungsverfahren zu konstruieren.

Während für den Aussagenkalkül schon Anfang der zwanziger Jahre die Frage geklärt waren [POS21], standen sie für denPrädikatenkalkül noch zur Debatte. Das Problem, eine allgemeine Methode zu finden, nach der für eine gegebene Formel entschieden wird, ob sie beweisbar ist oder nicht, konnte erst geklärt werden, nachdem man sich über den Begriff des allgemeinen Verfahrens klargeworden war.

Die Fragestellung nach Entscheidungsverfahren ist erst seitSchröder [SCHR95], Löwenheim [LO15] und {\scHilbert} [HIL4] in der Logik zu finden. Bei ihrer Beantwortungkonzentrierte man sich zunächst darauf, ein konkretes Verfahren zu finden, wie es etwa Post mit der Methode der Wahrheitstafeln für dieAussagenkalkül angegeben hatte.

Einen ersten Teilerfolg hatte Löwenheim schon 1915 erzielt.Seinen Beweis vereinfachte Skolem 1919 durch die Einführungneuer innertheoretischer Hilfsmittel (neue SkolemscheNormalform) [SK19]. Die Probleme bezüglich der Vollständigkeitfanden durch Gödel ihre Lösung: 1930 zeigte er, da\ssderPrädikatenkalkül 1. Stufe vollständig ist (wenn eine Formel nicht widerlegbar ist, so ist sie in einem Modell gültig) und wenig später, da\ssder Prädikatenkalkül 2. Stufe diese Eigenschaft nichthat [GO34].

Mitte der dreißiger Jahre wurden fast gleichzeitig zwei Verfahrenskonzepte entwickelt: Turing entwickelte die nach ihmbenannte theoretische Maschine, und Church konstruierteden lambda-Kalkül (vgl. Abschnitt 3.8). Mit diesemHilfsmittel gelang die Beanwortung der offenen Frage: Es gibt keine Entscheidungsverfahren für den Prädikatenkalkül.

Es ist nur natürlich, da\ssin dieser Atmosphäre auch der Begriffder Funktion neu durchdacht wurde (z.B. [MEN53,SCHO25])und in Beziehung zu der Frage der Berechenbarkeit gestellt wurde. Eine Kulmination erlebten diese Arbeiten durch Church und seineSchüler Kleene und Rosser. Die von anderenEntwicklungen weitgehende Unabhängigkeit des Aufbaus des lambda-Kalküls und seine 1936 bewiesene Äquivalenz (was den Bereich der definierbaren Funktionen betrifft) zum Kalkül der rekursiven Funktionen war ein äußerst wichtiges Resultat.

Um dieselbe Zeit entwickelten Turing [TU36] und Post[POS36] unabhängig voneinander die Vorstellung von den {\emberechenbaren Funktionen} weiter. Ihre Begriffe der rechnenden Maschinen bzw. der Produktionen dienten zur exakten Definition der Berechenbarkeit und des Verfahrens, und die durch Turing selbstbewiesene Gleichheit der Begriffe der Turing-Berechenbarkeitund der lambda-Definierbarkeit veranlaßte Church zurFormulierung seiner These, da\ssder Begriff der allgemeinenrekursiven Funktion den intuitiven Begriff der Berechenbarkeit umfassend festlegt und jede neue Funktionen enthält, die nicht allgemein rekursiv sind [CH36a].

Damit ist klar,welche Bedeutung der Begriff der rekursiven Funktion bei der weiteren Forschung auf dem Gebiet der Berechenbarkeit haben mußte.

Durch Probleme motiviert, die im Zusammenhang mit der Vollständigkeit der Definiertheit der rekursiven Funktionen auftreten, führte {\sc Kleene} [KLE38] 1938 den Begriff der {\em partiell rekursivenFunktion} ein.

Auf die so erreichte Abrundung der Theorie folgte eine Zeit des Aufbaus, der heute noch nicht abgeschlossen ist. Der Fortschritt läßt sich gut an den wesentlichen Lehrbüchern über die Theorie der rekursiven Funktionen ablesen. Wichtige Meilensteine sind hier R.PetersBuch [PE51], die ``Einführung in die Metamathematik'' von S.C.Kleene [KLE52], die Werke von M.Davis [DAV58] und H.Rogers [ROG67] Ende der fünfziger bzw. Mitte der sechziger Jahre.

Mit dem Aufkommen elektronischer Rechenanlagen wurden viele zunächst rein technische Fragestellungen plötzlich praktisch bedeutungsvoll. Als die Rechner so leistungsfähig geworden waren, da\ssdie Programmierung sich nicht mehr auf Platz- undEffektivitätsprobleme konzentrieren mußte, traten nach und nach methodologische Probleme in den Vordergrund, auf die die mathematische Theorie der rekursiven Funktionen keine Antwort wußte und die sie eigentlich auch nicht geben wollte. Allen Kalkülen der mathematischen Logik ist gemeinsam, da\sssie für die Klärung prinzipieller Fragenaufgebaut sind und nicht dazu, da\ssmit ihnen wirklich praktischgearbeitet wird. Es ist das Verdienst von McCarthy, mit demLISP-Kalkül (Kalkül der bedingten Ausdrücke) einenFormalismus geschaffen zu haben, der sowohl eine Antwort auf die drängenden Darstellungsfragen gab als auch theoretische Vereinfachungen brachte.

``Der Formalismus McCarthys gleicht insofern dem allgemeinen rekursiven System von Kleene, als er auf einigen grundlegenden Funktionen beruht, auf Komposition und Gleichheit, wobei aber der bedingte Ausdruck allein sowohl das primitiv-rekursive Schema als auch den Minimisierungsoperator ersetzt... Er unterscheidet sich aber in der Hinsicht, da\sser explizite Vorkehrungen für Selbstbezug aufweist,so da\sser, statt schwierige arithmetische Methoden zu verwenden,Berechnungen, Aufzählungen, universelle Verfahren usw. unmittelbar beschreiben kann.'' (M.Minsky [MIN67][S,247])

 

Grundlegende Definitionen der Theorie rekursiver Funktionen

Der Platz reicht hier nicht aus, um eine einigermaßen abgerundete Einführung in die Theorie rekursiver Funktionen zu geben; auch würde dies den Rahmen des Buches sprengen.

Immerhin ist der Begriff der rekursiven Funktion für LISP so bedeutsam, da\sswenigstens die Basisdefinitionen angegeben werdensollen. Indem dies auf verschiedene Arten demonstriert wird, soll der Vorteil der bedingten Ausdrücke hervorgehoben werden.

Gegeben seien drei Mengen von Zeichen: eine Menge von Zeichen für Objekte, eine Menge von Zeichen für Funktionen und eine Menge von technischen Zeichen. Die Objektsymbole seien etwa {\em a, b, x, $x_{1}$, ... ,} die Funktionssymbole {\em $f^{1}$, $f^{0}_{1}$}, usw. und die technischen Symbole (Klammern, Kommata, ...).

Aus diesen Alphabet werden nun Zeichenketten geformt. Unter diesen interessieren uns bestimmte, die wir Terme nennen wollen:

(T1) Jedes Objektsymbol ist ein Term.
(T2) Es mögen n Terme gegeben sein: $t_{1}$, ... , $t_{n}$.   Dann ist $f(t_{1}, ..., t_{n}$) ein Term, wenn $f$ ein $n$-stelliges 
Funktionensymbol
  ist.
(T3) Terme werden nur gemä\ssder Regeln (T1) und (T2) gebildet.

Terme bekommen einen Wert, wenn der Menge der Objektsymbole eine Menge von Werten aus einer Grundmenge zugeordnet und jedem Funktionszeichen eine Funktion aus einem passenden Produkt dieser Grundmenge in die Grundmenge zugeordnet wird.

Es kann vorkommen, da\ssden Funktionssymbolen partielle Funktionenzugeordnet werden. Hier wird vereinbart, da\ssder Wert eines Terms$f(t_{1}, ..., t_{n})$ undefiniert ist, wenn entweder ein $t_{i}$ undefiniert ist oder der Wert der Funktion, die dem Symbol $f$ zugeordnet wurde, in dem Punkte, der dem Tupel $(t_{1}, ..., t_{i})$ entspricht, undefiniert ist.

Hat man einige Funktionen, die auf einer Grundmenge {\bsy X} gegeben sind, so kann man mit Hilfe von Termen eine unendliche Anzahl neuer, auf derselben Menge {\bsy X} definierter Funktionen aufschreiben. So sei die Grundmenge etwa {\bsy N}, d.h. die Menge der natürlichen Zahlen. Als Grundfunktionen (Ausgangsfunktionen) seien gegeben:

(F1) die Nachfolgerfunktion $s$ mit $s(x) = x + 1 = x'$,
(F2) die n-stelligen Nullfunktionen $o^{n}$ mit $o^{n}(x_{1}, ..., x_{n}) = 0$,
(F3) die n-stelligen Projektionen $I^{n}_{m}$ mit$I^{n}_{m} (x_{1}, ... ,x_{n}) = x_{m}$ 
  ($1< m < n, n = 1,2, ...$).

Folgende Operationen erzeugen aus diesen Anfangsfunktionen alle partiell-rekursiven Funktionen:

(O1) Die Operationen der Substitution: Es seien n beliebige partielle Funktio-
  nen $f_{1}$, ... , $f_{n}$ ein und derselben Stelligkeit m gegeben, die Werte in der
  Grundmenge annehmen können (d.h., die Funktionen bilden das n-fache  Produkt der Grundmenge in diese ab); weiter sei eine 
  n-stellige partielle Funktion f definiert, die n-Tupel aus der der Grund-  menge überführt. Dann läßt sich mit 

$g(x_{1}, ..., x_{m}) = f(f_{1}(x_{1}, ..., x_{m}), ..., f_{n}(x_{1}, ..., x_{m}))$

eine m-stellige Funktion g aus den Funktionen f sowie $f_{1}, f_{2}, ..., f_{n}$ ein- führen. (O2) Die Operation der primitiven Rekursion: Es sein zwei partielle Funktio- nen g und h gegeben; sie bilden Tupel aus der Grundmenge in Werte aus derselben ab. g sei n-stellig und h sei n+2-stellig. Die n+1-stellige Funktion f entsteht aus g und h primitiv rekursiv, wenn für alle Tupel $x_{1}, x_{2}, ..., x_{n}, y$ gilt:

$f(x_{1}, x_{2}, ..., x_{n}, 0) = g(x_{1}, ..., x_{y})$, $f(x_{1}, x_{2}, ..., x_{n}, y+1) = h(x_{1}, x_{2}, ..., x_{n}, f(x_{1}, ..., x_{n}, y))$

 

Eine Funktion heißt primitiv rekursiv, wenn man sie nur vonden Ausgangfunktionen $s,o$ und $I^{n}_{m}$ beginnend durch eine endliche Zahl von Operationen der Substitution und der primitiven Rekursion erhalten kann.

(O3) Die Operation der Minimalisierung: Gegeben sei eine n-stellige partielle   Funktion f. Der Ausdruck

$\mu_{y}(f(x_{1}, ..., x_{n-1}, y) = z$

bezeichne den kleinsten Wert y, für den die Gleichung

$f(x_{1}, ..., x_{n-1}, y) = z$

bei festgehaltenem z und festen $x_{1}, ..., x_{n-1}$ erfüllt ist. y ist offenbar ab- hängig von den $x_{i}$ und von z. Deshalb kann über

$g(x_{1}, x_{2}, ..., x_{n}) = \mu_{y}(f(x_{1}, x_{2}, ..., x_{n-1}, y) = x_{n}$

eine n-stellige Funktion eingeführt werden. Man sagt, {\emg} entsteht aus f über die Operation der Minimalisierung.

 

Die partiell-rekursiven Funktionen werden [MAL74] unter Verwendungdieser Operationen definiert: Eine partielle Funktion heißt partiell-rekursiv, wenn sie aus den Anfangsfunktionen $s, o$ und $I^{n}_{m}$ durch eine endliche Zahl von Operationen der Substitution, der primitiven Rekursion und der Minimalisierung erhalten werden kann.

Es läßt sich übrigens zeigen [MIN67], da\ssderMinimalisierungsoperator allenfalls nur einmal bei dieser Erzeugung benötigt wird. Rekursive Funktionen sind Funktionen, die durch Gleichungen definiert werden\footnote{Allerdings leisten Gleichungen mehr: Es gibt nichtberechenbaren Funktionen, die durch Gleichungssysteme definierbar sind. Durch die Ableitungsregeln werden diese Funktionen ausgeschieden [KALM55}.].

Der Gleichungskalkül

Kleene hat für die Einführung der partiellen rekursivenFunktionen einen Gleichungskalkül aufgebaut, der ohne der Bezugnahme auf die Operationen der Minimalisierung und der primitiven Rekursion auskommt.

Die Zeichenmenge entspricht fast vollständig der bisher benutzten: Die Menge der Zeichen für Objekte enthalte ein Zeichen 0 für dieNull und weitere Zeichen für die Zahlen (Zahlenvariable, Numerale); die Menge der Funktionssymbole bleibt, dabei wird etwa eines für die Nachfolgerfunktion ausgewählt (etwa $f_{1}$) und ein weiteres freigehalten für die Funktion, deren definierendes Gleichungssystem wir schreiben wollen. Zu den technischen Symbolen kommt noch das Gleichheitszeichen hinzu.

Die Termdefinition entspricht völlig der vorangegangenen. Der Klarheit wegen könnte man die erste Klausel aufteilen:

(TLi)   Die Konstante 0 ist ein Term. 
(TLii)   Die Zahlenvariablen sind Terme.

Weitere Definitionen sind:

(G)   Eine Gleichung ist eine Zeichenfolge t = u, wobeit und u Terme sind.(GL) Eine endliche Menge von Gleichungen heiße Gleichungssystem.

Im Kalkül der rekursiven Funktionen wird ein Ableitbarkeitsbegriff (der in etwa einem Rechenverfahren entspricht) eingeführt, in dem folgende zwei Regeln definiert werden:\footnote{Wir folgen hier der Darstellung von V.Kalm\'ar [KALM55]. S.C.Kleeneerlaubt die Einsetzung nur von Numeralen, d.h. Termen der Form $O, f_{1}(O), f_{1}(f_{1}(O))$ usw., und die Ersetzung von Termen, die außer dem Funktionssymbol nur Numerale enthalten, durch einen Term, der ein Numeral ist, falls die entsprechende Gleichung ableitbar ist ([KLE52], S. 264). Damit präsentiert Kalm\'ar im Grundeeinen Call-By-Name-Kalkül, während Kleenes Kalkül sicherdem Call-By-Value entspricht. Allerdings klammert Kalm\'ar das Problem der Undefiniertheit völlig aus, das den eigenttlichen Unterschied macht. Vgl. hierzu [MORS68,CA72,V73,ROE74] und schließlich als wichtigste Arbeit [BAKK75}.]

{\bf Einsetzung:} Es seien t und u Terme, a sei eineZahlenvariable. Setzt man für a an allen Stellen, wo es unterden Zeichen der Zeichenfolge t vorkommt, die Zeichenfolge {\emu} ein, so entsteht wieder ein Term, das Ergebnis der {\em Einsetzung} von u für a in t.

{\bf Ersetzung} (Substitution): Es seien t, u, w Terme. Ersetzt man beliebig viele Vorkommen derZeichenfolge u als Teil (d.h. als Folge vonhintereinanderstehenden Zeichen) der Zeichenfolge t durch dieZeichenfolge w, so entsteht wieder ein Term, das Ergebnis derErsetzung von w für u in t.

Aus einem gegebenen Gleichungssystem S sind mit diesen Regeln folgende Gleichungen ableitbar:

(A1) die Gleichungen von S,(A2) wenn die Gleichung s = t aus S ableitbar ist, s und t      Terme und v eine   Zahlenvariableist, dann sind ableitbar:
   t'= s',  wobei t' bzw. s' das Ergebnis der Einsetzung von O für v in t bzw. s  darstellt; 
   t'' = s'',   wobei t'' bzw. s'' das Ergebnis der Einsetzung von $f_{1}(v)$ für v in t bzw.   s darstellt,(A3) wenn die Gleichungen s = t und r = u ableitbar sind, r, s und t Terme  sind, dann sind alle Gleichungen 
   t' = s'   ableitbar, wobei t'bzw. s' ein mögliches Ergebnis der Ersetzung von r   für u in t bzw. s darstellt.

Die Funktion, die das beliebige $r_{2}$-Tupel ($r_{i}$ soll die Arität der Funktion $f_{i}$ sein) von Elementen aus dem Grundbereich in jedes m überführt, für das dieGleichung $f_{2} = z_{m}$ ableitbar ist,\footnote{$z_{i}$ sind irgendwelche Numerale.} heißt die durch das Gleichungssystem definierte Funktion. Eine Funktion heißt allgemein rekursiv, wenn man die positiven ganzen Zahlen $k, l, r_{2}, ..., r_{i}$ und das allgemein rekursive Gleichungssystem S so wählen kann, da\ssS ein definierendesGleichungssystem für diese Funktion ist (dabei sei k dieAnzahl der Zahlenvariablen und l die Anzahl derFunktionsvariablen).

Die Grundidee für den Gleichungskalkül ist nicht neu. Man kann Vorläufer dafür in vielen älteren Werken der Mathematik finden. Dort wird z.B. die Definition durch Fallunterscheidung erwähnt. Ein typischer einfacher Fall einer solchen Definition -- der, wie man sieht, mittels zweier Gleichungen zu notieren ist -- ist die Sprungfunktion:

\[S(x) = \left\{ \begin{array}{ll} 0, & \mbox{falls $x\le 0$} 1, & \mbox{falls $x>0$} \end{array} \right. \]

Von einfachen Fallunterscheidungen gelangt man zur induktiven Definition, wenn man zuläßt, da\ssfür die Formulierung desDefiniendum (der Aussage, die zum Definieren benutzt wird) das Definiens (der definierte Begriff) verwendet wird.\footnote{Um die Korrektheit der Definition zu zeigen, d.h. um ihre Zirkelfreiheit zu erweisen, müßte eigentlich ein Rechtfertigungsbeweis geführt werden.}

Induktive Definitionen haben eine wohlstrukturierte Form -- man unterteilt gewöhntlich in Basisklauseln, in denen dieDefinition direkt für gewisse spezielle Objekte ausgesprochen wird, in induktive Klauseln, in denen von der Erfüllung der Definitionfür bestimmte Objekte auf ihre Gültigkeit für andere, in präziser Art zu diesen Objektenin Beziehung stehenden Objekten festgestellt wird und schließlich die Extremalklausel, in derausdrücklich niedergeschrieben wird, da\ssdie Definition nicht fürandere Objekte gilt. Die Struktur dieser Definition, die meist von der formalen Struktur des definierten Objekts abhängt, läßt sich in allen Induktionsbeweisen für Eigenschaften von den Objekten wiederfinden.

Wird mit induktiven Definitionen eine Klasse von Grundobjekten eingeführt -- Kleene [KLE52] spricht in diesem Fall von``fundamentalen induktiven Definitionen'' --, dann kann man weiter induktive oder rekursive Definitionen über dieser Klasse vornehmen, in dem man sich bei der Fallunterscheidung auf die verschiedenen Klauseln der fundamentalen Definition bezieht.

So wird bei der Berechnung des Werts einer rekursiven Funktion für jedes Argument, das nicht zur Menge der primitiven Objekte (Basisklauseln!) gehört, dieser Wert bestimmt durch Bezugnahme auf Werte, die die Funktion für Argumente annimmt, die unter dem Blickwinkel der fundamentalen induktiven Definition ``früher'' generiert wurden.

Diese Aussagen gelten etwa für die natürlichen Zahlen, bei denen, den Peanoschen Axiomen folgend, die Generierung mittels derNachfolgerfunktion erfolgt und wo also der Begriff des ``Früher'' mit der gewöhnlichen Ordnungsrelation zusammenfällt. Sie gelten aber ebenfalls für Formeln, z.B. wenn diese wie üblich induktiv eingeführt werden -- und ganz allgemein für jeden Datentyp, d.h. für jede rekursiv aus Teilstrukturen aufgebaute Klasse von Objekten (Terme, Records usw.usf.).

Bedingte Ausdrücke

Der Gleichungskalkül wurde nun aber nicht für die praktische Verwendung, d.h. als effektives Definitionsinstrument für rekursive Funktionen, erdacht, sondern für prinzipielle Untersuchungen von Eigenschaften solcher Funktionen. Für solche Beweise -- etwa Eindeutigkeitsbeweise, Äquivalenzbeweise mit anderen Formulierungsmitteln wie Turing-Maschinen usw. -- kommt manExtremfällen, d.h. einigen höchst speziellen Beispielen, aus. Dabei sind die Gleichungen meist in ihrer Zahl stark begrenzt und die auftauchenden Terme nicht übermäßig kompliziert. Solange er nur zu den ihn interessierenden Beweisen kommt, macht sich der Mathematiker im allgemeinen leider wenig Gedanken über Darstellungsfragen.

Will man den Gleichungskalkül benutzen, um mit ihm konkrete Funktionen zu beschreiben oder gar wirkliche Probleme zu formulieren, so gewinnt diese Frage aber enorme Bedeutung. Die ungeordneten Systeme und der vage Berechnungsbegriff bringen hier große Schweirigkeiten mit sich.

McCarthys Idee, die Gleichungen zu ordnen, sie zulinearisieren und auf den Fall der Funktionsdefinition zu spezialisieren, schafft hier große Erleichterung. Die sequentielle Ordnung der Gleichungen\footnote{Es gibt andere lineare Notationsweisen; die Auswahl der korrekten Gleichungen bzw. des korrekten Terms erfoglt dann durch der Trick, diesen Term mit 1 zu multiplizieren und die anderen Anteile mit 0 [AC29}.] appelliert an das Gefühl des Programmierersfür die zeitliche Reihenfolge der Abarbeitung; die Bedingungen filtern aus den vorher üblichen Termen die relevanten, den Spezielfall bestimmenden Anteile heraus.

Der Grundbegriff bei McCarthy [MCC63a] ist die Form,die weitgehend dem Term entspricht. Neu ist, da\ssdieVariablennamen unterschiedlichen Grundbereichen zugeordnet werden können. Unter den verschiedenen Grundmengen spielt die Menge {\bsy B} der Wahrheitswerte, d.h. {\bsy B} = \{T, F\} eine besondere Rolle.

(F1) Eine Variable x mit einem zugeordneten Grundbereich {\emU} ist eine Form, 
  und ihr ordnen ebenfalls U zu.   Eine Konstante in einem Grundbereich U ist eine Form, der wir ebenfalls
  U zuordnen.(F2) Sind $e_{1}, ... , e_{n}$ Formen mit zugeordneten Bereichen $U_{1}, ... , 
U_{n}$ so ist auch 
  $f(e_{1}, ..., e_{n})$  eine Form mit zugeordneten Bereich V, wenn  $f: U_{1} \times U_{2} \times ... \times U_{n} \mapsto V$ eine 
Funktion mit n Stellen ist.(G) Wenn in der Form e nur die Variablen $x_{1}, ..., x_{n}$ vorkommen, dann kann
  man mit $h(x_{1}, ..., x_{n}) = e$ die Funktion h definieren. Wenn in e genau die   Funktionen $f_{1}, ..., f_{m}$ vorkommen, dann sagt man, h ist durch Komposi-   tion der Funktionen $f_{1}, ..., f_{m}$ definiert worden.

Die Funktionen müssen nicht für alle Werte der Variablen definiert sein. Die n-Tupel, für die eine n-stellige Funktiondefinert ist, die durch Funktionskomposition eingeführt wurde, werden bestimmt aus den n-Tupeln, für die die Funktionen, die dieKomposition ausmachen, definiert sind.

Die Funktionen, die Werte in {\bsy B} annehmen, werden {\em Prädikate} genannt. Eine Form, die Werte in {\bsy B} annimmt, heißt Aussagenform.

(C) Bedingte Ausdrücke sind Zeichenketten der folgenden Gestalt:

($p_{1}\rightarrow e_{1}, ... , p_{n}\rightarrow e_{n})$

wobei die $p_{i}$ Aussagenformen sind und die $e_{i}$ Formen (i = 1, ... , n). Der Wert des Ausdrucks ist der Wert von $e_{i}$, wenn i die kleinste Zahl ist, für die $p_{i} =$ T gilt. Sind die Werte aller $p_{i}$ F, ist der bedingte Ausdruck undefiniert. Dasselbe gilt, wenn ein undefiniertes $p_{i}$ mit $j\le i$ existiert und i die erwähnte kleinste Zahl ist, für die $p_{i} =$ T, sowie wenn $e_{i}$ undefiniert ist.

 

Um die Schreibweise der Aussageformen zu vereinfachen, können die logischen Konnektoren eingeführt werden:

  $p\wedge q = (p\rightarrow q, T\rightarrow F),$
  $p\vee q = (p\rightarrow T, T\rightarrow q),$
  $\neg p = (p\rightarrow F, T\rightarrow T),$
  $p\Rightarrow q = (p\rightarrow q, T\rightarrow T).$

Angenommen, es ist eine gewisse Grundkollektion von Funktionen, {\bsy F}, gegeben, die zugeordnete Definitionsbereiche und Wertebereiche besitzen. Dann sei $C(${\bsy F}$)$ die Klasse aller Funktionen, die sich mittels des angegebenen Formalismus aus ihnen definieren lassen. Wir nennen sie die {\em Klasse der Funktionen, die mittels der Basisfunktionen aus {\bsy F} berechenbar sind}. Es ist nicht schwer, zu zeigen, da\ssetwa$C(\{succ,eq\})$ mit der Menge der partiellen arithmetischen Funktionen zusammenfällt.

Sei $succ(x) = x+1$, die Nachfolgerfunktionen,

und $eq$ die Gleichheitsfunktion:

\[ eq(x_{1}, x_{2}) = \left\{ \begin{array}{ll} T, & \mbox{falls $x_{1} = x_{2}$}, F & \mbox{sonst}, \end{array} \right. \]

Nun mu\sszunächst gezeigt werden, da\ssdie Ausgangsfunktionen $s, o^{n}$ und $I^{n}_{m}$ in $C(\{succ,eq\})$ liegen. Nun ist $succ$ nur eine andere Bezeichnung für s. Für die beiden übrigen Funktionen gilt:

 $o(x_{1},...,x_{n})$ = 0.
 $I^{n}_{m}(x_{1},...,x_{n}) = x_{m}$.

Dann mu\ssbewiesen werden, da\ss$C(\{succ,eq\})$ abgeschlossen istbezüglich Komposition, primitiver Rekursion und Minimalisierung. Dies gilt nach Definition für die Komposition.

Wir definieren die Funktion $\mu_{f}$:

  $\mu_{f} = ($$eq(f(x_{1},...,x_{n-1}, y)\rightarrow y,$
   $ T\rightarrow \mu_{f}(x_{1},...x_{n-1}, succ(y))$.

Man sieht leicht, da\sszu vorgegebenem f die Form

\begin{center}$\mu_{f}(x_{1}, ..., x_{n}, 0)$\end{center}

der Minimalisierung entspricht.

Das Schema der Primitiven Rekursion läßt sich direkt als bedingter Ausdruck schreiben:

  $f(x_{1}, ..., x_{n-1}) = ($\=$eq(x_{n}, 0)\rightarrow g(x_{1}, ..., x_{n-1}),$
   $T\rightarrow h(x_{1}, ..., x_{n}, f(x_{1}, ... , x_{n}-1)))$,

wenn die Minusoperation wie üblich definiert wurde.

Der bedingte Ausdruck ersetzt also die erforderlichen Funktionsbildungsoperationen. Mit seiner Hilfe geschriebene Funktionsdefinitionen sind aber auch übersichtlicher als die unter Verwendung des Gleichungskalküls bzw. der einfachen Fallunterscheidung. Dies kann nur an Beispielen gezeigt werden.

Vergleich der Formulierungsmittel

Eines der beliebtesten Beispiele ist immer wieder die Funktion zur Berechnung der Fakultät n! einer natürlichen Zahl n.Als Fallunterscheidung wird formuliert:

\[ Fakultat(n) = \left\{ \begin{array}{ll} 1, & \mbox{falls $n = 0$}, n * Fakultat(n - 1) & \mbox{sonst}, \end{array} \right. \]

\noindent im Gleichungskalkül ist zu schreiben:

\begin{center}$Fakultat(0) = 1$, $Fakultat(n') = Fakultat(n * (n + 1))$\end{center}

und mit bedingten Ausdrücken:

\begin{center}$Fakultat(n) = (x = 0 \rightarrow 1, T\rightarrow n * Fakultat(n - 1))$.\end{center}

Scheinen hier, wegen des geringen Gesamtaufwands, die drei Formen noch gleichartig zu sein, so ändert sich das Bild, wenn die Funktionen kompliziert werden. Als nächstes Beispiel wählen wir das {\sc Ackermann}sche verallgemeinerte Funktional [ROG67][S.XX], das eineWeiterführung der Potenzierung darstellt:

\begin{center}$ack(0, x, y) = y + x$, $ack(1, x, y) = y * x$, $ack(2, x, y) = y^{x}$, usf.\end{center}

Diesmal lauten die verschieden formulierten Definitionen:

\[ f(z,y,x) = \left\{ \begin{array}{ll} y, & \mbox{falls x = 0 und $z\neq 1, z\neq 2$,} f(0,x - 1, y) + 1, & \mbox{falls z = 0 und $x\neq 0$,} 0, & \mbox{falls x = 0 und z = 1,} 1, & \mbox{falls x = 0 und z = 2,} f(z - 1, f(z,x - 1,y),y) & \mbox {sonst.} \end{array} \right. \]

Im Gleichungskalkül bestehen jetzt ernste Probleme, da die Ungleichheitsbedingung nicht ausgedrückt werden können. Wir verwenden die originale Schreibweise von Ackermann[AC29]:\footnote {die Gleichungen bei Rogers ([ROG67]), S. XX)sind unvollständig, ebenso bei Hermes ([HERM61], S. 84). Wirändern an der Ackermannschen Version nur die Funktionsnamen.Man sieht, da\ssdie Funktionen $f_{1}$ und $f_{2}$Steuerzwecke erfüllen.}

\begin{center}$f_{1}(a,a) = 1, f_{1}(a,b) = 0$, $f_{2}(a,a) = 0, f_{2}(a,b) = 1$, $f(a,b,0) = a + b$, $f(a,0,c + 1) = f_{3}(a,c) = f_{1}(c,1) + f_{2}(c,1) * f_{2}(c,0) * a$, $f(a,b + 1,c + 1) = f(a,f(a,b,c + 1),c)$.\end{center}

Um die wirklich vergleichbaren Formulierungen zu gelangen, müßten wir nun noch jeweils zwei Gleichungen für Addition (+) und Multiplikation (*) hinzufügen.

Nun folgt die Formulierung mittels bedingter Ausdrücke:

  $f(z,x,y) = ($$x = 0\rightarrow (z = 1\rightarrow 0, z = 2\rightarrow 1, T\rightarrow y)$,
   $z = 0 \rightarrow f(0,x - 1,y) + 1$,
   $T \rightarrow f(z - 1,f(z,x - 1,y),y))$

Das Fazit ist also, da\ssdie Formulierung im Gleichungskalkül ohneBedingungen auskommen muß. Deshalb werden diese in Hilsfunktionen versteckt -- und die Gleichungen werden schwer lesbar. In der Definition durch Fallunterscheidung können wir eine Wichtung der Bedingungen nur durch die Reihenfolge erreichen. Viele verknüpfte Bedingungen sind nicht überschaubar. Im Kalkül der bedingten Ausdrücke kann man durch die Ineinanderschachtelung gemeinsame Bedingungen gewissermaßen ``ausklammern'' und damit eine gut lesbare Strukturierung durchsetzen.

Ursache für die Möglichkeit, bedingte Ausdrücke ``ausklammern'' zu können und Quelle für eine Fülle von Einsatzvarianten ist die Tatsache, da\ssdiese einen Wert haben. Die bedingten Ausdrücke ... besondersvon den Fallunterscheidungen. Der rechts der Definitionsgleichheitstriche stehende Ausdruck soll nicht nur die Definition beschreiben, sondern er kann überall statt der linken Seite, statt des funktionalen Terms, statt der Form $f(z,x,y)$ stehen. Damit kann oft eine weitere wesentliche Vereinfachung erzielt werden.

 

Der lambda-Kalkül

Historische Anmerkungen

Die Notation des lambda-Kalküls wird in LISP benutzt, um Funktionen zu bezeichnen [MCC63][S.45]. Dieses Problem trat im Zusammenhang mitFunktionalen auf, d.h. Funktionen mit Funktionen als Argument. Da die funktionalen Argumente nicht immer Grundfunktionen sind, mußte ein Mittel eingeführt werden, mit dem eine beliebige Funktion angegeben werden kann und mit dem der Bindungsproze\ssder Variablen korrektwiedergegeben wird. Hier bot sich der lambda-Kalkül an, der als formaler Funktionskalkül aufgebaut worden ist, um die Eigenschaften von Variablen, die Substitution und die Abstraktion von Funktionen zu studieren [CH41].

Der lambda-Kalkül ist eines der wesentlichsten Ergebnisse, die in der Logik beim Studium des Funktionsbegriffs erzielt worden sind. Wie allgemein gut bekannt, spielt der Begriff der Funktion, die einebestimmte Beziehung zwischen Objekten herstellt, in der Mathematik eine große Rolle. Insbesondere im 19. Jahrhundert wurden wesentliche Schritte zur Klärung dieses Begriffs vollzogen. Damit war die Zeit reif, da\ssdie ersten systematischen Versuche, die Logik und aufihr aufbauend die Mathematik zu formulieren, auch den Funktionsbegriff behandelten.

Die Wiedersprüchlichkeit des ersten Systems dieser Art, dessen Autor Frege war, führte zu größerer Sorgfalt bei derFormalisierung durch Einführung von Typen, durch die Mengen von Mengen nicht ohne weiteres mit einfachen Mengen vergleichbar sind und ebenso Funktionen über Funktionen einen anderen Typ haben als Funktionen über Grundobjekten.

Peano und Burali-Forti bearbeiteten Anfang des20.Jahrhunderts Aspekte des Funktionsbegriffs, die in einem klaren Zusammenhang allerdings erst von Schönfinkel [SCHO25]formuliert wurden. Schönfinkels wesentliche Idee war dieBeseitigung der Variablen aus der Logik. Zu diesem Zweckeführte er Grundfunktionen ein (combinators in der englischsprachigen Literatur), mit deren Hilfe er die logischen Formeln ohne Variablen ausdrücken könnte. Wesentlich bei der Durchführung dieses Gedankens war die Erweiterung des Funktionsbegriffs, so da\ssWerte undArgumente einer Funktion selbst Funktionen sein konnten. {\sc Schönfinkel} führte auch den Begriff der Funktionsanwendung in dieLogik ein.

Ein Mangel in Schönfinkel Arbeit war die fehlendeBeweistechnik, so da\ssnicht gezeigt werden konnte, da\ssz.B. zweiintuitiv äquivalente Grundfunktionen (combinators) gleich sind. Seine Ergebnisse inspirierten jedoch andere Logiker; Ende der zwanziger Jahre stellte H. B. Curry das erste System der kombinatorischen Logikauf [CU29,CU30].

Das in dem anspruchsvollen Namen ausgedrückte Ziel einer neuen Grundlegung der Logik strebte unter anderen auch A. Church aufähnlichen Wegen wie Curry an. Church baute eineAussagenlogik auf, in der die Abstraktion einer Funktion aus ihren unspezifizierten Werten durch die sogenannte lambda-Operation eine zentrale Rolle spielte [CH32,CH33]. Über diese Operation enthielt dasChurchsche System praktisch auch die Combinators, deren Begriffkurz zuvor durch Curry eingeführt worden war

Church hoffte, da\sssein Ansatz zur Logik über den neuenallgemeinen Kalkül benutzt werden könnte, um die Probleme der naiven Mengenlehre zu klären. Gemeisam mit seinen Schülern [CU58][S.105]S.C.Kleene und J.B.Rosser arbeitete Churchzu Beginn der dreißiger Jahre die Darstellung verschiedener mathematischer Theorien in dem neuen logischen System aus, insbesodere die rekursive Zahlentheorie, die Ordnungszahlentheorie, den Prädikatenkalkül usw. Dabei entwickelte Kleenehauptsächlich die in Verbindung mit der Rekursionstheorie stehenden Teile [KLE35b], während Rosser sich mit den kombinatorischenAspekten beschäftigte [ROS35].

Der typenfreie Aufbau des neuen logischen System war aber nicht einwandfrei, und nachdem Kleene und Rosser ihreDissertationsschriften praktisch fertiggestellt hatten, entdeckten sie Widersprüche (die Kleene-Rosser-Paradoxie [KLE35a]). Der Zwang,alle betroffenen Teile aus seiner Arbeit zu streichen, führte Kleene zu seinem Ansatz der Theorie rekursiver Funktionen. Auch aus Rossers Promotionsschrift, die schon im Druck war, mußtenviele Teile gestrichen werden.

Die Wurzel für die Paradoxie lag in einer fundamentalen Inkompatibilität zwischen den Begriffen der {\em kombinatorischen Vollständigkeit} und dem der Vollständigkeit, die durch das Ableitungstheorem ausgedrückt wird [CU58][S.10]. Durch Streichungvon Teilen des Systems beziehungsweise durch Einführung von Einschränkungen konnte ein widerspruchsfreies System erzielt werden ([CH36b] Beweis der Widerspruchsfreiheit durch das {\scChurch-Rosser}-Theorem). Church konstruierte, auf diesemrevidierten System aufbauend, ein neues System der Logik [CH34,CH35]. Imselben Jahr 1936 erschienen auch Churchs wichtige Arbeiten überdie Unentscheidbarkeit des lambda-Kalküls bzw. des Prädikatenkalküls [CH36a,CH36c]. Diese Entwicklungen und andereEinflüsse brachten Churchs Interesse an der Grundlegung derLogik zum Schwinden. So enthält das Buch, in dem die endgültige Form des lambda-Kalküls fixiert ist [CH41], keinerlei Teile, die sich aufdie Aussagenlogik beziehen.

Nachdem die erste stürmische Entwicklungsetappe des lambda-Kalküls vorbei war, wurde es relativ ruhig um ihn. Er wurde für die Darstellung in Werken über kombinatorische Logik benutzt [CU58],aber weniger als Forschungsintrument oder -gegenstand.

Die zweite, noch andauernde Anwendungsperiode des lambda-Klaküls wurde durch McCarthy [MCC60c] eingeleitet. Die Verwendung alsNotationshilfsmittel in LISP und in der formalen Sprache seines Kalküls der rekursiven Funktionen [MCC63a] wirkte allgemein anregend.Burge [BURG64a], Landin [LAN64a,LAN66], {\sc Barron,Strachey} et al. [BARS63] und Böhm [BO64] entwickeltenSprachen, in denen der lambda-Kalkül eine ähnliche Rolle spielte wie in LISP. Die Idee, diese einfachen Sprachen zur Definition komplizierterer, wie etwa ALGOL60, zu benutzen, scheint nahezu gleichzeitig aufgenommen zu sein. Sicher hat McCarthys Vortragauf dem IFIP-Kongress 1962 anregend gewirkt [MCC62b].

Schon 1964 werden mehrere ähnliche Ansätze publiziert: von {\sc McCarthy} [MCC64], Landin [LAN64b], Strachey [STR64]und Böhm [BO64]. 1968 hebt Wegner [WEG68] dieBedeutung des lambda-Kalküls als einfaches Studienobjekt zur Beschreibung von Funktionsauswertungen hervor. Scott [SCO66]diskutierte das durch LISP aufgeworfene Problem, lambda-Ausdrücke, die explizite Verweise auf sich selbst enthalten (typisch für rekursive Funktionen) durch äquivalente lambda-Ausdrücke darzustellen.

Seit etwa 1968 kann man zwei Entwicklungslinien verfolgen: Einerseits dient der lambda-Kalkül als Modell, um die korrekte Implementierung von Funktionskonzepten in höheren Programmiersprachen an einem extrem reinem Beispiel zu untersuchen -- {\em operationale Beschreibung der Semantik}. Beispiele für diese Verwendung stellen Arbeiten von {\sc Morris} [MORS68], McGowan [MCG71,MCG72,BERR71] und {\scWegner} [WEG72a] dar.

Andererseits sind der lambda-Kalkül und seine Modelle selbst wieder Forschungsgegenstände. Diese Entwicklung wurde durch die Formulierung des Programms der mathematischen Semantikbeschreibung (derersten Entwicklungslinie zuzurechnen) durch {\sc C. Strachey, de Bakker} und D.Scott [SCO71,SCO69b,SCO70] ausgelöst. Insbesonderedie Arbeiten von Scott über Modelle des lambda-Kalküls[SCO73], wodurch die Beziehung zwischen kleinsten (schwächstem, engl. least)Fixpunkt rekursiver Funktionsdefinitionen und dem Y-Kombinator geklärt wurde und weitere seiner Arbeiten [SC072,SCO75a,SCO76] führten zu einerAktualität, die durch weltweite Forschung charakterisiert ist.

Ein deutliches Merkmal dafür war der Kongre\ssüber den``LAMBDA-Kalkül in der Computertheorie'', der im März 1975 in Rom stattfand. Scotts Arbeiten in den Veröffentlichungen [SCO75b]gaben ausgezeichnete Zusammenfassungen der aktuellen Problematiken und der erzielten Resultate.

Kurze Darstellung des lambda-Kalküls

Eine Funktion ist eine Zuordnungsregel, die Elemente aus einem Definitionsbereich Elemente aus einem Wertebereich zuordnet. Die Mengelehre erlaubt die Identifizierung einer Funktion als die Menge der Paare (x,y), wo x aus dem Definitionsbereich genommenwird und y x als Wert zugeordnet ist.

Wollte man jede Funktion als Menge von Paaren angeben, dann käme man zu einem schwerfälligen Notationssystem. Im Bereich der natürlichen Zahlen etwa kann man Funktionen durch formale Ausdrücke angeben, mit denen implizit gemeint ist, da\sssie eine Vorschrift zurBerechnung des Wertelements aus den Paaren sind.

Um das Beispiel von Church zu benutzen, so ist der Ausdruck ($x^{2} + x)^{2}$ keine Funktion, sondern er wird benutzt, um auf die Funktion zu deuten, die jedem x die Zahl ($x^{2} + x)^{2}$ zuordnet. Für gegebenes x ist der Ausdruck immereine konkrete natürliche Zahl.

Soll dieser Ausdruck zur Funktionsbezeichnung verwendet werden, so ist es wesentlich hervorzuheben, da\ssx eine Variable ist. Um dieFunktion zu bezeichnen, die die Zuordnung von x zu ($x^{2} + x)^{2}$ beinhaltet, schlägt Church die Verwendung des Zeichens lambda vor:

\begin{center}$(\lambda x.(x^{2} + x)^{2})$\end{center}

Ganz allgemein wird, wenn M ein Ausdruck ist, der x alsfreie Variable ent hält, durch $(\lambda x.M)$ die Funktion bezeichnet, die für ein konkretes Element a aus demDefinitionsbereich den Wert liefert, wenn a und x inM substituiert wird.

Da man sich vorstellen kann, da\ssdie Funktion alsZuordnungsvorschrift durch Verallgemeinerung aus vielen einzelnen Paaren x, M gewonnen wurde, verwendet Church die Redeweise,da\ssdie Funktion, die durch $(\lambda x.M)$ bezeichnet wird, ausM durch Abstraktion gewonnen wurde. $\lambda x$kann dann als Abstraktionsoperator angesehen werden.

Die notationelle Unterscheidung zwischen einem arithmetischen Ausdruck und der Funktion, die nach Übermittlung eines Arguments, d.h. eines Elements aus dem Definitionsbereich, den Wert liefert, der durch Einsetzung des Arguments in den Ausdruck resultiert, ist in jeder modernen Programmiersprache ein Gemeinplatz. Der Unterschied zwischen den Programmiersprachen und dem lambda-Kalkül liegt im syntaktischen Aufwand: Ob nun, wie in ALGOL60 und anderen Sprachen, Funktionen bzw. Prozeduren mittels Schlüssenworten deklariert werden\footnote{Hier übernimmt dieses Schlüsselwort gewissermaßen Funktionen von lambda, allerdings kommt die Einführung des Funktionsnamens als wesentlicher Dienst der Deklaration hinzu.}.

So kann der lambda-Kalkül heute regelrecht als einfache Programmiersprache angesehen werden ([WEG68], S. 180ff.). Einfach nicht nur deshalb, weil er ein so beschränktes Alphabet hat, sondern weil es auch nur einen Wertetyp gibt: Die Menge der Operatoren (Funktionen) fällt mit der Menge der Operanden zusammen. Außerdem gibt es keine Vielfalt von Anweisungen oder Ausdrücken, sondern Bindung durch Reduktion mittels Substitution von Argument für gebundene Variable ist die einzige ``Grundaktion'', die die Sprache bietet. Der Vorteil ist, daß es keinerlei Seiteneffekte gibt -- der Nachteil, da\ssdie Ausdrückeallzu unstrukturiert vor uns stehen.

Das Alphabet des lambda-Kalküs bestehet nur aus zwei Teilmengen -- der Menge der Variablen (es werden kleine Buchstaben $a, b, c, ..., x, y, z, a, b, ... , z, a,$ ... verwendet) und der Menge der technischen Zeichnen (man käme mit lambda und der runden Klammern aus, allerdings wäre das Ganze dann reichlich unbequem; so werden faktisch auch $\rightarrow$, Punkt und eckige Klammern benutzt. Sie ``werden nur der Bequemlichkeit halber eingeführt und sind kein echter Teil des formalen Systems'' ([CH41], S. 12)).

Aus Bequemlichkeit werden ferner große Buchstaben als Abkürzungen für lambda-Ausdrücke verwendet. Church gibtz.B. folgende Nominaldefinition:

\begin{center}$I\rightarrow (\lambda a.a)$\end{center}

Schematische Definitionen dienen zur Einführung neuer Klassen von Ausdrükken; sie stellen Schemata dar, nach welchen jeder der neuen Ausdrücke für eine wohlgeformte Formel stehen kann. Dabei übernehmen halbfette kleine Buchstaben zusätzliche Sondernfunktionen [CH41].

Die wohlgeformten Formeln (wir werden auch von lambda-Ausdrücken sprechen) werden induktiv definiert ([CH41], S. 8):

(L1) Eine Variable ist eine wohlgeformte Formel.
(L2)   Sind F und A wohlgeformt, so ist auch $(F A)$ eine wohlgeformte Formel. (L3)   Ist M wohlgeformt und enthält mindestens ein freies Vorkommen der Va-  riablen x, dann ist $(\lambda x.M)$ eine wohlgeformte Formel.

Wird die Bedingung, da\ssfreie Vorkommen von x betreffend,fallengelassen, so erhält man den lambdaK-Kalkül ([CH41], S. 58ff.). Was aber ist freies Vorkommen?

(F1) Das Vorkommen der Variablen x in der wohlgeformten Formelx ist frei.(F2) Kommt die Variable x in der wohlgeformten Formel F frei bzw. gebun-
  den vor, so ist sie in $(F A)$ ebenfalls frei bzw. gebunden; kommt sie in A  frei bzw. gebunden vor, so ist sie in der wohlgeformten Formel $(F A)$ eben-
  falls frei bzw. gebunden.
(F3) Die Variable x in $(\lambda x.M)$ kommt nur gebunden vor. Jede andere Variab-
  le y, die in M frei bzw. gebunden vorkommt, ist auch in $(\lambda x.M)$ frei
  bzw. gebunden.

Nach diesen Definition sind folgende Ausdrücke {\em wohlgeformte Formeln:}

\vspace{2mm}

 

$(\lambda x.x\lambda x.x)$ -- $x$ kommt nur gebunden vor;
$(xy)$ -- x und y kommen frei vor;
$(\lambda x.(x(yx)))$ -- y kommt frei und x gebunden vor.

\vspace{2mm}

Die Formeln $(\lambda x.M)$ stellen im Kalkül die Funktionen dar (es genügt die einargumentige Form; durch Verschachtelung kann man leicht mehrargumentige Funktionen simulieren). Die Ausdrücke der Form $(F A)$ drücken die Anwendungen der Funktion F auf ein Argument A aus und werden zur Darstellung der formalen Berechnungsvorgänge verwendet. Diese Berechnungsvorgänge oder Auswertungen beruhen auf der Substitution von Argument für gebundenen Variable bzw. auf der Unbenennung der gebundenen Variablen und werden als Konversionen bezeichnet. Drei dieser Transformationsregeln sind erlaubt:

(K1) Jeder Teil M einer Formel darf durch das Resultat der Substitution einer
  Variable x für eine Variable y überall in M ersetzt werden, vorausge-
  setzt, da\ssy keine freie Variable in M ist und x noch nicht in M vor-  kommt.
(K2) Jeder Teil $((\lambda x.M)N)$ einer Formel darf durch das Resultat der 
Substi-
  tution von N für x in M ersetzt werden, vorausgesetzt, da\ssdie gebunde-  nen Variablen von M von x und von den freien Variablen in N verschieden  sind. 
(K3) Jeder Teil einer Formel, der durch Substitution von N für x in M ent-  standen sein kann, darf durch $((\lambda x.M)N)$ ersetzt werden, vorausgesetzt,
  da\ss$((\lambda x.M)N)$ wohlgeformt ist und die gebundenen Variablen von M ver-  schieden sind von x und von freien Variablen in N.

Der Begriff ``Teil'' in diesen Regeln ist so zu verstehen, da\sses sich umeine Teilzeichenkette der gesamten Formel handelt, die selber eine wohlgeformte Formel ist und nicht direkt auf das lambda-Symbol folgt (d.h. keine Variable in Bindungsstellung ist).

Die Regel (K1) ist die Umbenennungsregel, die Regel (K2) dieReduktionsregel und die Regel (K3) die Expansionsregel.

Eine Reduktion ist eine Anwendung von Regel (K2), usw. ErlaubteUmbenennungen sind z.B. $(\lambda x.(xy))$ zu $(\lambda z.(zy))$, Reduktionen z.B. $(\lambda x.x\lambda x.x)$ zu $(\lambda x.x)$. Natürlich stellt die Reduktionsregel die grundlegende Regel dar, da Umbenennungen nur erforderlich sind, um Namenskonflikte zu lösen. Ziel der Konversion ist ein lambda-Ausdruck, auf den keine weitere Reduktionen angewandt werden können. Ein solcher heißt Normalform oder reduzierte Form [WEG68]. Es gibt Ausdrücke, die keine Normalform haben; etwa

\begin{center}$((\lambda x.(xx)x))(\lambda x.((xx)x)))$.\end{center}

Durch eine kanonische Umbenennung [CH41][S.14] oder Bildung aller reduzierten Formen, die durch Umbenennung ineinander übergeführt werden können, kann ein Endresultat der Auswertung spezifiziert werden, das nach dem Church-Rosser-Theorem eindeutig ist, d.h., gelangt man nach zwei verschiedenen Folgen von Reduktionen und Umbenennungen zu zwei Normalformen, dann liegen sie in der selben Werteklasse bzw. können in die gleiche prizipielle Normalform übergeführt werden. Die lambda-Ausdrücke ohne Normalform heißen {\em nicht definiert} oder ohne Sinn.

Im lambda-Kalkül ist die Auswertungsreihenfolge also ohne Belang für das Endresultat. (Im lambda-K-Kalkül besteht die Möglichkeit, da\sseine Folge von Reduktionen zu einer Normalform führt, die andere nicht.) Wie Wegner bemerkt, bedeutet dies, da\sslambda-Ausdrücke parallel ausgewertet werden können durch asynchrones Multiprocessing in willkürlicher Auswahl lokaler Teilausdrücke [WEG68][S.185].

Während im einfachen lambda-Kalkül demnach beliebige Strategien für die Auswahl der nächsten Reduktion möglich sind -- etwa immer im innersten linken Teilausdruck anzufangen und damit praktisch die Aufrufregel Call-By-Value durchzuführen -- ist das im lambda-K-Kalkül nicht möglich. Es läßt sich jedoch zeigen, da\sshier eine Strategie, die der Regel Call-By-Name entspricht (von links-außen anfangen) akzeptable Resultate liefert [WEG68][S.186].

Im Lichte unserer Bemerkungen über bedingte Ausdrücke und die Darstellung rekursiver Funktionen ist es reizvoll, noch etwas in Churchs Weise, die Äquivalenz von lambda-Definierbarkeit und Rekursivität zu zeigen, einzudringen.

Es war schon gesagt worden, da\ssder Definitionsbereich der Funktionen im lambda-Kalkül die Menge dieser Funktionen selbst ist. Die natürlichen Zahlen werden demzufolge als Abkürzungen für Funktionen eingeführt:

\vspace{3mm}

 

(N) $1\rightarrow (\lambda a.(\lambda b.(ab)))$
  $2\rightarrow (\lambda a.(\lambda b.(a(ab))))$
  $3\rightarrow (\lambda a.(\lambda b.(a(a(ab)))))$, usw.

\vspace{3mm}

Natürlich mu\ssnun, um Konfusionen zu vermeiden, zwischen 1 1 und 11 unterschieden werden (das Leerzeichen ist kein Bestandteil des Alphabets) -- dazu wird eine Überstreichung mehrstelliger Zahlen verwendet.

Innerhalb der möglichen Argumente läßt sich damit der Definitionsbereich der natürlichen Zahlen eingrenzen. Eine Funktion F von natürlichen Zahlen heißt lambda-definierbar, wenn es eine Formel F gibt so da\ss

 

Die Nachfolgerfunktion kann nun definiert werden:

\begin{center} $S\rightarrow (\lambda a.(\lambda b.(\lambda c.(b(ab)c))))$ \end{center}

Um ähnliche Ausdrücke abzukürzen, wird vereinbart, da\ssin so einem Fall nur ein lambda geschrieben werden mu\ss, aber ein Punkt zwischen der letzten Bindungsvariable (d.h. hier c) und dem hinteren Teil (dem Körper) notiert wird. Außerdem darf die jeweils äußere Klammer weggelassen werden:

\begin{center} $S\rightarrow \lambda abc.b((ab)c)$ $\{x + y\}\rightarrow \lambda ab.((xa) ((ya)b)).$ \end{center}

Die anderen Grundoperationen $*$ und Potenzierung werden mit ähnlichen komplizierten Ausdrücken eingeführt. Für die Behandlung der rekursiven Funktionen mu\sses jedoch Auswahl- oder Bedingungsoperationen geben, um etwa das Schema der primitiven Rekursion oder die Mimimierung ausdrücken. Dies wird mit Hilfe der geordneten Paare und Triaden erreicht:

\[[M, N] \rightarrow \lambda a.aMN ( = \lambda a.((a M)N),\]

\[[L, M, N] \rightarrow \lambda a.aLMN (= \lambda a.(((a L)M)N)),\]

\[2_{1} \rightarrow \lambda a.a(\lambda bc.((c I)b)),\]

\[2_{2} \rightarrow \lambda a.a(\lambda bc.((bI)c)),\]

\[3_{1} \rightarrow \lambda a.a(\lambda bcd.((((c I)d)I)b)),\]

\[3_{2} \rightarrow \lambda a.a(\lambda bcd.((((b I)d)I)c)),\]

\[3_{3} \rightarrow \lambda a.a(\lambda bcd.((((b I)c)I)d)).\]

Die Funktionen $2_{i}$ und $3_{j}$ sind praktisch Selektoren, denn es läßt sich zeigen, da\ss$2_{1}[M, N]$ zu $M$ reduzierbar ist, ebenso $2_{2}[M,N]$ zu $N$, $3_{1}[L, M, N]$ zu L, $3_{2}[L, M, N]$ zu $M$ und $3_{3}[L, M, N]$ zu $N$.

Mit Triade und 3-Selektoren läßt sich nun die Vorgängerfunktion $P$definieren,

und damit eine Bedingung darstellen:

\[P\rightarrow \lambda a.3_{3}(a(\lambda b.[S(3_{1}b), 3_{1}b, 3_{2}b])[1, 1, 1]).\]

Grundlage dieser Möglichkeit sind die zwei Reduktionsbeziehungen

\begin{center}$(\lambda b.[S(3_{1}b), 3_{1}b, 3_{2}b]) [K, L, M]$ wird reduziert zu $[SK, K, L]$\end{center}

und

\begin{center}$(A(\lambda b.[S(3_{1}b), 3_{1}, 3_{2}b])[1, 1, 1]$ ist reduzierbar zu $[SA, A, B]$,\end{center}

wenn A eine natürliche Zahl repräsentiert, dann stellt B den Vorgänger dar. Die Startbedingung $[1, 1, 1]$ sorgt dafür, da\ss$1$ anders behandelt wird als die folgenden Zahlen.

Auf dieser Grundlagen kann dann weiter aufgebaut werden: Subtraktion, Minimumbildung usw. sind nun definierbar. Noch der dem primitiv rekursiven Schema entsprechende Ausdrruck ist strukturell mit der Vorgängerfunktion verwandt:

Die Formel F, die der durch die Funktionen $G_{1}$und $G_{2}$ primitiv rekursiv definierten Funktion F:

\[F(x_{1}, ... ,x_{n},l) = G_{1}(x_{1}, ... ,x_{n}),\]

\[F(x_{1}, ... ,x_{n},y + 1) = G_{2}(x_{1}, ... ,x_{n},y,F(x_{1}, ... ,x_{n},y))\]

entspricht, lautet:

\[F\rightarrow \lambda x_{1}, x_{2}, ..., x_{n}.3_{3}(y(\lambda z.[S(3_{1}z), G_{2}(x_{1}, ... ,x_{n}, 3_{1}z, 3_{2}z), 3_{2} z][l, G_{1}(x_{1}, ... , x_{n}), 1).\]

Man sieht deutlich, wie in der Startbedingung nun statt der 1 eine dem Ausdruck $G_{1}(x_{1}, .... , x_{n})$ entsprechende Formel steht und da\ssdas mittlere Element der Triade auf die erforderliche Art rekursiv weitergestellt wird.

Ohne Zweifel aber ist diese Notationsweisen auch mit halboffiziellen Abkürzungen einigermaßen unbequem und unverständlich.

 

LISP als Implementation des lambda-Kalküls

Stellt LISP eine korrekte Implementation des lambda-Kalküls dar? Diese Frage kann weitgehend positiv beantwortet werden, denn die gelegentlich geäußerte Meinung, LISP sei auf der Grundlage eines dynamischen Variablen-Wert-Bindungsschemas zu implementieren [ALL78,BAK77a], ist falsch [BERR70]. Obwohl viele existierende Implementationen dem Vorbild von LISP1.5 hierin nicht folgen, also keine korrekte Implementationen des lambda-Kalküls darstellen\footnote{eigentlich auch keine korrekte LISP-Implementation}, ist LISP mit vollständig durchgeführten FUNARG-Mechanismus korrekt. Der FUNARG-Mechanismus sichert nämlich das statische Variablen-Wert-Bindungsschema [BERR70,DI60] und die Erhaltung der Wertbeziehungen (retention)[BERR70].

Für diese Einschätzung kann selbstverständlich nur das ``reine LISP'' in Betracht gezogen werden, da die erzeugbaren Seiteneffekte jede Bindung zerstören können.

Inzwischen ist in LISP-Kreisen eine deutliche Abkehr von der Idee anzutreffen, die dynamische Bindung sei die korrekte Implementationstechnik. Dialekte wie SCHEME, CommonLISP und 3LISP sind definiert worden, die gerade die korrekte statische (auch ``lexikalische'') Bindungssemantik realisieren.

Wir betrachten bei der Begründung der obigen Behauptung nur die $\alpha$-Regel und die $\beta$-Regel (d.h. (K1) und (K2)). Die Regel (K3) wird in LISP überhaupt nicht beachtet und ist auch bei der Konversion zur Normalform uninteressant.

Die $\alpha$-Regel kann in LISP nicht falsch implementiert werden, da sie überhaupt nicht benutzt wird (d.h. sie ist im LISP-Kalkül nicht verfügbar). Wo sie bei (bzw. vor) Anwendung der $\beta$-Regel (K2) erforderlich ist, wird sorgfältig die Korrektheit zu prüfen sein.

Allens [ALL78][S.171] Behauptung, auch die $\alpha$-Regelwäre in LISP sinnvoll, aber nicht korrekt durchführbar, ist in der gegebenen Form nicht aufrecht zu erhalten: Allen nimmt als Gegenbeispiel an, da\ssim Ausdruck

\begin{center}$(\lambda x.fx))$ bzw. (LAMBDA (X) (F X))\end{center}

x in f frei vorkomme. Dies ist explizit aber in der Regel verboten (vgl. S. 92). In der von Allen zitierten Regel fehlt diese Bedingung. So kann

\begin{center}$(\lambda x.fx)$ mit $f\rightarrow (\lambda y.xy)$\end{center}

niemals zu $(\lambda x.(\lambda y.xy)x)$ führen. Wenn die Aktion in LISP möglich, im lambda-Kalkül aber verboten ist, so kann man hierin keinen Versto\sssehen: Sie ist auszuklammern. (???)

Etwas Sinn in diese Behauptung kann man nur bringen, wenn sie betreffs der $\beta$-Regel ausgesprochen wird, um f zu einer Variablen zu machen.

In LISP kann die freie Variable in $f$ nur innerhalb einer Definition erscheinen:

\begin{center}$f\rightarrow (\lambda z.xz)$ bzw. (DE F (Z) (X Z)).\end{center} X wird gewissermaßen im Hauptniveau (top level) gebunden. Um die gleiche Situation im lambda-Kalkül widerzuspielen, genügt die ohnehin ``informale'' Definition nicht: Eine explizite Bindung mu\ssnotiert werden:

\[(\lambda f.(\lambda x.fx)(\lambda z.xz)).\]

In diesem Kontext stellt sich nun aber folgendes heraus: Nach Substitution des Ausdrucks $(\lambda z.xz)$ für f würde in der Tat das freie x in $f$ in den Bindungsbereich des anderen $x$ geraten. Diese Substitution ist aber nicht erlaubt -- die Regel (K2) verbietet es.

Betrachten wir nun also die Regel (K2) und ihre Verwirklichung in LISP. Ihre Anwendung ist im lambda-Kalkül nur erlaubt, wenn in dem für die gebundene Variable x zu substituierendenAusdruck $N$ keine Variable frei ist, die innerhalb des Körpers $M$ gebunden vorkommt oder wenn x nicht noch einmal in $M$ gebunden auftritt. Vor der Anwendung mu\ssim lambda-Kalkül mittels der $\alpha$-Regel (K1) unbenannt werden.

Die zweite Bedingung besagt, da\ssdie Substitution nur im Bindungsbereich von x durchzuführen ist. Innere erneuteBindungsbereich sind durch Umbenennung der Variablen auszuschließen. So ist etwa verboten, da\ss

\[(\lambda x.(\lambda x.x^{2}x)1)\]

mit der Regel (K2) behandelt wird, da nicht

\[(\lambda x.1^{2}x)\]

entstehen darf, sondern

\[(\lambda x.x^{2}1).\]

Deshalb wird vorher eine Umbenennung gefordert:

\[(\lambda x.(\lambda y.y^{2}x)1)\]

ist konvertierbar.

Der Argumentübergabemechanismus (als LISP-Lösung gegenüber der Substitution) kann korrekt ohne diese zusätzlich Forderung vollzogen werden, da die Bindungsbereiche nach innen sorgfältig auseinandergehalten werden. Dadurch geschieht faktisch eine Indizierung -- d.h. die gewünschte Umbenennung [STE76]. Bei Substitution (korrekter lambda-Kalkül-Implementation gemä\ssder Regeln) ist entweder die Forderung aufrechtzuerhalten oder eine genaue Prüfung der Bindungsbereiche durchzuführen.

Die erste (noch unerledigte) Bedingung besagt, da\ssfreie Variable aus $N$ nicht in innere Bindungsbereiche gebracht werden dürfen, d.h., es ist verboten, da\ss

\[(\lambda x.(\lambda y.xy1)y)\]

in

\[(\lambda y.yyl) = (11)\]

transformiert wird. Statt dessen mu\ssumbenannt werden:

\[(\lambda x.(\lambda z.xz1) y),\]

und es wird es richtig zu

\[(\lambda z.yz1) = (y 1)\]

konvertiert.

Diese Bedingung ist in LISP offensichtlich verletzt, wenn ohne {\tt FUNARG} gearbeitet wird, da in diesem Fall der Argument-Übergabe-Mechanismus keine Indizierung durchführt. Genauer gesagt wird die zunächst korrekt gemachte Indizierung nicht geschützt und so durch die innere Konversion überschrieben: Aus

$((\lambda x.(\lambda y.xy)1)$ \=$y)$  .
 .
 .
 $E_{0}$

wird nicht

$(\lambda y.$\=$yyl)$   sondern $(\lambda y.yy)$. .
 .
 .
 $E_{0}$

Eine Lösung bietet FUNARG durch ``Abschließung'' des freien y und daraus folgender Verhinderung der falschen Umbenennung (Indizierung). Es entsteht so wirklich

$(\lambda y.$\=$yy1)$   und   $($\=$y1)$. . .
 . .
 . .
 $E_{0}$  $E_{0}$

Die Umbenennungsindizes müssen also vor Neuindizierung geschützt werden.

In LISP formuliert lautet das entsprechende Probblem etwa:

\begin{center}(SETQ Y 'ADD1)(DE F(X) (G 1))(DE G(Y) (X Y))(F 'Y).\end{center}

Hier wird ein Fehler ausgelöst, weil im Innern von G einmal die richtige (letzte) und einmal die falsche (nicht die erste) Bindung benutzt wird. Der Wert von X ist Y und, der Wert von Y ist 1, so da\ssder semantisch sinnlose Ausdruck

\begin{center}(1 1)\end{center}

auszuwerten ist.

Durch Mitnahme der Bindungsumgebung (Indizierung) und Erzeugung eines FUNARG kann dieses Problem gelöst werden:

\begin{center} (SETQ Y 'ADD1)(DE F(X) (G 1))(DE G(Y) (X Y))(F (FUNCTION Y)).\end{center}

Diesmal ist die Bedeutung von X das FUNARG:

\begin{center}(FUNARG Y $Umgeb.$),\end{center}

wobei in der Umgebung $Umgeb.$ Y zu ADD1 gebunden ist. Demnach wird schließlich statt (1 1) der Ausdruck {\tt (ADD1 1)} auszuwerten sein. Alles läuft korrekt ab, der Wert ist 2.

Soweit zu den Bedingungen für die Ausführbarkeit der $\beta$-Regel (K2). Nun zur Durchführung selbst. Diese läuft in LISP immer korrekt ab, wenn alle Variablennamen verschieden sind\footnote{Weil sich dies im Fall rekursiver Funktionen nicht vermeiden läßt, sind die ersten Beispiele für Probleme bei der korrekten Bindung rekursive Funktionen. Sie beruhen darauf, da\sseines der Argumente der rekursiven Funktionen ein funktionales Argument ist, das ein anderes Argument der Hauptfunktion frei enthält. Durch den rekursiven Aufruf wird dieses freie Vorkommen in einen gleichnamigen Bindungsbereich übergeführt.} und wenn die Konversion normal von außen nach innen abläuft. Da die Substitution durch einen Mechanismus zur Wertübergabe ersetzt ist, bleiben die Variablennamen in den Ausdrücken erhalten. Daraus können sich zwei Arten von Konflikten ergeben: 1., beim Verlassen eines lambda-Ausdrucks gehen die Werte verloren, und 2., beim tieferen Eindringen in den lambda-Ausdruck werden sie überschrieben.

Zur 1. Möglichkeit. Im lambda-Kalkül wird

\[((\lambda f g. (\lambda x.f g x)f_{1}f_{2})arg)\]

zu

\begin{center}$f_{1}f_{2}arg$ bzw. $(f_{1}(f_{2}arg))$\end{center}

konvertiert. In LISP ohne FUNARG (d.h. dynamischer Bindung) ergibt sich:

 (SETQ F 1) (SETQ G 2) (DE COMPOSE(F G) (LAMBDA(X) (F (G X)))) ((COMPOSE F1 F2) 'ARG).

Es entsteht (1(2 ARG)), weil außerhab des {\tt COMPOSE}-Körpers F und G die Werte 1 und 2 haben.

Durch Erzeugung eines FUNARG -- Abschließung und damitMitnahme der Bindungsumgebung innerhalb COMPOSE -- kann diesesProblem beseitig werden:

 (SETQ F 1) (SETQ G 2) (DE COMPOSE(F G) (FUNCTION (LAMBDA(X) (F (G X))))) ((COMPOSE F1 F2) 'ARG)

wird im Verlauf der Auswertung zu:

\begin{center}(FUNARG (LAMBDA(X) (F (G X))) Bindung)\end{center}

In der Bindung sind folgende Assoziationen:

\begin{center}F... Wert ist F1G... Wert ist F2\end{center}

und damit zu:

\begin{center}(F1 (F2 ARG)).\end{center}

Überschreibungen im Innern des lambda-Ausdrucks sind einerseits nur möglich, wenn gegen die Beschränkung verstoßen wird, da\ssdie Variable im Innern erneut wieder gebunden auftritt. Andererseits kann die Überschreibung durch Transport einer freien Variablen (der bereits ein Wert, d.h. ein Index, zugeordnet ist) in eine Bindungsumgebung geschehen -- dies ist ebenfalls bereits besprochen worden.

LISP kann also durch gewisse notationale Hilfsmittel (FUNCTION)und die durch FUNARG erzwungene statische Bindung und Aufbewahrung (Retention) derselben den lambda-Kalkül korrekt modellieren.

Der Argumentübergabemechanismus (call-by-value) tritt dabei gar nicht in Erscheinung. Er bedeutet lediglich Bevorzugung einer Auswertungsreihenfolge, die aber im Bereich der ``sinnvollen'' lambda-Ausdrücke erlaubt ist (Church-Rosser-Theorem). Auf Grund seiner Eigenschaften in bezug auf nicht-strikte Funktionen wird aber der Mechanismus Call-By-Name dem lambda-Kalkül mehr gerecht [MORS68].

Funktions-basierte Programmiersprachen (Ausdruckssprachen)

LISP entwickelte sich aus FORTRAN unter Betonung der algebraischen Bestandteile der Sprache. McCarthy schien es von großer Wichtigkeit, durch Verschachtelung einfacher Terme komplizierte Aktionen auslösen zu können. Die Verschachtelung entspricht ja der Funktionskomposition.

Durch die Erfindung der bedingten Ausdrücke wurde dieser Ansatzausgeweitet, so da\ssauch herkömmliche, in mehreren Schritten zu programmierende algorithmische Abläufe in einem umfassenden Term dargestellt werden konnten.

Da die Programmierer mit der neuen funktions-orientierten Programmierung, die mit den Termen allein möglich war, nicht zurecht kamen, erweiterte McCarthydas Konzept und beschrieb auch echte Aktionen durch Terme. Die Listendarstellung der Programme (S-Ausdrücke) erzwang die notwendige Vereinheitlichung: Auch die Teile von LISP, die völlig den FORTRAN-Statements entsprachen, mußten durch S-Ausdrücken dargestellt werden. Auch ihre Verwendung außerhalb der sequentiellen Programmstücke (PROG-Körper) konnte nicht gut verboten werden -- also mußten möglichst natürliche Werte festgelegt werden. So wurde LISP zu einer Sprache, die sowohl als funktions-basiert als auch als anweisungs-orientiert angeshene werden kann. Eine solche Sprache nennt man auch ``Ausdruckssprache'', denn jedes Sprachelement nimmt einen Wert an.

LISP war die erste dieser Art -- inzwischen sind weitere gefolgt. Das Beispiel der Sprache BLISS [WU70] zeigt, da\ssdas Prinzip der Ausdruckssprache sehr wohl vereinbar ist mit hoher Effizienz der compilierten Maschinenprogramme. Im Vergleich zu BLISS hatte LISP1.5 eine eher arme Menge an Steuerkonstrukten. Neuere Systeme wie CommonLISP oder SCHEME sind jedoch reicher.

Die Charakteristik, eine Ausdruckssprache zu sein, hat zwei Aspekte: Einerseits beruht sie auf der Feststellung, da\ssjedes Sprachelementeinen Wert annimmt. Dies erscheint im Himblick auf mögliche Implementationen sinnvoll und an Erscheinungen auf dem Maschinenniveau anknüpftend: Wenn man mit Maschinen arbeitet, bei denen ein Rechenregister (Akkumulator) existiert, dann ist klar, da\ssnach jeder Aktion irgendeinWert im Akkumulator zurückbleibt -- dies kann sehr naheliegend als der ``Wert'' betrachtet werden.

Schwieriger fällt allerdings hier die Assoziation, wenn eine Reihe von Akkumulatoren oder allgemeiner Register existiert: Nach der Abarbeitung eines beliebigen Programmstücks kann nicht ein Wert ausgezeichnet werden -- vielmehr wurde ein Zustand erreicht.

Der zweite Aspekt der Ausdruckssprachen beruht darauf, da\ssbei der Verschachtelung von Ausdrücken, die keinerlei Seiteneffekt auslösen, -- d.h. wenn man sich auf den funktions-basierten Teil allein beschränkt -- der Wert des Gesamtausdrucks nur von den Werten der Teilausdrücke abhängt: Der Austausch eines beliebigen von ihnen durch einen anderen, solange der Wert gleich bleibt, ändert daran nichts\footnote{referential transparency nach Quine [QIN60}]. So wird der Begriff des Werts für Ausdruckssprachen zur zentralen semantischen Kategorie -- der Zustand des Speichers (d.h. verschiedenster Register und Programmgrößen) wird nebensächlich -- lediglich eine Frage der Implementation.

Die Entdeckung, da\sses eine abgeschlossene Teilsprache von LISP gibt, die der Hauptforderung -- keine Seiteneffekte -- genügt, war Anla\sszur Erforschung derselben, des ``reinen'' LISP, und zur Betonung beschreibenden Charakters von seiteneffektlosen Ausdruckssprachen \footnote {funktions-basierte Sprachen im eigentlichen Sinne, auch als deklarative Sprachen [LOM62], applikative Sprachen [SY66], denotative Sprachen [SY66] etc. bezeichnet.}.

Auch der lambda-Kalkül ist, im Lichte der Rechenschritte Variablenumbenennung und Substitution (Konversion) als Programmiersprache gesehen, eine Ausdruckssprache. Der Wert eines lambda-Ausdrucks ist seine Normalform. Dieser Wert wird durch eine nicht spezifizierteAbfolge von Rechenschritten erreicht, bzw. der Auswertungsproze\ssterminiert nicht, weil keine Normalform ermittelt werden kann. Bei einer wichtigen Teilklasse (den definierten lambda-Ausdrücken, [WEG68]) von lambda-Ausdrücken wird immer eine Normalform erreicht, gleichgültig in welcher Reihenfolge und auf welche Elemente des betreffenden Ausdrucks die Rechenregeln angewendet werden. Auch hier wird die Frage des algorithmischen Ablaufs uninteressant -- der lambda-Ausdruck scheint nicht so sehr einen Wertermittlungs- bzw. Rechenproze\sszu bezeichnen, sondern einen Wert allein.

Das gleiche gilt für das reine LISP, obwohl hier eine feststehende Auswertungsreihenfolge durch die Standardimplementation im Hintergrund steht -- der Variablenübergabemechanismus ``Aufruf mit Wertübergabe'' (call-by-value, innermost-left).

Der Bedeutungsverlust der sonst zu zentralen Begriffe gehörenden Speicherzustand und zeitlicher Ablauf macht funktions-basierteSprachen zu einem interessanten Forschungsobjekt.

Wenn eine Programmiersprache gewöhnlich dazu dient, ein Programm zu notieren, so scheinen\footnote {Zunächst ist die Bedeutung der drei Begriffe nach Morris ziemlich klar. Die Ausdeutung für Programmiersprachen scheint dagegen für Semantik und Pragmatik kontrovers zu sein.} die Relationen zwischen den Sprachelementen, der Bedeutung und der Benutzung wie folgt angegeben zu sein:

Die Syntax beschreibt die Beziehungen zwischen den Zeichnen untereinander -- die erlaubten Kombinationen, die Regeln, nach denen für eine gegebene Zeichenkette entschieden werden kann, ob sie zur Sprache gehört usw.

Die Semantik beschreibt die Beziehungen der Zeichenkette zuihrer Bedeutung. Die Bedeutung des Programms in den höheren Sprache ist das Programm in der Maschinensprache. So hat die Semantik die Korrektheit von Übersetzungsverfahren zu prüfen bzw. durch Entwicklung geeigneter Instrumentarien zur Beschreibung der Bedeutung von Konstruktionen in Programmiersprachen zu gelangen, die für die Übersetzerherstellung maßgebend sein kann.

Die Pragmatik untersucht die Beziehung zwischen Programm und Nutzer -- hier sind Fragen der Zweckmäßigkeit, Bequemlichkeit, Verwendbarkeit, Verständlichkeit und Abarbeitbarkeit des gegebenen Programms wichtig. Statt der semantischen Bewertung mit der Wahrheitsfunktion lassen sich Programme als imperative Strukturen nur pragmatisch bewerten.

So ``realisiert'' der Syntaxprüfer die Syntax, der Compiler die Semantik und der Rechner einen guten Teil der Pragmatik.

Überraschenderweise verschieben sich diese Relationen bei den funktions-basierten Sprachen: Die Syntax behält ihre Funktion, aber Semantik und Pragmatik sind neu auffaßbar: Es gibt gute Gründe dafür, da\ssein komplexer Ausdruck keineswegs die Folge der ihn realisierendenBefehle auf Maschinenniveau bedeutet, sondern lediglich den Wert bezeichnet. (Deshalb ja auch der Terminus ``deklarativen Sprachen''.) Damit wird sich die Semantik nicht mit der Beziehung zu einem Programm niederen Niveaus befassen, sondern mit der Beziehung des Ausdrucks zu seinem Wert. Weil der Ausdruck aus einfachen Teilausdrücken besteht, hat die Semantik die Beziehung zwischen den Werten der Teilausdrücke und dem Gesamtwert zu untersuchen. Demnach richten sich hier die Bemühungen auf die Feststellung der Verknüpfung von Werten -- d.h. die funktionale Beziehung\footnote {Wie wäre sonst der Satz Landins [LAN66]zu interpretieren: ``Für reine Ausdrücke hat ausschließlich der Wert semantische Bedeutung''.}.

Mit einem Ausdruck wird nicht ein Programm beschrieben, sondern eine funktionale Beziehung zwischen Werte zum Ausdruck gebracht. Diese Beziehung wird durch die Auswertung realisiert. So ist es kein Wunder (obwohl historisch nicht beabsichtigt), da\ssso häufig für Ausdruckssprachen statt des Compilers ein Interpreter die Sprachverarbeitung übernimmt\footnote {Beachte dagegen Allens [ALL78][S. 162] Ansicht, da\sssogenannte operational semantics zur Pragmatikzu rechnen sei.}.

Zeitweise waren die Programmiersprachenwissenschaftler scharf geteilt in eine Partei, die die beschreibenden Sprachen befürwortete, ihre leichte Verständlichkeit hervorhob und zu einer guten Sprache unbedingt die Eigenschaft, Ausdruckssprachen zu sein, rechnete [SY66], und in die Gegenpartei, die diesen Standpunk rigoros ablehnte und eigentlich in allen Punkten völlig gegenteiliger Meinung war. Selbst das Argument der Liebhaber von Ausdruckssprachen, da\ssihre Sprachen das Verifizieren von Programmeigenschaften leichter gestatte, als dies im Fall von sequentiellen Sprachen mit Anweisungen und Sprüngen möglich sei, akzeptierten sie nicht und betonten, die Übergänge zwischen Zuständen seien einfacher beschreibbar und damit verifizierbar.

Heute hat sich der Streit merklich abgekühlt, obwohl die Fronten weiterhin zu bestehen scheinen. War es zunächst die Unklarheit, wann Sprachelemente wirklich beschreibend und wann sie anweisend (imperativ) seien, so hat sich inzwischen deutlich herausgestellt, da\ssdie Kriterien fehlen, um diese Kontroverse zu entscheiden. Immerhin ist wohl das Lager derjenigen, die eine Anweisungs-Orientierung befürworten, wesentlich größer als das derjenigen, die für Ausdrücke (Funktions-Orientierung) sind. Dafür hat vor allen die Notwendigkeit, mit riesigen Programmpaketen (10000 bis 100000 Anweisungen) umgehen zu müssen, gesorgt.

Von der Seite der Ausdruckssprachen mu\sseingeräumt werden, da\ssder algorithmische Aspekt, d.h. die Methode, durch schrittweise Zustandsänderung die Lösung zu erreichen, nicht ignoriert, verdammt oder als unverständlich bezeichnet werden kann. In vielen Anwendungen (Echtzeitsysteme) spielt die deutlich zeitlich bestimmte Einhaltung bzw. das Erreichen gewisser Programmzustände eine zentrale Rolle. Hinzu kommen viele Probleme, deren Beschreibung so ungenau ist, da\sssie nur mittels des Lösungsverfahrens, d.h. letztlich mittels des Programms, eingegrenzt werden können. Häufig hat ein Benutzer das unbestimmte Gefühl, da\ssein Programm seine Wünsche erfüllt, ohne da\sser dies klar, geschweige formal, ausdrücken kann (und dieses Gefühl ändert sich meist mit der Zeit). Es scheint zudem so, da\ssauf einem theoretisch recht unklaren Gebiet ein Programm besser durch schrittweise Herantasten an die Lösung entwickelt werden kann.

Demgegenüber ist die Formulierung mittels Ausdrücken oft die elegantere und kürzere. Man beachte dabei jedoch, da\ssgroße Programme (mit 10000 Programmschritten und mehr) in jeder Formulierung unverständlich sind. Die Ausdrucksformulierung dürfte eine weitgehende Kenntnis des Problemhintergrundes und eine gründliche theoretische Erforschung der zugeordneten Gesetze im Objektbereich erfordern.

Die strukturierte Programmierung [DA72,BAT76a] hat zwar deutlich Abläufe betont, d.h. sequentielle und zyklische Strukturen. Der methodische Ansatz der virtuellen Maschinen jedoch kann durchaus innerhalb von Ausdruckssprachen akzeptabel verwirklicht werden: Ausdruckssprachen betonen den Funktionsbegriff und die Notwendigkeit, zur Manipulation von Datenstrukturen Systeme von Basisfunktionen bereitzustellen. Eine harmonische Menge von Basisfunktionen fällt aber mit Dijkstras Begriff der virtuellen Maschine zusammen(siehe überdies [NO74]).

Ausdrücke sind typischerweise Operator-Operanden-Strukturen. Als Operanden kommen selbst wieder Ausdrücke in Frage. Durch das Vorhandensein gewisser einfacher Ausdruckselemente -- Zahlen, Wahrheitswerte, Datenstrukturelemente, aber auch Grundfunktionen und Variablen -- wird die induktive Definition möglich. Um die der Ausdrücke eindeutig zu machen, werden gewisse Regeln formuliert, um zu zeigen, auf welche Operanden sich ein bestimmter Operator bezieht. Dies kann einerseits durch Bezugnahme auf die Stelligkeit der Operatoren erreicht werden: Lukasiewicz' [LUK21] klammernlose Notation des Aussagenkalküls zeigt dies. Will man auch Infixnotationen benutzen, so werden Vorrangregeln für die Operatoren erforderlich. Im allgemeinen versucht man, durch Einführung technischer Zeichen (Klammern) die Übersichtlichkeit und Verständlichkeit von Ausdrücken zu erhöhen und die weitbekannten arithmetischen (algebraischen) Ausdrücke der Elementarmatematik in etwa zu erreichen.

Verzichten wir hier die Einfachheit halber (vgl. die komplexen Ausdrücke bei Landin [LAN66] oder Burge [BUR75]) auf Infixoperatoren, so können wir folgende rekursive Ausdrucksdefinition angeben:

(A1) Alle Zahlen sind Ausdrücke.
(A2) \=Sind die $a_{i}$ Ausdrücke und ist op ein $n$-stelliger Operator, 
dann ist 
 $(opa_{1}, ... ,a_{n})$ ein Ausdruck.(A3) Nur gemä\ssder Regeln (A1) und (A2) werden Ausdrücke gebildet.

Die so definierten Ausdrücke sind relativ arm, da nur eine feste Menge von Operatoren angenommen werden kann. Durch Einführung von Ausdrücken für Operatoren (Funktionen) wird ein entscheidender Schritt getan: Variablen und Bindungsbereiche kommen ins Spiel.

Der Mathematiker schreibt z.B. ``f(x,y), wobei $x=1$und $y=2$ gilt'' (vgl. [LAN66]). Er will damit ausdrücken, da\ssx und y Variablen sind, die mit bestimmten Werten zu belegen sind.

Wie bereits in Abschnitt 3.8 ausgeführt, ist lambda-Kalkül ein entwickeltes System für derartige Ausdrücke. Bindungen werden vollzogen durch die lambda-Notation, Wertbelegung wird mittels Konversion realisiert.

Die oben informell geschriebenen Bindungsverhälltnisse spiegelt der lambda-Ausdruck

\[(\lambda xy.(f x y) 12)\]

exakt wider.

Richtig bequem wird eine Ausdruckssprache erst durch Aufnahme von Mitteln zur Funktionsdefinition. Erst dann wollen wir auch von einer funktions-bbasierten Sprache sprechen. Rein theoretisch kann das zwar vermieden werden, da für nicht rekursive Funktionen lambda-Ausdrücke genügen müssen und für rekursive Funktionen entweder die Label-Lösung von LISP [MCC60c] oder der paradoxe Kombinator Y verwendet werden kann. Die explizite Angabe jeder Funktion macht jedoch einen Ausdruck unleserlich.

Die Bequemlichkeit resultiert auch in einer höheren Abstraktion. Die lambda-Abstraktion, die aus Termen Funktionen macht, ist rein strukturell. Strukturgleiche Terme werden als äquivalent betrachtet und die Klasse dieser Ausdrücke durch den Abstraktor lambda benannt. Bei der Programmierung möchte man aber die funktionale Abstraktion vornehmen: Nicht nurstrukturgleiche Terme sollen in eine Klasse kommen, sondern alle Terme, die bei gleichen Variableneinsetzungen gleiche Werte liefern. Es geht also um die Äquivalenz von Ein-/Ausgabe-Beziehungen! Die Funktionsnamen sollen das Zeigen auf diese Termklasse ermöglichen.

So ist üblich, Mechanismen zu liefern, die eine Variable als Funktion deklarieren: durch Bekanntgabe des Namens, der formalen Parameter und des Funktionskörpers. Ob ohne die von Church nur als bloße Abkürzungen außerhalb des Kalküls gehaltenen Definitionen der lambda-Kalkül in komplizierteren Beweisen noch handhabbar gewesen wäre, kann mit Fug und Recht bezweifelt werden.

Bedingte Ausdrücke a la LISP (vgl. S.83) sind Mittel, um eine weitere Stufe der Übersichtlichkeit zu erreichen. Gleichzeitig kommt durch sie ein deutlich algorithmisches Element ins Spiel: Jede semantische Beschreibung der bedingten Ausdrücke, wen diese in ihrer einsatzfähigsten Art benutzt werden sollen, bezieht sich auf Auswertungsreihenfolgen d.h. algorithmische Abläufe.

Mit Ausdrücken für wiederholte Auswertungen und Steuerausdrücken wie in BLISS [WU70], mit denen Koroutinenaktivierungen beschreibbar sind, wird deutlich das Schwergewicht in Richtung auf die anweisungs-orientierten Sprachen verschoben: Neben dem Wert der Teilausdrücke ist nun durchaus die Vorgeschichte der Abarbeitung wichtig.

Ohne diese anweisungs-orientierten Ausdrucksmittel legen die Ausdruckssprachen dem Programmierer einen statischen Programmierstil -- den funktions-orientierten -- nahe gegenüber dem mehr dynamischen der anweisungs- bzw. instruktions-orientierten Sprachen. Es werden nicht so sehr die zeitlichen Abläufe bei der Abarbeitung eines Algorithmus betrachtet, vielmehr wird in einem gewissen Sinne das Ergebnis beschrieben. Wie der Rechner die Ausdrücke auswertet, kümmert den Programmierer wenig. Dies war auch der Grund, da\ssLombardi [OM62] Ausdruckssprachen als deklarative Sprachen bezeichnete: Ihnen fehlt jede Kommandostruktur, und Prozesse werden als Funktionen beschrieben.

Programme, die in Ausdruckssprachen geschrieben werden, sind a priori strukturiert im Sinne der strukturierten Programmierung. Ausdrücke haben nämlich nur einen Eingang (sich selbst) und eine Ausgang -- wenn ihre Auswertung abgeschlossen ist. Gemeisam mit dem Funktionskonzept ermöglichen sie in naheliegender Weise die Top-Down-Programmierung. Ausdruckssprachen gehen über die Forderungen der strukturierten Programmierung hinaus, indem sie die Beschreibung der Ergebnisse gegenüber der Beschreibung der Mechanismen, die zu den Resultaten führen, ermöglichen. Damit kann eine weitere Vereinfachung bzw. Verbesserung der Programmierung verbunden sein.

Freilich kann die Beschreibung der Ergebnisse durch Ausdrücke sehr komplex sein. LISP trennt noch ein großer Abstand von {\tt PLANNER} [HEW71c], einer Sprache, in der der Benutzer die Zustände plant und dem Rechner Wissen in Form von Theoremen mitteilt. Wie die Auswertungsmechanismus das Wissen zur Erreichung des Ziels verwendet und ob er das überhaupt tut, ist uninteressant, so lange das Ziel erreicht wird.

Es war allerdings schon auf die Problematik hingewiesen worden, da\ssin vielen Zusammenhängen eine Zustandsorientierung die Algorithmisierung eines Verfahrens bzw. die Beschreibung eines Lösungsprozesses vereinfachen kann. Es kommt hier noch ein zweites Element hinzu: Wenn die Abarbeitung so vollständig dem Rechner überlassen wird, stellt sich im Normalfall die Folge ein, da\ssder Wert langsam ermittelt wird. Die Effizienz wird aber wohl immer wichtig sein, solange gerechnet wird. Zwar werden die Maschinen immer schneller, aber auch die Aufgaben gewinnen an Komplexität. Meist steigt die Appetit schneller als das Angebot. Auf Grund dieses Defekts wurde PLANNER von CONNIVER [SUS72a] kritisiert (siehe Abschnitt 4.8). Das implementierte LISP 1.5 im Unterschied zum reinen LISP begegnet einer möglichen Kritik aus dieser Richtung; denn von Anfang an waren anweisungsähnliche Elemente vorhanden.

Es ist in gewissem Sinne das Schicksal von LISP, in seinem Ausdruckteil (``reines" LISP) aus dem Rohmaterial von FORTRAN ein höchst modernes Konzept entwickelt zu haben, während in dem Bereich der sequentiellen Programme alle schlechten Erbschaften der anweisungs-orientierten Programmierung erhalten blieben. Denn in diesem Bereich kann man alle Regeln der strukturierten Programmierung verletzen. In vielen Implementationen sind globale Sprünge erlaubt -- oft kann der Programmierer die Marken berechnen. Durch die Zuordnung eines Werts zu den Anweisungen wird für die trickreiche Mischung der beiden Sprachkonzepte gesorgt: Zuweisungen als Argumente und ebenso Sprünge (die mitten aus einem Auswertungsproze\ssausbrechen) und Funktions-Returns sorgen für die übelste Art der Ausnutzung von Seiteneffekten.

So hebt die Kooperation von Anweisungen und Ausdrücken, in der Art wie das LISP erlaubt, viele positive Eigenschaften reiner Anweisungssprachen wieder auf. Kein Wunder, da\ssDijkstra [DI72] ein Bonmot zitiert, wonach LISP die intelligenteste Art sei, einen Computer zu mißbrauchen...

Man hat sich inzwischen bemüht, disziplinierte Kontrollstrukturen zu entwickeln (vgl. 3.9.3).

Listenverarbeitung

Einleitung

LISP ist, wie schon der Name (LISt Processor) besagt, eine Listenverarbeitungssprache. Hierin folgte es IPL [NEW60], der ersten Programmiersprache für symbolische Berechnungen, die Baumstrukturen für die Repräsentation der symbolischen Daten einführte, d.h. die Listen.

War um 1960 durch die neu aufgekommene Problematik das Interesse an der Implementation symbolischer Verarbeitungssysteme noch recht hoch, so ist hier eine große Veränderung spürbar. Man interessiert sich heute entweder für die Beziehungen der Datenstrukturen zur Programmiermethologie [ASD76], wenn man die Seite der Forschung betrachtet, bzw. für spezielle Probleme der Symbolmanipulation selbst [ASA76]. Die Implementation ist weitgehend in die Hände spezialisierter Hersteller bzw. Systemhalter übergegangen. Von den vielen Ansätzen zur Symbolmanipulation, Listenverarbeitung und Verarbeitung von baumartigen Strukturen und den verschiedenen dafür implementierten Systemen [IM69] sind im wesentlichen nur LISP und SNOBOL [FAR64,FAR66,GRIE68] übriggeblieben.

Dabei mu\ssbemerkt werden, da\ssder Gegensatz zwischen Listen- und Zeichenkettenverarbeitung sehr in der Tiefe liegt. Für viele einfache Anwendungsfälle eignen sich beide Konzepte gleich gut. COMIT [YN62], eine typische Zeichenkettenverarbeitungssprache, wurde auf Grund ihrer Implementationstechnik hin und wieder als Listenverarbeitungssprachen bezeichnet. Auch SNOBOL verwendet gewisse Listentechniken, um die Zeichenketten intern zu manipulieren [MAD67,GRIE75]. Auf der anderen Seite bietet SNOBOL Notationsmöglichkeiten, die über die Darstellung rein linearer Strukturen hinausgehen. Dies galt auch schon für die Zeichenketteverarbeitungssprachen in der Mitte der sechziger Jahre. So wurde auf der Tagung über Symbolmanipulationssprachen folgende Darstellung eines Graphen als Zeichenkette angegeben und für adäquat gehalten: Der Graph

\vspace{3mm}

\begin{picture}(400,120) \put(198,102){a} \put(145,50){d}\put(252,50){b} \put(198,-5){c} \put(150,50){\line(1,1){50}}\put(150,50){\line(1,-1){50}} \put(250,50){\line(-1,1){50}}\put(250,50){\line(-1,-1){50}} \end{picture}

\vspace{3mm}

wird als a(b,d)b(a,c)c(b,d)d(a,c) geschrieben [BO68b][S.222]. Dadurch da\ssdie Zeichenkettenverarbeitung auf dem Algorithmenmodell von Markow [MAR54] und die Listenverarbeitung auf dem Modell der rekursiven Funktionen [KN68] basiert, werden auch theoretisch die gleichen Möglichkeiten gesichert. Gleichzeitig bedeutet dies, da\ssmit beiden Bereichen eine völlig verschiedeneProgrammierkultur verbunden ist. Das Markow-Modell ist das Verarbeitungsmodell von regel-basierten Programmiersprachen, das Modell der rekursiven Methodenliegt unter funktions-basierten Sprachen. Keines der beiden Denkmodellekennt eigentlich Begriffe wie Anweisung, Aktion o.ä. Um denVergleich zu ermöglichen, werden wir eine Abbildung auf ein für beide anwendbares Vokabular versuchen -- die Resultate sind aber mit Vorsicht zu genießen und vor dem Hintergrund der prinzipiellen Verschiedenheit der Verarbeitungsmodelle zu sehen.

Wir versuchen also Unterschiede zu finden, die sich in der Verwendung wiederspiegeln und in der Bequemlichkeit, wie bestimmte Aktionen ausführbar sind. Es dürfte -- trotz der Problematik -- wesentlich für die Charakterisierung der Listenverarbeitung sein, sie durch Vergleich von der Zeichenkettenverarbeitung abzuheben.

Zunächst kommen eine Reihe von Unterschieden in den Datenstrukturen selbst zum Ausdruck: Zeichenketten sind vom Konzept her linear, d.h., selbst wenn es im Formalismus dieser oder jener Sprache möglich ist, da\sskompliziertere Strukturen beschreibbar sind, so liegt doch die Betonung auf der Linearität. Vom Gegenstandbereich (Texte in natürliche Sprache) wird man in Sonderfällen ebenfalls eine Dreiebenenstruktur erwarten: Sätze -- Wörter -- Buchstaben.

Listen sind dagegen Darstellungsmittel für allgemeine Baumstrukturen, d.h., konzeptionell spielen Teilordnungen zwischen den Elementen eine entscheidende Rolle. Die Zahl der Listenebenen, durch die diese Ordnungsrelationen repräsentiert werden, ist prinzipiell unbegrenzt (und spielt eigentlich gar keine Rolle). Wegen der Bequemlichkeit des menschlichen Nutzers (bzw. seiner Verständnisgrenzen) hat die horizontale Ordnungsrichtung eine besondere Bedeutung. Es ist sinnvoll, von linearen Listen zu sprechen [KN68], ja dieser Extremfall liegt sogar recht häufig vor.

Andererseits ist es möglich, allgemeine Graphenstrukturen, unter anderem zirkulären Listen, in Listenverarbeitungssystemen zu behandeln. Allerdings wird dann die Komunikation mit dem Menschen problematisch. Ideen für die Ein- und Ausgabe von zikulären Listen wurden zuerst von G. van der Mey für das LISP 1.5 auf der X8 [POE67] entwickelt, und InterLISP [TE74] traf hier ähnliche Vorsorge.

Im Unterschied zu den linearen Listen, wo der Programierer meist einzelne Elemente im Auge hat, interessiert sich der Anwender eines Zeichenkettenverarbeitungssystems für Folgen von Zeichen [EL75][S.184].

Vergleich mit Zeichenkettenverarbeitung durch Betrachtung der Grundoperationen

Dem Markowschen Algorithmenmodell folgend stehen bei der Transformation von Zeichenketten die Operationen der Suche nach Teilzeichenketten und die Ersetzung einer solchen Teilkette durch eine andere bzw. der Austausch verschiedener Teilketten im Vordergrund.

In der Listenverarbeitung werden dagegen Suchoperationen seltener augeführt. Insbesondere findet man so gut wie nie Operationen, die sich auf eine lineare Folge gewisser nebeneinanderstehender Listenelemente beziehen. Die Verarbeitung ist element- bzw. restlistenorientiert. Sie läuft ab, indem neue Listen rekursiv auf Grund der Analyse alter Listen aufgebaut werden, beginnend mit den Basiselementen. Eine Grundoperation [KN68][S. 409], die nur für allgemeine Listen interessant und für Zeichenketten völlig belanglos ist, ist das Durchqueren (traversing).

Beim Vergleich zweier Zeichenketten interessiert (neben einfacheren Fragen, wie etwa der nach der lexikalischen Ordnung) die Identität oder die Eigenschaft, Teilkette zu sein. Für Listenstrukturen ist die Identität weitgehend uninteressant: Was interessiert, ist die Strukturgleichheit. Strukturähnlichkeitsvergleiche kommen ursprünglich aus dem Bereich der Zeichenkettenverarbeitung (PostscheProduktionen!), doch sind sie auch für Listenstrukturen interessant. Wir sprechen heute neutral vom ``Mustervergleich'' (pattern matching).

 

Eine ganze Reihe der Basisoperationen, die für die Manipulation der Zeichenketten bzw. Listen zur Verfügung zu stehen haben, ähneln sich weitgehend. Man findet [EL75]:

  1. a) den Zugriffsoperator ACCESS. Im Zusammenhang mit Zeichenketten hat dieser Operator gewöhnlich drei Argumente: die Objektzeichenkette, das Zeichen, von dem ab in dieser Zeichenkette ein Teil zugegriffen werden soll und schließlich die Länge dieses Teils.

    Will man auf Teile von Listen zugreifen, dann werden selten Teilstücke bestimmter Länge benutzt. Vielmehr wird zwischen Element und Rest unterschieden.

     

  2. b) den Zugriffsoperator FIRST. Bei Anwendung auf Zeichenketten ist es vernünftig, diesem Operator zwei Argumente zu geben: die Objekzeichenkette und eine Angabe darüber, wie lang das Anfangsstück sein soll. Im Zusammenhang mit Listen repräsentiert FIRST einen der grundlegenden Zugriffsoperatoren, mit dem das erste Element einer Liste geliefert wird.

     

  3. c) den Zugriffsoperator NEXT. Für Zeichenketten werden zwei Parameter benutzt, um die Objektzeichenkette und die Länge des Anfangsstücks anzugeben, hinter dem der nächste Teil gesucht wird.

    Bei der Anwendung auf Listen fällt dieser Operator mit dem Zugriffsoperator zusammen, der den Rest einer Liste, d.h. die Liste ohne das erste Element, liefert.

     

  4. d) den Änderungsoperator INSERT. Soll in eine Zeichenkette ein neuer Teil aufgenommen werden, so wird ein INSERT benutzt, das drei Parameter hat: die Objektzeichenkette, die aufzunehmende Teilzeichenkette (d.h. eine Sequenz von Zeichen) und das Element, nach dem die Zeichenkette erweitert werden soll.

    Für die Listenverarbeitung könnte der Operator mit entsprechenden Parametern übernommen werden, allerdings würde wohl statt einer Folge von Listenelementen nur eines als 2. Argument auftreten. In den existierenden Systemen zur Listenverarbeitung, insbesondere in LISP, tritt diese Operation praktisch nicht als Grundhandlung auf. \footnote {In BESM-6-LISP ist INS verfügbar. Siehe Abschnitt 5.3.}

     

  5. e) den Beseitigungsoperator DELETE. Die Beseitigung von Teilen aus Zeichenketten läuft zur Erweiterung komplementär ab: Man gibt die Objektzeichenkette (1. Argument), die Stelle, nach der beseitigt werden soll (2. Argument) und die Länge des zu beseitigenden Teils an (3. Argument).

    Im Fall der Listenverarbeitung verwendet man meist ein DELETE, das nur ein Listenelement beseitigt: So sind nur zwei Argumente nötig. Auch diese Operation gilt normalerweise nicht als Grundoperation in LISP \footnote {In neueren LISP-Systemen verfügbar. Ein Spezifikum vom LISP ist die Unterscheidung von physischer und kopierender Änderung.}.

     

  6. f) den Operator CATENATE zum Aneinanderreihen. In beiden Fällen werden zwei Argumente angegeben: die Zeichenkette bzw. Listen, die zusammengehängt werden sollen \footnote{APPEND bzw. NCONC} in LISP..

     

  7. g) den Operator SEPARATE zum Zerteilen zweier Datenstrukturen. In beiden Fällen werden zwei Argumente angegeben: die Objektstruktur (Zeichenkette oder Liste) und eine Beschreibung des Zerteilungspunktes \footnote{Diese Aktion kann nur mittels RPLACA bzw. {\tt RPLACD} in LISP ausgeführt werden}.

     

  8. h) die Funktion LENGTH zum Bestimmen der Länge einer Struktur. Sie ist in beiden Fällen einargumentige Funktion. Für Zeichenketten wird die Anzahl der Zeichen, für Listen die Anzahl der Elemente gemessen.

     

  9. i) die Funktion FIND, die in einer Struktur sucht. Für Zeichenketten liefert FIND gewöhnlich den Platz, wo das Gesuchte steht, ausgedruckt als Zahl (Zeichennummer). Es kann nach Teilzeichenketten gesucht werden.

    In Listen wird nach einem Element gesucht. Als Ergebnis wird entweder ein Wahrheitswert oder die Liste geliefert, die mit dem gesuchten Element beginnt.

Knuth [KN68] beschreibt folgende Operationen als Grundhandlungen an linearen Listen: 1. Zugriff zum i. Element, 2. Einfügung eines neuen Elements direkt vor dem i. Element, 3. Beseitigung des i. Elements, 4. Kombination von zwei oder mehr Listen in eine einzelne Liste, 5. Aufteilung einer Liste in zwei oder mehr Listen, 6. Kopieren einer Liste, 7. Bestimmen der Zahl der Elemente, 8. Sortieren der Liste und 9. Suche eines bestimmten Elements. Im Fall allgemeiner Listen, d.h. Baumstrukturen, fügt er hinzu: Durchqueren, Kopieren und Ein- und Ausgabe.

Ein wesentlicher Unterschied kommt in den bisher angegebenen Basisoperationen nicht zum Ausdruck: In Zeichenketten ist immer klar, von welchem Typ eine Teilzeichenkette ist: eben wieder eine Zeichenkette. In Listenstrukturen jedoch können die Elemente von verschiedenem Typ, mindestens jedoch von zwei Typen sein: selbst wieder Listen oder nicht. Für die Datenelemente, die keine Liste sind, wird üblicherweise der Sammelbegriff Atome verwendet. Gruppieren wir die obigen Operationen und versuchen ihnen die Etiketten {\em Konstruktoren, Selektoren} und Prädikate anzuhängen, so kommen wir in einige Schwierigkeiten. Zwar ist unmittelbar klar, da\ssdie Operatoren {\tt ACCESS, FIRST, NEXT} und FIND Selektoren sind und {\tt INSERT, DELETE, CATENATE} und SEPARATE etwas mit Konstruktion zu tun haben, so scheinen die Prädikate ganz zu fehlen.

Deshalb fügen wir doch j) das Prädikat EQUAL hinzu, das für Zeichenketten zum Identitätsvergleich zweier Zeichenketten verwendet wird, während es im Listenfall die Strukturgleichheit festzustellen hilft.Auf eine Funktion MATCH wollen wir hier verzichten.

Generell wären für die Listenmanipulation weiterhin soviele den Typ prüfende Prädikate hinzuzufügen, wie es verschiedene Datentypen gibt, während im Fall der Zeichenkettenverarbeitung nur Zeichen oder Zeichenketten denkbar sind.

Die Konstruktorfunktionen scheinen bisher eine merkwürdige Eigenschaft zu haben: Es mu\ssschon etwas Struktur da sein, die dann zusammengefügt, vermehrt, verändert werden kann. Man kann sich zusätzlich eine Grundoperation für Zeichenketten vorstellen, die aus einzelnen Zeichen (nicht: aus Zeichenketten der Länge 1) Zeichenketten aufbaut. In der Listenverarbeitung liegt der Fall aber anders: Listen bestehen aus listenfremden Elementen und können, von diesen ausgehend, aufgebaut werden. Die Basiskonstruktoroperationen sind hier

k) CONS und LIST. CONS fügt zwei allgemeine Strukturen zu einer neuen zusammen -- einem Baum, dessen linker Zweig dem ersten Argument und dessen rechter Zweig dem zweiten Argument entspricht. LISP konstruiert aus einer belliebigen Anzahl von Elementen eine Liste, die diese in geordneter Folge als Elemente enthält.

 

Listenverarbeitung in LISP

Die Listenverarbeitung in LISP ist neben der speziellen Auswahl der Basisfunktionen durch zwei besondere Eigenschaften charakterisiert: Die leere Liste wird mit dem Atom NIL identifiziert\footnote{In 3LISP wirddiese Konfusion beseitigt!} -- es gibt also das ``Nichts'' nicht -- im Unterschied zu Zeichenkettensprachen, in denen die leere Kette ein fester Begriff ist. Zweitens ist bei allen Operationen der Unterschied zwischen zerstörenden bzw. {\em physischen} und kopierenden zu machen. Der Nutzer kann so weit an die internen Repräsentationen der Listen heran, da\ssfür ihn der Unterschied zwischen Strukturgleichheit und Identität wichtig wird.

Diese letztere Möglichkeit und die in die meisten Systemen gegebene Unmöglichkeit, gewisse interne Strukturen auszugeben, hat dazu geführt, da\ssLISP in den Geruch eines unseriösen Mischmasch von exzellenter Klarheit, mathematischer Eleganz und finsterster Verschrobenheit durch Bezugnahme auf Implementierungsdetails geraten ist. Landin [LAN66]: ``LISP hat einige finstere Winkel, speziell außerhalb des `reinen'LISP, in welchen sowohl Lehrer als auch Programmierer gezwungen sind, über Adressen zu sprechen und Speicherdiagramme zu zeichnen.''

Ursache dieses Ärgers ist die Tatsache, da\ssLISP tatsächlich keinereine funktions-basierte Sprache ist, die (mathematische) Objekte in (neue, andere) Objekte abbildet. LISP ist bezogen auf die Listenstrukturen mehr objekt-basiert, d.h. erlaubt sich ändernde Objekte.

Von den Selektoren bietet LISP gewöhnlich nur FIRST und {\tt NEXT} als CAR bzw. CDR. Typisch für Listenverarbeitung ist, da\ssKompositionen von horizontaler und vertikaler Richtung häufig auftreten. LISP hält dafür die Abkürzungen CAAR, CADADDAAR\footnote{Diese einstmals so bedeutsamen Kombinationen sind heute in einen schlechten Ruf geraten. Ursache ist, da\ssalle Programme, die komponierte Zugriffsfunktionenenthalten, nicht nach den Prinzipien der Datenabstraktion entworfen worden sind.} bzw. bereit. Ähnliche Kompositionen wird man sich in Kettenrichtung vorstellen können, doch dann nur in der Art SECOND = FIRST (NEXT(...)). Daneben kennt LISP noch den Zugriff auf das letzte Element mit LAST.

Der Selektor ACCESS heißt in LISP gewöhnlich NTH oder ELEM.\footnote{im BESM-6-LISP vgl. Abschnitt 5.3.}.Er gilt nicht als Grundoperation, da er leicht mittels CAR und {\tt CDR} definierbar ist. Zudem ist der Zugriff zu einem Listenelement, dessen relative Position über eine Zahl bezeichnet wird, nicht eben häufig.

Von den Konstruktoren sind in jedem LISP-Sytem mindestens CONS und LIST vorhanden. Daneben gibt es gewöhnlich Grundfunktionen zum Umkehren von Listen (REVERSE), zum Aneinanderhängen ({\tt APPEND}), Kopieren (COPY), Beseitigen gewisser Teile ({\tt DELETE}) und für komplexere Operationen, wie etwa für die Substitution von Ellementen durch Elemente in einer Liste (SUBST). In Zeichenkettenverarbeitung unnötig ist der Konstruktor APPEND1, der ein Element ans Ende einer Liste stellt. Alle diese Veränderungsfunktionen lassen sich jedoch mit Hilfe der Selektoren {\tt CAR} und CDR sowie des grundlegenden Konstruktors CONS definieren.

Die Veränderungsoperationen haben die Eigenart, ganz aus dem Rahemn der funktions-orientierten Programmierung zu fallen. Streng genommen handelt es sich hier nicht um Funktionen, denn es werden nicht Objekte auf andere Objekte abgebildet, sondern Objekte verändert. ``Veränderung'' von Listenstrukturen auf streng funktionsbasierte Weise kann nur durch Neukonstruktion erreicht werden.

Echte Veränderung durch Austausch von Strukturbestandteilen ist anweisungs- oder objekt-orientiert denkbar. Da die Aspekt der Speichergröße und des Ortes der Listenstrukturen völlig uninteressant sind, erscheint der Denkrahmen der objekt-orientierten Programmierung als angemessener.

Veränderung durch Neuaufbau der Listenstruktur liegt in einem größeren Listenverarbeitungssystem nahe, da dieses im Allgemeinen funktions-orientiert programmiert wird. Doch mu\ssauch auf Effizienz geachtet werden. Hat man großeListenstrukturen, in denen nur marginale Änderungen stattfinden sollen, dann wird die Konstruktion des Resultates denselben Platz in Anspruch nehmen, wie die Ausgangsstruktur. Natürlich wird auf diese Art der Speicherverwalter mehr Arbeit zu erledigen haben. Er arbeitet aber auf Kosten der dem Anwendungsproblem zugute kommenden Prozesse.

Die funktions-orientierte Listenverarbeitung konnte seinerzeit nicht durchgehalten werden, weil die Rechner zu langsam und die Speicherräume zu klein waren. Aus den anweisungs-orientierten Systemen sickerten daher viele der problematischen Techniken der Arbeit mit Zeigern ein. Viele der so geschriebenen Programme, die ohne Speicherdiagramme unverständlich bleiben müßten, waren effizienter als die konzeptionell klaren funktions-orientierten Programme.

Dennoch hat LISP die Listenverarbeitung nicht in dieser Richtung gestaltet, sondern ein Gutteil des Einflusses der funktions-orientierten Programmierung blieb erhalten. Die Änderungsoperationen wurden nur über eine kleine Menge von Grundfunktionen gestattet, Arithmetik mit Zeigern oder Platzgrößen wurde unterdrückt. So werden die Diagramme eher konzeptionelle Skizzen von Strukturen statt Beschreibungen des Speichers.

Mit den Strukturdefinitionen (DEFSTRUCT) kommt nun ein deutlicher Zug zur Datenabstraktion und damit zur objekt-orientierten Programmierung in die Listenverarbeitung mit LISP. Wenn die Terme noch als Nachrichtensendungen verstanden werden könnten -- und das wäre möglich, wenn das erste Argument bei der Auswahl der konkreten Funktion ausgehend von der Nennung eines generischen Namens eine hervorgehobene Rolle spielte -- dann könnte LISP als echte objekt-basierte Sprache aufgefaßt werden.

Wichtig ist auch, da\ssdie Änderungsfunktionen die einzigen Mittel sind, um Graphen allgemeinerer Art zu erzeugen, d.h. Strukturen mit Zyklen bzw. mit mehrfach benutzten Unterlisten. Für solche Datenstrukturen wäre neben den Grundoperationen zum Selektieren und Konstruieren das Durchqueren äußerst hilfreich. LISP bietet hier keine Hilfen, und der Programmierer mu\sssich selbst kümmern. Der Garbage Collector (und in Van Der Meys X8-Implementation das Druckprogramm) ist jedoch in der Lage, durch Markierung gesehener Teile eine völlständige Durchquerung zu vollziehen.

Listenverarbeitung in LISP ist nicht denkbar ohne die Typprädikate. Mindestens die Klasse der Atome mu\ssdiagnostizierbar sein: ATOM ist die zugeordnete Funktion. Es ist aber üblich, für jeden Datentyp weitere Prädikate zu liefern: Für Zahlen insgesamt NUMBERP, für ganze Zahlen FIXP, für Gleitkommazahlen FLOATP, für Atomsymbole LITATOM, für Zeichenketten STRINGP, usw.

Obwohl es, wie schon gesagt, in LISP kein Äquivalent der leeren Ketten gibt -- die leere Liste ist vereinbarungsgemä\ssfatalerweise mit dem Atom NIL identifiziert --, ist doch ein Prädikat vorhanden, das die Fragen nach der leeren Liste erlaubt. Intern wäre damit ohne große Gewaltakte eine leeere Liste definierbar, die nicht NIL ist. NULL heißt das zugeordnete Prädikat. Der Name stammt noch aus der Zeit, als NIL die Adresse 0 hatte.

Zum Vergleich von Listen wäre zunächst nur die Funktion {\tt EQUAL} anwendbar, die auf strukturelle Gleichheit prüft. Dieser Begriff ist in LISP ein wenig anders zu verstehen als die Gleichheit zweier Zeichenkette. Zwei gleiche Zeichenkette müssen nicht identisch sein, sind gleichlang und enthalten dieselben Zeichen. Das gleiche gillt zunächst für Listen, d.h. zwei strukturgleiche Listen haben dieselbe Listenstruktur (gleiche Anzahl von Ebenen, gleiche Listenlänge usw.) und die Enden, d.h. die Atome, sind identisch. Diese Assage ist aber in zweierlei Hinsicht zu modifizieren: Unter den Atomen nehmen die Zahlen einer Sonderstellung ein, da sie gewöhnlich nicht physisch einmalig repräsentiert sind. Etwa auftretende Gleichkommazahlen sind nur bis zur Genauigkeitsgrenze gleich. Andererseits aber reflektiert die Strukturgleichheit überhaupt nicht die Unterschiede, die durch physische Änderungen erzeugt sind, soweit diese nur die mehrfache Benutzung einer Unterstruktur betreffen. Eine Liste, die drei {\em gleiche} komplizierte Elemente a, b, c enthält, ist strukturgleich mit einer Liste, die dreimal dasselbe Element a enthält.

Durch die Dichotomie von strukturgleichen und identischen Listen ist in LISP ein weiteres Prädikat erforderlich, das die physische Identität überprüft. Aus Gründe der Ersparnis wird dazu gewöhnlich die Funktion benutzt, die für die Feststellung der Gleichheit von Atomen zu verwenden ist, nämlich EQ.

Eine etwas befremdende Eigenschaft der LISP-Listenverarbeitung ist, da\ssim Verlauf der Zeit Strukturgleichheit und Identität auseinanderfallen können. Die Programmierung von Seiteneffekte erlaubt den Aufruf der Funktion EQUAL mit zwei Argumentausdrücken, wovon einer eine Liste liefert, der zweite aber ebendiese Liste verändert. So ist dann beim eigentlichen Aufruf von EQUAL eine ganz andere Liste zu vergleichen als zunächst sichtbar:

      (EQUAL(PROG1 (SETQ A'(1 2 3)) (PRINT A))(RPLACA A A)),

es wird {\tt(1 2 3)} gedruckt, und dies scheint das erste Argument zu sein, aber die Veränderung macht daraus {\tt((1 2 3)2 3)}, und dies wird mit sich selbst verglichen. Auf Grund der physischen Gleichheit liefert EQUAL natürlich T für ``true''.

Anders haben wir aber folgenden Fall:

	         (SETQ A'(1 2 3))
         (EQUAL '(1 2 3) (PROG1 A (PRINT A) (RPLACA A A)))

auch hier wird {\tt(1 2 3)} ausgedruckt, aber gleich anschließend die Liste verändert. Das erste Argument bleibt {\tt(1 2 3)}, das zweite wird {\tt((1 2 3)2 3),} und EQUAL liefert NIL.

\subsection {Zeichenkettenverarbeitung in LISP} LISP ist sicher keine Sprache für die Zeichenkettenverarbeitung, dennoch erlauben praktisch alle Implementationen den Umgang mit diesen Datenstrukturen. Es gibt dabei zwei Realisierungsebenen: In den tieferen Ebene ist eine eigentliche Zeichenkettenrepräsentation nicht vorhanden. Das Rohmaterial für die Verarbeitung bilden die Namen der Atome (meist nur der Atomsymbole -- der literalen Atome -- seltener auch der Zahlen). Diese werden mittels Grundfunktionen in lineare Listen von Zeichenobjekten (das sind normale lineare Atome, deren Namen aus einem Zeichen besteht) konvertiert. Die benötigten Grundfunktionen für die Zeichenkettenverarbeitung lassen sich nun leicht aus denen für die Listenmanipulation definieren. Schließlich sind gewöhnlich wieder Funktionen vorhanden, die eine lineare Liste von Zeichenobjekten in Atomnamen umformen.

Sicher lassen sich so alle Operatoren für die Zeichenkettenverarbeitung realisieren, wenn auch die interne Repräsentation nicht die beste ist: Wirklich umfangreiche Problemen lassen sich damit wohl schlecht lösen. Das eigentliche Problem ist aber nicht einmal die Speicherproblematik. Viel drückender stellt sich die Begrenzung bei der Ein- und Ausgabe dar. Atome sind in LISP gewöhnlich in ihrer Länge begrenzt -- selbst InterLISP gestattete nur Längen von 100 Zeichen. Dabei können Sonderzeichen ernste Probleme verursachen. Prinzipiell könnte ein Text mit Listenklammern umgeben werden und wortweise eingelesen. Etwa auftretende Klammern oder Punkte bringen jedoch Schwirigkeiten mit sich.

Moderne Systeme, wie CommonLISP oder 3LISP enthalten regelrechte Teilsysteme für die Zeichenkettenverarbeitung. Sie befinden sich damit auf der höheren Realisierungsebene: Der Datentyp Zeichenkette ist vorhanden. In diesem Fall sind die Probleme bei der Ein- und Ausgabe weitgehend gelöst und nicht komplizierter als in angepaßten Verarbeitungssystemen: Die Zeichenketten dürfen beliebig lang sein, sind aber mit Anfangs- und Endezeichen zu begrenzen. Die Grundoperationen basieren meist auf dem Vorbild von PL/I. Das bedeutet, da\ssein Grundinstrument zur Arbeit mit der Zeichenketten, neben dem Zeiger, ein Zeichenzähler ist, d.h. eine ganze Zahl, die sich auf das entsprechende Zeichen, vonm jeweiligen Anfang aus gezählt, bezieht.

In InterLISP etwa wird der Zugriff ACCESS ebenso wie die Operationen FIRST und NEXT mit der Operation {\tt SUBSTRING} realisiert. Um die Zahlenangaben für die Argumente (Startposition und Länge) zu ermittel, sind die Funktionen {\tt NCHARS} und STRPOS zu benutzen. STRPOS, genauso wie INDEX in MacLISP, realisieren ein Gutteil dessen, was die Grundoperation FIND verlangt.

Von den Veränderungsoperatoren ist praktisch nur CATENATE vorhanden (in InterLISP: CONCAT). InterLISP gestattete nochdie gezielte Ersetzung eines Zeichenkettenabschnitts durch eine neue Zeichenkette. Diese mu\ssaber physisch Platz finden, d.h., die gesamte Kette darf nicht länger werden! Die Operationen DELETE und INSERT sind so durch Komposition von SUBSTRING-Bildung und CONCATENATion zu realisieren.

Die Gleichheit von Zeichenketten wird entweder durch EQUAL mit überprüft oder eine spezifische Funktion, STREQUAL, übernimmt die Arbeit.

Charakteristisch für die Zeichenkettenmanipulation in LISP ist, da\ssFunktionen vorhanden sind, die einen Übergang von Zeichenketten zu anderen LISP-Datentypen gestattet: Atome können erzeugt werden, in dem die Zeichenkette als Name erklärt wird; aus einzelnen Zeichen, die aus der Zeichenkette gelöst werden, können ebenfalls literale Atome gebildet werden. Umgekehrt konnte etwa in InterLISP jede beliebige Listenstruktur in eine Zeichenkette umgewandelt werden durch einen Proze\ss, der etwa dem Drucken ähnlich ist.

Damit bietet die LISP-Systeme die Dienste verteilt an, die etwa SNOBOL4 [GRIE68] in das ungemein flexible und anwendungsfähige Musterkonzept integriert hat. Die Implementation von ähnlich tragfähigen Musterbeschreibungssprachen in LISP zeigt jedoch, da\ssdie angebotenen Basisfunktionen nicht weniger leistungsfähig sind [HEW71c,SM73a].

 

Dynamische Speicherplatzverwaltung

Programme für die Symbolmanipulation haben die gemeinsame Eigenschaft, da\ssder Speicherbedarf nicht abgeschätzt werden kann. Während ein in ALGOL60 geschriebener Algorithmus für ein matematisches Problem im allgemeinen auch für unterschiedliche Eingabedaten eine gleiche Belegung des Hauptspeichers erfordert (bei Verwendung dynamischer Felder, d.h. Felder, deren Größe erst zur Laufzeit festgelegt wird, oder beim Aufruf rekursiver Prozeduren können allerdings auch hier unerwartete Situationen auftreten), kann eine kaum merkliche Änderung in einem symbolischen Ausdruck einen völlig anderen Bedarf an Speicherplatz erfordern. Man denke etwa an Probleme der symbolischen Integration, wo in einem Fall sich ein Bruch aus Polynomen ergeben mag, der sich auf eine ganz einfache Grundfunktion reduzieren läßt, während im anderen Fall eine komplizierte Partialbruchzerlegung zu einer ganzen Folge von Teilintegralen von ähnlicher Kompliziertkeit führen kann.

Im Zusammenhang mit numerischen Rechnungen läßt sich der Speicherbedarf durchweg entweder direkt auf die Grundoperationen aufgeschlüsselt berechnen oder durch Formel beschreiben: Bei einem gewissen Ungenauigkeitsgrad soundso viel Stufen feiner zu arbeiten, das erfordert eine Punktematrix, die soundso vielmal größer ist usw. usf. Bei nichtnumerischer Verarbeitung läßt sich eine derartige Rechnung selten ausführen.

Sind die Listenstrukturen die für solche Probleme angepaßten Datenstrukturen, so ist mit ihnen das Problem der dynamischen Speicherplatzverwaltung unmittelbar verknüpft. In einem umfassenden festbegrenzten Bereich wachsen oder schrumpfen die Listen im Verlauf der Berechnung, werden ständig neue erzeugt und alte, deren Teilstrukturen in solchen neuen aufgehen, werden nicht mehr benötigt.

Müßte der Nutzer, wie etwa in IPL [NEW61], selbst die Speicherplatzverwaltung übernehmen, d.h. selbst nach neuen freien Stellen suchen, wo Listen unterzubringen sind, bzw. nicht mehr benutzte Listen freigeben, so wäre er einerseits mit einer komplizierten Aufgabe belastet, andererseits wäre verwickelten Fehlersituationen Tür und Tor geöffnet, wie die Erfahrung gezeigt hat.

Die dynamische Speicherplatzverwaltung hat die Aufgabe, den Nutzer hier völlig zu entlasten, indem sie die verfügbaren Stellen verwaltet und bei Anforderung zur Verfügung stellt bzw. nicht mehr benutzte Teile von Listen als solche erkennt und dem Breich der verfügbaren Speicherplätze hinzuschlägt.

In Systemen zur Symbolmanipulation, die auf Zeigerstrukturen basieren gibt es zwei grundsätzliche Lösungen für dieses Problem: Die Referenzzähler nach Colllins [COL60,COL63] und das Garbage Collection nach McCarthy [MCC60c]. Referenzzähler zeigen die Benutzung von Listen an. Ist ein Zähler 0, so kann das Speicherelement neu verwendet werden. Allerdings haben Referenzzähler den Nachteil, da\ssfür die Speicherplatzverwaltung ständig ein ernstzunehmender Prozentsatz (in Collins ursprünglichen System 1/3, d.h. 33\%) des knappen Speichers abgezweigt werden mu\ss. Außerdem gibt es Probleme mit zyklischen Strukturen, denn diese werden nie frei.

Das Garbage Collection benötig für seine Arbeit lediglich ein Markierungsbit pro Strukturelement. Es wird aktiviert, wenn von einem Speichervorrat (meist als Freispeicherliste implementiert) kein oder nicht mehr genügend Platz beschafft werden kann. Ausgehend von einigen {\em Basiselementen} mu\ssjede aktive Datenstruktur erreichbar sein. Diese wird markiert oder in einen neuen Bereich umgespeichert. Wenn markiert wurde, ist eine zweite Phase erforderlich, in der die nicht markierten, demnach freien Zellen gesammelt werden oder die markierten Zellen in eine ``Ecke'' kompaktiert worden. Wenn gleich umgespeichert wurde, ist sofort ein kompaktierter Zustand erreicht und der verfügbare Platz durchgängig verfügbar.

Das Garbage Collection erscheint für LISP vorteilhaft, weil zyklische Strukturen vorkommen können und weil die Speicherelemente verglichen mit den Referenzzähler, klein sind: Diese würden 1/3 bis 1/5 des gesamten Platzes belegen. Zudem ist der Verbrauch des Speicherplatzes zentralisiert: Es gibt nur eine Funktion, die Speicherplatz anfordert, nämlich CONS, die Konstruktorfunktion für S-Ausdrücke. So kann das Garbage Collection als Ausnahmebehandlung dieser Funktion beigeordnet werden.

Mit dem Garbage Collection sind jedoch auch Nachteile verbunden: In der konventionellen Implementation wird diese Speicherreorganisation nur tätig, wenn aller verfügbare Platz erschöpft ist. Das bedeutet, da\ssdie Listenmanipulation völlig ausgesetzt werden mu\ss, bis ein neuer Speichervorrat aufgehäuft ist. Da die Listenräume oft repektable Größen erreichen, ist die Zeitdauer entsprechend\footnote{{\sc Kurokawa} [KUR75] gibt verschiedene Beispiele von LISP-Verwendungen, bei denen der Anteil des Garbage Collection zwischen 1/3 und 1/2 der gesamten Verarbeitungszeit beanspruchte}.

Für Echtzeitverarbeitung ist das Aussetzen des Verarbeitungsprogramms völlig unakzeptabel. Auch im Dialog kann es höchst unbequem sein, plötzlich mitten in der eifrigsten Interaktion einen Wartezustand wahrnehmen zu müssen.

Arbeiten auf diesem Gebiet haben jedoch gezeigt, da\ssein vollständiges paralleles oder wenigstens schrittweises Garbage Collection möglich ist [MU76,STE75,DI75,WAD76].

 

Resümee

Sicher gehört die Listenverarbeitung zu den einfach handhabbaren Techniken, und Knuth hat recht, wenn er hier jeden falschen Glanz von geheimnisvoller Komplexität abstumpfen will [KN68]. Es ist jedoch kurios, da\ssin der vorhandenen Literatur zwar viel von Sprachen zur Listenverarbeitung [BO73a], von der Brauchbarkeit dieser Technik [WILK65] und von Beispielen ihrer Anwendung [FOS68] die Rede war, aber eine eigentliche kritische Würdigung bisher nicht zu finden ist. Knuth [KN68] und Elson [EL75] formulieren kaum Unterschiede zwischen Zeichenketten- und Listenverarbeitung, und auch auf dem Symposium über Symbolmanipulationssprachen [BO68b] war man dazu nicht in der Lage, obwohl es das Thema mancher Diskussion war. Ob die hier gegebene bereits befriedigend ist, ist wohl auch anzuzweifeln.

Es ist das Gefühl des Autors, da\ssallzu oft auf der Basis derart mangelhaften Wissens bzw. ungenügender Sachanalyse Urteile angegeben werden, die sich nach kurzer Zeit nur als falsch herausstellen können.

Zu einem dieser völlig unbegründeten und am Kern vorbeigehenden Urteil ist etwa 1969 B. Highman gekommen: ``Gegenwärtig hat es den Anschein, da\ssSprachen zur Listenverarbeitung überholt sind. Sie haben ihre Schuldigkeit getan, indem sie die Eigenschaften herausgeschält haben, die für eine wirksame Behandlung von Listen benötigt werden. Diese Eigenschaften werden nun in universelle Sprachen mit eingebaut, jedoch nicht als aufgepfropfte Fremdkörper, sondern als integrierender Bestandteil der Sprache von Beginn ihrer Entstehung an ...'' [HIG67][S.153].

Wie wenig Highmans Voaussagen bisher in Erfüllung gegangen sind, kann man an dem ständig steigenden Nutzerkreis von LISP erkennen. da\ssdie allgemeinen Sprachen wie PL/I oder ALGOL68 aber völlig ungenügend für die Zwecke der Symbolverarbeitung waren, läßt sich schon aus der Studie von Housden [HOU75] über die Möglichkeiten der Zeichenkettenverarbeitung in diesen Sprachen ablesen. Viel besser steht es nicht mit PASCAL und ADA.

 

Datenstrukturdarstellung der Programme

Durch den großen Zufall in der Entwicklung der Programmiersprache LISP (vgl. Kapitel 5) hat es sich ergeben, da\ssdie Programme sowohl intern als extern wie Daten behandelt bzw.notiert werden. Auch in IPL-V [NEW61] wurde ein Programm intern als Liste dargestellt (vgl. [HIG67][S.159ff.]) jedoch in einem von den Daten völlig abgetrennten Bereich. Extern wurden sie völlig anders als Listen notiert.

Man beachte auch den Unterschied zu SNOBOL [GRIEG68] und anderen Zeichenkettenverabeitungssprachen, die natürlich auch Programme als Daten abzeptieren. In diesem Fall ist aber jede Zeichenkette ein potentielles Datum. Als Teil eines Programms, und damit in der Sprache korrekt formuliert, gilt eine Zeichenkette aber erst dann, wenn sie in Apostrophe eingeschlossen ist. Einmal als Zeichenkette gegeben, gibt es keine Möglichkeit, diese als Programm zu interpretieren und abzuarbeiten. Allerdings ist das keine prinzielle Hürde. Ähnlich dem No-Device-Channel in LISP [KUR78] könnte eine Einleseprozedur definiert werden, der diese Konversion vornimmt. Prinzipiell unmöglich erscheint allerdings die Rückübersetzung von Programm in Zeichenkette.

Außerdem ist eine strukturelle Darstellung im Unterschied zur Zeichenkettendarstellung wesentlich besser handhabbar [SAN75b]. Ursache dafür ist, da\ssein gewisser Anteil an syntaktischer Analyse bereits erfolgt ist: Die Programmkomponenten (Identifier, Teilausdrücke, Zahlen, Datenelemente usw.) sind bereits herausgeschält, isoliert und so leichter erreichbar. Insbesondere die Ausdrücke zeigen deutlich ihre Struktur aus Operator oder Funktion und Argumenten.

Dadurch, da\ssdiese Programmrepräsentation auch während der Abarbeitung erhalten bleibt (das Eingabedatum des Interpreters ist eben diese interne Programmdarstellung), eröffnen sich überraschende und weitreichende Möglichkeiten:

  1. Wenn alle Eingaben (Programme und alle Datentypen) wieder ausgabefähig sind, so liegt eine Sprache vor, die hervorragend für die Dialogarbeit geeignet ist. Wenn gar überdies die Syntax der Ausgabeform mit der Eingabeform übereinstimmt, so mu\ssdie Bequemlichkeit beim Dialog recht hoch veranschlagt werden.
  2. Wenn Programme wie Daten behandelt werden, dann können sie intern verarbeitet werden, indem man sie analysiert, verändert oder konstruiert. Das Besondere bei LISP liegt in der Möglichkeit, die Verarbeitungsergebnisse sofort auch als Programme anzusehen und abzuarbeiten. Sandewall [SAN78a] weist auf die Vorteile hin, wenn man im Fehlerfall sofort einen Editor aufrufen kann, der es erlaubt, das Programm zu berichtigen, ohne da\ssdiffizile Dateimanipulation oder Systemwechsel erforderlich sind.
  3. Programme können in Datenstrukturen als Elemente auftauchen. Die Arbeit mit Datenbasen braucht sich nicht darauf zu beschränken, da\ssDatenstrukturen analysiert werden und entsprechende Teile des Programms aufgerufen werden, sondern die aufzuführenden Programmteile sind in der Datenstruktur selbst mit enthalten und werden bei der Analyse gefunden und aktiviert. Damit ergibt sich die unschätzbare Möglichkeit, Daten mit zugeordneten Basisaktionen in einer Einheit zu behandeln und abzulagern. Die Verfügbarkeit einer Datenbasis mu\sssich nicht mehr auf ein zugeschnittenes Verarbeitungs- und Verwaltungsprogramm beschränken, sondern ist für alle Programme gegeben, die die Zugriffsfunktionen integrieren und aktivieren können (data driven programming, [SAN75b])

     

  4. Die Variablen (Identifier) unterscheiden sich von denen in anderen Sprachen (SNOBOL geht hier allerdings ähnlich vor; vgl. [MAD67]): Wenn Programme Daten sind, müssen auch alle Teile eines Programms Daten sein. Alle Variablen werden somit als Namen im Programm als auch als Daten für das Programm benutzt. Wenn etwa im Programm eine Marke M auftritt und vom Programm wird innerhalb irgendeiner Liste erneut das Symbol M aufgerufen, so werden diese in direkte Beziehung miteinander gesetzt.

LISP ist also eine ideale Dialogsprache. Diese Eigenschaft wird nicht nur durch die hier diskutierte syntaktische Spezialität unterstützt, sondern auch durch die interpretative Abarbeitung (siehe Abschnitt 3.7) und die Einbettung in ein Gesamtsystem zum Erarbeiten, Testen, Edieren, Optimieren und Verwalten von Programmen (siehe Abschnitt 3.8). Obwohl das Vorbild-LISP-System (LISP 1.5 auf der IBM7090) auf die Stapelverarbeitung orientiert war, ist es doch grundsätzlich falsch, LISP als Stapelverarbeitungssprache zu charakterisieren (wie es J. Sammet [SAM69] tut). Bereits die erste Implementation auf der IBM704 enthielt Dialogmöglichkeiten

Die Beschränkung auf die gegebenen Eingabemöglichkeiten an der Maschine der zweiten Implementation bedeutet keine Aufgabe dieser wichtigen Eigenschaft.

Um den springenden Punkt noch einmal zu unterstreichen: Auch für eine Sprache wie FORTRAN könnte eine interne Programmrepräsentation entwickelt werden. Angesichst der verfügbaren Datenstrukturen würde man dazu Felder einer passenden Dimension verwenden. Es wäre sicher möglich, diese Felder, ausgehend von Eingaben, zu füllen, dann zu manipulieren und endlich sogar zu interpretieren: Es ist aber praktisch nicht möglich, Felder in ALGOL strukturiert auszugeben. Ebenso wie die Eingabe in ein Feld, so geht die Ausgabe von einem Feld zu einer linearen Folge der Feldelemente, die ebenso von mehreren Feldern oder von Feldern völlig anderer Dimensionen kommen kann.

Auch in neueren Programmiersprachen, die weitergehende Datenstrukturierungsmittel enthalten, wie etwa Pascal, liegen die Verhältnisse nicht anders. Es ist keine externe Darstellung der Records bekannt.

Die Listenstrukturen (oder S-Ausdrücke) von LISP jedoch, als die wesentlichen Datenstrukturen dieser Sprache, besitzen eine externe Repräsentation. Einleseprogramm und Druckprogramm bewerkstelligen die Konvertierung zwischen dieser sichtbaren Darstellung und den internen Strukturen.

Für das Programmiersystem ist diese Tatsache von unschätzbaren Wert: Die Fehleranalyse kann vollständig symbolisch erfolgen. Der Programmierer erhält noch in komplizierten Situationen korrekte Datenstrukturen, die in seiner Programmiersprache formuliert sind, und ist keineswegs auf Speicherabzüge oder Splitter von Datenstrukturen angewiesen.

Hinzu kommt die inkrementelle Verarbeitung im LISP-System: Das System vollzieht in einem Zyklus drei einfache Grundhandlungen: Es liest einen Ausdruck ein, wertet ihn aus und druckt das Resultat. Die Ausdrücke können zur Definition von Prozeduren (Funktionen) dienen, zum Einspeichern in eine Datenbasis, können als Testfälle gedacht sein, um eine neue Funktion zu erproben, oder sie lösen die Berichtigung interner Fakten (Funktionsdefinition bzw. Daten in der Datenbasis) aus [SAN75b][S.3].

Jedes Stück Programm, jede Anweisung an den Rechner (in LISP: jeder eingegebene Ausdruck) wird vom System mit dem jeweiligen Resultat beantwortet. Dabei geht die Antwort in jedem Fall über eine bloße Quittung hinaus: Die Werte auch von Funktionsdefinitionen sagen dem Nutzer etwas über den erfolgreichen Vollzug. Auch wenn LISP in einem Stapelverarbeitungssystem aktiviert wird, spielt sich dieser Dialog des Systems mit seiner Umwelt ab. Die Wahl der tatsächlichen Geräte ist für das Programmsystem unerheblich. Das Problem für die Maschine (bzw. das Betriebssystem und natürlich für den Nutzer, der auf einen wirklichen Dialog verzichten muß!) besteht darin, da\ssdieAntwort (Ausgaben) auf ein anderes Medium zu bringen sind, als das, von dem die Eingabe kommen.

Besonders kritisch wird die Aufrechterhaltung des Dialogs, wenn der Nutzer Fehler macht, indem er entweder fehlerhafte Ausdrücke eingibt (syntaktische Fehler) oder Ausdrücke auswerten läßt, die fehlerhafte Programme aktivieren (semantische Fehler). Auch auf diesem Gebiet zeigt sich die Qualität von LISP: Neben Fehlernachrichten und standardmäßig eingerichteten Informationen über die Fehlersituation ermöglichen moderne LISP-Systeme dem Nutzer, in einem speziellen Fehlerstatus erneut einen Dialog zu führen, um den Fehler durch Klärung der Fehlerumgebung zu finden bzw. zu beseitigen [TE74,MOO74].

LISP ist zu diesen Hilfen befähigt, weil es nicht nur über die passenden Datenstrukturen verfügt, sondern weil die Implementatoren ein Gesamtsystem zur Entwicklung von Programmen im Auge haben: Ein Programmiersystem. Aus dieser Sicht wird eine Charakteristik im Abschnitt 3.8 versucht.

Alle Programmiersprachen, die Zeichenkettenverarbeitung enthalten, ermöglichen im Prinzip die Analyse, Transformation und Synthese von Programmen. Damit ein erzeugtes Programm aber zur Abarbeitung kommt, mu\sses im allgemeinen erst aus- und dann wieder eingegeben werden(über einen sekundären Speicher), um vom Compiler akzeptiert und übersetzt werden zu können. Dieser schließt meist die gleichzeitige Existenz des erzeugenden Programms aus: Nur mittels komplizierterer Schritte, wie unabhängigem Übersetzen des erzeugten Programms, Erzeugen eines verschiebbaren Moduls, Zusammenfügen mit dem ursprünglichem Programm und erneuten Aktivieren, kann man ein derartiges Ziel erreichen. Aber dann können die Ergebnisse der Abarbeitung des erzeugten Programms nur in seltenen Fällen vom Erzeugungsprogramm benutzt werden, um das Programm eventuell weiter zu verbessern und zu vervollkommen.

Es sollte bei der hohen Einschätzung bezüglich der Bedeutung und der Leistungsfähigkeit dieser Eigenschaft von LISP jedoch nicht übersehen werden, da\sserhebliche methodologische Probleme mitselbstmodifizierenden bzw. abarbeitungsfähigen codeerzeugenden Programmen verknüpft sind. Soweit ein solches Problemm automatisch abläuft, dürfte es außerordentlich schwer zu verstehen, zu verwalten und für richtig zu befinden sein. Die Idee von {\sc J. v. Neumann}, die elektronischen Rechenanlagen so zu konzipieren, daß die Programme intern von Daten nicht unterschieden werden können, hat zwar ungeahnten Möglichkeiten eröffnet, aber auch zu einer Komplizierung geführt. Die Entscheidung der meisten Programmiersprachen gegen die Etablierung dieses Prinzip ist weitgehend bewußt aus methodologischen Erwägungen erfolgt: Man bemüht sich, Daten und Programme möglichst deutlich zu separieren.

Indem LISP höhere Datenstrukturen zur Beschreibung der Programme einführte, distanzierte es sich gleichzeitig von den anrüchigen Spielereien mit Bits, um Programmstücke in unterschiedlichen Kontexten zu verwenden und ``superschnell'' zu machen. Der Bereich der Programme, die die Datennahme sind Programme, die ausgesprochen zur Programmerzeugung aufgestellt wurden [AD75].

Es dürfte aber klar sein, da\ssein System, das aus gegebenenInformationen lernt, sich vervollständigt, verbessert und so Probleme lösen kann -- mit einem Wort, ein allgemeiner Problemlöser, wie ihn die künstliche Intelligenz versteht [LEH72] -- notwendig dieseMöglichkeit braucht. Wie soll die Vervollständigung und Verbesserung neben quantitativer Vergrößerung der Datenbasis ablaufen, wenn nicht durch Konstruktion von neuen Teilprogrammen?

Unter diesem Aspekt ist es kein Wunder, da\ssdie Idee von derprozeduralen Darstellung des Wissens [WOO68] von LISP-Expertenentwickelt wurde, die auf dem Gebiet der Künstlichen Intelligenz forschen. Darstellung von Wissen in prozeduraler Form bedeutet, daß die Datenbasen nicht nur in Form von Faktensammlungen nach der Vorbild eines Lexikon oder Thesaurus entworfen werden, sondern da\sssiedynamische Komponenten enthalten, die bei der Suche nach Wissen aktiv werden und entweder dies Wissen konstruieren oder doch den Suchproze\ssbeeinflussen.

Neben diesen sehr weitgehenden Konsequenzen aus der Tatsache, daß LISP Programme wie Daten behandelt, eröffnen sich aber auch einige naheliegende Anwendungen für den Systemprogrammierer, die dem Nutzer Hilfestellungen bieten: Der überwiegende Teil der Systemprogramme zum bequemen Arbeiten mit den LISP-Programmen kann in LISP selbst entwickelt werden. Der Systemprogrammierer ist also Nutznießer des von ihm selbst geschaffenen Programmiersystems und somit an dessen Perfektionierung erheblich interessiert.

Ein Beispiel dafür sind die Programme, die beliebige andere Programme ``lesbar'' (bzw. ``schön'') ausdrucken, Dieses Problem brennt dem LISP-Programmierer natürlich besonders unter den Nägeln, weil ein als normale Listenstruktur ausgedrucktes Programm durch die vielfältige Klammernstruktur im allgemeinen unlesbar ist. Mit Hilfe eines PRETTYPRINT-Programms [Gols73] kann der LISP-Nutzer das (und mehr) erreichen, was ein Paragrapher dem Benutzer einer klassischen anweisungs-basierten Programmiersprache liefert [YO75,CON70].

Man kann sogar mehr: Es ist möglich (und wurde auch verschiedentlich ausgeführt), in LISP einen Programmanalysator (codewalker) zu schreiben [TE74,TE65a],mit dem die Datenstruktur, die eine Funktion repräsentiert, manipuliert werden kann. Besonders interessant ist dabei die Orientierung auf syntaktische Strukturen im Unterschied zu der auf Zeichen oder auf Eingabezeilen. Dadurch wird der Programmierer im Umgang mit bedeutungsvollen Programmelementen unterstützt. Er denkt in Begriffen wie fehlenden Argumenten, überflüssigen Bedingungen, unrichtigen Namen usw., statt da\sser an einzelnen Zeichen undZeilen orientiert wird.

Auf ähnliche Weise kann sich jeder Programmierer in LISP Hilfsmittel entwikkeln, die ihm methodisch wünschenwert erscheinen. Ein schönes Beispiel dafür ist das Programm zum Sichtbarmachen der hierarchischen Aufrufstruktur eines Programmsystems [BO69]. DasProgramm {\tx DWIM} (Do What I Mean) von Teitelmanist ein exzellenter Fall eines Systemprogrammes, das durch Programmanalyse reale Hilfsstellung bietet: Im Fehlerfall aufgerufen, vesucht es, den ``Sinn'' des falschen Programmstücks zu ermitteln und Änderungsvorschläge abzuleiten, die zu einer Fehlerbeseitigung führen. Dabei steht unter anderem die Erkennung von einfachen Schreibfehlern (vergessenes Drücken der Taste ``numerisch'' bei Klammern, Schreibfehlern in Namen usw.) im Vordergrund [TE72a,TE74]. Überhaupt sind die vonW. Teitelman entwickelten Programme zur Unterstützung desProgrammierers, insbesondere des im Dialog arbeitenden, von ihrer Nützlichkeit her betrachtet, einmalige Hilfsmittel [TE66,TE69,TE72b,TE77]und basieren auf der Eigenschaft von LISP, Programme und Daten prinzipiell gleich zu behandeln.

Prozeduren (Funktionen) können nicht nur Wissen aus einer Datenbasis ableiten helfen bzw. es konstruieren. Prozeduren, die Datenbasen zu geordnet sind, können auch die Zugriffsroutinen selbst verkörpern bzw. die Operationen, mit denen bestimmte Teile verknüpft werden können.

Sandewall [SAN75a] hat diese Form der Verwendung der zur Debattestehenden Eigenschaften von LISP eingeführt und sie später in einer Gesamtmethodologie der Programmierung, des Conceptual Programming[SAN75p], eingebettet. Die auf diese Weise in LISP mögliche Methodeder Programmierung von Datenbanksystemen geht über die Idee der strukturierten Programmierung hinaus und korrespondiert in macher Weise mit den Konzept der abstrakten Datenstrukturen [LISK74].

Das allgemeine Verwaltungsprogramm einer Datenbasis liest zusammen mit den (statischen) Daten aus den Datenvorrat die Routinen mit ein, die die Zugriffsweise auf die Daten und ihre Verknüpfungen beschreiben und durchführen. Globale Aktionen sind mehrfach parametrisiert: Neben den Daten taucht die angepaßte Manipulationsfunktion mit auf.

Indem die möglichen Grundfunktionen in Klassen eingeteilt werden, kann der Verwalter die Daten zugeordneten Routinen aktivierbar machen und abarbeiten. Da dies es beim Zugriff auf einem bestimmten Datentyp geschieht, kann man von einer Programmstruktur sprechen, die von den Daten statt von einem generellen Monitor gesteuert wird (data driveness [SAN75b]).

Durch SIMULA67 ist das Klassenkonzept ins Gespräch gebracht worden[DA70]. Der inzwischen entwickelte Begriff der {\em abstraktenDatenstruktur}, mit den die statische Datenstruktur und erlaubte Aktionen an ihr bzw. mit ihr in Form zugeordneter Prozeduren erfaßt werden, ermöglicht eine Modularisierung der Programme von den Daten her. Diese Ideen diskutiert man seit Anfang der siebziger Jahre unter dem Begriff objekt-orientierte Programmierung. Obwohl LISP keine echte objekt-basierteSprache ist, enthält es doch viele der Möglichkeiten von Anfang an.

Wenn man in einer der bekannteren Programmiersprachen, nehmen wir z.B. PASCAL, eine Variable einführt, so sind die Namen dieser Variablen für den Ablauf uninteressant. Eine beliebige Änderung, die nur Konflikte zwischen den Namen vermeidet, ist möglich. Nach der Compilierung liegt das Programm in interner Form (Maschinensprache) vor -- die Namen und ihre Bedeutungen sind völlig verloren. In einem guten Programmiersystem ist zwar eine Symboltabelle aufgehoben worden, aber vom Programm her gibt es praktisch keinerlei Möglichkeit, sich auf sie zu beziehen. Wenn man nun etwa ein Programmzu schreiben hätte, das Daten einliest, die aus Zeichenketten und Zahlen bestehen (hier muß schon angenommen werden, da\ssdiese verfügbar sind), so ist praktischnicht möglich, die Zeichenketten als Information über die Variablen aufzufassen, denen das zugeordnete numerische Datum zugewiesen werden soll. In PL/I ist dieser kleine Dienst mit Hilfe eines besonderen Feature möglich (get data). Auch hier wäre es unmöglich, durcheine Abfolge von Zeichenkettenmanipulationen eine Zeichenkette zu erzeugen, deren Inhalt mit der vom Programmierer notierten Variablen übereinstimmt, und dann eine Zuweisung auszulösen.

Die Namen der Variablen verschwinden spätestens am Ende des Compilerlaufs, und der Nutzer müßte sich sein eigenes System zur Arbeit mit einer Symboltafel schreiben.

Ernster als diese fehlende Verknüpfung von Zeichenkette und Variable ist etwa der Defekt in PASCAL, da\ssgewisse nichtnumerischeDaten keinerlei definierte Ein- oder Ausgabemöglichkeiten haben. Die Skalare in Pascal sind zu deklarieren und werden während der Ablaufzeit praktisch wie ganze Zahlen behandelt. In manchen PASCAL-Systemen scheint es möglich zu sein einer Variablen vom Typ Farbe (mit type farbe = (rot, grün, gelb)) durch eine Einleseoperationeine 1 (für rot) als rot selbst zuzuweisen.

In LISP dagegen bleibt die Symboltafel bestehen, die Atome werden dynamisch behandelt. Werden die Programme interpretiert, so besteht eine ständige enge Verbindung vom Namen einer Variablen zu ihrem Wert. Ähnlich wie in SNOBOL oder TRAC ist es möglich, einen Namen neu zu konstruieren und ihn dann als Namen einer Variablen zu betrachten, d.h. ihm einen Wert zuzuweisen.

Neben der Verwendung als Variablen stellen die Atome aber auch wirklich Daten dar: Ihr Name repräsentiert einen guten Teil nicht numerischer Information. Außerdem kann jede Variable (in LISP: Atom) Ausgangspunkt einer komplizierten Datenstruktur, der Eigenschaftsliste, sein.

 

Interpretative Abarbeitung

Da\ssLISP durch ein Interpretersystem verarbeitet wird, hat sichhistorisch durch einen Zufall ergeben. Doch war die Situation nicht neu zu jeder Zeit (1958), und so manche andere gleichzeitige Symbolmanipulationssprache wurde interpretiert: IPL [NEW61] und COMIT[YN62] waren damals bzw. wurden etwa gleichzeitig mit LISP erstmaligimplementiert.

Als dann Ende 1959 der erste Compiler arbeitsfähig war, begann LISP sein Doppelleben mit beiden Übersetzungsmöglichkeiten: Während der Interpreter Teil des gesamten Verarbeitungssystems ist und dem Nutzer in der zweiten Phase des grundlegenden Zyklus ``Einlesen -- Verarbeiten -- Ausgeben'' entgegentritt, paßt sich der Compiler an einer bescheideneren Stelle ein -- er ist nur Pseudofunktion im Gesamtsystem der Funktionen, die auf Verlangen gewisse Funktionen verarbeitet und dabei als Seiteneffekt in equivalentes Programm in Maschinencode herstellt, das zwar schneller abläuft, aber praktisch nicht mehr analysierbar ist.

Interpretation und Compilierung sind die zwei grundsätzlichen Arten der Übersetzung einer Programmiersprache. Dabei umfaßt die Interpretation nicht nur die Übersetzung, sondern gleichzeitig die Abarbeitung, Auswertung, Berechnung. Dies ist der Grund dafür, daß Allen [ALL78] diese Programme zur Pragmatik schlägt.

Als Interpretation bezeichnet man gewöhnlich die Art vonSprachübersetzung, die die Programmteile, entweder so wie sie sind oder in eine passende interne Struktur übergeführt, analysiert und entsprechende Aktionen ausführt. Das bedeutet insbesondere, daß ein gegebenes Teilstück eines Programms jedes Mal, wenn es interpretiert wird, neu zu analysieren ist.

Im Gegensatz zur Interpretation steht die Compilierung (oderCompilation), wobei die Programmteile erst sorgfältiganalysiert werden und dann eine Folge von Maschinenbefehlen aus ihnen erzeugt wird. Faßt man den internen Code auch als eine Sprache auf, so läßt sich der Begriff der Compilierung verallgemeinert als die Erzeugung eines Programms in einer Zielsprache, ausgehend in einem Programm in eine Objektsprache auffassen. Im Unterschied zu diesem sehr allgemeinen Übersetzungsschema scheint im Begriff der Compilierung ein deutlicher Niveauunterschied zwischen Objekt- und Zielsprache mitzuschwingen: erstere ist höheren, letzteren niederen Niveaus (deshalb z. B. Recompilierung). Das Programm, das diese Art vonÜbersetzung realisiert, ist der Compiler. Es bekommt dasgesamte Programm in der Objektsprache als Eingangsinformation. Da moderne Sprachen mit dem Typ- und anderen Deklarationsangaben dem Compiler weitreichende Möglichkeiten zum Erfassen der Programmsemantik mitgeben, kann ein Compiler oft erheblich optimierte Programme herstellen und eine ganze Reihe von Fehlern, die man normalerweise in dem Bereich der Semantik schlagen würde, erkennen und anzeigen.

Da ein Programm zuletzt doch immer von einer Rechenanlage abzuarbeiten ist, liegt schließlich entweder ein Maschinenprogramm vor, das die Programmaktionen hervorruft, oder ein Interpreter (der ein Maschinprogramm ist), der der, wie oben beschrieben, das betreffende Programm oder irgendeine aus ihm abgeleitete Zwischenform analysiert und die gewünschten Aktionen ausführt.

Ohne Zweifel läuft ein compiliertes Programm schneller ab als ein interpretiertes, und man mag sich fragen, ob die Interpretation sich überhaupt lohne. Hat Highman [HIG67] recht, wenn er dieInterpretation in den Listenverarbeitungssprachen (die alle etwa 1958-64 entstanden sind) als ``dem damaligen Stand der Wissenschaft'' entsprechend bezeichnet, d.h. also für unmodern erklärt?

Die Entwicklung hat gezeigt, da\ssHighman unrecht hat mitseiner Behauptung. Interpretation ist ein höchst modernes Prinzip, wenn sie in einem gesunden Wechselspiel mit der Compilierung steht und wenn das Verarbeitungssystem interaktiv betrieben wird.

Schon die Kostenfrage erscheint überdenkenswert: Während dieInterpretation eine gewisse einfache Phase der Umformung enthält, entfällt die meiste Zeit auf die eigentliche Abarbeitung. Anders als der Compiler, sieht der Interpreter aber nicht das ganze Programm: Er arbeitet nur die Teile ab, die von der gegebenen Testdatenmenge abhängt. So kann es vorkommen, da\ssdie Interpretationskosten sehrgünstig im Verhältnis zu Compilationskosten liegen: Werden nur wenige Programmteile wiederholt ausgeführt, so dürfte die Interpretation bei weitem billiger sein, da der große Posten für die Compilierung selbst nicht unter den Tisch fallen darf.

Für die reine Abarbeitung selbst wird ein Geschwindigkeitsfaktor von 10 [BROW76] erwartet. Dabei ist festzuhalten, da\ssauch diecompilierten Programme gewisse interpretative Phase kennen: Ein- uns Ausgabe, Übergang in das Run-Time-System usw. Die Vorteile der Interpretation sind [BROA75]:

  1. Leichtere Änderung eines laufenden Programms. Weil einweitgehender Teil der Information über das ursprüngliche Objekprogramm erhalten geblieben ist, gibt es genügend Unterstützung, wenn ein neuer Ausdruck (bzw. eine neue Anweisung) eingegeben wird: Die Beziehung zu den Programmgrößen kann leicht hergestellt werden, der Platz, an den der verbesserte Programmteil gebracht werden muß, kann ermittelt werden usw.

    Sogar wenn neue Deklarationen oder ganze Prozedurköpfe zu ändern sind, kann der Anschlu\ssan die ungeänderten Programmteile beimnächsten Interpretationslauf erfolgen.

     

  2. Reduktion der Größe des Objektcodes. Einen typischenFall dieses Vorteils sieht Broadbent, wenn die Datentypen derProgrammobjekte vor der Laufzeit noch nicht vorhanden sind und in das Programm deshalb Routinen eingeschlossen werden müssen, die die Typüberprüfungen vornehmen. In einem Interpreter kommen diese Routinen nur einmal vor und müssen deshalb nicht an verschiedenen Stellen eingebaut werden, wo überall Typüberprüfungen für erforderlich gehalten werden.

    Übehaupt ist der Compiler weitgehend ratlos, wenn die Typen der Daten nicht bekannt sind. Daher ist ein gewisse Anteil an Interpretationen zur Laufzeit lebenswichtig [BROW76].

     

  3. Bessere Diagnostik und Möglichkeiten der Reaktion aufFehler. Mit einer Darstellung des Programms, die dem ursprünglichen Quelltext eng entspricht, sind Test- und Fehlersucharbeiten leichter auszuführen. Sicherlich kann man auch in compilierte Prtogramme hilfreiche Informationen einschließen, wie z. B. die Anweisungsnummer, um bei einem Fehler zur Laufzeit wenigstens die Fehlerstelle ermitteln zu können.

    Das Problem besteht aber darin, da\ssman vielfältigeInformationen über den Zustand des Programms beim Auftreten des Fehlers und seine Vorgeschichte benötigt, um zur Fehlerursache vorzudringen. Ist ein Programm aber erst einmal in der Maschinensprache, so sind wichtige Kenntnisse im allgemeinen nach dem Lauf des Compilers verlorengegangen.

    Es gibt nun Compilersysteme (WATFOR, siehe [KEN70]), dieetwa hauptsächlich für die Lehre gedacht sind und deshalb von vornherein darauf zugeschnitten sind, da\ssder Programmierer vieleFehler macht und das Programm in seiner gegenwärtigen Form nur einmal angeboten wird. Für den einen Lauf hebt ein solches System die Symboltafel auf, die die notwendigen Informationen enthält.

    Doch in leider allzuvielen Fällen wird der Programmierer auch heute noch allenfalls mit einer Fehlernachricht (die meist nur mitteilt, da\ssein Fehler aufgetreten ist), mit einer Anweisungsnummer und miteinem hexadezimalen oder oktalen Speicherauszug konfrontiert.

    Alle Systeme, die dem Programmierer das Fehlersuchen erleichtern wollen, interpretieren wenigstens teilweise die Programme. Dies kann mit dem Objektprogramm erfolgen oder mit dem Quellproramm [KUL69, SAT75].

     

  4. Leichtere Portabilität der Sprache. Während einCompiler oft erheblichen Aufwand kostet, kann ein kleiner Interpreter oft einfach, schnell und kostengünstig in einer höheren Programmiersprache geschrieben werden, die an der neuen Installation verfügbar ist.
  5. Vereinfachung des Übersetzers. Weil so viel erst zurLaufzeit abgewickelt wird, was sonst normalerweise schon zur Compilierungszeit erledigt wird -- wie z. B. die Typüberprüfung -- hat der Übersetzer selbst eine einfache Struktur und ist wesentlich kleiner.

Die Entwicklung in der Rechnerarchitektur hat dazu geführt, daß heute schon oft nicht mehr unterschieden werden kann, wo die Interpretation anfängt oder wo sie aufhört. Viele Rechner der dritten Generation enthalten Mikroprogramme, die ihrerseits die sogenanten Maschinenprogramme interpretieren. Man hat schonversucht, das logische Niveau der Maschinenprogramme zu heben um dem der höheren Programmiersprachen anzugleichen [BURR64, AU74].Inzwischen beginnt man sogar, Rechner zu entwickeln, die mittels ihrer Firmware verschiedene Sprachen höheren Niveaus interpretieren [WILN72].Dies gilt insbesondere für LISP (vgl. S. 215, 220).

Für LISP ist die Kopplung von Interpretation und Compilation hauptsächlich aus methodischen Gründen wichtig. Der Interpreter-Compiler-Verbund wird normalerweise so genutzt, da\ssdieFunktionen (Programme) mit Hilfe des Interpreters symbolisch ausgetestet werden. Man hat dabei den Vorteil, sowohl spezifische Test als auch Systemtest -- d.h. die Funktion im Zusammenspiel mit anderen Funktionen -- durchführen zu können. Hilfsfunktionen für die Testarbeit, also für die Aufbewahrung von Programmablaufsgeschichte (backtracing), für das Überwachen von Zuweisungen, von Sprüngen und von Funktionsaufrufen sowie zur Setzung und Abarbeitung von Unterbrechungspunkten sind in fast jedem LISP-System in der Qualität enthalten, die für andere Programmiersprachen nur von Fall zu Fall geliefert werden.

Hat sich der Programmierer von der Zuverlässigkeit einer bestimmten Funktion überzeugt, dann compilert er sie und gewinnt die etwa benötigte Geschwindigkeit.

Allen [ALL78] hat wohl als erster in Zusammenhang mit LISPdarauf hingewiesen, da\ssauch unabhängig von der Fehlersuche eineKooperation von Interpretation und Compilierung kostengünstig ist: Während der Interpretation könnten die erreichten Codestücke compiliert werden. Bei wiederholter Abarbeitung von Programmteilen gewinnt man so die gewünschte Geschwindigkeit der Maschinenprogramme. Die nicht berührten Parteien des Programms behalten ihre alte Form. Das beschleunigt die Compilierung und macht das ganze zu einem inkrementellen Proze\ss.

In einer höchst interessanten Studie haben Hansen und {\scWulf} [HAN76] die Effektivität einer Compiler-Interpreter-Symbiosegezeigt: Es ist inzwischen bekannt, da\ssein überwiegenderProzentsatz der Laufzeit eines Programms in kleineren Codestücken verbracht wird. Kennt man diese und konzentriert die Fähigkeiten des Compilers auf die Optimierung eben dieser Programmteile, dann kann eine erhebliche Verringerung der Laufzeit bei geringen Kosten erreicht werden. Der Programmierer ist im allgemeinen auf dem Holzwege bei der Vermutung, welches die kritischen Codestücken sind.

Innerhalb eines speziellen FORTRAN-Compiler-Systems wurde durch Kombination von Interpretation, Compilation und Messung der Abarbeitungsfähigkeit gezielt stufenweise optimiert. Ergebnis ist ein System, das sowohl für einmalige Programmläufe als auch für den Dauerlauf außerordenlich kostengünstig arbeitet.

 

LISP als Dialogsprache

 

Zum Begriff des Dialogs

Im heute noch normalen Fall ist der Informationsaustausch zwischen Rechenmaschine und Mensch stark behindert durch die Peripherie und durch die Organisationsmittel für den Transfer der Informationen, die Programmiersprachen und -systeme für die Steuerung der Maschine. In einem üblichen Stapelverarbeitungssystem hat der Mensch den Austausch normalerweise auf einen einmaligen ``Wortwechsel''zu begrenzen: {\sf Ich plane und du kannst den Plan entweder nur aus formalen Gründen ablehnen oder mußt nach ihm arbeiten und Resultate bzw. Fehlschläge melden.} Allenfalls kann er ein Spektrum möglicher Antworten voraussehen und dementsprechend Erwiderungen von Anfang an mitliefern.

Die Aufteilung eines Jobs in Schritte und das damit verbundene Wechselspiel von Systemaktionen und Steuerinformationen bzw. Daten ist völlig deterministisch -- wenn man von unvorhersehbaren (Hardware-)Fehler- oder Problemsituationen absieht.

Diese konventionelle Umgehensweise mit den Rechenmaschinen ist immer dann sinnvoll, wenn der Mensch seinerseits in der Lage ist, seinen Part des überlegenen Planers, Informators oder großen Steuermanns zu spielen. Während er Ziele und Zwecke besser einschätzen kann, Querverbindungen zu anderen Wissenbereichen schneller sieht und mit seinem begrifflichen Denken zur Integration unterschiedlichster Informationen in der Lage ist, kann der Rechner wesentlich exakter und genauer mit großen Datenbeständen umgehen und eine ganze Reihe von Überlegungen und Rechnungen um Größenordnungen schneller als der Mensch erledigen. Dabei ist die Exaktheit bemerkenswerterweise vom Umfang der Datenmengen nicht abhängig.

So kann es denn Situationen geben, wo der Mensch keineswegs der überlegene Denker ist. Wenn er Schritte planen mu\ss, die für ihn derartig komplex und umfangreich sind, da\sser das erwartete Ergebnisnicht vorwegnehmen kann, ist er zur Planung nicht in der Lage. Er wünscht, die Schritte vollziehen zu lassen, um dann ``operativ'' entscheiden zu können. Wenn er es mit Informationsstrukturen zu tun hat, die zu umfangreich sind, als daß er sie auf einmal angeben kann, möchte er je nach den Umständen seinen Standpunkt und sein Gesichtfeld verändern können.

In diesen Fällen lenkt der Mensch zwar den Handlungsablauf, ist aber zur Erstellung eines abarbeitungsfähigen Programms nicht in der Lage.

Es kann aber auch sein, da\ssder Rechner der überlegene Partnerist: Jedes größere Programm ist nahezu sicher falsch -- der Rechner kann mit Leichtigkeit syntaktische Fehler finden, die der Mensch allein wegen der Programmgröße übersehen hat. Läuft auf dem Rechner ein Lehrsystem, so ist der Schüler a priori der schwächere Partner -- das Lehrsystem führt ihn, verlangt von ihn Antworten, richtet auf diese Antworten seine Lektionen ein und paßt sich dem Lermtempo an. Da jeder Schüler anders reagiert, wird ein gutes Lehrprogramm sehr flexibel sein müssen. Im Fall einer rechnergestützten Datenbasis schließlich möchte der Mensch Auskünfte vom Rechner. Er weiß zwar ungefähr, was er erfragen will, kann aber durchaus Probleme bei der Formulierung seiner W\"nsche haben und die Möglichkeiten, die das System ihm bietet, nur zu einem geringen Teil kennen.

In diesen Fällen genügt ein einmaliger Wortwechsel nicht. Wenn es die zur Verfügung stehenden Organisationsmittel nicht mehr erlauben, ergibt sich durch Weiterführung des Wortwechsels zu anderer Zeit ein aufwendiger Austausch, bei dem Mensch und Maschine Probleme haben werden, sich wieder so einzustellen, wie es dem Endergebnis förderlich ist.

Effektiver ist demgegenüber ein Dialog, bei dem der Menschunmittelbar auf Mitteilungen des Rechners reagieren und ihn durch neue Aufgabenstellungen zu Auskünften oder weitergehenden Aktionen veranlassen kann. Gewöhnlich wird jeder Partner warten müssen, bis der andere sich auf eine Mitteilung hin geäußert hat. Wenn es sogar möglich ist, bei allzu langwierigen Dialogpausen einzugreifen und sich über die ablaufende Handlung zu erkundigen, spricht man von {\em Interaktion} [KUP76].

 

Dialogsysteme

Um die Nachrichten, Anfragen oder Befehle zu formulieren, ist eine Sprache erforderlich. Da diese Sprache nicht, wie gewöhnlich, nur menschliche Mitteilungen erlauben soll, sondern auch die Äußerungen von der Rechnerseite erfassen mu\ss, sprechen wir von Dialogsprachen.

Neben den Dialogsprachen für Auskunfts- und Informationssysteme, für Lehrsysteme und graphisch orientierte Systeme spielen die für die interaktive Programmentwicklung derzeit eine große Rolle. Das liegt daran, da\ssan der Entwicklung eines die für eigene Arbeitnützlichen Werkzeugs jeder Programmierer interessiert ist. Zudem ist das Ziel der Programmierung der Rechner: Von der Fehlerhaftigkeit eines Programms kann man sich gut überzeugen, wenn der Rechner es abarbeitet und in eine Fehlersituationen gerät.

Die Dialogprogrammiersprachen sind selten für die Programmentwicklung einer beliebigen Programmiersprache gedacht. Alle wichtigen Entwicklungen dieser Art enthalten Dialoginstrumente für die Programmerstellung in eben dieser Dialogprogrammiersprache selbst. Kupka und Wilsing [KUP76] unterscheiden hier zwischender Sprachebene zur Erfassung der problemorientierten Datenstrukturen und Operationen der zur Programmstrukturierung und Dialogsteuerung. In einem detaillierteren Modell der Sprachstruktur von Dialogsprachen unterscheiden sie:

  1. den Kern, der die nicht dialogspezifischenproblemorientierten Datenstrukturen und die zugehörigen Operationen enthält,

     

  2. die Schicht der Programmiertechnik, die dieKontrollstrukturen für die Strukturierung von Programmschritten und -teile umfaßt, wie Sequenz, Alternative, Wiederholung, Funktionen, Prozedur -- um aus normalen Programmiersprachen bekannte Sprachelemente anzuführen, und

     

  3. die Schicht der Dialogtechnik, die Mittel zum Umgehen mitProgrammen (``ausführbare Objekte'') -- wie Erzeugung, Verwendung, Aktivierung, Ausgabe, Löschen, Speichern, Editieren -- und Möglichkeiten zur dynamischen Kontrole der Ausführung dieser Programme einschließt.

Außer bei der Verwendung eventuell in der Sprache implementierter Dialogsysteme (Auskunfts-, Lehr- und ähnliche Systeme) kommt in einem Dialogsystem der Dialog bei der Programmentwicklung, bei der Ablaufsteuerung und bei der zweckgerichteten Ausführung fertiger Programmteile (auch als Tischrechnerfunktionen bezeichnet) zur Anwendung.

Die interaktive Programmentwicklung basiert hauptsächlich auf den Mitteln zur Eingabe von Programmtexten und zu einer Änderung.

Bei der Eingabe kannn das Verarbeitungssystem auf vielfältige Art Hilfestellungen bieten, indem z. B. nach Niederschrift einer syntaktischen Einheit sofort Fehler reklamiert werden, falls gegen die Regeln der Grammatik verstoßen wurde. Das System kann darüber hinaus Korrekturvorschläge anbieten bzw. versuchen, in gewissen Fällen abgekürzte oder angedeutete Texte auszuschreiben oder fortzuseetzen. Die Hilfestellungen können sich auf einzelne Zeichen, ganze Zeilen oder gar Programmsegmente und ganze Programme beziehen. Kutschke[KUT77] bezeichnet diese Ebene als Minidialog.

Zum Korrigieren bedient man sich einer Editierungssprache, die den Editor aktiviert. Dieser Editor kann sich auf den externen Text in einer Datei oder auf eine interne Repräsentation beziehen. Da die Editierung in einer Datei bei anschließendem Wunsch, den berichtigten Text zu aktivieren, auf Probleme bei der Beschaffung des Platzes stoßen wird und sicher langsam abläuft, wäre die Änderung eines anschließend aktivierbaren internen Objekts vorzuziehen. Da die Änderung in Einheiten der Programmiersprache bzw. auf den externen Text hin orientiert sein mu\ss, ist die Abarbeitung der Programme durch Interpretation einer Datenstruktur, im die das Programm eindeutig umgeformt werden kann, wünschenswert.

Neben der Wahl der Editororientierung auf intern verfügbare Repräsentation oder externe Dateien, auf einzelne Zeichen des Programms oder sinnvolle syntaktische oder semantische Komplexe der Sprache, können weitere Entscheidungen die Handlichkeit dieses zentral wichtigen Programms stark beeinflussen: Soll die Editierung einen kompletten Wechsel der Programmebenen erfordern, d.h. mu\ssman, wennman sich zum Editieren entschlossen hat, in einen Editorstatus übergehen, eine bestimmte Kette von Operationen in diesem Status völlig außerhalb des normalen Verarbeitungssystems ausführen und dann versuchen, wieder den ursprünglichen Systemzustand mit dem Editierungsresultat zu erreichen, oder soll die Editierung durch einzelne kleine Operationen in jeder Umgebung möglich sein? Soll der Editor die Resultate und eventuell ein Protokoll drucken, oder sollte man von vornherein auf den Bildschirm orientieren [SAN78a]?

Für die interaktive Ablaufsteuerung ist neben der Aktivierung von Programmteilen und ihrer Versorgung mit Testdaten vor allen wichtig, da\ssselektive Information über den Abblauf bereitgestellt wird. EinKernspeicherabzug in interner Darstellung (Dump) ist unlesbar, in symbolischem Format ist er nicht überschaubar. Benötig wird natürlich der Inhalt einer oder weniger kritischer Variablen in dem Augenblick, wo der Fehler verursacht wird. Da diese Information praktisch nicht beschaffbar ist, da eben nach ihr gesucht wird, muß es wenigstens möglich sein, von der Stelle, wo der Fehler sichtbar geworden ist, einige Schritte rückwärts zu gehen, diese Stelle klar zu charakterisieren und die Variablen, die vermutlich in den Fehler verwickelt sind, zu inspizieren.

Oft reichen diese Informationen über den Zustand nach dem Fehler nicht aus. Dann werden Hilfsmittel benötig, um das dynamische Verhalten des Programms und die Veränderung ausgewählter Variabler verfolgen zu können.

Das dynamische Studium wird wesentlich gefördert, wenn an gewissen Punkten -- entweder vorprogrammierten (ausgewählt durch das Eintreffen gewisser Kontrollerreignisse, d.h. die Ausführung eines anvisierten Programmteils, oder durch das Eintreffen eines bedeutsamen Wertzustands) oder durch direkten Eingriff von außen bestimmten -- Unterbrechungen der Abarbeitung vorgenommen werden können. In einem speziellen Unterbrechungsstatus sollte es dann möglich sein, den erreichten Zustand zu erforschen (sowohl bezüglich Variablenwerten als auch bezüglich des kontrollpunkts und seiner Stellung im Programm -- durch Analyse von Aufrufketten u. ä.). Nach Klärung der offenen Fragen mu\ssder normale Verarbeitungsproze\ssweitergeführt werdenkönnen, als ob er nicht eingefroren gewesen wäre.

Die Verwendung der Dialogsprache des Kerns in kleinen semantischen Einheiten wird gern als tischrechnerartige Verwendung [KUP76]bezeichnet. Hierbei werden etwas einzelne Anweisungen oder bloße Ausdrücke ausgewertet. Das System vollzieht in einem Hauptniveau (top level) einen Zyklus von Einlesen -- Verarbeiten -- Ausgaben. Die jeweiligen Eingaben werden sofort ausgewertet. Zu diesem Zweck -- um dem Nutzer die Ausführung komplizierterer Aktionen zu ermöglichen -- mu\ssdie Sprache viele implizite Anweisungen akzeptieren, vieleFunktionssymbole bereitstellen, eine umfängliche Ausdrucksteilsprache enthalten und bequeme Notation (möglichst mathematische Schreibweise) gestatten. Darüber hinaus mu\ssnatürlich die Ein- und Ausgabejeder manipulierbaren Datenstruktur definiert sein.

In demselben Verarbeitungsniveau werden die Kommandos der dritten Sprachschicht eingebracht und sofort verarbeitet. Kupka undWilsing sehen hier folgende Ziele: a) Systemzugriff, b)Übergang zum Editieren, c) Dateiverwaltung, d) Übersetzung uns Ausführung von Programmen, e) Organisation des Hintergrundstapels, f) Systemverwaltung, g) Betriebsmittelzuteilung und h) Kommunikation mit anderen Nutzern.

Bei der verschiedenen Zielfunktionen der Sprachen in den verschiedenen Schichten scheint es letztlich doch ungünstig, insgesamt von der Dialogsprache zu sprechen. Die Charakterisierung desGanzen als Programmiersystem und die Zerlegung der in Schichtenaufgeteilten Dialogsprache in mindestens drei Sprachen(Programmier-, Editier,- und Kommandosprache) bildet wohl die Wirklichkeit wesentlich besser ab [SAN78a]. Wesentlich ist dabei, daßalle diese Funktionen unter einem Dach innerhalb eines Systems bewältig werden, ohne da\ssder Nutzer unter Rettung vonZwischenresultaten das Betriebssystem zum Wechsel zwischenden Ebenen -- Programmentwickler, Interpreter, Editor, Tester usw. -- aktivieren mu\ss(vgl. auch [BO73b]).

 

Das LISP-Programmiersystem

Welche Forderungen sind nun an die Basissprachen zu stellen? Die einfachsten Bedingungen stellt die Programmierung von Tischrechnern: Die Sprache sollte prozedurorientiert sein, ihr Kern weitgehend frei von Deklarationen, und es sollte gewisse kleine semantische Einheiten geben, die direkt auswertbar sind und schrittweise eine größere Verarbeitungsaufgabe lösen lassen (Sandewall [SAN78a]bezeichnet dies als die Inkrementalität der Sprache). DieserSprachteil sollte möglichst vielgestaltige Ausdrücke enthalten. Dann sollte die Syntax bzw. der Syntaxanalysator so beschaffen sein, da\ssfehlerhafte Eingaben nie zuZusammenbrüchen führen: Alles mu\ssinterpretiertbar sein und --dies ein Wunsch an das Verarbeitungssystem -- mit verständlichen und direkten Erwiderungen vom System beantwortet werden.

Für eine breitere Anwendung wären komplexere Datenstrukturen als etwa Zahlen und Zeichenketten sehr erwünscht, für die allerdings Ein- und Ausgabe vollständig definiert sein müssen. Wenn man mit der Sprache Datenbanken aufbauen könnte, wäre dies eine wesentliche Bereicherung.

Sicher wäre es besonders bequem, wenn sogar das ganze Programmiersystem selbst in der Sprache programmiert werden könnte. Offensichtlich ist ja die Entwicklung eines solchen Systems keine leichte Aufgabe. Der Service, den das System bietet, würde glleichzeitig dem Entwickler zugute kommen. Außerdem könnte jede Nutzer eigene angepaßte Systemerweiterungen vornehmen.

Ein derartiger Wunsch ist nur realisierbar, wenn man in der Basissprache mit Programmen umgehen kann -- es mu\sseineDatenstrukturdarstellung von Programmen, und zwar von Programmen der Sprache selbst geben.

LISP genügt weitgehend allen diesen Kriterien, und es ist etwas kurios, feststellen zu müssen, da\ssdiese Sprache in dem Werk überDialogsprachen von Kupka und Wilsing [KUP76] völligignoriert wird. An bestimmten Stellen scheint LISP etwas ungewöhnliche Notationsweisen zu erfordern (z. B. Arithmetik), an anderen Stellen wieder bewährt es sich hervorragend (z. B. Programme als Datenstrukturen, LISP als Systemprogrammiersprache, Interpretation als Grundprinzip der Verarbeitung usw. usf.).

Etwas problematisch erscheint der Zwang zum Verlassen der üblichen algebraisch-arithmetischen Ausdrucksschreibweise vor allem bei der Verwendung des Programmiersystems als Tischrechner. Dieses Problem ist in LISP jedoch nur auf Kosten der Einheitlichkeit der Sprache lösbar, weil generell eine Listennotation für Programme beobachtet wird. Ein durch W.Teitelman entwickelter Lösungsansatz (CLISP), dieseProbleme durch ein angepaßtes Fehlerbehandlungssystem aufzuheben, ist kontrovers. Da sich LISP aber zur Implementation höherer Sprachen eignet, könnten durch Einbringung einer neuen Sprachebene bequeme Notationshilfsmittel bereitgestellt werden. Sandewall [SAN78a]spricht hier von Surface Languages, weil die höhere Sprachedas LISP-Basissystem nur überdeckt. Wenn eine solche Sprache gar zu einem Verarbeitungssystem erweitert wird, wie dies etwa im Fall des Formelmanipulationssystem {\tx REDUCE} [HEA73] geschehen ist, könnendie Fähigkeiten des Tischrechners wesentlich erweitert werden.

In den LISP-Systemen sind die verschiedenen Sprachschichten weitgehend integriert. Durch das Funktionskonzept spiegeln sich die verschiedenen Dienste wenig in der äußeren Form der Sprache selbst wider. Sie werden vielmehr durch Gruppen von Funktionen abgedeckt. Nur für gewisse Spezialzwecke hat man das Ausdruckskonzept verlassen: Der Editor in InterLISP, Vorbild aller guten LISP-Editoren ([TE74], Section9), verfügt über kurze Kommandos immer dann, wenn das Argument klar ist: der aktuelle Punkt der Aufmerksamkeit in der zu ändernden Programmdatenstruktur. Auch im Unterbrechungszustand ({\tx BREAK}) bei der Testung sind gewisse Kommandos möglich, die nicht in die Sprache LISP eingeschlossen werden können ([TE74], Section 15).

 

Ein Beispiel

In einem kleinen Beispiel soll ein wenig von den Dialogfähigkeiten eines LISP-Systems anklingeln. Das ist bei weitem nicht soviel, wie etwa Sandewall [SAN78a] oder Teitelman [TE72a,TE72b,TE69,TE77]präsentieren, soll aber durch Verwendung eines einfachen funtionsorientierten Editors -- er verfügt über keine LISP-frenden Kommandos -- ganz in LISP ablaufen.

Die Grundfunktion des Editors, EDIT, arbeitet strukturorientiert und ist resident [SAN78a]. Der Programmierer ersetztTerme durch andere Terme. Der anvisierte Term wird durch eine Suche in dem Funktionskörper gefunden, die der Druckrichtung entspricht: Zunächst wird ein ganzer Ausdruckt geprüft, ob er der gewünschte ist, dann werden die Argumente von links nach rechts (rekursiv) ebenso geprüft. Durch eine Selektorliste können mehrere Aufrufe bzw. ein bestimmtes Exemplar bei Wiederholungen bezeichnet werden.

Die allgemeine Form eines Aufrufs von EDIT lautet:{\em

(EDIT\=  ((in welcher Funktion welcher Ausdruck)  (wie oft, welches Vvorkommen) wodurch zu ersetzen)  (...))

}

Zum Beispiel ändert EDIT((F1 F2) (2 6) (F3 NIL))) in der FunktionF1 den 2. und 6. Aufruf von F2 in den Ausdruck (F3 NIL).

Wie sieht ein typischer Dialog mit einem LISP-System aus? Vermutlich gibt es keine wirklich typischen Vorgänge dieser Art, weil jeder Programmierer sich anders verhält. Dennoch soll versucht werden, das Beispiel möglichst allgemeinen zu halten. Bevor der Nutzer starten kann, benötigt er eine Erlaubnis dazu und Platz auf den externen Speichermedien. Die Erlaubnis hat er meist in Gestalt einer Kundennummer oder eines Paßwortes in der Hand, das er dem System zu Anfang mitteilen muß.

Wenn wir annehmen, da\ssder Nutzer schon öfter interaktivgearbeitet hat, bedeutet das, da\ssseine Dateien (oder Files) auf denexternen Geräten (meist Direktzugriffsgeräten, d.h. Platteneinheiten) wenigstens teilweise gefüllt sind. Die Dateien enthalten also schon Folgen von LISP-Ausdrücken, meistens Funktions- und Konstantendefinitionen, seltener auch andere Ausdrücke, die gewüschte Zustände herstellen sollen. Die eigentliche Arbeit beginnt dann also damit, da\sseine gewisse Auswahl von Dateien geladen wird.

Diese Arbeit ist nun stark systemabhängig, denn das Betriebssystem verwaltet die Dateien, und es mu\ssnicht jede Art vonDateizugriff erlauben. Im Prinzip gibt es zwei Varianten: Entweder der Nutzer lädt eine Datei als Gesamtheit (dabei bleibt das Terminal das aktuelle Eingabegerät) oder er veranlaßt das LISP-System, das Eingabemedium zu dem Gerät zu wechseln, auf dem die Datei liegt. Statt vom Terminal fließt nun der Eingabestrom von der angesprochenen Datei in das System. Am Ende der Datei oder wenn in dem Eingabestrom Umschaltoperationen eingeschlossen sind, wird dann wieder das Terminal als Eingabemedium angesehen (vgl. auch [KUR78]).

Für den Anfang ist auch eine zweite Prozedur denkbar: Wenn der Programmierer eine Auswahl seiner Dateien geladen hat, neue Definitionen und Daten hinzugefügt und Änderungen und Tests vollzogen hat, verkörpert der so erreichte Zustand eine gewisse, nutzerspezifische Inkarnation des LISP-Systems. Es kann sein, da\sser Wert darauf legt,in eben dieser Daten- und Programmumgebung weiterzuarbeiten. Dies ist in vielen LISP-Implementationen möglich, indem der Systemzustand als Speicherabzug \footnote{Auch Overlay (Texas-LISP) oder {\emCheckpoint} (STANFORD LISP/360).} gerettet wird. In InterLISP wird auch ohne besondere Vorkehrungen so verfahren, weil die Seiten des virtuellen Speichers ohnehin auf dem externen Seitenspeicher in der Form abgelagert sind, in der das System sich zu einem bestimmten Zeitpunkt befindet. Der Nutzer mu\ssnur Sorge tragen, da\ssdiese Seiten, dieseine Inkarnation des LISP-Systems ausmachen, bis zu seiner nächsten Sitzung geschützt werden.

Kehren wir zum DOS/ES LISP 1.6 [STO78] zurück und nehmen an, derNutzer baut sich seine Inkarnation auf, indem er die gewünschten Dateien komplett lädt:

$\rightarrow$ (*COPY FILE1)$\leftarrow$ FILE1$\rightarrow$ (*COPY FILE2)$\leftarrow$ FILE2

Die Symbole $\rightarrow$ bzw $\leftarrow$ bedeuten Eingabe von Terminalbzw. Ausgabe (Antwort des Systems) zum Terminal. Nun möge eine Datei Funktionen enthalten, die der Programmierer beim letzten Dialog gerade erst erstellt hat. Er möchte jetzt testen, nachdem er sich Gedanken über möglichst signifikante Testbeispiele gemacht hat. Diese gibt er nun der Reihe nach ein und bewertet die gelieferten Ergebnisse:

$\rightarrow$ (FX '(TESTDATEN) '(TESTDATEN) ...)$\leftarrow$ ERGEBNIS1...

Plötzlich tritt ein Fehler auf. Direkt nach der Fehlernachricht und dem angezeichten falschen Ausdruck folgt eine Information über die Vorgeschichte des Fehlers. Die unmittelbar vor dem Fehlerereignis durchgeführten Auswertungsaktionen werden mitgeteilt:

$\leftarrow$ **ERR1 : NONUMERICAL ARGUMENT$\leftarrow$ (ABCD$\leftarrow$ ****BACKTRACING****$\leftarrow$ X$\leftarrow$ Y$\leftarrow$ (*PLUS Y X)... $\leftarrow$ (FY (CDR L1) COUNT1 COUNT2)..,.

(Die Lage des Backtracing hat der Programmierer selbst bestimmt.) Der Nutzer erkennt, da\sser beim Aufruf der Funktion FY dieArgumente verwechselt hat: X und Y sollten mit dennumerischen Werten COUNT1 und COUNT2 versorgt werden,die Liste sollten als drittes Argument erscheinen. Die Änderung ist einfach, der fehlerhafte Ausdruck steht in der Funktion FX.

Aus einem Listing der Funktion FX (man glaube nicht, daßPapier völlig überflüssig wird. Auch eine interaktive Sitzung mu\sssorgfältig vorbereitet sein. Ganz ``aus der Kalten'' wird mansehr viel Zeit verschwenden) entnimmt unser Programmierer, da\ssessich um das zweite Vorkommen von FY im Funktionskörper vonFX handelt. Unter Verwendung der einfachen Editierfunktion {\tt EDIT} gibt er demnach ein:

\noindent$\rightarrow$ (EDIT ((FX FY) (2) (FY COUNT1 COUNT2 (CDR L1))))$\leftarrow$ FX

Um sich über die Korrektheit der Änderung zu überzeugen, läßt sich unser menschlicher Dialogpartner die Funktion FX``schön'', d.h. übersichtlich und verständlich, ausgeben:

\noindent$\rightarrow$ (PRETTYPRINT FX)$\leftarrow$ (LAMBDA (L1 L2 L3)$\leftarrow$ (PROG (COUNT1 COUNT2)... $\leftarrow$ (COND$\leftarrow$ (...(FY COUNT1 COUNT2 (CDR L1)))...

Auf dem Bildschirm steht die gesamte Funktion und läßt sich vorzüglich betrachten. Die Änderung ist richtig angekommen. Ein erneuter Aufruf mit denselben Testdaten bringt keinen Fehler mehr:

\noindent$\rightarrow$ ERR2:CAR OF AN ATOM$\leftarrow$ NIL$\leftarrow$ ****BACKTRACING****$\leftarrow$ X$\leftarrow$ (CAR X)$\leftarrow$ (CDR (CAR X)... $\leftarrow$ (FZ (CDDDDR LISTE) (CADR NUMLISTE))...

In diesem Fall möge der Fehler so kompliziert sein, da\ssder Nutzerihn nicht auf Anhieb findet. Möge etwa die Funktion FZ, dieoffenbar einen gewichtigen Anteil an der Erzeugung des Fehlers hat, relativ gro\ssund umfangreich sein und außerdem an vielen Stellendes Programms vorkommen. Ein TRACE-Lauf, wobei jeder Eintrittund Austritt in bzw. aus FZ protokolliert wird, ist nichtangebracht. Der Name X der fehlerhaften Variablen (offenbarmu\sssie eine kürzere Liste als Wert gehabt haben, als zunächstangenommen) erscheint auch ungünstig gewählt, weil überall {\tt X} vorkommt: Deshalb ist auch die Überwachung der Zuweisungen nicht günstig, weil X allzuoft Ziel einer solchen Zuweisungen ist.

Nach langem Grübeln glaubt der Programmierer, da\ssein Aufruf derFunktion F7 in der Funktion FZ kritisch für den Fehlersei: Ist dieser Ausdruck ohne Fehller ausgewertet, dann wird die Sache völlig problematisch: Eine kleine Umgereimheit hier würde manches erklären. Da auch für F7 ein TRACE-Lauf zu vielInformationen bringt, wird ein ganz gezielter Unterbrechungspunkt in die Funktion FZ gesetzt: Es genügt zu wissen, wie der Wert vonF7 an der anvisierten Stelle unter einer speziellen Bedingungist. Hier möge der Aufruf eine ganz spezifische Gestalt haben (d.h., F7 wird in FZ an keiner anderen Stelle mit genau diesenaktuellen Parametern aufgerufen): (F7 (F5 ARG1) (F4 ARG1)).

Dieser Ausdruck interessiert nur, wenn ARG1 nicht NIList. Daher wird in der Funktion FZ an der vorgesehenen Stelleein bedingter Unterbrechungspunkt plaziert:

$\rightarrow$ (BREAK ((FZ (F5 ARG1) (F4 ARG1))) () ARG1 T))$\leftarrow$ FZ.

Der Aufruf von BREAK ähnelt sehr dem von EDIT, nur daßjetzt hinter der Wiederholungsliste die Bedingung steht. Hier ist die Wiederholungsliste leer, das bedeutet ``alle derartigen Ausdrücke ändern''. Nach der Bedingung steht ein T, damit wird dieUnterbrechungsaktion ``Ausgebe des Wertes''ausgelöst.

Erneut wird das Testbeispiel versucht:

$\rightarrow$ (FX'(TESTDATEN13) '(TESTDATEN131)...).

Nach kurzer Zeit ist der Unterbrechungspunkt erreicht:

$\leftarrow$ *** BROKEN : F7$\leftarrow$ VALUE IS : (D) .

Dieser Wert ist völlig falsch! Wie kommt das nur? Der Programmierer möchte jetzt gerne etwas über die Argumente wissen. Da das System am Unterbrechungspunkt (d.h. nach Auswertung des anvisierten Ausdrucks) auch in der Unterbrechungszustand gagangen ist, kann er in der vorliegenden Umgebung Ausdrücke auswerten lassen.

Was ist mit ARG1?

$\rightarrow$ ARG1$\leftarrow$ (1 (A) 2 (B) 3 (C) 4 (D)...) .

Unerklärliches Resultat! Und (F5 ARG1)?

$\rightarrow$ (F5 ARG1)$\leftarrow$ (4 (D))

Plötzlich fällt unserem Programmierer etwas Schreckliches ein: Das Auftreten von ARG1 an dieser Stelle ist Unsinn! Es hätte jaARG2 heißen müssen! Natürlich...! Ganz klar...! Wiekonnte ich nur...!

Also ändern:

$\rightarrow$ (EDIT ((FZ (F7 (F5 ARG1) (F4 ARG1))) () (F7 (F5 (ARG2) (F4 ARG1))))$\leftarrow$ FZ.

Unterbrechungszustand Aufhebung und Verarbeitung abbrechen (d.h. zurück ins Hauptniveau):

$\rightarrow$ GO

Und erneut testen:

$\rightarrow$ (FX '(TESTDATEN13) '(TESTDATEN131)...)$\leftarrow$ ERGEBNIS13.

Ebenso richtig laufen alle anderen Testbeispiele. Die Funktion ist richtig, sie kann nun compiliert werden:

$\rightarrow$ (COMPILE FX)$\leftarrow$ (FX).

Und der Programmierer entwickelt seine nächste Funktion:

$\rightarrow$ (DE F33 (X Y Z) ....

Wir sehen, er hat aus seinem Fehler noch nicht genügend gelernt. Die Namen sind immer noch nicht problemspezifisch. Aber wir wollen ihn in Ruhe weitere Fehler machen lassen und beenden das Beispiel.

Als beste interaktive LISP-Implementation galt Ende der siebziger Jahre bereits InterLISP [TE74] \footnote {InterLISP bedeutet interaktivesLISP}. Weder CommonLISP noch die modernen LISP-Maschinen haben wesentliche qualitative Verbesserungen bezüglich der Programmierumgebung erreichen können -- besser sind nur die Bildschirme, die Maschinen sind schneller. Neben einem Editor, der wesentlich bequemer ist als der hier vorgeführte, waren in InterLISP vielfältige Testunterstützungen vorhanden: Das BREAK-Paket, mit der Unterbrechungspunkte gesetzt und verwaltetwerden, der Advisor, mit dem Änderungen in Funktionen ausgeführtwerden, ohne da\ssexakt deren Struktur bekannt ist, das DWIM-Paket, das automatisch Fehler zu korrigieren versucht, in Zweifelsfällen dem Nutzer Änderungsvorschläge unterbreitet und auf dem wichtigsten Fehlergebiet, dem der Schreib- und Tippfehler aktiv ist, das Teilsystem Assistent des Programmierers(programmers' assistant), bei dem die Aufbewahrung von Informationen über den Interpretationsablauf wichtig ist, so da\ssim FehlerfallAktionen rückgängig gemacht werden können und der Nutzer im Dialog bis zur Fehlerursache vorstoßen kann (statt Symptome zu erkunden).

Natürlich hat der Dialog seine Berechtigung nicht nur bei der Programmerarbeitung und bei der Testung. Die Programme selbst können auf interaktive Mithilfe des Menschen angewiesen sein. Ein Beispiel hierfür ist der interaktive Theormbeweiser der Universität Texas [BLE75a], der es dem Mathematiker ermöglicht, bei fehlgeschlagenenBeweisversuchen oder zu lange dauernden Beweisschritten helfend einzugreifen.

Mit der Verfügbarkeit dieser Möglichkeiten spielt LISP eine Pionierrolle auf dem Gebiet der Programmiermethodik, die allzu oft vergessen wird.

 

Weitere Besonderheiten und Charakteristika

 

Eigenschaftslisten

Eigenschaftslisten (oder kurz P-Listen von {\em porpertylist}) sind Datenstrukturen, die mit den Atomen verknüpft sind. In ihnen wird gewöhnlich Information aufbewahrt, die zu dem Atomsymbol gehört, die es in gewissen Sinne umfassender beschreibt, als dies der Name kann und tut.

In manchen LISP-Systemen kann man geradewegs das Atom mit seiner Eigenschaftsliste identifizieren [QA72a], in anderen stellt dieEigenschaftsliste neben einer Kopfzelle den wesentlichen Teil dar [MCC62c,STO78] oder tritt nur als Bestandteil unter anderen auf [TE74,NOR69b,KUR76a].

Eigenschaftslisten sind als Assoziationslisten aufgebaut, allerdings in der älteren (und ungünstigeren) Form: Indikatoren und zugehörige Eigenschaft sind nicht in gepunkteten Paaren angeordnet, sondern sequentiell hintereinander.

Die Operationen, die mit den Eigenschaftsllisten möglich sind, stellen sie in eine Reihe mit den Records in PASCAL [WIR72] bzw. denStrukturen in PL/I oder ALGOL68 [WIJ75]. Teile einer P-Liste, d.h. dieEigenschaften, können über Selektoren (die Indikatoren) angesprochen werden. Wie jede Aktion in LISP, so läuft auch diese Zugriffsaktion mit Hilfe einer speziellen Funktionen ab: Üblicherweise wird {\tt GET} dazu benutzt.

Der PL/I-Notation STRUCTUR. SELECTOR entspricht die LISP-Notation (GET 'STRUCTUR 'SELECTOR\})

Die Quotierung deutet eine der gegenüber den erwähnten Programmiersprachen existierende Erweiterungen dar: Sowohl die Struktur selbst (dies ist auch in ALGOL 68 m\"glich) als auch der Selektor können errechnet werden. Mit Hilfe dieser Möglichkeit bietet LISP dem Nutzer den verketteten Zugriff zu Elementen von Teilstrukturen. Hierbei ist allerdings die Notationsform in LISP weniger übersichtlich, weil die verschachtelten Funktionsaufrufe die Zugriffskette verdecken. Statt STRUCTUR.PARTSTRUKTUR1.PARTSTRUKTUR11.ELEMENTwird (GET(GET(GET 'STRUCTUR 'PARTSTRUCTUR1)'PARTSTRUCTUR11) 'ELEMENT)notiert. Ein Teil der Verbesserungen von MLISP2 [SM73a93] bezieht sichauf diesen Punkt, indem eine übersichtlichere Notation eingeführt wird.

Zur Veränderung einer Eigenschaft bzw. Aufbau eines neuen Elements der Struktur wird die Funktion PUTPROP eingesetzt\footnote{In CommonLISPhüllt man einfach einen GET}-Term mit dem SETF-Macro ein.: Als Argumente werden Struktur (also Atomnamen), Selektor (d.h. Indikator) und neuer Wert angegeben.

Ihre Flexibilität bekommen diese LISP-``Strukturen'' durch ihre Implementation als Listen: Jede Eigenschaft kann beliebig kompliziert werden, ohne da\ssder Programmierer Vorkehrungen zu treffen hat. Wieüblich werden keine Typ-Vereinbarungen betroffen, denn man geht ganz allgemein von der Möglichkeit aus,den Typ zur Laufzeit ermitteln zu können. Die Eigenschaften sind ganz normale Listenelementen.

Auch die Eigenschaftsliste selbst profitiert davon, da\sssie eineganz normale Liste ist (die allerdins nur über GET und PUTPROP ereichbar ist): Sie kann beliebig lang sein. Der Nutzer muß sich weder Gedannken machen über die Form seiner diversen Strukturen, er kann sie auch zur Laufzeit ändern: Die P-Listen haben beliebig viele Indikator-Eigenschaftspaare; je nach Notwendigkeit keine, einige oder sehr viele.

Von hoher Bedeutung bei der Verkettung dieser Strukturen ist die Eigenschaft von LISP, da\ssdie Symbole zur Laufzeit vorhanden sind undeine direkte Beziehung zwischen den Programmkonstanten, -variablen und sonstigen Größen und den Eingabedaten besteht: Jedes Atom existiert nur einmal (vgl. Abschnitt 3.6). Weil Atome selbst als Eigenschaften auftreten können (die Indikatoren sind üblicherweise auf Atome eingeschränkt), kann man ein Netz von verflochtenen Eigenschaftslisten aufbauen. LISP-Datenbasen sind üblicherweise Mengen von Atomen mit ihren Eigenschaftslisten. Sie sind besonders flexibel, weil unter den Eigenschaften und Programme (Abschnitt 3.6) auftauchen können, die etwa die Verarbeitungsweise anderer Eighenschaften beschreiben.

Alles in allem sind die P-Listem also ein interessantes und handliches Mittel zur Strukturierung großer Datenmengen. Die Analyse aller LISP-Systeme, die für Probleme der Verarbeitung notürlicher Sprache oder anderer ähnlich komplexer Anwendungsgebiete geschrieben wurden, zeigt die extensibe Verwendung dieses Prinzips. {\sc Sandewall} [SAN69a] beschreibt eine allgemeine P-Listen-Struktur fürsolche Systeme.

 

Besondere Mechanismen für die Parameterübergabe

Jede prozedurorientierte Sprache würde bei korrekter Implementation die $\beta$-Regel des lambda-Kalküls verwirklichen müssen (vgl. Abschnitt 3.8). Da die treue Befolgung der Konversion nur mittels Umbennenung und Substitution möglich ist, hat man von Anfang an bescheidenere Modelle der Parameterübergabe verwirklicht bzw. im Auge gehabt. Durch die strenge Beachtung unterschiedlicher Bindungsbereiche wurde eine Art impliziter Umbennenung vollzogen, funktionale Parameter, die mit den einfachen Mechanismen nicht verträglich waren, wurden verboten.

ALGOL60 führte mit dem Aufruf über den Namen(call-by-name) als Übergabemechanismus nahezu die volle Substitution ein. Probleme mit freien Variablen (die im lambda-Kalkül durch Umbennenungen gelöst werden) konnte man einerseits durch das Implementierungsschema der statischen Bindung [DI60] lösen,den Schutz vor erneuter Bindung bei Lieferung funktionaler Werte nach außen durch Konstruktion einer Abschließung und Aufhebungder benötigten Kellerspeicherteile (retention) konnte man in ALGOL 60 nicht verwirklichen.

Die Programmierer hatten sich aber an die einfacherern Mechanismen Aufruf über den Wert (call-by-value) bzw. {\em Aufruf überReferenz} (FORTRAN, CPL, PP/I, Pascal) gewohnt und standen dem komplizierten Substitutionsmechanismus skeptisch gegenüber.

Beim Aufruf mittels (über den) Wert wird der aktuelle Parameter zuerst berechnet, und wenn alle Parameter wertmäßig vorliegen wird der jeweilige Wert dem formalen Parameter zugeordnet. Dabei wird eine Berechnungsreihenfolge (von links nach rechts) fest eingehalten. Die Wertzuordnung erfolgt vor dem Eintritt in die Prozedur (Prozedurhauptteil). Benutzt man in der Prozedur einen solchen Wert-Parameter, so hat er, wenn inzwischen keine Zuweisung ihn geändert hat, den Wert, den der entsprechende aktuelle Parameter hatte.

Beim Aufruf mittels (über) Referenz wird der aktuelle Parameter berechnet, auf eine bestimmte Stelle gespeichert und die Adresse dieser Stelle dem entsprechenden formalen Parameter übergeben. Handelt es sich bei dem aktuellen Parameter um eine Variable (ob indiziert oder nicht indiziert ist unwesentlich), dann wird sofort die zugeörige Adresse genommen. Die Übergabe dieser Adressen als Parameterwerte erfolgt sonst wie im Fall des Aufrufsmittels Wert.

Benutzt man in der Prozedur einen derartigen formalen Parameter, so erfolgt eine indirekte Bezugnahme (über die angegebene Adresse) auf die Stelle, wo der aktuelle Parameter steht (bzw. auf die Variable im aufrufendem Block). Das bedeutet, da\sssich Benutzungen eines solchenParameters praktisch nicht von denen von Parametern unterscheiden, die mittels Wert aufgerufen worden sind, solange diese Benutzungen nicht Zuweisungen sind. Tritt aber ein solcher formaler Parameter in einer Ergibtanweisung als eine linksstehende Variable auf, dann wird nicht der formale Parameter, sondern die Stelle, auf die er sich bezieht geändert. Man kann also Werte nach außen geben. Der formale Parameter behält seine Referenz zu dieser Stelle.

Beim Aufruf mittels (über den) Namen wird der aktuelle Parameter überhaupt nicht ausgewertet. Vielmehr wird die Prozedur so abgearbeitet, als ob an jeder Stelle, so der formale Parameter auftaucht, der aktuelle Parameter substituiert worden wäre. Somit wird bei jedem Auftreten des formalen Parameters in der Prozedur der aktuelle berechnet. Es ist klar, da\ssman damit diffizileImplementationsprobleme hat, insbesondere, wenn Konflikte mit Namen eintreten. Die Beschreibungen im ALGOL-Report ([B62], S.26) enthältdie Substitutionsimplementation.

Deutlichste Unterschied zwischen den drei Mechanismen zur Parameterübergabe ist das Auftreten einer indizierten Variablen als aktueller Parameter

\begin{center}f(A[i], A[i], A[i]),\end{center}

der erste möge per Wert, der zweite per Referenz und der dritte per Namen (besser wäre die Bezeichnung: per Substitution) übergeben werden. Während beim Aufruf mittels Wert der Wert der Variablen, d.h. das im Feld an der bezeichneten Stellen stehende Argument, übergeben wird, ist es beim Aufruf mittels Referenz seiner Adresse (der Platz im Feld) und beim Ruf mittels Namen der Ausdruck der indizierten Variablen -- es kann also auf verschiedene Stellen im Feld Bezug genommen werden, wenn sich der Index i ändert [HIG67].

Als LISP entwickelt wurde, war auf diesem Gebiet noch nicht viel Wissen vorhanden. Als naheliegende Form der Parameterübergabe wurde der Aufruf über den Wert gewählt, d.h., die Argumentausdr\"cke müssen von links nach rechts ausgewertet werden, bevor diese Werte den Funktionsvariablen zugeordnet werden und die Funktion angesprungen ist.

Für einige spezielle Terme erwies sich dies jedoch als semantisch nicht naheliegend -- man nannte sie ``Special Forms''. In diesen Fällen waren die Terme gerade dadurch gekennzeichnet, da\ssdas Symbol in funktionalerStellung keine eigentliche Funktion war, sondern ein Hinweis auf eine spezielle Abarbeitung der in der Spezialform zusammengefaßten Terme. Dies Symbole beschrieben gewissermaßen die Auswertungsreihenfolge bzw. teilweise sogar die Bedeutung der Subterme. Die äußerlich gleicher Form der Spezialformen zu den normalen Termen führte zur Übernahme des Funktionskonzepts auch für die benennenden Symbole der Spezialformen bei völlig unterschiedlicher Semantik. Man versuchte die Sicht, da\sses sich um abartige Funktionen mit spezieller Argumentübergabehandele.

Auch die Terme in höchsten Niveau bereiten Unbequemlichkeiten bei Durchsetzung des normalen Wertübergaberegimes: Läuft eine Berechnung erst einmal, dann hat man keine Sorgen mit dem Parameterübergabemechanismus ``Aufruf mittells Wert''. Durch Bezugnahme auf Variable und verschachtelte Argumente mu\ssjederaktuelle Parameter ausgewertet werden. Beim eigentlichen Aufruf aber notiert der Programmierer neben den Namen der Funktion im Hauptniveau die Daten, z. B. irgendwelche Listen. Ihn interessieren aber die Liste als Daten, so wie sie sind, und nicht ein anderer Wert. LISP bietet hierfür mit dem Quotieren die Möglichkeit mitzuteilen, da\ssdieseListen für sich selbst stehen. Auf die Dauer ist das aber unbequem. Deshalb führte man einen neuen Parameterübergabemechanismus ein, bei den die Parameter unausgewertet übergeben werden.

Demnach wäre es in LISP besser statt ``Aufruf mittels Wert'' zu sagen ``Aufruf nach Auswertung'', um den Gegensatz zum zweiten Mechanismus, ``Aufruf ohne Auswertung'',hervorzuheben.

Es gibt aber eine gewisse Differenz in den beiden angegebenen Problemfällen: Während die Spezialformen eigentlich gar keine Argumente haben und nur in das Funktionskonzept gepreßt werden, indem der ganze restliche Ausdruck (ohne das anzeigende Schlüsselsymbol in funktionaler Stellung) als Argument angesehen wird, könnten die Hauptniveau-Funktionen durchaus unterscheidbare Argumente haben.

Ein weiterer Probemfall führt jedoch zur vorläufigen Systematisierung (historisch erst 1966): Unter den Grundfunktionen befindet sich eine, nämlich LIST, die offenbar auszuwertende Argumente bekommt, aber eine nichtfestgelegte Anzahl!

Demnach gibt es also zwei Grundprobeme: Parameter, die beim Funktionsaufruf nicht auszuwerten sind, und Parameter, deren Zahl nicht feststeht. Die Spezialformen verlangen nicht ausgewertete Parameter in beliebiger Zahl, die Hauptniveau-Funktionen sind für nichtauszuwertende Parameter in festgelegter Zahl gedacht, LISTund ähnliche Funktionen sollen ausgewertete aktuelle Prameter in beliebiger Zahl bekommen, und die normalen Funktionen erwarten ausgewertete aktuelle Parameter in begrenzter Zahl.

Da man nicht beiebig viele formale Parameter angeben kann, beschränkt man sich auf einen, über den die anderen erreichbar sind.

In den alten Systemen hat man den normalen Funktionen alle anderen als Ausnahme gegenübergestellt: Dieser wurde als ein Argument die gesamte unausgewertete Liste der aktuellen Parameter übergeben. Für etwa erforderliche Auswertung und Aufteilung auf lokale Variable waren die Funktionen dann selbst verantwortlich.

In den darauf folgenden Systemen sind die zwei Grundhandlungen bei der Parameterübergabe wieder auseinandergenommen worden. Am deutlichsten verfuhr hier InterLISP, das alle Kombinationen erlaubte: Normale Funktionen, wie CAR, CONS usw., benutzen Aufruf mit Auswertungund Übergabe durch Aufteilung auf einzelne formale Parameter, die Hauptniveau-Funktionen u. ä. benutzen Aufruf ohne Auswertung und Übergabe durch Aufteilung auf einzelne formale Parameter, die Spezialformen benutzen Aufruf ohne Auswertung und ohne Aufteilung bei der Übergabe, und die kleine Klasse der Funktionen mit beliebiger Argumentzahl benutzt Aufruf mit Auswertung und ohne Parameteraufteilung bei der Übergabe.

Obwohl bisher noch nicht in die Basissprache eingedrungen, sind in den Metasystemen weitere Übergabemechanismen erprobt worden. So kennen die Symbolmanipulationssysteme eine Art Aufruf nach Möglichkeit:Tritt als Parameter eines Funktionsaufrufs eine Variable auf, so wird geprüft, ob diese einen Wert hat. Fällt der Test positiv auf, so wird der Wert als aktueller Parameter übergeben, geht er negativ aus, dann wird die Variable sebst übergeben [BOG75], QA4 [RUL72] brachteder musterbedingten Übergabemechanismus auf: An der Stelle der formalen Parameter wird ein Muster notiert, in dem die Variablen in der Musterstruktur auftreten. Beim Aufruf der Funktion wird zunächst ein Mustervergleich durchgeführt. Geht er erfolreich aus, so wird der Funktionskörper abgearbeitet -- die Variablen sind während des Vergleichsprozesses mit lokalen Werten belegt worden. Geht der Vergleich negativ aus, so wird die Funktion nicht aufgerufen, ein Backtrack-Schritt erfolgt.

Die Arbeiten von Mannna, Cadiou und Vuillemin[MAN74, CA72, V73] haben aber auch bei der Betrachtung derÜbergabemechanismen für LISP neue Bewegung geschaffen. Die Feststellung der Nichtkorrektheit des Call-By-Value-Mechanismus für nichtstrikte Funktionen \footnote {Eine strikte Funktion ist undefiniert, wenn auch nnur eines der Argumente undefiniert ist. Der von Cadiou [CA72] betonte Unterschied von strikten und nichtstriktenFunktionen bei ihrem Fixpunktverhalten war von Vuillemin [V73]vernachl\"ssigt worden. De Roever [ROE74] und Bakker[BAKK75] haben ohne Anknüpfung an Cadious Resultat dieKorrektheit der Call-By-Value-Regel gezeigt.} und die Suche nach einer vergleichsweise effizienten Alternative haben zur Entwicklung des Mechanismus Call-By-Delay geführt: Den formalen Parameternwerden unausgewertete Argumente übergeben. Bei der ersten Benutzung eines Parameters erfolgt die Auswertung. Später wird immer der so gewonnene Wert verwendet. Das schöne Motto: ``Was du heut nicht mußt besorgen, das verschieb getrost auf morgen'', das sich schon im Leben manch menschlichen Faulpelzes als arbeitsparend erwies, ist die Grundidee dieses Ansatzes. Morris und Henderson habenschon 1976 einen auf dieser Grundlage arbeitenden LISP-Interpreter vorgeschlagen [MORR76].

 

Experimente mit allgemeineren Kontrollstrukturen

Im Normalfall wird in LISP der Ablauf des Berechnunsprozesses gelenkt durch die hierarchische Ordnung der ineinandergeschachtelten Ausdrücke (Terme). Diese implizite Steuerung wird durch die bedingten Ausdrücke erweitert und teilweise explizit gemacht. Besondere Ereignisse und komplizierte Algorithmen können auf diese Weise aber schwer beschrieben werden: Fehlerzustände und Ausnahmebegingungen erfordern Austrittsmöglichkeiten (exits) aus inneren Programmteilen [PEE73]. Globale Exits haben sich auch in anderen Programmiersprachen alswichtige Hilfsmittel zur Vereinfachung erwiesen.

Neben der Verschachtelung von Funktionsaufrufen bot schon LISP1 die Möglichkeit, Programmabläufe explizit darzustellen durch Programmierung sequentieller Ausdrucksfolgen (deren jeweiliges Ergebnis unbeachtet bleibt und die ausgelösten Seiteneffekte ihren Zweck bestimmen) mit Verzweigung durch GO (Sprünge). Obwohlanscheinend die Bereiche, innerhalb denen gesprungen werden darf, mehr eingeschränkt waren als bei gleichzeitigen blockorientoerten Sprachen (nur im jeweiligen Block), konnte doch die Marke berechnet werden. Allerdings waren keine Markenvariablen und keine Markenparameter zulässig. In LISP 1.5 wurde auch die Verwendung von Ausdrücken im GO verboten. Wenn man die den Sprüngen auferlegtenBeschränkungen als vorbildlich für ihre Zeit (1959!) ansehen darf, so bleibt dem undiziplinierten Programmierer noch genügend Freizeit, unverständlich komplizierte Programmstrukturen zu entwickeln, allerdings nur in einem Blockniveau.

Für die Behandlung von Fehlerzuständen war schon 1962 die Funktion ERRORSET eingeführt worden. Mit dieser Funktion hatder Programmierer die Möglichkeit, Fehlerbehandlungsniveaus und Fehlereinflußbereiche einzuführen. Die freie Verfügbarkeit eines derartigen Mechanismus ist wesentlich besser anwendbar und effektvoller als der ON-Mechanismus in PL/I:

Bei der Interpretation lösen bestimmte Ausdrücke Unterbrechungen der Verarbeitung aus -- Division durch O, arithmetische Operationen mit nichtnumerischen Parametern, fehlerhafte Argumentanzahlen, Typfehler u.a. --, die im Normalfall die Auswertung beenden. ERRORSETbegrenzt den betroffenen Bereich auf einen ERRORSET-Ausdruck(faktisch aud das Argument von ERREOSET, das ein Ausdruck ist),erlaubt eine Analyse des Fehlerzustands und erneutes Abarbeiten von Ausdrücken.

Eine solche Funktion ist unbedingt erforderlich, wenn man in LISP z.B. eine andere Programmiersprache implementieren will. Nehmen wir an, ein fehlerhaftes Programm löst einen Fehler im LISP-System aus. Der Nutzer der Gastsprache (die in LISP implementiert ist) kann aber nicht mit den Fehlernachrichten des LISP-System konfrontiert werden, da die Implementationstechnik ihn verwirrt und er die Ursachen von den Symptomen nicht ableiten kann. Er benötigt vielmehr bedeutungsvolle Nachrichten, bezogen auf seine Handlungen in der Gastsprache.

Mit Hilfe von ERRORSET kann man die LISP-Basis vor ihnverbergen, die Fehler analysieren und ihm informative Fehlernachrichten liefern, die in seinem Sprachniveau verfßt sind.

Einige LISP-Systeme haben die Möglichkeiten von {\tt ERRORSET} erweitet durch Einführung einer zugeordneten Funktion {\tt ERR} [QA72a, STO78, MOO74]. Nun wird ERRORSET nicht nur imFehlerfall angesprochen, sondern auch durch direkte Auslösung über diese Funktion ERR. Man hat hiermit in beschränktem Maßedie Mittel, Zustände der Berechnung als fehlerhaft zu bezeichnen und innere Niveaus über Fehlerunterbrechungen zu verlassen. Dabei kann ERR Informationen über die Art der Ausnahmesituation nachaußen geben.

Die fortgeschrittensten Systeme, InterLISP und MacLISP, gehen inzwischen noch einen Schritt weiter: Schon immer waren speziell die Autoren von InterLISP der Meinung, da\ssder Nutzer Zugang zu allenSystemteilen haben sollte [BO73b]. In Verfolgung dieser Grundeinstellungermöglicht InterLISP die Manipulation des vom System aufgebauten Kellerspeichers. Der Programmierer kann z. B. zu einer beliebigen Zeit die Struktur des Kellerspeichers erforschen und sich Informationen über die tatsächliche Verschachtelungsstruktur verschaffen. Indem er sich auf Funktionsnamen bezieht, kann er der letzten unvollendeten Aufruf einer Funktion ermitteln. Mit Hilfe der Funktionen {\tt RETFROM} bzw. RETTO kann er willkürlich zu beliebigenAufrufebenen zurückkehren ([TE74], 12.10).

Während diese unspezifische Lösung nicht ganz unbedenklich zu sein scheint (aber große Möglichkeiten für eine automatische Erholung im Fehlerfall bietet), steht die Idee, die man im MacLISP entwickelt hat, in klarer Beziehung zum Konzept der globalen Austritte und ist eine Verallgemeinerung (??) der ERRORSET-Funktion: Ein Paarvon Funktionen, CATCH und THROW, ermöglicht dieÜbergabe der Kontrolle zwischen zwei Ebenen der Berechnung. Durch CATCH wird ein Anfangniveau eingerichtet, das ähnlichwie in BLISS [WU70] die zu verlassenden Kontrollstrukturen, mit einenNamen versehen werden kann. Wird nun irgendwo bei der Auswertung innerhalb dieses Anfangniveau ein THROW aufgerufen, das sich aufdiesen Namen bezieht, dann erfolgt ein globaler Austritt aus dem erreichten Verarbeitungsniveau und der CATCH-Aufruf wird miteinem durch das THROW spezifizierten Wert verlassen ([MOO74], S.5.3).

Ähnlich MacLISP bietet VLISP [CHA76] begrenzte Mechanismen fürglobale Austritte: Während die Funktion LESCAPE ein Verlassendes letzten expliziten lambda-Ausdrucks auslöst (für Funktionale von interessantem Effekt), ermöglicht ESCAPE die Deklarationeiner Exit-Funktion.

Die auf LISP aufgebauenden höheren Sprachen für die künstliche Intelligenz (PLANNER [HEW71c], CONNVER [MCD72], {\tt QA4} [RUL72] und QLISP [SAC76]) haben zur Bewältigung derkomplizierten algorithmischen Aufgaben mit weiteren Kontrollstrukturen experimentiert. Dabei sind alte Konzepte, wie etwa das Backtracking,wieder aufgenommen worden, aber auch neue Ideen entwickelt worden, wie etwa der Funktionsaufruf über Zielmuster (pattern directed function invocation oder die Dämone (auf Aktivationsbedingungen wartendeProzeduren).

Die weite Nutzung des Backtracking in Programmen der künstlichen Intelligenz hat Bobrow und Wegbreit zu ihrer allgemeinenStudie über Kontrollstrukturen geführt [BO73c, d].

Backtracking ist eine mindestens schon Ende der fünfziger Jahre hin und wieder anzutreffende Methode, Suchräume zu durchqueren und ``Tiefe -- zuerst''-Suchalgorithmen zu programmieren. Golomb undBaumert [GOLO65] beziehen sich in ihrem ``erstem Versuch, denBereich und die Methoden der Backtrack-Programmierung in ihrer vollen Allgemeinheit'' zu formulieren, auf mehrere ältere Anwendungen. Während sie zu allgemeinen Grundprinzipien vorstoßen und interessante Anwendungsbeispiele analysieren, lassen sie das Problem der Implementation und der nötigen Steuerkonstruktionen in einer höheren Programmiersprache offen.

Floyd [FL67b] machte den nächsten Schritt, indem er sowohlüber primitive Funktionen nachdachte, als auch über mögliche Implementationen. Seine Grundidee fußt auf der Herstellung einer Abarbeitungsgeschichte in Form einer sequentiellen Folge von inversen Anweisungen, die den tatsächlich abgearbeiteten entsprechen und im Fall des Backtracking die ursprüngliche Situation durch schrittweises Rückgängigmachen der Anweisungen (mittels Ausführung der inversen Anweisung) wiederherstellen. Wie Golomb und Baumert siehtFloyd Backtracking als korrekte Wiederherstellung des Zustandszu der Zeit, als die Entscheidung für den nun abgebrochenen Zweig fiel (am Entscheidungspunkt).

PLANNER [HEW71c] unterschied zwischen {\em rückgängig zumachenden} und unwichtigen Anweisungen. Die Implementation {\scMICROPLANNER} [SUS70, 71] brachte die Unterscheidung von Kontroll- und Datenbacktracking. Wir folgen hier der Ansicht von Smith undEnea [SM73b], die sich über diese Unterscheidung wie folgtäußerten: ``Diese Unterscheidung ist ein negativer Aspekt der Theorie des Backtracking, der die zur Diskussion stehenden Dinge eher verdeckt hat als der Klarheit zugeführt. Der Hauptzweck des Backtracking ist es, einem Programm die Möglichkeit zu geben, spätere alternativen in einem Entscheidungsbaum so auszuprobieren, als ob frühere, die sich als nicht erfolgreich erwiesen haben, überhaupt nicht betrachtet worden sind. Wird der Berechnungszustand nicht zurückgestellt beim Beginn jeder Alternative, dann werden sich die Alternativen verschieden verhalten in Abhängigkeit von der Reihenfolge, in der sie versucht worden sind. ... wenn der Programmierer wünscht, da\ssbestimmte Informationen nach Versagen einerAlternative erhalten bleiben, dann sollte er dies explizit sagen, und jede gute nichtdeterministische Programmiersprache sollte ihn mit Hilfsmitteln dafür ausrüsten.''

Selbst die sonst so ausgezeichnete Diskussion der zugrundeliegenden Konzepte durch Bobrow und Wegbreit versagt an dieserStelle. Es ist mit den angegebenen Funktionen ([BO73d], S. 593) bzw.([BO73c], S. 247) nicht möglich, die vollständige Rettung desDatenzustands beim Backtracking zu beschreiben. Die Funktion {\tt MKFRAME} kreiert bei genaueren Hinsehen nicht einen Rahmen (frame), sondern nur die Rahmenerweiterung (frameextension), in der die für den Nutzer nicht sichtbaren temporären Größen plaziert sind. Globale Änderungen können somit nicht abgefangen werden. Das Beispiel ([BO73d], S. 595) macht hier nur aus der Not eine Tugend.

Dennoch ist die Arbeit von Bobrow und Wegbreitäußerst bemerkenswert. \footnote {Ein kritischer Neuansatz wird von Steele [STE77a} präsentiert.] Schon der Titel weist daraufhin, da\ssdas eigentliche Problem bei der Einführung allgemeinererSteuerstrukturen nicht in der Schwierigkeit liegt, den Programmablauf in gewünschter Weise zu lenken, sondern darin, da\ssnach Erreichung desFortsetzungspunktes die entsprechende Datenumgebung vorhanden sein muß.

Für Implementatoren konventioneller blockorientierter Programmiersprachen ist das nicht Neues, da etwa ein Sprung aus einem inneren Block, in dem eine gewisse lokale Größe A neudeklariert sei, in einen äußeren Block, in dem sie schon auftreten ist -- entweder durch lokale Deklaration oder global \footnote {d.h. deklariert in einem außen liegenden Block.} -- auch einen wechsel der Bedeutung von A mit sich bringt. Durch die Displaytechnikist dafür gesorgt, da\ssdie Sprünge von innen nach außen imallgemeinen unproblematisch sind, während sie in der umgekehrten Richtung ein umfangreiches Laufzeit-Unterstützungssystem benötigt. Welch komplizierte Vorkehrungen bei der Absicherung globaler Sprünge aus Prozeduren in Blöcke der umfassenden Prozedur, wie sie etwa in ALGOL60 oder PASCAL möglich sind, zu trefen sind, kann man nur ahnen.

Beim Backtracking geht dieses Problem der Berechnung der richtigen Datenumgebung jedoch der Nutzer ganz persönlich an. In verschiedenen LISP-Systemen liegen gegenwärtig divergierende Lösungsversuche vor. Während InterLISP auf dem Modell von Bobrow und {\scWgebreit} aufgebaut hat und eine Spaghetti-Struktur des Kellerspeichers aufweist, um die verschiedenen Umgebungen zu representieren, hat MAGMA-LISP [MON75] einen Baum von Kontexten, die der Programmiererexplizit verwalten kann. Ähnliche Möglichkeiten bieten die strackgroups in ZetaLISP.

DOS/ES LISP 1.6 bot, den Ideen von Smith und Eneafolgend, primitive Funktionen für das Backtracking an. Die Zustände werden in einem Kontextspeicher aufbewahrt. Basisfunktionen zum Setzen von Entscheidungspunkten ist DECPOINT. DECPOINT verhält sichneben siner Aufgabe als Funktion zum Initialisieren der Rettung der Umgebung (die wirkliche Rettung dieser Umgebung erfolgt über die Zeit verteilt bei jeder Änderung) wie ein Prädikat: Der Wert Twird geiefert, wenn der Entscheidungspunkt gesetzt wird und der Wert NIL, wenn der Entscheidungspunkt durch einen Mißerfolgaufgehoben wird.

Die von Bobrow und Wegbreit angegebene Funktion {\tt SELECT} ([BO73d], S. 595) lautet unter Benutzung von DECPOINT:

{\tt

 select = p\=rog(()\+
           sl: \=if null(set) then failure();\+
               if decpoint() then return(ear(set));
               set:=cdr(set);
               go(sl);

}

Der Parameter undolist ist unnötig, weil ohnehin alleZuweisungen, auch die in beliebig höheren Umgebungen, beim Aufruf von FAILURE der zweiten Basisfunktion, rückgängig gemachtwerden.

Anders als dies Smith und Enea behaupten, ist eineweitere Basisfunktion, die den Erfolg einer Alternative beschreibt, erforderlich. Gäbe es eine solche Funktion nicht, dann könnten auch unbedingt richtige Abarbeitungsabläufe wieder rückgaängig gemacht werden, wenn zu einem späteren Zeitpunkt ein völliges Versagen aller Alternativen auftritt. Ohnehin ist aus technischen Gründen die Beseitigung unnötiger (spricht erfolgreicher) Entscheidungspunkte erforderlich; so stellt in MLISP2 [SM73a] natürlich {\tt FLUSH} die Erfogsfunktion dar, obwohl die Autoren die Unnötigkeit einer solchen Funktion beschwören.

 

 

LISP als erweiterbare Sprache

Die einfachste Art der Erweiterbarkeit von LISP besteht in der Neudefinition von Funktionen. An sich ist diese Eigenschaft von LISP nichts Besonderes, und man kann durch Hinzufügen immer neuer Funktionen bzw. Prozeduren auch in ALGOL, PL/I und ähnlichen Sprachen dasselbe erreichen. Dort hat man aber im allgemeinen unangenehme Probleme außer der Prozedurdefinition zu bewältigen. Das Zusammenfügen mu\ssbei weitem nicht einfach sein -- Neucompilierenoder Verbinden der Prozeduren sind Aktionen, die außerhalb des Sprachverarbeitungssystems bewältigt werden müssen. Der Unterschied, der hier gleich zu Anfang betont werden mu\ssliegt in derBequemlichkeit in LISP, die dazu geführt hat, da\ssder Programmiererauch \underline{wirklich} mit Funktionsmengen arbeitet.

Seit Dijkstra sein Konzept der virtuellen Maschinenentwickelte [DA72], ist diese Idee vielfach nachgeahmt worden und ineine Programmiermethodik aufgegangen. Denning [DEN76] gibt eineklare Beschreibung dieser Vorgehensweis: ``Der Begriff der verschachtelten (nested) virtuellen Maschinen wird charakterisiert durch eine Serie abstrakter Maschinen $M_{0}$, $M_{1}$, ... $M_{k}$, in welcher $M_{0}$ die Basismaschine ist (der verfügbare Hardware-Vorat). Assoziiert mit dem Niveau i ($1 \le i \le k$) ist eine Mengevon Instruktionen $I_{i}$, die durch $M_{i}$ ausführbaren Komandos sein sollen; ein Programm für $M_{i}$ ist eine Folge von Instruktionen aus $I_{i}$. Einige der Instruktionen in $I_{i}$ sind implrmentiert als Prozeduren (Programme) in $M_{i-1}$; $P_{i}$ möge diese Menge bezeichnen. Einige der Instruktionen von $M_{i-1}$ können für die Programme, die $M_{i}$ benutzt, unrelevant sein... Man kann an diesen Definitionen verschiedene Feststellungen machen. Zum ersten mu\ssjedeInstruktion eines Programms, das auf $M_{i}$ läuft, unzerteilbar sein bezüglich der Ausführung dieses Programms, obwohl diese Instruktion tatsächlich als Programm auf irgendeiner Maschine implementiert sein kann, die in $M_{i}$ enthalten ist. Zweitens ist implizit in der Definition enthalten, da\ssProgramme, die in $M_{i}$ laufen, in keinerWeise von der Definiton oder Existenz irgendwelcher Niveaus $j$ ($j \le i$) außerhalb vom $M_{i}$ abhängen. Drittens erzeugen diese Definitionen letzten Endes eine partielle Ordnung zwischen den Programmen des Systems, und zwar die Relation, Prozedur-Aufruf: Eingegebenes Programm kann nur Programme aktivieren, für die es Nachfolger ist in der Ordnung... Die Methodologie der verschachtelten virtuellen Maschinen zog zuerst Aufmerksamkeit auf sich beim Entwurf von Betriebssystemen...'' [DEN76][S.199].

Sicher wurde der Begriff virtuelle Maschine zuerst von IBM inZusammenhang mit dem Time-Sharing-System CP/CMS aufgebracht. Was aber die Priorität des zugrundeliegenden Konzepts betrifft, so scheint es ganz interessant, dem Denning-Zitat einige Sätze aus einemalten Artikel über Symbolmanipulationssprachen gegenüberzustellen [GRB61]: ``Der wichtigste Vorteil der Listenverarbeitungssprachen liegtnicht in den Listenspeichern als solchen, noch in der Rekursion, sondern in der Einfachheit, mit welcher immer größere Verarbeitungseinheiten aufgebaut werden können und vom Programmierer als Einheit benutzt werden können. Die Programmierung kann in Ebenen zerteilt werden, so da\ssjedes einzelne Niveau dem Detail sehr wenigAufmerksamkeit widmen muß. Auf jedem Verarbeitungsniveau kann der Programmierer in Begriffen (hier ``units'' -- d. Verf.) denken und schreiben, die für das betreffende Niveau natürlich sind. Es ist schwer, das deutliche Gefühl von Freiheit und Erleichterung mitzuteilen, das man hat, wenn man eine Listenverarbeitungssprache benutzt... ``(edb., S.735),,... Das Listenprogramm ist eine Hierarchie von Unterprogrammen; aufeinanderfolgende Niveaus liefern mehr und mehr Details...``(edb., S. 732).

Da\ssman mit einer Sprache, die es erlaubt, beliebige Mengen vonFunktionen (Unterprogrammen, Prozeduren) zu definieren, sich Gruppen von Funktionen erzeugen kann, die bezüglich bestimmter Datenstrukturen Basisoperationen durchführen, und da\ssman später diese Funktionenbenutzt, ohne sich um ihren inneren Aufbau zu kümmern, ist ein so naheliegendes Verfahren, da\sswir es nicht mehr weiter diskutierenwollen. Nur die extensive Verwendung dieses Konzepts in InterLISP [TE74]bei der Konstruktion des Systems sollte noch erwähnt werden, wo über einem Kern handgeschriebener Basisfunktionen (virtuelle InterLISP Maschine) eine ganze Serie von LISP-Funktionen gelegt wurde. Bei der Generierung eines konkretes Systems werden diese Funktionen compileirt, und der LISP-Nutzer merkt praktisch nicht, ob er es mit Basisfunktionen oder abgeleiteten Funktionen zu tun hat.

Über dieser Basis 1. Stufe sind nun eine ganze Reihe von Subsystemen aufgebaut, deren sich der Nutzer als kompletter Einheiten bedienen kann. Über diesen Subsystemen baut dann der Anwender seine Programmsysteme auf, die, wie etwa die Sprache QLISP [SAC76],selbst wieder Mittel sind, um Anwendungssysteme zu programmieren. Nicht viel anders als InterLISP Anfang der siebziger Jahre sind moderne LISP-Systeme (LeLISP, CommonLISP) oder die LISP-Maschinen realisiert.

LISP bietet neben dieser funktionalen Erweiterung des Sprachkerns die Möglichkeit der syntaktischen Erweiterung [BO64d]. Da dieSystemroutinen für die Ein- und Ausgabe, mit denen der Interpreter selbst arbeitet, auch dem Nutzer zugänglich sind, kann man in LISP Prozessoren für andere Programmiersprachen schreiben. Die typische Anwendung dieser Möglichkeit besteht darin, da\ssman Sprachenimplementiert, die die syntaktische Darstellung von LISP verändern, etwa in Richtung zu ALGOL, aber die semantische Eigenschaften von LISP bewahren. Ein Präprozessor setzt die höhere Sprache in LISP-Ausdrücke um. Normalerweise von LISP nicht unterstützte Aktionen werden durch neue Funktionen ausgeführt. Auf diese Weise kann sich ein Programmierer passende Sprachebenen übereinanderlegen und sich ihrer nach Belieben bedienen.

Bei dieser Überlagerung von Sprachen, die durch Umsetzung in die Basissprache bewerkstelligt wird, ist auch ein heikles Problem nicht ausgeklammert: die semantischen Fehler, Während syntaktische Fehler von Präprozessor erkannt werden, könnten semantische Fehler bei der Verarbeitungsfehler in irgendeiner tieferen Ebene ausgelöst und den Anwender mit Fehlernachrichten konfrontieren, die einem ihm unbekannten Sprachniveau angehören. LISP enthält Möglichkeiten, hier Sperren zum Abfangen solcher Fehler aufzubauen.

Bekannte Verwirklichungen dieses Konzepts der Überlagerung und Erweiterung sind METEOR [BO63a] -- eine Sprache zwischen und derZeichenkettenverarbeitungssprache COMIT [YN62] --, MLISP [SM70]-- eine Sprache zwischen LISP und ALGOL 60, sowie LISP2 [AB66b]und REDUCE [HEA73], die in dieselbe Richtung zielen. Beispielfür eine zweistufige Überlagerung ist die Implementation von Pascal in MLISP2 [SM73a], einem Nachfolger von MLISP.

Zwei neuere Techniken für die syntaktische Erweiterung werden heute angewandt: MacLISP [MOO74] enthält Makrozeichen, die beim Einleseneine Funktion anstoßen. Innerhalb dieser Funktion sind auch Einleseaktionen möglich. Das Resultat der Funktion wird als interne Repräsentation des Makrozeichens benutzt. Der Programmierer kann in MacLISP seine eigene Einleseroutine an die Stelle der Systemfunktion READ stellen. Dadurch kann er systematisch eigene syntaktischeVorstellungen verwirklichen. MacLISP und DOS/ESLISP 1.6 boten zudem die Auswechselbarkeit der Symboltabellen: Der Systemprogrammierer kann unterscheiden zwische Namensgruppen verschiedener Ebene, kann diese voneinander trennen und so wichtige Systemprogramme und Systemgrößen vor dem Überschreiben schützen.