Einführung in die LISP-Programmierung

Einleitung

Welches ist die beste Methode, eine gute Einführung in eine Programmiersprache zu geben? Es scheint ja prinzipiell so zu sein, daß man mit Gewinn nur in Dinge eingeführt werden kann, die man schon in gewissen Grade kennt und praktiziert. So wird hier angenommen, daß der Leser mehr als grundlegende Kenntnisse bezüglich des Programmierens in einer höheren Programmiersprache hat.

Der Zweck des vorliegenden Buches ist es auch nicht, die Einführung in das Programmieren mit LISP durch den naheliegenden Weg der Beispiele zu vollziehen. Es soll vielmehr der Wunsch danach ausgelöst werden, LISP zu lernen. Das wird versucht durch die Darstellung von LISP als Sprache für Menschen (Anwendungsgebiete), die von Menschen erdacht (Begriffswelt, Grundideen) wurde (Geschichte). Da allerdings vieles unverständlich bleiben müßte, ist eine äußerst knappe Darstellung der Umrisse der LISP-Programmierung vorangestellt worden. Noch vor wenigen Jahren hätte eine solche Vorgehenweise mindestens als verantwortungslos bezeichnet werden müssen. Außer C.Weissmans ``LISP Primer'' [WEIS67] mußte immer noch J.McCarthys Manual [MCC62c] alsLehrmaterial benutzt werden. Die dann erschienenen Bücher von D.Friedman[FRI74] und W.Maurer [MAU73] haben die Lücke nicht gefüllt.

Doch in den letzten Jahren ist eine bemerkenswerte Verbesserung der Situation zu verzeichnen. Mit dem wachsenden Interesse an LISP sind auch die erforderlichen Lehrbücher erschienen, etwa [STO76],P.Winston [WINS77] und J.Allen [ALL78] zeichnen sich dadurch aus,daß sie LISP in den Kontext der interessierenden Probleme und Lösungsansätze im Wissenschaftsbereich der ``Künstlichen Intelligenz'' stellen. Inzwischen kann man von einer ganzen Flut solcher Lehrbücher sprechen.

 

Terme

LISP unterscheidet sich schon im äußeren Bild wesentlich von den meisten Programmiersprachen. Der rigorose Verzicht auf den sogenannten syntaktischen Zucker, der von der Verwandtschaft zu älteren Funktionenkalkülen der mathematischen Logik herrührt, und die damit gegebene einfache, übersichtliche, ja sogar arme syntaktische Struktur sind die Hauptkennzeichen dieser Singularität.

Will man jemanden, der schon mit anderen Programmiersprachen vertraut ist, die LISP-Programmierung besonders schnell und an Gewohnheiten anknüpfend nahebringen, so kann man die Arbeit mit LISP als Arbeit mit einer beliebigen höheren Programmiersprache vergleichen, die nur über eine große Menge von Standardfunktionen verfügt und keine Anweisungen (sei es zu Zuweisungs- oder Kontrollzwecken) oder arithmetische Formelausdrücke enthält. Die mit Hilfe dieser Sprachelemente sonst bewirkten Dienste verwirklichen in LISP spezielle Funktionen.

Diese Erklärung trifft die Sache nicht ganz, weil LISP zum guten Teil eine funktions-basierte Sprache ist. Im reinen Funktionenkalkül sind eigentlich gewisse solche Dienste (wie Zuweisungen) völlig unnötig (also auch in einer Funktionssprache, wie E.Dijkstra bemerkt [DI76]) --LISP brauchte also keine Sprachelemente zu ihrer Realisierung enthalten. Wenn entsprechende Ausdrucksmittel dennoch vorhanden sind, dann liegt das an der Gewöhnung der Programmierer von 1958 an ``Zuweisungsaktionen''. LISP stellt ein Gemisch dar aus einer anweisungs- und einer funktions-basierten Sprache. Man könnte so tun, als ob die anweisungs-basierten Elemente nicht existierten, weil sie ein schönes theoretisches Bild stören. Es scheint aber verfehlt, Eigenheiten einer Programmiersprache als zufällig bzw. ``nur der Effizienz zuliebe aufgenommen'' zu bezeichnen, die in ihrer großen Anzahl oder wesentlichen Benutzungsfrequenz unzweifelhaft das Äußere bestimmen. Eine Programmiersprache muß auch noch immer, trotz vielfach geäußertem Zweifel, das Schreiben effizienter Programme ermöglichen.

Die Notation der Funktionsaufrufe bzw. der Funktionsausdrücke oder Terme (engl. forms) hat LISP wesentlich von seinem logischen Vorbild,dem $\lambda$-Kalkül von A.Church [CH41] übernommen: ImUnterschied zur üblichen Schreibweise der Mathematiker und der Programmierer in anderen Programmiersprachen wird die die Argumente umgebende Klammer schon vor dem Funktionsnamen geschrieben: Statt abs(x)notiert man (abs x).

Damit könnte mit einigem Recht der Programmierkurs für LISP, gedacht für erfahrene Programmierer (vgl. die Verfahrensweise von L.Siklossy [SIK76]) beendet werden: Der interessierte Nutzerbenötigt nur noch ein LISP-Handbuch (etwa [STO78] oder [STE83]), in dem er dieverfügbaren Standardfunktionen nachschlägt. Damit hat er das Wissen, die erforderlichen Funktionsausdrücke zu formulieren, die durch die verschachtelte Ineinanderfügung von Funktionsausdrücken für Argumente entstehen und ihm die erwünschten Ergebnisse liefern.

Freilich sind damit noch keine Programme aufgestellt, die sich durch die oftmalige Verwendbarkeit für unterschiedliche Dateneingabe auszeichnen.\footnote{Außerdem wird so nur die anweisungs-orientierte Programmierunggetrieben. LISP-Programmierung ist aber typischerweise funktions-orientiert, und dieser Schritt fordert gerade vom erfahrenen Programmierereinen erheblichen Umdenkprozeß.} Der einfache Schritt dazu wird in LISP durch die Eröffnung der Möglichkeit zur Selbstdefinition von Funktionen auf der Basis der verschachtelten Funktionsausdrücke und der zusätzlichen Deklaration und Verwendung von Variablen vollzogen.

Wie aus dem bisher Dargelegten leicht zu schließen, gibt es auch dafür gewisse Standardfunktionen, die als Argument in dieser oder jener Form Funktionsnamen, Variable (formale Parameter) und Funktionsausdruck akzeptieren und eine über den Namen aufrufbare Funktionen bilden. Typisch ist etwa die Funktion DE, die gerade drei Argumente in dieserReihenfolge hat. Als Beispiel folgt die Definition einer Funktion TANGENS aus den (hier vorgegebenen) Grundfunktionen QUOTIENT, SINUS und COSINUS:

(DE TANGENS (X) (QUOTIENT (SINUS X)(COSINUS X)))

Man kann sich leicht vorstellen, daß man mit geeignet gewählten Funktionen die Menge der Grundfunktionen entscheidend vergrößern kann. Dabei gibt es Qualitätsunterschiede zwischen ganzen Funktionsebenen. Haben Funktionen wie TANGENS und SINUS noch etwa die gleiche Kompliziertheit und Abstraktionsstufe, so wäre mit einer neu definierten Funktion (bzw. Funktionsmenge) zur Fourier-Analyse offenbarein höheres Niveau erreicht. Ähnlich könnte man sich höhere Funktionsmengen zur Lösung von Gleichungen, zur Integration uzw. vorstellen.

Nun sind solche Gesamtheiten von Funktionen immer nur soweit interessant und logisch vollständig, inwieweit sie übliche Grundaktionen oder oft benutzte Basishandlungen über Klassen von Objekten enthalten. Da die Objekte dem LISP-Programm in irgendeiner Form als Daten oder Datenaggregate übergeben werden, kommen wir (indem wir die Frage nach den möglichen Datenarten und ihrer Beschreibung durch Anknüpfung an die jedem Leser geläufige Datenart der Zahlen bisher überspielt haben) damit zu den von LISP unterstützten Datenstrukturen.

 

Datenstrukturen

Der LISP-Programmierer beschreibt normalerweise seine Datenstrukturen nicht strukturell, er fordert auch keinen Speicherplatz an über eine Deklaration und assoziiert zu seinen Variablen keine Datentypen.

Bei anderen Programmiersprachen muß man diese Aktionen ausführen, damit für jede Variable des Typs Speicherplatz bereitgestellt wird und damit die richtigen Operationen zum Zugriff und zur Verarbeitung ausgewählt werden.

Das eine kann unterbleiben, da der gesamte Speicher dynamisch verwaltet wird (heap,Halde). Die Variablen sind auch nicht als Adressen von Plätzen anzusehen, in denen Werte des Typs untergebracht werden, sondern als Namen von -- immer schon existierenden -- Datenobjekten.

Strukturdeklarationen sind nicht sehr sinnvoll, wenn mit ihnen die innere Struktur von Daten über Selektoren transparent wird. In Wahrheit wird der Typ eines Datums nicht so sehr von der Belegung des Speichers bestimmt -- die sich ohnehin mit jeder Programmversion ändert -- als vielmehr von den Operationen, die man auf das Datum anwenden will. In der untersten Ebene sind dies Konstruktions-, Selektions-, Modifikations- und Vergleichsoperationen. Der LISP-Programmierer hat diese vom Datentyp abhängigen Funktionen selbst auszuwählen. Indem er mit einer solchen Funktion ein Datum konstruiert, selektiert oder modifiziert, deklariert der Programmierer gewissermaßen implizit. Dennoch gibt es sicher Situationen, in denen der Datentyp eines Objektes, das durch einen Term berechnet wird, nicht voraussagbar ist. Die Sicherheit der Programme könnte wahrscheinlich erhöht werden, wenn die Typen aller Ausdrücke streng festliegen würden.

Diesen Weg ist McCarthy nicht mit LISP gegangen. Ein wesentlicher Grund dürftein der Unbequemlichkeit liegen, die die Deklarationen für die Dialogarbeit bedeuten würden. Ein Ersatz kann darin gesehen werden, daß die Typen der Datenobjekte zur Laufzeit prüfbar sind. Ein Programm, das in eine Umgebung eingebaut wird, in der die Parameterübergabe durch unkontrollierbare Einflüsse (Nutzereingabe) gestört sein kann, wird die Richtigkeit des gelieferten Datentyps immer zu prüfen haben. Die Kommunikation der Funktionen in einem fertigen Programmsystem wird meist völlig ohne Typprüfung ablaufen.

Die verfügbaren Datenstrukturen lassen sich in zwei Klassen einteilen -- die der einfachen (in LISP: ``atomaren'') Objekte und der zusammengesetzten Strukturen. Obwohl die atomaren Objekte nicht ohne innere Struktur sind (eine Real-Zahl besteht aus Mantisse und Exponent, eine Zeichenkette aus einzelnen Zeichnen), beruht die Einteilung darauf, daß die einfachen Datenstrukturen keine Teilstrukturen haben, die selbst LISP-Datenstrukturen sind.

Wie aus den obigen Beispielen ersichtlich, gehören Zahlen zu deneinfachen (atomaren) Datenstrukturen. Jede einigermaßen fortgeschrittene LISP-Implementierung ermöglicht ganze Zahlen (integer) und Dezimalzahlen (in LISP nur als Gleitkommazahlen realisiert); besonders weitentwickelte Systeme, wie etwa MACLISP, die für numerische Verwendung ausgelegt sind, bieten sogar ganze Zahlen beliebiger Größe und Gleitkommazahlen mit beliebig genauer Mantisse und beliebig großen Exponenten an. Die anwendbaren Operationen umfassen natürlich keine Selektions- und Modifikationsoperationen, sondern nur Konstruktionsoperationen: die üblichen Verknüpfungen von Zahlen und typische Zahlenfunktionen (SIN, LOG usw.).

In den modernen LISP-Systemen gehören Zeichenketten zu den atomarenDatenstrukturen. Dies sind Folgen von Zeichen, aber nicht von Zeichenobjekten, die als primitive Daten manipulierbar wären. Es gibt normalerweise etwa folgende Verarbeitungsfunktionen für Zeichenketten: Konstruktion aus Zeichen bzw. Teilzeichenketten, Selektion von Zeichen oder Teilzeichenketten, Modifikation entsprechender Teile, Vergleich von Zeichenketten auf Gleichheit oder lexikalische Ordnung sowie Konvertierung in Listen von Zeichen. Die Zeichenketten werden jedoch für die meisten Aufgaben, zu deren Lösung man sie in anderen Programiersprachen einsetzt, überhaupt nicht benötigt. Manchmal arbeitet man mit Folgen von Zahlen, die dem internen Code entsprechen. Eigentliche Ursache für die Nichtverwendung der Zeichenketten zu Zeichenkettenmanipulationsaufgaben ist das Vorhandensein einer ganz besonderen, LISP eigentümlichen Datenart: des Atomsymbols (`literales Atom' oder oft auch kurz `Atom' genannt). Atomsymbole werden in LISP-Funktionen -- wie schon gesagt -- statt Zeichenketten benutzt; darüber hinaus aber auch für Aufgaben verwendet, für die in anderen Programmiersprachen Identifier bzw. Bezeichnungen benutzt werden: Sie dienen als Variablen, Sprungmarken und Funktionsnamen. Das bedeutet, daß mit einem Atomsymbol ein Name verknüpft ist.

Die Namen der Atome genügen in etwa den Regeln, die für die Bezeichner in ALGOL60 gelten. Allerdings hat die Einbettung in LISP dazu geführt, daß man auch Namen bilden möchte, die diesen Regeln nicht genügen. Die Besonderheit von LISP besteht darin, daß die Namen als nichtnumerische Daten während der Programmabarbeitung verfügbar sind. Werden über die normale Systemeingabe weitere Atomsymbole eingelesen, so werden sie mit den schon benutzten in Beziehung gesetzt. Ergebnis ist, daß jedes Atomsymbol (normalerweise) rechnerintern nur einmal vorkommt: Ein Datum kann also sehr eng mit einer im Programm benutzten Sprungmarke verbunden werden!

Werden Atomsymbole als Daten verarbeitet, so ist nur ihr Name interessant. Dienen sie als Variable, so benötigt man vor allem den ihnen zugeordneten Wert -- nur im Fehlerfall ist es für den Programmierer wichtig, Namen und Wert gemeinsam zu kennen. Schließlich kann man mit einem Atom auch eine ganze Folge von Eigenschaften (Werten) assoziieren -- ähnlich wie in PL/I oder ALGOL68 in den Strukturen. Diese speziellen LISP-Strukturen (``Eigenschaftslisten'' genannt) sind aber wieder dynamisch organisiert, so daß Deklaration und Beschreibung unterbleiben können und beliebiges Wachstum gesichert ist.

Die Klasse der zusammengesetzten (nicht atomaren) Datenstrukturen besteht aus Vektoren bzw. Feldern (arrays) und Listenstrukturen.Felder sind in jedem guten LISP-System implementiert. Üblicherweise gibt es keinerlei Dimensionsbeschränkungen. Die Indizes beginnen aber meist mit 0 oder 1. Nur wenn sich der Programmierer selbst Zugriffsfunktionen schafft, kann er zu Indizierungen übergehen, die von dieser Norm abweichen. Die Feldelemente müssen nicht notwendig alle vom gleichen Typ sein. Wenn der Nutzer die Bürde des Typprüfens auf sich nimmt, kann er neben Zahlen auch Felder und Listen in einem Feld unterbringen. Zur Arbeit mit Feldern stehen Konstruktionsfunktionen\footnote{In den alten Implementationen nahmen Felder in LISP insofern eine Sonderstellung ein, als sie meist mit einem Atomsymbol, dem Feldnamen, assoziiert waren. Während Zahlen, Zeichenketten, und Listen erzeugt werden können, ohne daß sie über ein Atom erreichbar sind, dessen Wert sie sind (im Ablauf der Abarbeitung verschachtelter Ausdrücke), blieb das Feld an das Atomsymbol, das seinen Namen darstellt, gekoppelt. Es gab also keine von Atomsymbolen unabhängige Konstruktionsfunktion.}, Selektionsfunktionen zum Zugriff auf Feldelemente, Modifikationsfunktionen zur Änderung derselben und Konvertierungsfunktionen von Feldern in Listen zur Verfügung.

Die für LISP (list processing language) wichtigsten Datenstrukturen sind die Listen. Auf den kleinsten Bestandteil, das gepunktete Paar(oder Cons [M0074]) bezogen, stellen sich Listen dar als Folgen vonsolchen Paaren. In LISP ist es üblich, nur solchen Listenstrukturen den Namen ``Liste'' zu geben, die in einer bestimmten Weise linear sind (linear zu Ende gehen). Die übrigen allgemeineren Strukturen, welche beliebige Baumstrukturen darstellbar machen, nennt man ``S-Ausdrücke'' (symbolische Ausdrücke). Als Paar besteht das Cons aus zwei Teilen, dem Car und dem Cdr. Jeder dieser Teile kann selbst ein Cons oder einbeliebiges Atom sein (alle Namen sind von den betreffenden Selektionsfunktionen abgeleitet). Listenstrukturen sind universell anwendbar, weil sich mit ihnen praktisch alle Halbordnungsrelationen darstellen lassen.

Listen werden geschrieben, indem man die geordneten oder zufällig hintereinander angeordneten Listenelemente (selbst Listen oder andere Datenstrukturen) in runde Klammern einschließt; Unterordnung kann durch tiefere Listenklammerung zum Ausdruck gebracht werden. Typisches Beispiel für Listenstrukturen sind die Daten für ein Verarbeitungssystem mathematischer Formeln, die arithmetischen Ausdrücke:

   ((A+B)*(C-(2/(E+F+G)))).

Als Listenverarbeitungssprache stellt LISP eine genügende Zahl an Basisfunktionen für den Aufbau von Listen, den Zugriff zu Listen, die Modifikation von Listenkomponenten, den Vergleich von Listen, usw. zur Verfügung.

In vielen Einführungen in die LISP-Programmierung wird vor der Modifikation von Paaren gewarnt. Es besteht aber kein prinzipieller Unterschied in der Änderung von Zeichenketten, Feldern oder Listen. Grund der Forderung entsprechender Vorsicht ist, daß viele Beispiele reiner funktions-orientierter Programmierung mit Listen arbeiten. Funktions-orientierte Programmierung kennt aber keine sich ändernden Objekte -- Daten werden auf neue Daten abgebildet. Will man rein funktions-orientiert programmieren, sollte man die Verwendung von Modifikationsfunktionen unterlassen. Programmiert man objekt-orientiert, sieht man die Daten als sich ändernde Objekte mit Individualität -- und diese Sicht ist ganz natürlich in LISP -- dann haben die Modifikationsfunktionen eine natürliche Aufgabe.

Für die Möglichkeiten von LISP besonders folgenreich ist die Tatsache, daß auch die Programme (Funktionen) als Gebirge funktionaler Ausdrücke in Listenschreibweise notiert werden. Damit kann ein solches Programm regelrecht als Liste angesehen werden, d.h. als Datenstruktur. Die Variablen die in der betreffenden Funktion auftauchen, und die Funktionsnamen sind dann nichts anderes als Daten. Daher ist es leicht möglich, LISP-Programme in LISP zu analysieren, zu zerlegen und zu konstruieren. Der Gipfel der Anwendungsvarianten ist damit erreicht, daß ein so erzeugtes Programm sofort laufen kann! Ursache dafür ist, daß LISP die Programme nicht nur in Maschinensprache umsetzt und so abarbeitet, sondern sie zunächst als Listenstrukturen abspeichert und diese interpretiert.

 

Auswertung und Interpretation

Ohne Zweifel muß sich der LISP-Novize erst an die Datenstrukturen und an den Umgang mit ihnen gewöhnen. Hat man einige komplexere Beispielprogramme (oder, wie man in LISP sagt, ``Beispielfunktionen'') geschrieben und beherrscht die Syntax der Sprache einigermaßen (die Klammerstrukturen können sehr tückisch sein), dann kann man einige Konzequenzen ins Auge fassen, die bisher unbetont geblieben sind.

Da die Funktionsausdrücke (Terme) von LISP den Funktionsaufrufen in anderen Programmiersprachen entsprechen, bedeutet dies (Funktionen liefern immer Werte), daß jede Aktion in LISP von einem Sprachelement ausgelöst wird, das einen Wert hat. Eine Sprache die diese Eigenschaft hat, heißt ``Ausdruckssprache''.

Weil die Aktivierung eines wie auch immer gearteten LISP-Programms mit Hilfe eines Funktionsausdrucks geschieht, liegt auch nach dieser Aktivierung ein Wert vor. Zwar kann es sein, daß dieser Wert unwichtig ist und nur ad hoc gegeben wird, doch sollte man die Möglichkeit nie aus den Augen lassen, daß die heute umfassendsten Funktionen morgen in ein neues Funktionssystem eingebunden werden können. Man sollte sich der Werte bedienen und alle Funktionen bewußt so anlegen, daß ihr Resultat als dieser Wert übergeben wird und nicht als sogenannter Seiteneffekt.

Wie in anderen Programmiersprachen lesen die LISP-Programme möglicherweise benötigte Daten ein und geben Ergebnisse aus. Genauso wie die Ergebnisausgabe normalerweise über den Ausdruck-Wert-Mechanismus vollzugen wird, geschieht die Dateneingabe selten über regelrechte Eingabe-Transfers von der aufgerufenen Funktion aus. Im Normalfall verarbeitet ein LISP-Programm Daten in der Form von LISP-Datenstrukturen, die als Parameter (Argumente) übernommen wurden. Diese Daten (im allgemeinen Listen) werden über dasselbe Eingabeprogramm in die interne Repräsentation umgewandelt wie die Programme. Das bedeutet, daß ein größer Teil des Sprachverarbeitungssystems für LISP ständig präsent ist und daß (für das System) kein wesentlicher Unterschied zwischen Programmeingabe (Funktionsdefinition) und Programmlauf besteht -- beides erfolgt in Termen und beides wird bei der Aktivierung mit einem Wert beantwortet.

Es war schon darauf hingewiesen worden, daß die Terme die Form von Listen haben. Wird ein solcher Ausdruck eingegeben, so wird er in die interne Datenstrukturform gebracht und dann analysiert: Die gemeinte Funktion wird ermittelt und der Funktionsaufruf mit der Übergabe der Argumente (die die eigentlichen Daten darstellen und nun schon eingelesen sind) bewerkstelligt. Man kann so durchaus davon sprechen, daß die Funktionsausdrücke der höchsten Ebene ``interpretiert'' werden.

Eine Besonderheit von LISP besteht nun darin, diese Behandlungsweise der umfassenden Funktionsausdrücke auf alle Unterausdrücke auszudehnen. Mit gewissem Recht kann man nämlich sagen, daß die Compilierung (d.h.die Umsetzung der Funktionen in lineare Folgen von Maschinenbefehlen) in LISP eine Ausnahme ist und die direkte Interpretation der in ihrer internen Datenstrukturform aufgebauten Funktionen die Regel. Diese Vorgehensweise hat Vorzüge und Nachteile: Ganz sicher dauert die Verarbeitung wesentlich länger, wenn man interpretiert (typisch etwa mit dem Faktor 4 bis 10). Jedoch kann ein Programm, das selbst als Datenstruktur vorliegt, wesentlich besser verarbeitet werden als eine lineare Befehlsfolge: Der Service zur Fehlerbehandlung kann erhöht werden, die Programme können leichter berichtigt werden (unmittelbar nach dem Lauf im Dialog), und sie können vor, nach und sogar während ihres Laufs verarbeitet werden. Im Extremfall könnte ein laufendes Programm sich selbst analysieren und verändern.

Abgesehen davon bringt auch die Darstellung der Funktionen als Datenstrukturen erheblichen Gewinn: Unterschiedslos können in größere Datenvorräte sowohl die reinen Daten als auch Zugriffs- und Verarbeitungsfunktionen untergebracht werden!

Man sieht, daß die Interpretation ihre Vor- und Nachteile hat und die positive Seite nicht unterschätzt werden darf (siehe Abschnitt 3.7). Die Interpretation der Funktionsausdrücke bewirkt, daß der LISP-Programmierer sich in einem ständigem Dialog befindet: Er liefert einen Funktionsausdruck (gewissermaßen Programmname und Daten) und bekommt dafür einen Wert, und anschließend übergibt er einen neuen Funktionsausdruck und erhält den zugehörigen neuen Wert usw. usf., bis er mit der Arbeit aufhört.

Ein LISP-System ist also von vornherein ein Dialogsystem!

 

 

Programmierstile -- rekursive Programmierung

Benutzt ein Programmierer die Ausdrucksmittel seiner Sprache in angemessener, harmonischer Weise und gelangt er auf diese Art zu Programmen, die hohen Anforderungen der Effizienz genügen, so ist es üblich, von einem ``guten Programmierstil'' zu sprechen [WEIN70, KER74, STR72].

Wichtige Kennzeichen eines guten Stils sind Einfachheit, Verständlichkeit, Verwendung sicherer, gefahrloser Mittel (Gefahren sind oft durch allzugroße Maschinen- und Implementationsabhängigkeiten gegeben) und Befolgung der Regeln der strukturierten Programmierung wenigstens der Tendenz nach [BAT76a, DA72].

Während ein Teil dieser Grundsätze bzw. Kennzeichen eines guten Programmierstils für fast alle Programmiersprachen gültig ist, kann z.B. die Frage nach der Angemessenheit verwendeter Ausdrucksmittel schwer beantwortet werden und bleibt oft dem persönlichen Geschmack des einzelnen Programmierers überlassen. Hier zeigt sich dann die ``gute Schule'' genauso wie bei Schülern eines Meisters der bildenden Kunst oder der Architektur.

Ausgewählte Sprachelemente können sicher als angemessen gelten, wenn sie zu einem einfachen und einigermaßen effizienten Programm führen (und wenn man ``die gleiche Sache nicht einfacher machen kann''). Das Einfachheitskriterium aber wird bestimmt durch das Problem, d.h. die beabsichtigte Transformation der gegebenen Datenstruktur. Sicher ist nun auch wieder die Wahl der Datenstruktur eine Stilfrage und hängt wesentlich von der Fähigkeit des Programmierers ab, Datenstruktur und verarbeitendes Programm so aufeinander abzustimmen, daß ein Optimum erreicht wird.

Stilfragen sind nicht leicht zu behandeln -- alle Versuche erfahrener Programmierer, allgemeingültige Verfahrensregeln bzw. Geschmacksvorschriften einzuführen, haben bisher nicht die Gefahr der Überbeanspruchung von Allgemeinplätzen vermieden. Man muß sich beim gegenwärtigen Kenntnisstand damit abfinden, daß es sich um explizit nicht lehrbare Gegenstände handelt, die aber implizit, in Beispielen, wohl mit vermittelt werden. Das Studieren vieler Beispiele von Programmen erfahrener Programmierer führt meist nebenher zur Übernahme einzelner guter Elemente ihres Stils.

Die Programmiersprache mit ihren Mitteln zur Beschreibung von Daten und Programmstrukturen beeinflußt sicher stark den beobachteten Programmierstil. Der LISP-Programmierer steht normalerweise vor der Aufgabe, Verarbeitungsprogramme für nichtnumerische Daten aufzustellen, die intern in der Form von Listenstrukturen dargestellt sind. Das heißt, die Strukturen sind Bäume, bei denen jeder Teilbaum eine vergleichbare Komplexität haben kann wie der gesamte Baum. Mit anderen Worten, oft liegen rekursive Datenstrukturen vor [HOA73]. Typisches Beispiel sind die arithmetischen Ausdrücke: JederOperand eines der arithmetischen Operatoren kann selbst ein komplizierter arithmetischer Ausdruck sein:

\vspace{3mm}

 

A1: a+b
A2: (a+b)+b
A3: (a+b)+(a+b)
A4: ((a+(a+b))+b)+(a+b).

\vspace{3mm}

Bei der Verarbeitung solcher Daten sind rekursive Programme die angemessene Lösung, wenn eine Operation auf alle arithmetischen Operanden angewandt werden soll.

Es ist jedoch bekannt, daß rekursive Programme auch dann sinnvoll angewendet werden können, wenn die Daten selbst nicht rekursiv sind. D.Barron [BARR67] erwähnt hier Aufgaben, bei denen das zuprogrammierende Verfahren als Rekurrenzrelation oder rekursive Definition vorliegt oder wenn ein Verfahren zur Lösung einer Teilaufgabe ein umfassendes Verfahren rekursiv benutzt.

Listen werden häufig nur in ihrer ``Hauptebene'' verarbeitet, d.h., sie werden als sequentielle Folgen von Elementen betrachtet. In diesen Fällen stellt sich jedesmal die Frage neu, ob man iterativ oder rekursiv programmieren will [BL64].

Soll z.B. die Länge einer Liste berechnet werden, so bietet sich jedem etwas erfahrenen Programmierer sofort eine iterative Lösung an:

\vspace{5mm}

ALGOL mit Listen:   LISP:

{\tt

INTEGER PROCEDURE LENGTH (L);        (DE LENGTH(L)
  LIST L;
  BEGIN INTEGER N;        (PROG (N)
    N:=0;        (SETQ N 0)
   ZYKL:        ZYKL
    IF L$\neq$NIL        (COND (L
     THEN BEGIN
      L:=REST(L);       (SETQ L (CDR L))
      N:=N+1;           (SETQ N (ADD1 N))
      GOTO ZYKL END;       (GO ZYKL)))
    LENGTH:=N; END;        (RETURN N)))

}

\vspace{5mm}

Hier wird die Liste so lange abgearbeitet, bis das Ende erreicht ist. Für jedes Element wird der Längenzähler um 1 erhöht, der Maßstab wird also gewissermaßen Schritt für Schritt nach rechts verschoben.

Genausogut aber läßt sich folgende Überlegung in ein Programm umsetzen: Wenn die Liste leer ist, kann man die Länge unmittelbar mit 0 angeben. In allen anderen Fällen berechnen wir die Länge des Listenrests (Liste ohne erstes Element) und addieren 1: {\tt

INTEGER PROCEDURURE LENGTH (L);   	(DE LENGTH(L)
LIST L;						
IF L $\neq$ NIL     (COND \=(L\=
  THEN LENGTH:=1+LENGTH(REST(L))       (ADD1 (LENGTH (CDR L)
       )))
  ELSE LENGTH:=0;                     (T 0)))

}Dem Programmierer vom rechten Schrot und Korn wird diese Lösung sehr unsinnig vorkommen; sicher läuft das Programm nicht ganz so schnell wie das iterative. Aber die Hauptursache für sein Unbehagen liegt nicht so sehr in dieser kleinen Zeitdifferenz, sondern in seiner Gewöhnung, sequentiell und iterativ zu denken, die durch die Programmierung in einer Assemblersprache bedingt ist. Der Programmierer denkt gewissermaßen zu früh an das Programm.

Dem Mathematiker ist eine derartige Vorgehensweise nicht neu: Sehr oft beweist er ein Theorem dadurch, daß er Fälle abspaltet, die schon bewiesene Teilaussagen sind, und bei induktiven Beweisen wird für einfache Teilaussagen regelmäßig angenommen, sie seien schon bewiesen. Er denkt mehr an das Problem und an die Ökonomie, es im Kopf zu beherrschen. Wie es der Rechner beherrscht, interessiert ihn nur in zweiter Linie.

Der Unterschied zwischen der Denkweise, die den sequentiell arbeitenden Rechner und die Laufzeit des Programms in den Mittelpunkt stellt, und derjenigen, die die Problembeschreibung und die Denkökonomie bei der Abfassung des Programms betont, scheint in der Tat ein wesentlicher Stilunterschied zu sein.

Immerhin ist das Längenmeßproblem so einfach, daß die rekursive Lösung fast erzwungen erscheint. Dennoch kommt in der deutlichen Einfachheit der Wegfall technischer Rechenschritte zum Ausdruck. Man beachte dies bei folgendem komplizierteren Beispiel:

Eine Liste ist umzukehren. Die übliche LISP-Lösung ist:

   (DE REVERSE (L)
     (COND ((NULL L) NIL)
           (T (APPEND (REVERSE (CDR L)) (LIST (CAR X)))))).

Ist die Liste leer, so brauchen wir nicht umzukehren. Sonst trennen wir das erste Element ab, drehen die Restliste um und hängen das erste Element hinten an die Liste. Diese letzte Aufgabe kann ohne Modifikationsfunktionen -- und die passen, wie schon gesagt, nicht in die funktions-orientierte Programmierung -- nur durch das Zusammenhängen zweier Listen erreicht werden; sie wird deshalb notwendig recht aufwendig sein.

Eine mögliche iterative Lösung wäre:

   (DE REVERSEIT(L)
     (PROG(X)
       ZYK (COND ((NULL L) (RETURN X)))
           (SETQ X (CONS (CAR L) X))
           (SETQ L (CDR L))
           (GO ZYK) )).

Die Liste wird schrittweise abgearbeitet, und die jeweils anliegenden Elemente werden der Reihe nach in die Liste der umgekehrten Elemente gestellt.

Obgleich auch hier die iterative Lösung Details (die Zuweisungen) enthält, die mit der Problemstellung an sich nichts zu tun haben, scheint doch die Grundidee wesentlich natürlicher zu sein: Die einfache Konstruktion der umgekehrten Listen aus den nach und nach abgebauten Listenelementen der Ausgangsliste spricht für sich. Die APPEND-Operation in der rekursiven Lösung ist recht gekünstelt. Danun unnatürliche Behandlung und rekursive Funktion zusammenkommen, schneidet das rekursive Programm wesentlich schlechter in einem Laufzeitvergleich ab als die iterative. Folgende Resultate für das Umdrehen einer Liste mit 100 Elementen (Messungen im DOS/ES LISP 1.6 auf R40) dienen als Beispiel:

\vspace{5mm}

 

Funktion interpretiert compiliert
REVERSE 84 ms 54 ms
REVERSEIT 42 ms 6 ms

\vspace{5mm}

Wenn es eine schlechte rekursive Lösung gibt, muß damit nicht jede rekursive Lösung schlecht sein. Der natürliche Aufbauprozeß für die umgedrehte Liste läßt sich mit einer rekursiven Hilfsfunktion leicht nachvollziehen:

	     (DE REVERSE1 (L) (REVERSE2 L NIL))
    (DE REVERSE2(L E) 
      (COND ((NULL L) E)
            (T (REVERSE2 (CDR L) (CONS (CAR L) E)) ))).

Es zeigt sich nun, daß diese rekursive Hilfsfunktion ganz erstaunliche Zeitresultate liefert:

\vspace{5mm}

 

Funktion interpretiert compiliert
REVERSE1    
  31 ms 6 ms
REVERSE2  

\vspace{5mm}

Ergebnis ist also, daß auch rekursive Programme effizient sein können, wenn sie nur auf einem natürlichen und guten Lösungsansatz aufbauen.

Will man ein Programm zur Transformation einer rekursiven Datenstruktur aufstellen, so sollte man sich zunächst immer die Behandlung der einfachsten Fälle überlegen. Unter diesen nimmt die ``leere'' Datenstruktur (oft tritt diese nur auf, wenn das Ende erreicht ist) einen besonderen Platz ein; aber auch gewisse kleinste Elemente, die selber andere Teilstrukturen besitzen, gehören dazu. Beispiele dafür sind die Atome in Listenstrukturen oder Zahlen und Variablen in arithmetischen Ausdrücken.

Die Bewältigung dieser Fälle ist oft einfach -- sie ist programmtechnisch aber ungemein wichtig: Damit wird der Abbruch des rekursiven Programms gesichert.

Danach sollte man alle strukturellen Sonderfälle ins Auge fassen. Oft können sie mit einfachen zusätzlichen Schritten auf die einfachsten Fälle zurückgeführt werden (d.h. rekursiver Aufruf), manchmal erfordern gerade sie die die intensivste Überlegung. In einem einigermaßen komplizierten Programm werden hier die häufigsten Fehler vorkommen -- immer vergißt man Sonderfälle oder man schätzt ihre Spezifik nicht korrekt ab.

In der Regel gibt es zum Schluß den ``allgemeinen Fall''. Dieser kündigt sich in der Formulierungsweise ``und sonst ...'' an. Normalerweise kommt hier die Rekursivität der Datenstruktur vollständig zum Ausdruck. Es kann aber auch sein, daß durch vollständige Zerlegung der möglichen Fälle in Sonderfälle zum Schluß nur eine möglicherweise falsch aufgebaute Datenstruktur übrigbleiben kann.

Noch weiter von der konventionelle Programmierung entfernt man sich, wenn man im ersten Schritt Eigenschaften der Transformation durch Gleichungen beschreibt. Die linken Seiten dieser Gleichungen sollten durch Terme dargestellt werden, in der die Transformation mit verschiedenen Argumenten (die Klassen von echten Argumenten beschreiben) auftritt. Den Gleichungen können auch Nebenbedingungen zugeordnet werden.

Im zweiten Schritt muß man diese Gleichungen ordnen, wobei einfache Gleichungen an den Anfang und komplexere an das Ende geschoben werden. Insbesondere sollte die erste Gleichung eine sein, in der die Transformation nur konstante Argumente hat und auf der rechten Seite die Transformation nicht erneut auftritt.

Im dritten Schritt dann werden die Terme links der Gleichungen entfernt und die speziellen Argumente durch zusätzliche Nebenbedingungen ausgedrückt. Die für eine Gleichungen geforderten Nebenbedingungen werden auf die linke Seite geschrieben und das Gleichheitszeichen in einen Pfeil geändert.

Auf diese Art erhält man die Komponenten eines bedingten Ausdrucks, aus dem sich leicht eine Funktionsdefinition ableiten läßt.

 

Steuerung durch die Daten

Normalerweise stellt man sich die Struktur eines aus Funktionen (Prozeduren) bestehenden Programmsystems so vor, daß eine Funktion andere aufruft, diese wiederum weitere usw. usf., um gewisse Teilschritte zu erledigen. Dabei ist die Aufrufstruktur (Unterordnungsstruktur) festgelegt: Man könnte ein Programm (in LISP: PRINTSTRUCTURE) schreiben, das einen Graphen der konkretenAbhängigkeiten über die Aufrufe konstruiert.

Es gibt Situationen bei der Programmierung, in denen man bezüglich strukturell völlig verschiedener Daten konzeptionell gleiche Operationen durchzuführen hat. In konventioneller Herangehensweise testet man die verschiedenen Datentypen (schon das kann ein ernstes Problem sein in einer Programmiersprache, in der man zur Laufzeit nicht zu den Typen zugreifen kann) und führt dann verschiedene Manipulationen durch. Auf diese Weise wird die Verständlichkeit des Programms stark beeinträchtigt.

Beispielsweise seien in einem Programm Vektoren als Datenstrukturen vorgesehen. Es gäbe aber zwei prinzipiell verschiedene Typen von Vektoren, nämlich solche mit fester Länge und solche, deren Länge sich mit der Zeit ändern kann. Während man die erste Art als regelrechte Felder vereinbaren kann, hat man für die zweite Art in LISP nur die Möglichkeit, Listen zu verwenden\footnote{Die in CommonLISP gegebenen Möglichkeit, generische Sequenzen einzusetzen, ist eine gute Lösung für den speziellen Fall. Wir wollen aber ein Problem demonstrieren, das für beliebige Datenstruktur-Familien gilt.}. Damit wäre eine dynamische Längenänderung ohne Angabe einer maximalen Dimension möglich.

Soll nun zum i-ten Element eines Vektors zugegriffen werden oder soll geändert werden, so benötigen wir zugeordnete Funktionen: Eine Speicherfunktion, eine Ladefunktion und vielleicht weitere für andere Zwecke. Die Speicherfunktion für Vektoren fester Länge kann die eingebaute Funktion STORE (fest implementierte LISP-Grundfunktion) sein,zum Zugriff benötigen wir nur den Feldnamen. Auch für die variablen Vektoren (d.h. Listen) lassen sich die betreffenden Funktionen leicht definieren: Der Zugriff läßt sich mit der Grundfunktion NTHausführen, die Speicheroperation baut auf der ähnlichen Grundfunktion *NTH auf. Diese liefert das mit dem i-ten Elementbeginnende Listenstück -- wir müssen nur noch den Wert dort überlagern. Also genügt

   (RPLACA VALUE (*NTH I VECTOR)).

In einem Programm, das Zugriffe und Speicheroperationen durchführt, müssen nun ständig die Typen abgefragt werden:

                .
                .
                .
   ;Speichern;
    (COND((EQ (GET VECTOR 'TYP) 'FIXLENGTH)
           (STORE (VECTOR I) VALUE))
         ((EQ (GET VECTOR 'TYP) 'VARLENGTH)
           (RPLACA (*NTH VECTOR I) VALUE))
                .
                .
                .
   ;Zugriff;
    (COND((EQ (GET VECTOR 'TYP) 'FIXLENGTH)
           (APPLY VECTOR (NCONS I)))
         ((EQ (GET VECTOR 'TYP) 'VARLENGTH)
           (NTH I VECTOR)))
                .
                .
                .

Man sieht, das Programm wird nicht nur unübersichtlich, es ist nun auch unbequem lang. Diese Programmorganisation ist bei Änderungen sehr hinderlich: Soll ein neuer Vektortyp eingebaut werden, muß man überall neue COND-Klauseln einfügen -- ein gefährliches Unterfangen, weil korrekter Programmkode zu ändern ist! Dasselbe gilt, wenn ein Vektortyp zu ändern oder zu beseitigen ist.

Wesentlich günstiger (und LISP-gerechter) ist es, stattdessen den Vektoren neben dem Typ auch die Zugriffsfunktionen zuzuordnen und ihre Namen verfügbar zu machen. Dazu wird die dem jeweiligen Atom zugeordnete Struktur -- die Eigenschaftsliste -- verwendet.

Beim Ausführen einer beliebigen Operation greift man auf die angepaßte konkrete Funktion zu:

                   .
                   .
                   .
   ;Speichern;
    ((GET VECTOR 'STORE_FN) VECTOR I VALUE)
                   .
                   .
                   .
   ;ZUGRIFF;
    ((GET VECTOR 'ACCESS_FN)VECTOR I)
                   .
                   .
                   .

Diese Verfahrensweise ist nicht nur verständlicher, sondern sie hat auch den Vorteil, daß sie einfach zu erweitern ist: Neue Datenstrukturen können leicht in das Schema aufgenommen werden. Hinzu kommt, daß ein solches System für viele verschiedene Varianten von Datenstrukturen dennoch leicht dokumentierbar ist: Hat man einmal die Namenskonventionen für die Indikatoren der Verarbeitungsfunktionen in den Eigenschaftslisten festgelegt und erklärt, ist praktisch der wesentliche Teil der Dokumentation fertiggestellt.

E.Sandewall [SAN75b] beschreibt als wesentlich komplizierteres Beispieldas {\tx PCDB}-System. Dieses System verwandelt eine Datenbasis von Assertions, die mit Hilfe des Prädikatenkalküls formuliert sind, und es geht davon aus, daß jedes Relationssymbol eine Serie von zugeordneten Funktionen hat: Eine Speicherfunktion, eine Ermittlungs- bzw. Zugriffsfunktion, eine Suchprozedur, Funktionen zur Beantwortung noch offener Fragen usw. Von diesen Relationen gab es etwa 30, und insgesamt bestand das System aus mehr als 150 Funktionen mit einer nicht einfachen Aufrufstruktur.

``Normalerweise ist eine Menge von 150 beliebigen Prozeduren höchst schwer zu verstehen und auf dem laufenden zu halten. In diesem Fall jedoch war jede Prozedur durch ihren Relationsnamen, ihren Zweck (Speicherung, Ermittlung usw.) und im Fall der offenen Fragen durch die Position des erfragten Arguments charakterisiert. Im Ergebnis ist es trivial, die Prozedur zu finden, die eine gegebene Aufgabe erfüllt, und wenn das Programm modifiziert wird, gibt es kaum eine Frage, wo die Änderung durchzuführen ist und ob sie andere Programmteile in Mitleidenschaft ziehen kann. Und was nun besonders wichtig ist, das alles wurde erreicht ohne separate Dokumentation all dieser Prozeduren -- eine knappe Beschreibung der Namenskonventionen genügt.'' ([SAN75b], S. 14).

In dieser interessanten Arbeit diskutiert Sandewall eine Reihe vonStilfragen, die für fortgeschrittene LISP-Programmierung beachtet werden sollten.

Eine zeitgemäße Antwort auf die Herausforderungen der Softwareentwicklung durch Änderungen und Erweiterungen ist die objekt-orientierte Systementwicklung, die die konsequente Weiterentwicklung der daten-gesteuerten Programmierung darstellt. Eigentlich muß man die datengesteuerte Programmierung als Implementationstechnik für die objekt-orientierte Programmierung ansehen. Im objekt-orientierten Sinne führt man eine neue Datenstruktur ein durch Definition eines Typnamens und Assoziierung der auf den Datentyp bezogenen Grundfunktionen zur Konstruktion, Selektion, Modifikation, zum Vergleich oder zur Konvertierung sowie eventuell spezieller höherer Funktionen. Man vermeidet auf diese Weise die (im Beispielprogramm sichtbaren) Fallunterscheidungen zwischen den Datentypen. Statt dessen erhält man verteilte kleine Spezialfunktionen für den jeweiligen Typ. Diese Programmorganisation ist äußerst günstig für die Programmwartung. Unangenehm ist, daß man entweder viele Funktionsnamen erfinden muß -- wenn auch, wie Sandewall gezeigt hat, in die Benennung System gebracht werden kann. Reine objekt-orientierte Programmierung bedient sich des Nachrichtenversendens, eine Technik, die Identifizierung\footnote{in anderen Programmiersprachen als `Operatorüberladen' bekannt} der richtigen Funktion von dem ersten Argument, dem Empfänger der Nachricht, abhängigzu machen. Die Verarbeitungsfunktionen aller Typen, die einander konzeptionell ähnlich sind, können dann den gleichen Namen bekommen. In LISP kann eine derartige Vorgehensweise realisiert werden, wenn ein {\tx FLAVOR}-System benutzbar ist.

end