/|
Eine Einführung in die funktionale Programmierung mit /-|Lisp
-------------------------------------------------------------


Vorwort

Computer sind weit mehr als Rechenmaschinen. Sie können Symbole
verarbeiten. Wenn Sie so wollen, ist auch der Mensch ein
Symbolverarbeiter, allerdings möchte ich uns nicht auf die Stufe
von seelenlosen Maschinen stellen. Die Werbefachleute des großen
Computerherstellers mit den drei Buchstaben wollten dann in der
Computersteinzeit den Computer auch nur als reine Rechenmaschine
verkaufen, um nicht Arbeitsplatzängste bei den Angestellten Ihrer
Kunden zu wecken.
Aber ein Computer ist eben doch mehr. Und um seine verborgenen
Kräfte zu wecken, benötigt man entsprechende Werkzeuge. Die
Programmiersprache Lisp hat sich zur verbreitesten
Symbolverarbeitungssprache gemausert. Symbole sind hier mehr als
nur die Variablen anderer Sprachen. Sie können z.B. selbst wieder
Symbole zum Wert haben. Aber ich möchte hier nicht schon die Sprach-
beschreibung vorwegnehmen.
Was Lisp für Anwendungen auf dem Gebiet der sogenannten
Künstlichen Intelligenz (KI oder AI für Artificial Intelligence)
auch noch so interessant macht, ist die Tatsache, daß in Lisp
Daten und Programme gleich aussehen. So können Programme sich
selbst verarbeiten und ändern, also z.B. lernen.

Es lohnt also, sich näher mit Lisp zu beschäftigen !

Mit AmigaLisp liegt auf der Diskette ein Lisp-Interpreter für die
Commodore Amiga vor. Diese Einführung basiert auf dem
Sprachumfang dieses Systems, aber die Grundzüge der Sprache
gelten auch für andere Dialekte, wie CommonLisp oder XLisp.

Ich hoffe aber, den Einstieg in Lisp gerade mit dem beigefügten
Interpreter zu unterstützen, der eine komplette Arbeitsumgebung
mit Editor liefert.

Für konstruktive Kritik bin ich jederzeit dankbar. Auch würde ich
mich über besonders schöne Programmbeispiele in ALisp freuen, die
in späteren Auflagen als Beispiele dargestellt werden können.


			 Weeze im Frühjahr 1991, Steffen Goebbels



Inhalt
------


I.	Die Benutzerschnittstelle

	zur Bedienung der Interpretersoftware


II.	Die Programmiersprache Lisp

	II.1. Grundlagen : Auswertungsregeln und Listen
	II.2. Kontrollstrukturen
		 II.2.1 lambda- und macro- Terme
		 II.2.2 bedingte Anweisungen
		 II.2.3 Wiederholungsanweisungen
		 II.2.4 Logik
	II.3. Zahlen und Zeichenketten in ALisp
	II.3.1. Das Zahlenkonzept von ALisp
	II.3.2. Stringbefehle
	II.4. Ein/Ausgabe
	II.5. Grafik
	II.6. weitere Befehle


III. Programmbeispiele

	III.1. Sortieren
	III.2. Beispiele aus der Mathematik
		  symbolische Differentiation und das Lösen
		  linearer Gleichungssysteme
	III.3. Debugging

IV.	Ein Prolog-Interpreter in Lisp

	IV.1. Die Sprache Prolog
	IV.2. Programmierung des Interpreters


Anhang

	A. Befehlstabelle
	B. Fehlermeldungen
	C. Der Quelltext des Lisp-Interpreters
	D. Verzeichnis der Beispielprogramme



I. Die Benutzerschnittstelle
----------------------------

AmigaLisp läßt sich von der Workbench durch Anklicken starten.
Daneben können Sie aber vom CLI aus das Programm auch mit dem
Kommando 'AmigaLisp <Programmname>' aufrufen. Das bezeichnete
Lispprogramm wird gleichzeitig mitgeladen und gestartet.
Bitte achten Sie beim CLI-Aufruf darauf, daß der Stack genügend
groß dimensioniert ist, geben Sie also z.B. das Kommando
stack 32000 ein.
Auf Ihrer Bootdiskette sollte sich außerdem die 'arp.library'
befinden, da sie für einen Filerequester benötigt wird.
Daneben werden die Mathe-Bibliotheken der Workbenchdiskette
erwartet.

Ich möchte Sie zunächst dem äußeren Erscheinungsbild des Systems
vertraut machen. Dabei werden Sie sicher einige Feinheiten (z.B.
beim Requester für Variablenbearbeitung) nicht auf Anhieb
verstehen. In den späteren Kapiteln werden sich die Lücken aber
schnell schließen.

Die Benutzerschnittstelle des Interpreters besteht aus drei
Fenstern. Im Dialogfenster wird die Sitzung protokolliert. Für
kleinere Eingaben steht das Eingabefenster am unteren
Bildschirmrand zur Verfügung. Für umfangreicher Eingaben, wie
z.B. komplette Programme, ist ein Ganzseiteneditor eingebaut.


Das Dialogfenster

Sämtliche Ausgaben erscheinen in diesem Fenster. Damit Sie den
Dialog mit einem Lisp-Programm oder dem Interpreter jederzeit
nachvollziehen können, werden auch Ihre Eingaben hier nochmal
aufgeführt. Insgesamt umfaßt das Fenster 105 Textzeilen. Sie
sehen immer nur einen Ausschnitt, dessen Position Sie mit den
Gadgets in der Titelzeile des Eingabefensters oder mit den
Funktionstasten F1, F2 (zeilenweise) und F3, F4 (seitenweise
blättern) bestimmen können.


Das Eingabefenster

Hier können Sie bis zu drei Zeilen Text erstellen und edieren.
Der Cursor läßt sich frei bewegen, die RETURN bzw. ENTER-Tasten
schließen eine Eingabe ab. Ähnlich dem neuen CLI sind die letzten
7 Eingaben nicht verloren : Sie können Sie mit den Tasten
[SHIFT][Cursor hoch] bzw. [SHIFT][Cursor runter] wieder ins
Fenster zurückholen.
Daneben lassen die Kombinationen [SHIFT][->] bzw. [SHIFT][<-] den
Cursor an das Ende bzw. den Anfang des Textes springen.
Während Berechnungen sind Eingaben nicht erlaubt. Dann wechselt
der Mauspfeil zu einer ausgefüllten Scheibe.
Zum Eingabefenster gehört die Menüleiste im Kopf des Bildschirms,
die die folgenden Funktionen anbietet :

System

- Editor : Aufruf des Editorfensters

- Grafikfenster an/aus : Für die Grafikfunktionen der Sprache
  wird ein eigenes Fenster bereitgestellt. (siehe
  Grafikfunktionen)

- Knotenstatistik : gibt die Belegung des Speichers an. (siehe
  Abschnitt II.6 sonstige Befehle)

- Lispprogramm laden : läd ein als ASCII-File vorliegendes Lisp-
  programm ein und führt es aus. Ist das Editorfenster noch
  leer, so wird dieses Programm dort auch angezeigt.

- Dialog -> PRT: : die Bildschirmausgaben werden zusätzlich über
  die PRT:-Schnittstelle zum Drucker geschickt.

- Interpreter verlassen : beendet die Sitzung. Alle im Speicher
  befindlichen Lisp-Daten gehen dadurch verloren !

Variablen

- Symbolliste ansehen : zeigt die Namen aller gültigen
  Variablen (siehe Die Sprache Lisp) an.

- Variablen bearbeiten :

  In einem Requester wird die Liste der gültigen Symbole
  angezeigt. Dort können Sie bestimmte Variablen
  anwählen und ansehen/verändern/löschen. Hinter jedem Symbol
  steht eine Zahl. Diese gibt an, ob die Variable lokal oder
  global ist. 0 bedeutet global, andere Zahlen geben an, wieviele
  lokale Variablen es dieses Namens zur Zeit gibt. Wählen Sie
  diesen Menüpunkt an, so wird hinter jeder Variable eine 0
  stehen, gelangen Sie aber über das Pause-Menü in diesen
  Requester, also wärend eines Programmlaufs, so können lokale
  Symbole existieren. Diese sind dann gemäß ihrem Alter durch-
  numeriert. Mit einem speziellen Gadget können Sie dann eine
  bestimmte Inkarnation anwählen. Lokale Variablen dürfen jedoch
  nicht gelöscht werden, da sie später vom Interpreter selbst
  aufgehoben werden.
  Tritt ein Symbolname sowohl für eine globale Variable, als
  auch für eine lokale auf, so läßt sich der globale Wert über
  die Nummer 0 ansteuern.
  Mit dem Gadget 'weiter' verlassen Sie den Requester.
  Sind keine Variablen vorhanden, so geschieht beim Aufruf dieser
  Funktion nichts.
  Beim Menüpunkt Werte verändern rufen Sie bitte bei der Zuweisung
  keine Lispfunktionen auf, da durch einen noch nicht behobenen Pro-
  grammfehler sonst der Bildschirmaufbau durcheinandergerät.

- Bindungen löschen : Alle Lisp-Daten werden im Speicher
  gelöscht, unnötiger Speeicherplatz wird an das Betriebssystem
  zurückgegeben.

- Trace-Modus : Jedem Aufruf einer Funktion (siehe Lambda-Term)
  wird im Dialogfenster dokumentiert.

Abbruch

- Evaluierung abbrechen : Die Ausführung eines Lisp-Programms
  wird abgebrochen

- Pause : Die Ausführung wird nur vorübergehend unterbrochen. Es
  erscheint der beim Menü 'Variablen bearbeiten' beschriebene
  Requester.

In der Fußzeile sind schließlich noch drei Gadgets montiert, die
Systemzustände	anzeigen. (siehe dazu Trace-Modus, Dialog->PRT:
und die Befehle allow/forbid )


Das Editorfenster

Der Editor ist vergleichbar mit dem CLI-Befehl Ed. Er ist
schlicht gehalten und benötigt so wenig Speicherplatz. Dennoch
sind alle nötigen Funktionen vorhanden.
In dieser Version können max. 500-zeilige Programmtexte
bearbeitet werden. (Dies ist kein Nachteil, da lange Programme
ohnehin in übersichtliche Teile zerlegt werden sollten.)
Im Text kann mit dem Cursor frei umhergefahren werden, schreibt
man übers Zeilenende hinaus, so wird die Zeile automatisch
umgebrochen. Tippt man eine geschlossene Klammer ')' ein, so wird
die zugehörige offene angezeigt, falls sie sich im gerade
angezeigten Bereich befindet.

Spezielle Tastenkombinationen :

[SHIFT][->]		Sprung zum Zeilenende
[SHIFT][<-]		Sprung zum Zeilenanfang
[F3]/[SHIFTT][hoch]	Seite zurückblättern
[F4]/[SHIFT][runter]	Seite weiterblättern
[CTRL][->]		Sprung zur nächsten Klammer dieser Zeile
[CTRL][<-]		Sprung zur vorangehenden Klammer der Zeile
[CTRL][hoch]		Sprung zur ersten Zeile
[CTRL][runter]		Sprung zur letzten Zeile
[CTRL/ALT][b]		Blockanfang/Blockende markieren
[CTRL/ALT][d]		Block an die Cursorposition kopieren
[CTRL/ALT][e]		Block löschen
[CTRL/ALT][m]		Block verschieben
[CTRL/ALT][y]		aktuelle Zeile löschen
[CTRL/ALT][t]		Cursor 4 Zeichen nach rechts
[CTRL/ALT][i]		Zeile einfügen
[CTRL/ALT][f]		Zeichenkette suchen (Soll eine Zeichenkette
			mehrfach gesucht werden, so ist sie nur beim
			ersten Mal wirklich einzugeben.)
[CTRL/ALT][)]		alle bis zu dieser Stelle noch offenen
			Klammern schließen
[CTRL][RETURN]		neue Zeile einfügen,
			[RETURN] hingegen kopiert den Rest der alten
			Zeile in die neue hinein.
[CTRL/ALT][q]		Editor verlassen, d.h. zurück zum Interpreter

Einige dieser Funktionen sind auch über Pulldown-Menüs
erreichbar. (Menüpunkte Blockbefehle und Spezial)
Zudem finden sich in der Menüleiste noch die folgenden auf die
Menüoberpunkte Sytem und Blockbefehle verteilten Optionen :

Neues Dokument	:      löscht alle Textzeilen im Editor

Quelltext laden :      fügt eine ASCII-Datei an das bisherige
		       Textende an.

Datei speichern :      Schreibt das gesamte Dokument auf einen
		       Datenträger

Datei auswerten :      Das Dokument wird an den Interpreter zur
		       Auswertung übergeben.

Datei ausdrucken :     Das Dokument wird ausgedruckt. Dabei muß der
		       Druckertyp über das Workbench-Programm
		       Preferences eingestellt sein. AmigaLisp
		       erlaubt einen Kopftext über jeder Seite.
		       Dieser wird über einen Requester eingegeben.
		       Außerdem kann mit und ohne Zeilen- bzw.
		       Seitennumerierung gedruckt werden. Sollen die
		       entsprechenden Nummern ausgegeben werden, so
		       muß das zugehörige Gadget farblich unterlegt
		       sein. Dann können auch in weiteren Gadgets
		       die Anfangswerte für die Numerierung
		       definiert werden.
		       Letztlich wird noch die Anzahl der Zeilen
		       pro Seite abgefragt.

Block auswerten :      Nur der markierte Block wird dem Interpreter
		       übergeben.

Block speichern :      Der Block wird als ASCII-File gesichert.

Die letzte Bildschirmzeile dient als Statusleiste. Hier wird die
Position des Cursors in Koordinatenform angezeigt. Die Zahl
rechts außen gibt die aktuelle Zeilenzahl an.
In der Mitte der Zeile werden Meldungen des Editors ausgegeben.
Die Fehlermeldungen sind selbsterklärend.

Da der Cursor mit einem Sprite dargestellt wird, sollte es nicht
verwundern, wenn man ihn auch noch sieht, obwohl andere Fenster
ihn eigentlich verdecken müßten.




II. Die Programmiersprache Lisp
-------------------------------


II.1. Grundlagen

Lisp, das heißt ListProcessor, also Listenverarbeiter - und
nichts anderes ist Lisp. Die Liste ist die alles bestimmende
Grundstruktur. Eine Liste ist eine endliche Folge irgendwelcher
Lisp-Objekte, z.B. von Zahlen, die in Klammern gefaßt sind :

(1 2 3 4 5 6 7 8 9) ist eine solche Liste.

Innerhalb von Listen können wieder Listen auftreten :
(1 2 (3 (4 5) 6) 7 8 (9))
Die Glieder dieser Liste sind demnach 1, 2, die Liste
(3 (4 5) 6), 7, 8 und die eingliedrige Liste (9).
Mit dieser Datenstruktur lassen sich beliebige Programme
erstellen. Die dazu notwendige Konvention ist, daß das erste
Listenglied ein Befehl ist, die restlichen Glieder sind dann die
zugehörigen Parameter.
Geben Sie z.B. im Eingabefenster die folgende Zeile ein:

(+ 5 2 6 8 24 2)[RETURN]

Der Interpreter antwortet mit 47, der Summe der Parameter 5, 2,
6, 8, 24 und 2. Das erste Listenelement ist also der Befehl zum
Addieren von Zahlen. Man (frau) beachte, daß durch die Konvention
die sogenannte Polnische Notation oder auch Präfix-Notation
eingeführt ist : Die Operatoren stehen nun nicht mehr zwischen
ihren Argumenten, sondern davor. Damit kann sich ein Operator
direkt auf mehr als zwei Argumente beziehen, jedoch ist stets
eine Klammerung (hier als Liste) nötig.

Einige Beispiele :

23*4+7/3	  wird zu  (+ (* 23 4) (/ 7 3))
(34+22+12)/2/4*3  wird zu  (* (/ (/ (+ 34 22 12) 2) 4) 3)
(2+8*2)/(4-2)     wird zu  (/ (+ 2 (* 8 2)) (- 4 2))

Zu Anfang ist die Schreibweise sicher etwas ungewohnt. Sie
unterstützt aber den Interpreter ungemein, da er keine
Prioritäten beachten muß und sehr leicht das Ergebnis rekursiv
berechnen kann, d.h. die entsprechende Prozedur im Interpreter
ruft sich für jede Unterliste selbst auf.


Auswertungsregeln

Ein Lispprogramm ist letztlich eine Aneinanderreihung und
Schachtelung von Listen.
Um sinnvoll programmieren zu können, benötigt man Variablen und
Konstanten.
Lisp-Variablen können mit beliebig langen Zeichenketten (ohne
Sonderzeichen und Leerzeichen, jedoch ist der Untersprich _
erlaubt) benannt werden. Sie heißen Symbole.
Konstanten sind Zahlen, Zeichenkettenkonstanten (Strings) und
Wahrheitswerte.
Bei den Zahlen beschränken wir uns zunächst auf den
Ganzzahlbereich. Zeichenkettenkonstanten sind beliebige Folgen
von Zeichen, die aber mit einem Anführungszeichen beginnen und
enden. Anführungszeichen dürfen sonst nicht benutzt werden :
"Dies ist ein String"
Wahrheitswerte sind t (true=wahr) und nil bzw. () (falsch). Die
leere Liste () ist identisch mit dem Wahrheitswert nil.
Tippt man eine solche Konstante ein, dann erhält man die Eingabe
vom Interpreter als Ausgabe zurück : Konstanten werten zu sich
selbst aus - man sagt auch : evaluieren zu sich selbst.

Werden dagegen Symbole interpretiert, dann evaluieren sie zu
ihrem Inhalt.
An Symbole können sowohl Konstanten wie auch Listen gekettet
sein. Eine Zuweisung an ein Symbol geschieht mit der setq-
Funktion :

(setq variable 10) [RETURN]

Nun steht das Symbol variable für die Zahl 10. Geben Sie
variable [RETURN] ein, so wird die Eingabe ausgewertet, das
Ergebnis ist 10. Symbolnamen werde ich in der Regel mit
Kleinbuchstaben schreiben. ALisp unterscheidet zwischen Groß- und
Kleinschreibung.

Die gängigen imperativen Sprachen wie Basic, Pascal, Modula, C
oder Fortran sind typisiert, d.h. für verschiedene Datentypen
gibt es verschiedene Klassen von Variablen. Hat man eine Variable
für Zahlen eingeführt, so kann man ihr keine Zeichenkette
zuweisen.
In Lisp ist dies anders. Hier kann ein Symbol jederzeit alles
mögliche aufnehmen, unabhängig von seiner bisherigen Verwendung.
Symbole müssen auch nicht wie in vielen Compilersprachen
deklariert werden. Sie werden bei ihrer ersten Wertzuweisung
eingerichtet.

Wir haben bisher eine Addition und eine Wertzuweisung
durchgeführt. Dabei stand der Name der auszuführenden Operation
am Anfang der Liste, es folgten die Parameter. Wenn eine Formel,
wie z.B. 3+(2*4) so ausgerechnet werden soll, muß der Wert 2*4
bei der Addition bereits bekannt sein.

(+ 3 (* 2 4))
(* 2 4) ist wie 3 ein Parameter von +. Daher werden in Lisp
Parameter ausgewertet, bevor die zugehörige Operation ausgeführt
wird. 3 wertet hier zu 3, (* 2 4) zu 8 aus.
Vielleicht werden Sie jetzt "ja, aber" sagen, denn bei der
Anweisung (setq variable 10) hat das Symbol variable ja vor der
Zuweisung noch keinen Wert. Wenn aber die die Parameter zunächst
ausgewertet werden, so muß es hier ja Schwierigkeiten geben. Aber
die gibt es nicht, da für setq eine Ausnahmeregel existiert.

setq ist eine Form des set-Befehls. Bei (set variable 10) würde
variable tatsächlich zunächst ausgewertet, bei setq wird jedoch
nur die 10 evaluiert. Das Q deutet 'quote' an, der quote-Befehl
verhindert die Auswertung eines Atoms oder einer Liste.
(set (quote variable) 10) ist identisch mit (setq variable 10).
Die Auswertung von (quote variable) ergibt variable.
Also : quote gibt seinen Parameter unausgewertet zurück !

Da quote sehr häufig benutzt wird, gibt es hier eine Abkürzung,
das quote-Zeichen '. Es ersetzt den quote-Befehl mit seinen
Listenklammern. Aus (set (quote variable) 10) wird so
(set 'variable 10).
Manchmal wird als Parameter eine Liste benötigt, in der einige
Glieder ausgewertet, andere jedoch unverändert bleiben sollen.
Dann kann die Liste mit einem quote versehen werden. Die
auszuwertenden Atome der Liste werden durch ein vorangestelltes
Komma gekennzeichnet :

'(1 2 3 ,(+ 3 1) 4) wertet zu (1 2 3 4) aus.

Wo die Auswertung unterdrückt werden kann, sollte auch die
Möglichkeit der doppelten Auswertung bestehen.
Das Gegenstück zu quote ist eval. eval wertet seinen Parameter
doppelt aus und gibt den daraus resultierenden Wert zurück.
(eval (quote variable)) hat das gleiche Ergebnis wie die direkte
Auswertung des Symbols variable.

Die Namen eval, quote, set, setq und + bezeichnen fertige Befehle
des Lisp-Systems, sogenannte Primitive.
Die Auswertung eines dieser Symbole führt zur Ausführung des
zugehörigen Programmstücks des Interpreters, falls das Symbol
eine Liste eröffnet. In allen anderen Fällen werten aber auch
diese reservierten Symbole zu ihrem Wert aus. Der ist aber die
Ausführung eines Stücks Maschinensprache und das kann von Lisp
aus nicht kontrolliert werden. Aber man kann eigenen Symbolen den
Verweis darauf zuweisen : (setq meinBefehl setq)
Nun kann meinBefehl wie setq benutzt werden. Möchte man sich den
Wert von setq ansehen, so wird aber nur die Meldung #Primitive
Nr.4 angezeigt.

Wir wissen jetzt also, wie Listen und wie Atome ausgewertet
werden. Wenden wir uns jetzt wieder dem zentralen Element, den
Listen zu.


Listen

Betrachten wir zunächst die interne Darstellung der Listen.
Listen werden zur Laufzeit auf der sog. Halde (heap) angelegt.
Dabei bestehen sie aus zwei verschiedenen Knotentypen :
Punktepaaren und Atomen. Die Atome sind Konstanten und Symbole
von oben, die Punktepaare dienen der Verkettung der Atome zu
Listen. Ein Punktepaar besitzt zwei Zeiger (einen rechten und
einen linken), die jeweils auf ein weiteres Punktepaar oder auf
ein Atom zeigen können.
Eine einfache lineare Liste mit n Gliedern wird so aufgebaut :
n Punktepaare werden über die rechten Zeiger zu einer Liste
verkettet, der letzte rechte Zeiger zeigt auf nil, d.h. auf die
leere Liste. An die linken Zeiger werden die Knoten angehängt :

Interene Listenstruktur (als binärer Baum):

					    /\
					   a /\
		(a b c)  =                  b /\
					     c	nil

Nun können Listen innerhalb von Listen auftreten. Dazu werden die
Unterlisten wie oben aufgebaut und statt eines Atoms verweist ein
linker Zeiger der übergeordneten Liste auf sie.

		   /\				     /\
 (a (b c) d) =    a   /\         ((a b)(c d)) =  /\      /\
		    /\	/\			a /\	/\ nil
		   b /\ d  nil			 b nil c /\
		     c	nil				d  nil

Wenn Listen in der bisher benutzen geklammerten Form eingegeben
werden, so werden stets diese Strukturen intern erstellt. Es
besteht aber die Möglichkeit, diesen Aufbau selbst zu steuern.
Dazu dient der Punkt-Operator.
			      /\
(a.b) wird dargestellt als   a  b , also nicht in der üblichen
Listenform. Mit dem Punkt wird also ein Punktepaarknoten
vorgeschrieben. Also wird

		    /\
(a.(b.(c.nil))) zu a /\    und ist damit identisch mit (a b c).
		     b /\
		      c  nil

In Programmen werden nur die Standardlisten ohne Punkte
vorkommen. Aber der Punkt-Operator eignet sich hervorragend für
Datenstrukturierungen. Sollen z.B. Koordinaten der Ebene
gespeichert werden, bietet das Punktepaar (x.y) förmlich an.


Die Befehle car und cdr

In diesen Befehlen spiegelt sich die interne Speicherung stark
wieder, weshalb ich mit ihrer Darstellung fortfahren möchte.
Die Befehle car und cdr (sprich : kar und kudder) erwarten als
Parameter Listen bzw. Punktepaare. car gibt das erste
Listenelement, cdr die Restliste zurück. Anders formuliert : car
bestimmt den linken Teilbaum, cdr den rechten des Punktepaars.

Bsp:	(car '(1 2 3 4)) ergibt 1, (cdr '(1 2 3 4)) ergibt (2 3 4)

					 |
					/| \
				       1 | /\
			   car		 |2 /\	  cdr
					 | 3 /\
					 |  4  nil
					 |

	(car '(1 . 2)) ergibt 1, (cdr '(1 . 2)) ergibt 2

					 |
					/|\
			      car      1 | 2	  cdr
					 |

	(car '((a b)(1 2) 3)) ergibt (a b),
	(cdr '((a b)(1 2) 3)) ergibt ((1 2) 3)

Möchte man das zweite Glied einer Liste erhalten, so kann man car
und cdr kombinieren :
(car (cdr '(1 2 3 4)) ergibt 2.
Auf diese Weise kann man jedes Listenglied erreichen, allerdings
gibt es dafür bessere Befehle: cadr teilt das zweite
Listenelement mit und mit nth kann man schließlich auf einen
beliebigen Eintrag zugreifen. Dazu wird als erster Parameter die
Position innerhalb der Liste und als zweiter die Liste angegeben:
(nth 3 '(a b c d)) ergibt c.

Mit cons kann man ein Punktepaar einrichten :

(cons 1 '(2 3 4)) ergibt (1.(2 3 4)) also (1 2 3 4)
(cons '("hallo" "Du" "da") "!")
wird demnach zu (("hallo" "Du" "da")."!")
(cons 1 (cons 2 (cons 3 (cons 4 nil)))) ergibt wieder (1 2 3 4).
(cons 4 nil) wird also zu (4) bzw. (4.nil)

Es ist etwas mühselig, mit cons Listen zu erstellen. Daher wurde
der Befehl list geschaffen. Er erhält als Parameter die Glieder,
die zu einer Liste gefügt werden sollen :

(list 1 2 3 4) ergibt (1 2 3 4)
(list "Hallo" '(1 2 3) 'x) ergibt ("Hallo" (1 2 3) x)


Übungen

1. Zeigen Sie, daß quote und eval nicht vertauschbar sind, d.h.
   daß (quote (eval a)) und (eval (quote a)) nicht gleichwertig
   sind. Dazu belegen Sie das Symbol a passend.

2. Welche Listen sind korrekt gebildet. Prüfen Sie ihre Antworten
   mit dem Interpreter.

   (1 2 3 4 5 6)                (1 2 (2 34 2)
   (((3 1 3 4)) 23))            ((1.2) "Hallo".(2 3 (4)))
   (((((())))))                 ((1 e s 3)((3 2 3))
   (1.(a.(b c d e)))            (((()).4) 5)

3. Werten Sie die folgenden Lisp-Ausdrücke aus und kontrollieren
   Sie Ihre Ergebnisse mit dem Interpreter :

 (car '((a b)(1 2 3)))          (cdr (car (cdr '((a b)(1 2 3)))))
 (car (cdr '((a b)(1 2 3))))    (car (car (cdr '((a b)(1 2 3)))))
 (cdr (cdr '((a b)(1 2 3))))

4. Experimentieren Sie mit cons und list, indem Sie mit diesen
   Befehlen Listen generieren.




II.2 Kontrollstrukturen

Wie in den bekannten imperativen Programmiersprachen benötigen
wir auch in Lisp Kontrollstrukturen um eigene Funktionen zu
definieren, Schleifen zu bauen und für bedingte Anweisungen.


II.2.1 lambda-Terme

Beginnen wir mit den Funktionen. Die Primitive defun leitet eine
Funktionsdefinition ein:

(defun zweiter (x) (car (cdr x)))

Diese Eingabe definiert die Funktion zweiter, die das zweite
Glied einer Liste berechnet:

(zweiter '(6 4 8)) ergibt 4.

Nach defun folgt stets der Name der zu definierenden Funktion.
Dieser wird wie bei setq nicht ausgewertet. Es schließt sich die
Liste der Parameter an, welche bei der Übergabe evaluiert werden.
In unserem Beispiel muß nur eine Liste übergeben werden, also
steht hier die Liste mit dem einzigen Glied x. Nun folgen
beliebig viele Lisp-Ausdrücke, die der Reihe nach beim Aufruf der
Funktion interpretiert werden.
Der letzte Wert, der so berechnet wird, wird zum Wert der
Funktion und somit zurückgegeben, hier die 4.
In Lisp gibt (fast) jeder Befehl und jede Funktion einen Wert
zurück. So teilt defun den Namen der neuen Funktion mit. Die
bereits beschriebene Primitive setq gibt den der Variable
zugewiesenen Wert weiter, so daß Mehrfachzuweisungen möglich
sind: (setq a (setq b (setq c "Hallo"))).

An die in der Parameterliste aufgeführten Symbole werden beim
Funktionsaufruf die aktuellen Parameter gekettet. Diese Symbole
sind nur solange sichtbar, bis die Funktion beendet wird. Dann
existieren sie nicht mehr, sie sind lokal und beeinflussen nicht
bereits bestehende Symbole gleichen Namens, wie der folgende
Dialog mit dem Interpreter zeigt:

>(setq x 23)
 23
>(zweiter '(1 2 3))
 2
>x
 23

Insbesondere können innerhalb von Funktionen natürlich auch
weitere aufgerufen werden. Auch ihre Parameter beeinflussen die
der aufrufenden Funktion nicht.
Parametersymbole werden mit dem Stackprinzip verwaltet : Bei
jeder Parameterdefinition wird eine zugehörige Kennung auf einen
Stapel gelegt. Wird nun ein Symbol angesprochen, so wird die
Inkarnation ausgewählt, die im Stapel am höchsten liegt. Symbole,
die nicht als Parameter eingeführt sind, liegen im Stapel zu
unterst. Der Menüpunkt 'Variablen bearbeiten' verdeutlicht das
Prinzip : Hinter jeder Variable steht eine Zahl. Ist diese 0, so
existiert keine Parameterversion dieses Symbols. Andernfalls gibt
die Zahl an, wieviele Parameter dieses Namens bereits auf dem
Stack liegen.

Nun werden, z.B. für Nebenrechnungen weitere lokale Symbole
innerhalb von Funktionen benötigt, die ebenfalls nach außen nicht
stören sollen. Auch diese können in der Parameterliste definiert
werden. Dabei müssen zunächst die Parameternamen, dann das
Schlüsselwort &aux und schließlich die Namen der lokalen Symbole
eingetragen werden:

(defun test1 (a b &aux i j) (setq i 1)(setq j 2)(+ a b i j))
(test1 5 6) liefert 14.

Da einige Funktionen eine variable Anzahl von Parametern
erfordern, gibt es hier schließlich noch den &rest-Operator.
Hinter ihm muß genau ein Symbol stehen. Dieses Symbol erhält als
Wert die Liste aller noch nicht angeketteter aktueller Parameter:

(defun test2 (a b &aux rest) rest)

(test2 1 2 3 4 5 6) ergibt (3 4 5 6), 1 und 2 wurden an a und b
vergeben.

Werden &aux und &rest benutzt, so muß zuerst &rest, gefolgt von
seinem Parameter und dann &aux mit den lokalen Variablen stehen.

defun ist nur eine Variante des setq - Befehls. Die Definition
von test2 kann auch so vorgenommen werden :

(setq test2 '(lambda (a b &aux rest) rest))

Entsprechend läßt sich der Aufruf ersetzen durch

('(lambda (a b &aux rest) rest) 1 2 3 4 5 6)
Das erste Listenelement wertet also seinerseits zu einer Liste
aus. Daran erkennt der Interpreter, daß hier keine vordefinierte
Primitive ausgeführt werden soll. Das Schlüsselwort lambda weist
auf eine Funktion hin. Funktionen werden auch als Lambda-Terme
bezeichnet. Der defun-Befehl erspart Ihnen aber das Hantieren mit
diesem zugegeben etwas gekünzelten Konstrukt.

Neben den Lambda-Termen kennt ALisp noch Macro-Terme. Sie
unterscheiden sich formell nur im Austausch des Schlüsselworts
lambda durch macro. Entsprechend gibt es den defmacro-Befehl, der
wie defun wirkt.
Ein Macro ist ein Textersatz, z.B. gibt es in der
Programmiersprache C die Möglichkeit, Macros mit #define
einzurichten. Mit einem Namen wird hier ein Stück Programmtext
identifiziert. Überall, wo sich im Programm dieser Name findet,
wird dann vor der Übersetzung des Programms in Maschinensprache
oder Assemblercode das Stück Programmtext eingefügt.
Man erspart sich also Schreibarbeit und der Quelltext wird
kürzer.
Bei Interpretersprachen müssen die Macrosymbole während des
Interpretierens durch den zugehörigen Programmtext ersetzt
werden, falls nicht ein sog. Präprozessor zuvor bereits den
Quelltext modifiziert.
Lisp 'ersetzt' während des Programmlaufs. Eigentlich ist aber
hier (im Gegensatz zu Compilersprachen !) ein Macro doch nur ein
Funktionsaufruf. Der Unterschied zu den Lambda-Termen liegt nun
darin, daß die Parameter nicht ausgewertet werden, also
unverändert in der Macro-Funktion eingesetzt werden können. Das
Ergebnis der Berechnung wird schließlich jedoch zusätzlich
ausgewertet. Ein Beispiel möge den Sachverhalt verdeutlichen :

(defun keinMacro (a) 'a)
(defmacro Macro (a) 'a)

(keinMacro (+ 3 4)) liefert 7, a erhält bereits beim Aufruf den
Wert 7.

(Macro (+ 3 4)) liefert jedoch (+ 3 4). a hat hier den Wert
(+ 3 4). Dann wird (quote a) im Anweisungsteil des Macros
ausgewertet. Das Ergebnis ist natürlich a. Ein Lambda-Term würde
diesen Symbolnamen jetzt auch zurückgeben. Aber der Macro-Term
wertet a nochmal aus - und erhält somit (+ 3 4).
So könnte man z.B. mit defmacro die setq-Primitive definieren :

(defmacro setq (name wert) '(set name (eval wert)))

Experimentieren Sie doch selbst etwas mit defun und defmacro !

In Pascal und Modula gibt es zwei Formen der Parameterübergabe :
Werte- und Variablenparameter (Call by Value und Call by
Reference).
Bei den Werteparametern wird der Funktion nur ein Wert übergeben,
bei den Variablenparametern jedoch eine Verweis auf die
entsprechende Variable in der Parameterliste des
Funktionsaufrufs, im Prinzip rechnet man dann in der Funktion mit
der alten Variable, die jetzt den Namen des Parameters trägt,
weiter. Nach verlassen der Funktion hat sich so ev. der Wert der
Variable im Aufruf geändert :



VAR i : INTEGER;				Dieser Ausschnitt
PROCEDURE WerteParameter(x:INTEGER);            eines Modula2-
BEGIN						Programms ver-
  x:=10;					deutlicht den
END WerteParameter;				Unterschied :
PROCEDURE VariablenParameter(VAR x:INTEGER);    Der Aufruf der
BEGIN						ersten Funktion
  x:=10;					ändert den Wert
END VariablenParameter; 			von i nicht. Daher
						wird zunächst 20
BEGIN						ausgegeben. In der
  i:=20;					zweiten Funktion
  WerteParameter(i); WriteInt(i,3);             wird i jedoch ver-
  VariablenParameter(i); WriteInt(i,3);         ändert, schließlich
[...]						wird 10 ausgegeben.

Durch Seiteneffekte wie in der Funktion VariablenParameter werden
Programme schwerer verständlich und das Fehlerrisiko steigt. In
Lisp gibt es ausschließlich Werteparameter. Es werden stets
Kopien der Werte erzeugt, die dann übergeben werden oder mit
denen weitergerechnet wird. Sogar beim Aufruf einer Funktion wird
der Lambda-Term kopiert, und auf der Kopie wird
weiterinterpretiert. So können niemals Symbolwerte unbeabsichtigt
geändert werden.
Ein Nachteil dieser Methode ist die Speicherintensität und der
Zeitbedarf für das Duplizieren, sowie für die Verwaltung und das
Aufräumen des Speichers. Aber bei immer schnelleren Computern mit
immer mehr Speicher löst sich dieser Nachteil mit der Zeit von
selbst auf. Der Amiga ist durchaus in der Lage, eine sinnvolle
Arbeit mit Lisp zu ermöglichen.

Nach soviel grauer Theorie versuchen wir uns jetzt mal an einer
ersten Programmieraufgabe:


II.2.2. bedingte Anweisungen

Die Fakultätsfunktion ! ist so definiert :
1! := 1, n! := n*(n-1)!
mit dieser rekursive Definition ist die Zahlenfolge
1,2,6,24,120,... beschrieben.
Es soll nun eine Funktion pogrammiert werden, die das n-te Glied
dieser Folge berechnet.
ALisp speichert ganze Zahlen in Worten der Länge 4 Bytes. Dadurch
kann bereits 13! so nicht mehr dargestellt werden, es kommt zu
Überlauf-Fehlern. Dies ist in fast allen Programmiersprachen so.
Daher ist die effektivste Lösung des Problems diese :

(defun fakultät (n)
  (nth n '(1 2 6 24 120 720 5040 40320 362880 3628800 39916800
	   479001600)))

Wir können aber auch der rekursiven mathematischen Definition
folgen und an ihr die Funktion ableiten :

(defun fakultät (n)
  (cond ((eql n 1) 1)
	   (t (* n (fakultaet (- n 1))))))

Hier treten zwei neue Primitive auf : cond und eql.
cond leitet eine bedingte Anweisung ein, ähnlich dem IF bzw. CASE
aus Pascal. eql ist ein Vergleich :

Falls n=1 gib 1 , sonst n*(n-1)! zurück.

Die cond-Anweisung besteht aus dem Schlüsselwort cond, gefolgt
von beliebig vielen Listen. Jede Liste muß mit einem Ausdruck,
der zu einem Wahrheitswert (t oder nil) evaluiert, beginnen.
Danach dürfen in jeder Liste beliebig viele weitere Ausdrücke
stehen. Bei der Interpretation wird nun die erste Liste gesucht,
deren erster Ausdruck zu t auswertet. Dann wird der Rest dieser
Liste abgearbeitet. Der letzte so entstandene Wert wird zum
Ergebnis der gesamten cond-Anweisung, die damit verlassen wird.
Soll also eine Alternative eingerichtet werden, die dann
ausgeführt wird, wenn alle anderen Fälle nicht zutreffen, so kann
diese als letzte Unterliste eingetragen werden. Sie wird mit dem
Wahrheitswert t eröffnet, so daß spätestens hier verzweigt wird.

(cond (<Bedingung> <Ausdruck> [<Ausdruck>...])
	 (<Bedingung> <Ausdruck> [<Ausdruck>...])
	 usw.
)

Hier sollen die eckigen Klammern andeuten, daß die entsprechenden
Teile entfallen können. Spitze Klammern deuten an, daß hier
Lisp-Terme stehen dürfen, die ausgewertet werden. Schrägstriche
sollen demgegenüber andeuten, daß ein entsprechender Ausdruck
nicht ausgewertet wird (vgl. setq, quote). Ich werde von nun ab
diese Konvention bei der Einführung neuer Befehle verwenden.

(eql <Zahl> <Zahl>) vergleicht zwei Zahlen. Stimmen sie überein,
so wird t, sonst nil zurückgegeben.

Noch etwas ist am obigen Beispiel neu : Die Funktion ruft sich
selbst auf. Da ja auch Funktionen beim Aufruf dupliziert werden,
gibt es dadurch keinerlei Probleme, am Gültigkeitsbereich der
Variablen ändert sich nichts.

Ein neues Beispiel : Die Türme von Hanoi

Dieses Beispiel fehlt in keinem Buch, das sich mit rekursiven
Algorithmen beschäftigt.

Auf drei Stangen können Scheiben gesteckt werden. Die Durchmesser
der Scheiben sind unterschiedlich groß. Zunächst befinden sich
alle Scheiben auf der ersten Stange und sind ihrem Durchmesser
nach sortiert. Die größte Scheibe befindet sich unten. Nun sollen
die Scheiben auf die zweite Stange überführt werden. Dabei muß
jeweils eine von einer Stange oben weggenommen und auf eine
andere gesteckt werden. Allerdings darf nie eine größere Scheibe
über einer kleineren liegen.
Nun soll ein Programm geschrieben werden, daß eine Anleitung
ausgibt, wie die Scheiben umzustecken sind.

Es gibt eine schwer zu verstehende iterative Lösung dieses
Problems. Auf die soll hier aber nicht eingegangen werden.
Vielmehr legen die folgenden Überlegungen ein rekursives Programm
nahe :

- bringe alle Scheiben mit Ausnahme der letzten von Stange 1 auf
  Stange 2

- lege die einzelne Scheibe von Stange 1 auf Stange 2.

- bringe alle Scheiben von Stange 3 auf Stange 2

Der erste und der dritte Schritt entspricht dem Ausgangsproblem,
allerdings um eine Scheibe reduziert. Es läßt sich leicht
nachvollziehen, daß bei dieser Methode niemals eine größere über
einer kleineren Scheibe liegt.

Bevor wir dazu ein Lispprogramm schreiben, benötigen wir noch
einen Befehl für Bildschrirmausgeben. Er heißt princ.

(princ <Ausdruck> [<Ausdruck>...])

Die Ausdrücke werden ausgewertet und die so entstandenen Werte
werden, durch Leerzeichen getrennt, ausgedruckt. Bei
Zeichenketten (Strings) werden dabei ausnahmsweise die
Anführungszeichen weggelassen.
princ liefert in ALisp keinen Wert zurück und stellt somit eine
Ausnahme dar.

(princ "Hallo") ergibt: Hallo
(princ 1 2 "Text") ergibt: 1 2 Text

Um die Textausgabe in einer neuen Zeile fortzusetzen, wird die
parameterlose Primitive terpri (terminate printing) aufgerufen.

(defun StapleUm (t1 t2 t3 n)
  (cond ((eql n 1)(princ "lege Scheibe von" t1 "nach" t2)
	  (terpri)) ; Abbruchbedingung für die Rekursion
	   (t (StapleUm t1 t3 t2 (- n 1)) ; Reduktion auf n-1
		 (princ "lege Scheibe von" t1 "nach" t2)(terpri)
		 (StapleUm t3 t2 t1 (- n 1)))))
(terpri)(princ "Türme von Hanoi")(terpri)
(StapleUm 'Stange_1 'Stange_2 'Stange_3 3)

Der Parameter n zeigt an, wieviele Platten noch umgestapelt
werden müssen. Insgesamt sind beim Aufruf von StapleUm 3 Platten
vorhanden.

Kommentare machen Programme wesentlich übersichtlicher. Im ALisp
werden sie von einem Semikolon eingeleitet und reichen bis an das
Ende der Zeile.

Neben Kommentaren sollte man auf eine sinnvolle Formatierung des
Quelltextes durch Einrücken achten. So werden zusammenhängende
Programmblöcke auch optisch zusammengehörig.

Die Geschichte der Türme von Hanoi können Sie im Heft Spektrum
der Wissenschaften, Jan 85, nachlesen.

Auf der Diskette befinden sich sämtliche hier vorgestellten
Beispiele im Verzeichnis lisp, so daß Sie sie nicht abtippen
müssen. Programmdateien sind reine Textfiles, die Sie mit jedem
Editor erstellen können. Sie werden mit der Primitive load
eingelesen und interpretiert.

(load <Programmname>)  [siehe auch Abschnitt II.4]

Allerdings ist es komfortabler, den Menüpunkt 'Lispprogramm
laden' anzuwählen, da hier über einen Filerequester die
gewünschte Datei einfach angeklickt werden kann.

Der in ALisp integrierte Editor bietet sich natürlich für die
Programmerstellung besonders an. Über die entsprechenden
Menüpunkte 'Datei auswerten' bzw. 'Block auswerten' läßt sich das
eben Eingetippte sogleich ausprobieren.


Übungen

5. Die Ackermannfunktion ist ein Beispiel dafür, daß Rekursionen
   im Kopf nur begrenzt nachvollzogen werden können. Versuchen
   Sie doch mal, die Abarbeitung der folgenden doppelt rekursiven
   Funktion zu überschauen :

   (defun Ackermann (a b)
     (cond ((eql a 0) (+ b 1))
	   ((eql b 0) (Ackermann (- a 1) 1))
	   (t (Ackermann (- a 1) (Ackermann a (- b 1))))))

   Bereits die Berechnung von (Ackermann 3 4) erfordert 10306
   rekursive Aufrufe.

6. Die Zahlenfolge 1 1 2 3 5 8 13 ... ist rekursiv definiert :
   a1 = 1, a2 = 1, an = an-2 + an-1
   Implementieren Sie die Funktion rekursiv gemäß dieser
   Definition.

7. Formulieren Sie die Lösung zu 6 auch mit einem Macro.

8. Schreiben Sie eine Funktion, die die Anzahl der ihr beim
   Aufruf übergebenen Parameter zählt.




II.2.3. Wiederholungsanweisungen

Schleifen dienen dazu, ein Programmstück mehrfach auszuführen. In
Lisp benötigt man prinzipiell keine Schleifen, da mit der Technik
der Rekursion diese vollkommen ersetzt werden können.
Dennoch ist es übersichtlicher, auf sie nicht zu verzichten.

Die Fakultätsberechnung läßt sich natürlich auch iterativ
formulieren :

6! = 1*2*3*4*5*6 ,in Lisp ausgedrückt :

(defun fakultät (n &aux i ergebnis)
  (setq ergebnis 1)
  (setq i 2)
  (while (<= i n) ; solange i <= n ist, tue
    (setq ergebnis (* ergebnis i)) ; ergebnis:=ergebis*i
    (setq i (+ i 1))) ; i:=i+1
  ergebnis)

Der erste Parameter der while-Primitive ist die Abbruchbedingung
der Schleife. Sie wird vor jedem Schleifendurchlauf abgefragt,
d.h. ausgewertet. Ergibt sich t, so werden alle nachfolgenden
Ausdrücke interpretiert und der Vorgang wiederholt sich. Ergibt
sich jedoch nil, so wird die Schleife mit dem letzten berechneten
Wert verlassen.

(while <Bedingung> <Ausdruck> [<Ausdruck>...])

Eine Endlosschleife sieht demnach so aus :

(while t <Ausdruck> [<Ausdruck>..])

In der Abbruchbedingung wird die Primitive <= verwendet. Wie eql
vergleicht sie zwei Zahlen, wird aber genau dann zu t, falls die
erste Zahl kleiner der zweiten ist.

Manchmal ist es erwünscht, zunächst die Operationen der Schleife,
also den sog. Schleifenrunpf abzuarbeiten und dann erst die
Abbruchbedingung zu testen. Für diesen Test am Schleifenende
steht die do-Primitive zur Verfügung.

(do <Bedingung> <Ausdruck> [<Ausdruck>...])

Mit ihr ändert sich die Fakultätsfunktion wie folgt:

(defun fakultaet (n &aux i ergebnis)
  (setq i (setq ergebnis 1))
  (do (<= i n)
    (setq ergebnis (* ergebnis i))
    (setq i (+ i 1)))
  ergebnis)

i muß nun mit 1 initialisiert werden, denn falls n=1 ist, würde
sonst ergebnis mit 2 multipliziert.

Bei der Fakultätsberechnung steht die Anzahl der Iterationen
schon beim Schleifenbeginn fest. Daher ist eleganter, hier eine
Zählschleife zu verwenden :

(defun fakultät (n &aux i ergebnis)
  (setq i (setq ergebnis 1))
  (count (- n 1)
    (setq ergebnis (* ergebnis (setq i (+ i 1)))))
  ergebnis)

Bei der count-Primitive gibt der erste Parameter die Anzahl der
Schleifendurchläufe an. Entsprechend oft werden die folgenden
Ausdrücke ausgewertet. Ist die Anzahl kleiner oder gleich 0, so
wird der Schleifenrumpf nicht interpretiert.

Schleifen sind in ALisp nicht effizienter als Rekursionen, da
intern in etwa die gleichen Vorgänge ablaufen.
Vor jedem Schleifendurchlauf wird eine komplette Kopie des
Rumpfes erzeugt, die dann interpretiert wird. Bei einer Rekursion
geschieht genau dasselbe.



Übungen

9. Programmieren Sie Aufgabe 6 nun mit den Schleifenstrukturen,
   d.h. iterativ. Führen Sie dies für alle Schleifenarten durch.



II.2.4. Logik

In den Schleifen und in der bedingten Anweisung wurden Vergleiche
benötigt. Speziell für den Umgang mit Wahrheitswerten gibt es die
folgenden Befehle :

(and <Wahrheitswert> <Wahrheitswert> [<Wahrheitswert>...])
(or <Wahrheitswert> <Wahrheitswert> [<Wahrheitswert>...])
(not <Wahrheitswert>)

Sie sind Verknüpfungen in einer Boolschen Algebra.

and wertet zu t aus, wenn alle Parameter zu t evaluieren, sonst
ergibt sich der Wert nil.

or wertet zu t aus, wenn mindestens ein Parameter zu t evaluiert,
sonst ergibt sich nil.

not negiert den Wahrheitswert, d.h. aus t wird nil und aus nil
wird t.

Gelegentlich wird auch die exor-Verknüpfung benötigt. Sie hat
zwei Parameter und wird wahr, wenn genau einer davon zu t und
genau einer zu nil auswertet. Sie läßt sich so realisieren :

(defun exor (a b)
  (and (or a b) (not (and a b))))

Vergleiche liefern Wahrheitswerte. Bekannt sind hier bereits eql
und <=. Insgesamt lassen sich Zahlen und Zeichenketten mit
>, >=, <, <= und eql vergleichen. Alle Primitive fordern zwei
Parameter.

Beliebige Atome, also auch Symbolnamen werden mit eq verglichen.
Stimmen sie überein, so wird t zurückgegeben. Zahlen sollten aber
nur mit eql untersucht werden, siehe dazu das Kapitel 'Zahlen und
Zeichenketten in ALisp'.

Mit equal werden beliebige Ausdrücke verglichen. Hier gelten die
Anmerkungen zu eq.

(setq a '(1 2 (3 4)))
(equal '(1 2 (3 4)) a) liefert t

Da es in Lisp für Symbole keine Typenbindung gibt, benötigt man
Befehle zum Feststellen, ob eine Liste oder ein Atom vorliegt:

(atom <Ausdruck>) wertet zu t aus, wenn mit Ausdruck ein Atom
vorliegt.

(listp <Ausdruck>) wird t bei Listen und Punktepaaren.

(null <Ausdruck>) wird nur dann t, wenn Ausdruck zu einer leeren
Liste oder zum Wahrheitswert nil auswertet. Damit kann not auch
durch null ersetzt werden. Die Umkehrung ist jedoch nicht
möglich, da not Wahrheitswerte als Parameter erwartet.

Der Vergleich von Listen führt zum nächsten Beispiel.
Ein Palindrom ist eine symmetrische Zeichenkette wie z.B. "otto"
oder "einnegermitgazellezagtimregennie".
Es soll nun ein Programm geschrieben werden, das feststellt, ob
eine Zeichenkette ein Palindrom ist.
Dabei sollen die Buchstaben in Listenform eingegeben werden, z.B.
so : (o t t o)
Die Lösung des Problems besteht nun darin, die Liste umzukehren
und mit der ursprünglichen zu vergleichen.

(defun vertausche (liste1 liste2)
  (cond ((null list1) liste2) ; liste1 wurde umgedreht
	   (t (setq liste2 (cons (car liste1) liste2))
	      (vertausche (cdr liste1) liste2))))

(defun palindrom (liste)
  (equal liste (vertausche liste nil)))

Die Funktion vertausche liest rekursiv die liste1 von vorne und
baut gleichzeitig liste2 von hinten auf. Der eigentliche Test in
palindrom reduziert sich auf die equal-Primitive.

(palindrom '(o t t o)) ergibt t.
(palindrom '(h a l l o)) ergibt nil.

Bei den Zeichenkettenoperationen werden wir eine komfortablere
Form dieses Programms erstellen, bei der man dann wirklich
Strings eintippen kann.


Übungen

10. Schreiben Sie eine Funktion mit zwei Parametern, die diese
    Oder-verknüpft und das Resultat zurückgibt. Dabei darf die
    Primitive or nicht verwendet werden, sie ist durch and und
    not zu ersetzen.

11. Schreiben Sie eine rekursive Funktion, die zwei Listen ver-
    gleicht, ohne equal zu benutzen. Die Listen dürfen wieder
    Unterlisten enthalten. Mit atom und listp können diese von
    Konstanten unterschieden werden.




II.3. Zahlen und Zeichenketten in ALisp


II.3.1. Das Zahlenkonzept von ALisp

Dieser Abschnitt geht speziell auf unseren Lisp-Dialekt ein. Bei
anderen Interpretern finden Sie aber auf jeden Fall die ganzen
Zahlen ähnlich wieder.

Computerspeicher ist endlich. Daher können prinzipiell nur
endlich viele Zahlen gespeichert werden. Bei den ganzen Zahlen
bedeutet dies, daß ihr Wertebereich auf [-2147483648,2147483647]
beschränkt ist. Für sie werden intern jeweils Worte zu 4 Bytes
angelegt.
ganze Zahlen sind z.B. -23, +4711, 50 , d.h. formal dürfen sie
mit einem optionalen Vorzeichen beginnen. Es schließt sich eine
nichtleere Folge von Ziffern an.

Weiterhin kennt ALisp rationale Zahlen, also Brüche. Diese sind
aus zwei ganzen Zahlen zusammengesetzt, die durch einen
Bruchstrich getrennt werden : -23/3, +4711/23456, 67/3
Nur die erste der beiden ganzen Zahlen darf vorzeichenbehaftet
sein. Innerhalb der Zahl darf kein Leerzeichen stehen, so wäre
-23 / 3 unzulässig, der Interpreter würde das Divisionszeichen
als die Primitive für die Division erkennen.

Fließkommazahlen werden in ALisp durch zwei ganze Zahlen
dargestellt, die durch einen Punkt getrennt sind : 23.123,
-6375.245, 3.1413
Auch hier darf innerhalb der Zahl kein Leerzeichen auftreten. So
würde bei 23 . 123 der Punkt als Zeichen für ein Punktepaar
interpretiert.
Prinzipiell lassen sich diese Dezimalbrüche auch durch die
Bruchzahlen darstellen. Aber der Wertebereich der
Fließkommazahlen ist - zu Lasten der Rechengenauigkeit - größer
als der der Bruchzahlen. So kann man hier auch eine
Exponentialschreibweise verwenden : 1.67 * 1012 wird in ALisp zu
1.67e12. Der Exponent (hier 12) darf ein negatives Vorzeichen
besitzen, der Kennbuchstabe e darf auch großgeschrieben werden.
Je nach Rechnerimplementation ist der Exponent eingeschränkt. Oft
wird er durch 5 Bits dargestellt, so daß er vom Betrage kleiner
bzw. kleinergleich 16 bleiben muß.

Die reellen Zahlen sind vollständig und dicht. Daher können
niemals alle Zahlen eines auch noch so kleinen Intervalls exakt
im Computer dargestellt werden. Bei den Fließkommazahlen
entstehen so Näherungen, die bei Rechnungen ev. zu großen Fehlern
führen können. Die Darstellung durch Bruchzahlen ist dagegen
exakt. Jedoch lassen sich natürlich auch hier lange nicht alle
Zahlen aus Q ausdrücken. Für den Zähler bzw. den Nenner gelten
nämlich die Einschränkungen der ganzen Zahlen. Da ALisp jedoch
selbstständig weitestmöglich kürzt, werden Zähler oder Nenner nur
selten sehr groß werden und damit den erlaubten Bereich
überschreiten.
Bei Bereichsüberschreitungen gibt der Interpreter aus
Effizienzgründen keine Warnungen. Sie können aber erkannt werden,
wenn beispielsweise Vorzeichen nicht mehr stimmen.

Neben diesen reellen Zahlentypen kennt ALisp komplexe Zahlen.
Komplexe Zahlen setzten sich aus zwei reellen beliebigen Typs
zusammen. Diese beiden Zahlen werden in eckige Klammern
eingeschlossen. Die erste stellt den Realteil, die zweite den
Imaginärteil dar.

45 + 12i wird geschrieben als [45 12].
1/3 - 3.1413i wird zu [1/3 -3.1413].


Rechnen mit den Zahlentypen

In Rechnungen mit den Grundrechenarten +, *, -, / dürfen alle
Darstellungsweisen beliebig gemischt auftreten. Dabei gelten die
folgenden Umwandlungsregeln :

-Sollen ganze Zahlen und Brüche verknüpft werden, ensteht ein
Bruch, falls sich dieser nicht zu einer ganzen Zahl kürzen läßt.

-Sollen ganze Zahlen oder Brüche mit Fließkommazahlen verknüpft
werden, so entstehen Fließkommazahlen

-Sollen reele mit komplexen Zahlen verknüpft werden, so enstehen
komplexe Zahlen, falls sich ihr Imaginärteil von 0i
unterscheidet.

Beispiele :

(+ 1 2/3)        ergibt 5/3
(+ 4/3 2/3)      ergibt 2
(+ 1.23 1/2)     ergibt 1.73
(* 2 [23 34])    ergibt [46 68]
(- 2 [23 34])    ergibt [-21 -34]
(+ [1 2] [3 4])  ergibt [4 6]
(* [1 2] [3 4])  ergibt [-5 10]

Daneben gibt es noch Befehle für einzelne Zahltypen :

Für ganze Zahlen : div und mod

(div <ganze Zahl><ganze Zahl>) dividiert die beiden Zahlen und
schneidet den Rest ab, es entsteht also wieder eine ganze Zahl.

(mod <ganze Zahl><ganze Zahl>) berechnet genau den
abgeschnittenen Rest.

(div 23 4) ergibt 5
(mod 23 4) ergibt 3

Für beliebige reelle Zahlen: sin, cos, atan, sqrt, exp, log

Diese Funktionen sprechen für sich, sqrt ist die Abkürzung für
Quadratwurzel. Sie erfordern einen Parameter. Ihr Ergebnis ist
eine Fließkommazahl.

Fehlende transzendente Funktionen wie tan lassen sich aus den
vordefinierten zusammensetzen :

(defun tan (x) (/ (sin x)(cos x)))

Definitionen für die wichtigsten Funktionen sind in der Datei
setup.lsp vorhanden. Wird ALisp durch Anklicken gestartet, so
werden diese Informationen automatisch mitgeladen.

Für komplexe Zahlen : car und cdr

Komplexe Zahlen werden von ALisp als Punktepaar behandelt :

				  /\
			  Realteil  Imaginärteil

Daher läßt sich der Realteil mit dem Befehl car und der
Imaginärteil mit cdr herausziehen.

Bei den Grundrechenarten finden Typumwandlungen gemäß den
genannten Regeln statt. Typumwandlungen zwischen Bruch- und
Fließkomma- und ganzen Zahlen lassen sich auch erzwingen :

(float <reelle Zahl>)   überführt die Zahl in Fließkommadarstellung
(nofloat <reelle Zahl>) wandelt die Zahl in eine Bruchzahl um.
(cast <reelle Zahl>)    rundet die Zahl zu einer ganzen Zahl.

z.B. (float 1/2)  ergibt 0.5


Da die gleiche Zahl sehr unterschiedlich dargestellt sein kann
( z.B 1 = 1.0 = [1 0] = 1/1 = [1.0 0.0] usw. )
und da diese Unterschiede auch zu einer verschiedenen internen
Repräsentation führen, sollten Zahlen nur mit der Primitive eql
auf Gleichheit getestet werden. Die anderen dafür vorgesehenen
Möglichkeiten (siehe Kap.II.4) verlangen formale Gleichheit, die
z.B. zwischen 1 und 1.0 nicht besteht.

Werden die Relationen >,>=,<,<= auf komplexe Zahlen angewendet,
so werden deren Beträge verglichen.

Zahlen evaluieren zu sich selbst. (Kap.II.1) Dies gilt
insbesondere für komplexe Zahlen. Hier ist es aber auch erlaubt,
den Real- sowie den Imagintärteil durch Symbole darzustellen.
Wird ein solches Konstrukt ausgewertet, so werden die Symbole
evaluiert. Dabei sollen reele Zahlen entstehen. Diese nehmen dann
die Position der Variablen ein.

(setq a 10) (setq b 2/3)
[a b] wird zu [10 2/3] ausgewertet.
[15 b] wird zu [15 2/3].

Jedoch führt [d e] zu einem Fehler, wenn d oder e nicht existiert
oder nicht zu einer Zahl auswertet.


Mit dem Zahlenkonzept von ALisp werden auch mathematische
Anwendungen ermöglicht, bei denen es auf genaue Ergebnisse
ankommt. Beispiele dafür finden Sie in Kapitel III.


Übungen

12. Welche der folgenden Zahlen sind korrekt gebildet ?

     +12.3		4711.32 	334e15
     -23.532e6		.212E4		23.54E12
     1/324		-324/213	+2134/-123
     34/17.03		[1/3 7.342e5]	[-27 28i]



II.3.2. Stringbefehle

Neben den Zahlen sind Zeichenketten die wichtigsten Konstanten.
Deshalb gibt es in ALisp eine Fülle von
Manipulationsmöglichkeiten.

(strcat <String1> <String2>) fügt die beiden Zeichenkette zu
einer zusammen.

(strcat "Zusammen" "fügen") ergibt "Zusammenfügen".

Interessant ist auch die Länge einer Zeichenkette, z.B. für
Sortierverfahren.

(strlen <String>) gibt die Anzahl der Zeichen des Strings wieder.

(strlen "Dies ist ein Test") ergibt 17.

Wir können bereits Zeichenketten verknüpfen. Nun möchte man aber
auch ein Werkzeug besitzen, um sie wieder zu trennen.

(substr <String> <Anfang> [<Länge>]) schneidet aus dem String die
Teilzeichenkette heraus, die mit dem Zeichen an der Position
Anfang beginnt und die Länge <Länge> besitzt. Wird keine Länge
angegeben, so reicht der Teilstring bis zum Ende des Strings.
Die Position des ersten Zeichens ist 0.

(substr "Hallo" 1 3) ergibt "all"
(substr "Hallo" 1)   ergibt "allo"

Es kann hilfreich sein, Zahlen in Strings und Strings in Zahlen
umzuwandeln.

(ascii <String>) berechnet aus dem ersten Buchstaben der
Zeichenkette eine Zahl

(chr <Zahl>) wandelt eine ganze Zahl in einen einelementigen
String, also in ein Zeichen um.

(ascii "abcde") ergibt 65
(chr 65) ergibt "a"

Die Umwandlung wird gemäß der ASCII-Tabelle vorgenommen. Dies ist
eine Zuordnung zwischen Tastatur- bzw. Steuerzeichen und den
Zahlen 0 bis 127. Sie finden eine Übersicht in den Handbüchern
zum Amiga.

Mit den neuen Befehlen läßt sich das Programm für die Erkennung
symmetrischer Zeichenketten (Palindrome) wesentlich komfortabler
gestalten.
Nun soll eine Zeichenkette und nicht eine Zeichenliste eingegeben
werden.
Um unsere bereits erstellte Funktion weiterzuverwenden,
generieren wir zunächst aus dem String die Liste einzelner
Zeichen:

(defun generiereListe (zeichenkette &aux i liste)
  (setq i 0)(setq liste nil)
  (while (< i (strlen zeichenkette))
	(setq liste (cons (substr zeichenkette i 1) liste))
	(setq i (+ i 1)))
 liste)

(defun vertausche (liste1 liste2)
  (cond ((null liste1) liste2)
	   (t (setq liste2 (cons (car liste1) liste2))
		 (vertausche (cdr liste1) liste2))))

(defun palindrom (zeichenkette &aux merke)
  (setq merke (generiereListe zeichenkette))
  (equal merke (vertausche merke nil)))

Die Funktion generiereListe liest den String zeichenweise von
vorne und verknüpft diese Zeichen zu eine Liste. Da die Liste
jedoch von hinten aufgebaut wird, kehrt sich die Reihenfolge der
Zeichen dabei um. Für die Palindromerkennung spielt das natürlich
keine Rolle. Somit ist der Rest des Programms - bis auf den
Aufruf von generiereListe - gleichgeblieben.

(palindrom "OTTO") ergibt t.
(palindrom "hallo") ergibt nil.


Übungen

13. In der Funktion generiereListe wird eine while-Schleife
    eingesetzt, obwohl die Anzahl der Durchläufe bereits zu
    Beginn bekannt ist. Die count-Variante bietet sich also an.
    Ändern Sie die Funktion entsprechend.

14. Bei Parsern soll ein eingegebener Text analysiert werden.
    Dazu werden zunächst die einzelnen, durch Leerzeichen
    getrennten Worte erkannt. Schreiben Sie eine Funktion, die
    einen String in eine Liste von Zeichenketten gemäß den im
    String auftretenden Leerzeichen zerlegt. Mehrere
    hintereinanderfolgende Leerzeichen sollen dabei wie ein
    einziges behandelt werden.




II.4. Ein/Ausgabe

Bisher haben wir mit unseren Programmen kommuniziert, indem wir
unsere Eingaben den Funktionen als Parameter übergeben haben.
Ausgaben können wir gezielt duch die Befehle princ und terpri
steuern, aber nach Beendigung der Interpretation einer Funktion
teilt uns auch das System das Ergebnis als Wert der Funktion mit:

>(setq a '(1 2 3))
(1 2 3)  [Ausgabe des Systems]
>(defun hallo () ())
 hallo	 [Ausgabe des Systems]

Bei palindrom ist dies ja auch erwünscht, denn sonst würden wir
das Ergebnis nicht erfahren.
Das Mitteilungsbedürfnis des Interpreters kann sich aber auch
störend auswirken. Bei der Definition einer Funktion mit defun
wird z.B. der Name der neuen Funktion zurückgegeben und damit in
der Regel ausgedruckt. So erscheint nach der Eingabe des
Palindrom-Programms die Liste seiner Funktionen auf dem
Bildschirm:

generiereListe vertausche palindrom

Möchte man nur durch princ und terpri erzeugte Ausgaben auf den
Bildschirm bringen, so verbietet (forbid) die übrigen Ausgaben
des Interpreters. Mit (allow) werden sie wieder gestattet.
Das linke Gadget in der Fußzeile des Eingabefensters informiert
über den momentanen Zustand.

Geben Sie z.B. (forbid) ein (oder klicken Sie das Gadget an).
Nach (setq a 10) folgt keine Antwort des Systems mehr. Tippen Sie
nun den Variablennamen a ein, so erfolgt auch nicht mehr die
Ausgabe des an a geketteten Wertes 10.

Die Befehle allow und forbid dienen aber alleine kosmetischen
Zwecken und beeinflussen die Interpretation überhaupt nicht.

Wichtiger ist da

(read [<Zeichenkette>])

Dieser Befehl liest eine Liste oder ein Atom ein und übergibt
sie/es als Wert. Wird kein Parameter benutzt, so wird die Eingabe
vom Benutzer über das Eingabefenster erwartet. Wird ein String
als Parameter angefügt, so wird der Ausdruck aus diesem String
gelesen.

(read "(a b c)") liefert (a b c)

Nach (read) erscheint eine Aufforderung zur Eingabe, die Sie wie
üblich im Eingabefenster verrichten.
Geben Sie mehrere getrennte Lispausdrücke an, so wird von read
nur der erste beachtet.

Wir können nun an das Palindrom-Programm die folgenden Zeilen
anfügen :

(princ "Bitte geben Sie eine Zeichenkette ein :")(terpri)
(palindrom (read))

Eingaben und Ausgaben können sich auch auf Peripheriegeräte
beziehen. Möchten Sie Daten in eine Datei auf Diskette schreiben,
so muß diese zunächst mit open eingerichtet werden :

(open <Dateinname>)

Dateiname ist eine Zeichenkette. In ihr kann der Geräte- und
Pfadname enthalten sein. Die Anweisung liefert einen
Wahrheitswert, der den Erfolg der Operation mitteilt.
Existiert bereits eine Datei des gewählten Namens, so wird sie
mit open überschrieben und damit zerstört !

Die neu eingerichtete Datei kann nun mit dem Befehl princdat
aufgefüllt werden.

(princdat <Ausdruck> [<Ausdruck>...])

princdat wirkt ansonsten wie princ. Es können solange Ausdrücke
in die Datei geschrieben werden, bis das Speichermedium voll ist.

Schließlich muß die Datei mit (close) geschlossen werden.
Es darf in ALisp immer nur eine Ausgabedatei geöffnet sein.
Deshalb benötigt die close-Primitive auch keinen Parameter.

Zum Lesen der Dateien steht der Befehl readdat zur Verfügung:

(readdat <Dateiname>)

Dateiname ist wieder eine Zeichenkette. Beim Lesen muß die Datei
nicht geöffnet oder geschlossen werden. readdat liest vielmehr
die komplette Datei aus und verknüpft alle Einträge zu einer
Liste. Diese Liste wird als Wert des Befehls zurückgegeben. Mit
den bekannten Listenoperationen können die einzelnen Einträge
dann bearbeitet werden:

(open "ram:test.dat")
(princdat "Dies ist ein Test")
(princdat '(a b c d) "Hallo")
(close)

(readdat "ram:test.dat") liefert
("Dies ist ein Test" (a b c d) "Hallo").

Mit killfile können schließlich Dateien gelöscht werden
(Vorsicht!!!).

(killfile <Dateiname>), z.B. (killfile "ram:test.dat")

Schließlich dient der bereits angesprochene Befehle load dazu,
Lispprogramme zu laden und mit ihrer Auswertung zu beginnen. load
teilt in Form eines Wahrheitswertes mit, ob das gewünschte File
geladen werden konnte.

(load <Dateiname>)

Dabei werden die Daten bei ALisp zunächst in einen Puffer
geladen, der auf die Größe 40000 Bytes voreingestellt ist.
Längere Dateien können somit nicht komplett eingelesen werden und
müssen geteilt werden.
Dies ist auch aus Übersichtlichkeitsgründen sehr sinnvoll. Bei
großen Projekten sollten zusammengehörige Teile in eigenen
Dateien, sog. Moduln untergebracht werden. Die Verkettung der
einzelnen Dateien kann dadurch geschehen, daß als letzte
Anweisung jedes Files die Ladeoperation (load "Name des
Folgemoduls") für das nächste steht.


In anderen Lisp-Dialekten werden Dateien besser unterstützt, so
gibt es dort z.B. Datenströme. Mit den in ALisp existierenden
Dateibefehlen läßt sich aber dennoch arbeiten.


Übungen

15. Schreiben Sie die Funktion copy, die eine Lisp-Datei in eine
    andere kopieren kann. Dabei soll copy die Namen der Dateien
    direkt mit read vom Benutzer erfahren.



II.5. Grafik

ALisp besitzt einige mächtige Grafikbefehle.
Grafiken werden in einem extra Fenster erstellt. Dieses Fenster
wird mit (graphic) geöffnet. Wird es nicht mehr benötigt, sorgt
(text) für die Schließung. Das Grafikfenster kann auch über einen
Menüpunkt erzeugt werden.
Da die Grafik einen Teil des Dialogfensters überdeckt, werden die
Ausgaben nun so umformatiert, daß man sie noch lesen kann. Beim
Schließen des Fensters oder beim Blättern in den Ausgaben wird
wieder zur alten Darstellung übergegangen.

Die Punkte im Grafikfenster besitzen Koordinaten. Der Ursprung
des Koordinatensystems liegt in der Fenstermitte. Auf der
horizontalen Achse dürfen die Koordinaten aus dem Intervall
[-218,218] stammen, auf der vertikalen aus [-190,190].

Der zentrale Grafikbefehl ist draw.

(draw <Wahrheitswert1><Wahrheitswert2><Zahl1><Zahl2><Zahl3>)

zeichnet eine Linie ausgehend von der aktuellen Zeichenposition
in der Farbe des über Zahl1 gewählten Registers. Insgesamt stehen
vier Farbregister (0 bis 3) zur Verfügung. Ihre Farben können mit
dem Befehl

(rgb <Registernummer> <Rotanteil> <Grünanteil> <Blauanteil>)

gesetzt werden. Jede Farbe ist eine Mischung aus Rot, Grün und
Blau. Die Anteile dieser Grundfarben können im Bereich [0,15]
gewählt werden. 15 ist der maximale Anteil. Insgesamt stehen also
4096 Farben zur Auswahl.

Der draw-Befehl kennt vier verschiedene Koordinatendarstellungen.
Sie werden mit den beiden Wahrheitswerten gewählt.

Die aktuelle Zeichenposition sei die Stelle mit den Koordinaten
(x,y).

Wahrheitswert	Bedeutung der Zahlen 2 und 3
  1	2

  t	t		Es wird zum Punkt mit den Koordinaten
			(Zahl2,Zahl3) gezeichnet
 nil	t		Es wird zum Punkt mit den Koordinaten
			(Zahl2+x,Zahl3+y) gezeichnet (relative oder
			inkrementelle Koordinaten)
  t    nil		Es wird zu einem Punkt in der Entfernung Zahl3
			gezeichnet. Die dabei entstehende Strecke
			schließt mit der positiven horizontalen Achse den
			Winkel Zahl2 in Grad gemessen ein.
 nil   nil		Wieder wird zu einem Punkt in der Entfernung Zahl3
			gezeichnet. Die Strecke schließt mit der pos.
			horizontalen Achse den Winkel Zahl2+delta ein,
			wobei delta der Winkel der letzten gezeichneten
			Strecke mit der horizontalen Achse ist.
			(Winkelangaben relativ)

Der draw-Befehl zeichnet also bei einer aktuellen Position
beginnend. Um an einer beliebigen Stelle (x,y) loszuzeichnen,
kann man mit (draw t t -1 x y) den Zeichenstift dorthin bewegen.
Die Farbregisterwahl -1 bedeutet, daß nicht gezeichnet wird.
Entsprechend kann auch ein Ausgangswinkel definiert werden :
(draw t nil -1 Ausgangswinkel 0)
Alle Werte sind auf 0 voreingestellt.

Um die aktuelle Zeichenposition bzw. den aktuellen Zeichenwinkel
auslesen zu können, gibt der Befehl bei Wahrheitswert2=t die
Ausgangskoordinaten der Strecke als Punktepaar und bei
Wahrheitswert2=nil den Ausgangswinkel zurück.

Der erste Wahrheitswert wählt offensichtlich zwischen absolutem
und relativem Verhalten, der zweite zwischen kartesischen und
Polarkoordinaten. Daher verbessert es die Lesbarkeit, für die
Auswahl Symbole zu definieren :

(setq ABSOLUT t)
(setq RELATIV nil)
(setq KARTESISCH t)
(setq POLAR nil)

Im Modus ABSOLUT-KARTESISCH können sehr elegant Polygone
gezeichnet werden. Nachdem der Zeichenstift an die Startposition
gebracht wurde, müssen nur noch alle Eckpunkte angefahren werden:

(graphic)
(draw t t -1 -30 -30)
(draw t t  1   0  30) ; Diese Anweisungen erzeugen ein Dreieck.
(draw t t  1  30 -30)
(draw t t  1 -30 -30)

Im Modus RELATIV-KARTESISCH wird das Dreieck dann so konstruiert:

(draw t t -1 -30 -30)
(draw nil t 1 30  60)
(draw nil t 1 30 -60) ; Angabe der Koordinatendifferenzen
(draw nil t 1 -60  0)

Bei den beiden POLAR-Modi ist der Modus RELATIV-POLAR besonders
interessant. Er entspricht der Turtle-Grafik von Logo.

Bei der Turtle-Grafik kann man sich den Zeichenstift als
Schildkröte vorstellen. Ein draw Befehl bewirkt nun, daß sie sich
um den angegebenen Winkel dreht und die angegebene Streckenlänge
zurücklegt und dabei ihren Weg einzeichnet. Positive Winkel
bedeuten Drehung im mathematisch positiven Sinn, d.h. gegen den
Uhrzeigersinn, negative bedeuteten Drehung im Urzeigersinn.
Wir werden zwei sehr schöne Beispiele für Turtle-Grafik gleich
behandeln.
Zuvor aber noch die restlichen Grafikbefehle und ein anderes
Beispiel :

(clear) löscht den Inhalt des Grafikfensters.

(ellipse <Farbregister> <x> <y> <hradius> <vradius>)

ellipse zeichnet eine Ellipse in der gewählten Farbe um den
Mittelpunkt (x,y). hradius gibt den horizontalen und vradius den
vertikalen Radius der Kurve an. Wählt man hradius=vradius, so
entsteht ein Kreis.

(fill <Farbregister> <x> <y>)

fill füllt die Fläche, in der der Punkt mit den Koordinaten (x,y)
liegt mit der gewünschten Farbe aus.

(polygon <Farbe> <x-Koordinate><y-Koordinate>
			 [<x-Koordinate><y-Koordinate>...] )

polygon zeichnet ein ausgefülltes Vieleck, dessen Koordinaten
gemeinsam mit der Zeichenfarbe übergeben werden. Dabei muß der
Startpunkt nur einmal angegeben werden, der Linienzug wird
automatisch geschlossen.
(polygon 1 0 0 100 0 100 100 0 100) zeichnet ein Quadrat mit der
Farbe des Registers 1. In der Liste wird zu jedem Punkt erst die
horizontale und dann die vertikale Position angegeben.

Die Befehle fill und polygon benötigen zum Ausfüllen der Objekte
viel Arbeitsspeicher. Kann dieser bei der Auswertung vom
Betriebssystem nicht mehr bereitgestellt werden, so wird eine
entsprechende Fehlermeldung ausgegeben.

Schließlich möchte ich noch den random-Befehl hier einführen.

(random <Zahl>)

Mit dieser Primitive erhält man eine Zufallszahl aus dem
Intervall [0, Zahl). Zahl muß reell und größer 0 sein.

Sie werden jetzt sicherlich zu Recht fragen, was dieser Befehl im
Grafik-Kapitel zu suchen hat.
Nun, ich benötige ihn für die folgende erste Anwendung des draw-
Befehls:

Durch drei Eckpunkte ist ein Dreieck definiert. Die
Zeichenposition soll in einem der Eckpunkte liegen. Nun wird
zufällig ein Eckpunkt ausgewählt und die Zeichenposition in die
Mitte der Verbindungsstrecke zwischen alter Zeichenposition und
dem gewählten Eckpunkt gelegt. Die Position wird durch einen
Punkt markiert. Wieder wird ein Eckpunkt ausgewählt, wieder wird
die Mitte der Verbindungsstrecke zwischen bisheriger Position und
neuem Eckpunkt zur neuen Position und damit durch einen Punkt
markiert.
Führt man diesen Algorithmus sehr oft aus, so entsteht ein
verblüffendes, selbstähnliches Bild : Sierpinski-Dreiecke.

Das Programm dazu :

(graphic)
(clear)
(fill 3 0 0) ; damits´ schöner ausschaut

; neupos berechnet die Streckenmitte
(defun neupos (xeck yeck)
  (setq x (+ x (/ (- xeck x) 2.0)))
  (setq y (+ y (/ (- yeck y) 2.0))))

; zeichnen ist die Hauptfunktion
(defun zeichnen (&aux x y z) ; x,y bezeichnen den aktuellen Punkt
  (setq x 200.0)(setq y 190.0) ; Startpunkt wählen
  (count 20000  ; 20000-mal den Streckenmittelpunkt einzeichnen
    (setq z (random 3)) ; zufällig neuen Eckpunkt bestimmen
    (cond ((< z 1.0)(neupos -200.0 -190.0)) ;Eckpunkt 1
		((< z 2.0)(neupos -200.0  190.0)) ;Eckpunkt 2
		(t              (neupos  200.0  190.0)));Eckpunkt 3

    (draw ABSOLUT KARTESISCH -1 x y)
    (draw RELATIV KARTESISCH  1 0 0) ; einen Punkt setzen
)
(terpri)
(zeichnen)

Man beachte :

-In der Funktion neupos sind die Variablen x und y zur Laufzeit
bekannt. Denn die sind lokal in zeichnen, neupos wird aber nur in
zeichnen aufgerufen.

-Es wurden Fließkommazahlen gewählt. Der Wertebereich von
Bruchzahlen reicht hier nicht aus. Ist der Zähler der aktuellen
Position einmal ungerade, so kommt es schnell zu einem Überlauf
des Nenners. Denn es wird fortlaufend durch 2 dividiert, Kürzen
ist aber nicht möglich.



Nun soll aber auch die Turtle-Grafik nicht zu kurz kommen:

Definieren wir uns zunächst Funktionen mit sprechenden Namen,
statt des draw-Befehls :

(defun forward (Farbe Länge)
   (draw RELATIV Polar Farbe 0.0 Länge))

(defun turn (Winkel)
   (draw RELATIV POLAR -1 Winkel 0.0))

forward bewegt die Schildkröte vorwärts und turn dreht sie.

Im Rahmen des Bundeswettbewerbs Informatik wurden zwei sehr
schöne Turtle-Grafik-Aufgaben gestellt, die ich Ihnen nicht
vorenthalten möchte:

Der Baum des Pythagoras wird mit Quadraten aufgebaut, die sich um
rechtwinklige Dreiecke mit den Seitenverältnissen 3:4:5
gruppieren. Es ist ein Programm zu schreiben, daß diesen Baum,
wie er in der folgenden Abbildung zu sehen ist, erzeugt. Die
Verästelungen sollen soweit gezeichnet werden, bis die
Bildschirmauflösung erreicht ist.


Die eleganteste Lösung :

Mit der Turtlegrafik werden die Quadrate gezeichnet, die Turtle
wird dann so gedreht, daß der erste Kathetenbaum mit der gleichen
Funktion entstehen kann. Anschließend wird sie für den zweiten
Teilbaum zurechgedreht, und dieser wird gezeichnet.
Damit sieht die Lösung der des Hanoi-Spiels sehr ähnlich aus:

zeichne Baum :
- zeichne Quadrat
- zeichne rechten Teilbaum
- zeichne linken Teilbaum


Ausformuliert in ALisp :

(defun baum_zeichnen (seitenlänge &aux rechtes_Quadrat
				       linkes_Quadrat)
  (count 4
	(forward 1 seitenlänge) ; ein Quadrat zeichnen
	(turn -90.0)
  )

  (setq rechtes_Quadrat (* 4/5 seitenlänge)) ; Größen der Folge-
  (setq linkes_Quadrat (* 3/5 seitenlänge))  ; quadrate berechnen

  (cond ((>= linkes_Quadrat 2.0) ; Bildschirmauflösung erreicht ?
    (forward -1 seitenlänge); zur Startposition des ersten
    (turn -36.87); Unterquadrats fahren, -36.87 ergibt sich aus
			  ; dem Verhältnis 3:4:5 über sin bzw. cos.
    (baum_zeichnen rechtes_Quadrat)
    (forward -1 rechtes_Quadrat)    ; zur Position des zweiten
    (turn 90)                       ; Quadrats fahren
    (baum_zeichnen linkes_Quadrat)
    (turn 180.0)                    ; und zum Schluß noch zur
    (forward -1 rechtes_Quadrat)    ; Ausgangsposition
    (turn -53.13)                   ; zurückfahren...
    (forward -1 seitenlänge)
    (turn 180.0)                    ; ...angekommen
  )
)

(graphic)
(draw ABSOLUT KARTESISCH -1 0 -160) ;Startposition definieren
(draw ABSOLUT POLAR -1 90.0 0)
(baum_zeichnen 70) ; das erste Quadrat hat Seitenlänge 70

Sie können leicht die Grafikbefehle auf Papier nachvollziehen, um
so den Algorithmus besser zu verstehen.

Ohne Turtle-Grafik ist erheblich mehr Mühe in das Finden eines
geeigneten Algorithmus zu investieren. Das folgende Programm
berechnet zu zwei Punkten, die die Grundlinie eines Quadrats
bilden, die beiden restlichen Eckpunkte des Quadrats und den noch
fehlenden Eckpunkt des aufgesetzten rechtwinkligen Dreiecks. Mit
diesen Daten wird dann das Quadrat gezeichnet und die Funktion
ruft sich für die beiden Teilbäume mit den Informationen über die
drei errechneten Punkte selbst auf. So entsteht auch hier der
Baum des Pythagoras. Zur Abwechselung allerdings zum ersten
Programm gespiegelt. Die Quadrate werden mit der polygon-
Anweisung ausgefüllt. Die Hilfsfunktion abs berechnet den
Absolutbetrag einer reellen Zahl.


(defun abs (x) (cond ((>= x 0.0) x) (t (* -1.0 x))))

(defun zeichneBaum (x1 y1 x2 y2 &aux x3 y3 x4 y4 x5 y5)
  (cond ((or (> (abs (- x2 x1)) 2.0)  ;Auflösung nich nicht
		(> (abs (- y2 y1)) 2.0)) ;erreicht
    (setq x3 (+ x2 (- y1 y2))) ; hier die beiden restlichen
    (setq y3 (+ y2 (- x2 x1))) ; Eckpunkte des Quadrats
    (setq x4 (+ x1 (- y1 y2))) ; berechnen
    (setq y4 (+ y1 (- x2 x1)))
    (setq x5 (+ x3 (* 0.12 (+ x3 (* 3.0 x4)(* -4.0 x2)))))
    (setq y5 (+ y3 (* 0.12 (+ y3 (* 3.0 y4)(* -4.0 y2)))))
    ; hier wurde der noch fehlende Dreieckspunkt berechnet
    (polygon 1 x3 y3 x2 y2 x1 y1 x4 y4) ; Quadrat zeichnen
    (zeichneBaum x4 y4 x5 y5)  ;linken und
    (zeichneBaum x5 y5 x3 y3)) ;rechten Teilbaum zeichnen
  )
)

(graphic)
(zeichneBaum 10.0 -80.0 60.0 -80.0)

Wollen Sie diesen Algorithmus nachvollziehen, so werden Sie
zunächst bei der Berechnung von x5 und y5 Schwierigkeiten
bekommen. Diese Formeln ergeben sich aus der Trigonometrie des
Dreiecks. Offensichtlich ist die Turtle-Grafiklösung einsichtiger
und sie ist sogar etwas schneller.


Übungen

16. Mit dem polygon-Befehl lassen sich ausgefüllte Dreiecke
    erzeugen. Schreiben Sie eine Funktion, die die Farbe und
    die Position der Eckpunkte von 1000 Dreiecken zufällig
    auswählt und die Dreiecke einzeichnet.


Das zweite Beispiel entstammt dem 6. Bundeswettbewerb Informatik:

Schildkröten tanzen gelegentlich einen merkwürdigen Tanz. Dabei
entscheiden sie sich zunächst für ein Schrittmuster, z.B. für
"vor-rechts-vor-links-vor-vor". Bei diesem Muster legt die
Schildkröte diesen Weg zurück :

     _	 __		       Nachdem das Schrittmuster
      |_|		       getanzt ist, dreht sich
			       die Schildkröte um einen
bestimmten Winkel und tanzt es nochmals. Sie fährt damit solange
fort, bis sie wieder ihren Startpunkt erreicht hat. Die
Drehwinkel sollen also Teiler von 360 Grad sein. Danach tanzt die
Schildkröte über jeder Strecke des ersten Durchlaufs noch ein
komplettes Grundmuster. Beim dritten Umlauf werden die Strecken
des zweiten mit dem Grundmuster überdeckt. Der Tanz setzt sich so
beliebig lange fort.

Nun soll ein Programm erstellt werden, das das Muster der
Schilkröte eines beliebigen Durchlauf zeichnet.


Das folgende Programm erzeugt diese Grafik:

; tanze führt einen kompletten Tanzschritt mit allen
; erforderlichen Verfeinerungen aus:
(defun tanze (n &aux i) ;n gibt die Verfeinerungstiefe an
  (setq i 1)
  (count anzahl ;Nacheinander alle Schritte ausführen
    ; zunächst Richtung des nächsten Schritts einnehmen
    (cond ((eq (nth i schritte) 'rechts) (turn -90.0))
		((eq (nth i schritte) 'links ) (turn  90.0)))
    ; den Schritt machen oder enstprechend verfeinern
    (cond ((< n maxN) (tanze (+ n 1)))
		(t (forward 1 laenge)))
    ;in die Ausgangsrichtung zurückdrehen
    (cond ((eq (nth i schritte) 'rechts) (turn  90.0))
		((eq (nth i schritte) 'links ) (turn -90.0)))
    (setq i (+ i 1))
  )
)

; in der folgenden Funktion werden die Daten für das obige
; Beispiel gesetzt, die Tanzschritte und Drehungen werden
; zusammengesetzt

(defun TanzDerSchildkröte (&aux wi winkel)
  (setq anzahl 6) ; 6 Tanzschritte
  (setq schritte '(vor rechts vor links vor vor)) ; Schrittfolge
  (setq maxN (- 3 1)) ; 3-ter Umlauf
  (setq wi 0)(setq winkel 72) ;Drehungen vorbereiten
  (draw ABSOLUT KARTESISCH -1 -60 -120) ; zur Startposition gehen
  (draw ABSOLUT POLAR -1 0 0) ;Startwinkel festlegen
  (while (< wi 360)
    (tanze 0)                           ;Schritte gefolgt von Drehungen
    (turn winkel)
    (setq wi (+ wi winkel))
  )
)

(graphic)
(TanzDerSchildkröte)

Das Programm bedarf eigentlich keiner weiteren Dokumentation. Es
ist hier besonders schön, daß die Folge der Tanzschritte direkt
als Klartext in Listenform übergeben werden kann.



II.6. weitere Befehle

In diesem Abschnitt möche ich die noch fehlenden ALisp-Primitiven
aufführen.

weitere Listenbefehle :

(append <Liste1> <Liste2>)

append fügt die beiden Listen zu einer neuen zusammen, indem
Liste2 an Liste1 gehängt wird. Die gemeinsame Liste wird als Wert
von append zurückgegeben.

(append '(a b c) '(1 2 3 4)) ergibt (a b c 1 2 3 4)
(append '() '(a b c)) und
(append '(a b c) '()) ergeben (a b c)

(exchange <Position> <Liste> <Ausdruck>)

exchange ersetzt das mit Position bezeichnete Listenglied durch
den den angegebenen Ausdruck. Dabei hat das erste Listenglied die
Position 1. Die so beschaffene neue Liste wird als Wert der
Funktion zurückgegeben.

(exchange 3 ("A" "B" "C" "D" "E")) ergibt ("A" "B" "E" "D").


Systemfunktionen :

(kill <Symbolname>)
(killq /Symbolname/)

Diese beiden Funktionen bilden das Gegenstück zu set und setq.
Mit ihnen können Symbole wieder aus dem Speicher entfernt werden.
Analog zu set und setq wird der Parameter von killq nicht, der
von kill jedoch ausgewertet.
Symbole können nur dann gelöscht werden, wenn sie gerade keine
lokale Inkarnationen besitzen. D.h. auf Parameter und mit &aux -
deklarierte Symbole darf kill/killq nicht angewendet werden.
Diese werden schließlich beim Verlassen ihres zugehörigen Lambda-
Terms automatisch gelöscht, sind dann also nicht mehr sichtbar.
Mit diesen Befehlen kann der Speicher nach Beendigung eines
Programms aufgeräumt werden.


(free)

free zeigt die aktuelle Speicherbelegung an. Diese Funktion kann
auch über einen Menüpunkt aufgerufen werden.
Im Arbeitsspeicher werden die beiden elementaren Knotentypen
Atome und Punktepaare verwaltet. (siehe Abschnitt II.1)
Daneben wird zu jedem Symbol noch ein sog.
Variablenverkettungsknoten angelegt. Die Anzahlen dieser Knoten
werden bei free mitgeteilt. Daneben wird noch die Menge des
gesamten bisher für die Arbeit reservierten Computerspeichers und
dessen belegter Anteil mitgeteilt. Rufen Sie den Befehl free
mehrmals hintereinander auf, so werden beim noch freien Speicher
unterschiedliche Werte angezeigt. Dies liegt daran, daß natürlich
auch free Speicher benötigt, jedoch nur gelegentlich der
Arbeitsspeicher vom Müll überflüssig gewordener Informationen
bereinigt wird. (Garbage-Collection)
Das Fenster zum Menüpunkt 'Variablen bearbeiten' bietet in seiner
Kopfzeile ebenfalls die Informationen von free. Hier werden
zunächst die Zahlen der Atome, Punktepaare und dann die der
Variablenverkettungsknoten aufgezählt. Es folgt die Summe dieser
Zahlen. free gibt keinen Wert zurück.


(varlist)

Nach Aufruf dieser Primitive wird die Liste aller Symbolnamen
ausgedruckt. varlist gibt keinen Wert zurück.
Die Funktion kann auch über den entprechenden Menüpunkt
ausgeführt werden.


(progn <Ausdruck> [<Ausdruck>...])

progn fügt Ausdrücke zu einer Einheit zusammen. Wird die
Anweisung ausgewertet, so ist dies gleichbedeutend mit der
Einzelauswertung der Parameter. progn ist damit ein Mittel der
Strukturierung zusammengehöriger Programmteile. Außerdem kann
zwischen der Auswertung der Parameter keine Garbage-Collection,
also keine Speicherumorganisation stattfinden, während sie bei
einer Einzelauswertung der Ausdrücke auftreten kann. Daher dient
progn auch der Programmbeschleunigung, falls noch genügend
Speicher vorhanden ist.

(progn "Hallo" (+ 1 2) 23) bewirkt die Ausgabe "Hallo"  3  23.
Semantisch äquivalent ist also die Programmzeile

"Hallo" (+ 1 2) 23


Jetzt kennen Sie fast alle ALisp-Befehle. Der letzte ist eine
Gedächtnisstütze :

(help [<Befehlsname>])

Die help-Anweisung gibt Auskunft über den gewünschten Befehl,
dessen Name als String übergeben wird :

(help "car") liefert eine Beschreibung von car.

Daneben kann help auch ohne Parameter aufgerufen werden. Dann
zeigt die Primitive die Liste aller implementierten Befehle an.

help bezieht seine Informationen aus einer Datei namens
ALisp.help, die sich im Verzeichnis help der Diskette befindet.
Möchten Sie ALisp von einer anderen Diskette oder von Festplatte
aus starten, so sorgen Sie bitte dafür, daß sich dieses
Verzeichnis auf der zum Zeitpunkt des Aufrufs aktiven Diskette
oder Partition befindet. Andernfalls kann help nicht ausgeführt
werden.


Übungen

17. Schreiben Sie eine Funktion, die in einer beliebigen
    Schachtelung von Listen jedes Auftreten eines zu übergebenden
    Lisp-Ausdrucks durch einen andernen ersetzt.
    Benutzen Sie dabei einmal den Befehl exchange, realisieren
    Sie die Funktion aber auch einmal nur mit den elementaren
    Listenoperationen.




III. Programmbeispiele
----------------------


III.1. Sortieren

Wir möchten uns hier mit dem Sortieren von Listen beschäftigen.
Dies ist eine Aufgabe, die immer wieder benötigt wird und den
Umgang mit Listen trainiert.

Eine Vorstufe des Sortierens ist das Suchen. So soll z.B.
festgestellt werden, ob ein bestimmter Wert Glied einer Liste
ist. Eine passende Funktion sieht so aus:

(defun suche (liste wert)
  (cond ((null liste) nil)
	   ((eql (car liste) wert) t)
	   (t (suche (cdr liste) wert))))

Die Liste wird rekursiv durchsucht, falls das erste Element nicht
mit dem zu suchenden Wert übereinstimmt, wird die Funktion auf
die Restliste angewendet. Es wird spätestens abgebrochen, wenn
alles durchforstet ist.

Diese Funktion verarbeitet sowohl Zahlen als auch Zeichenketten
als Listenglieder. Allerdings sollten diese Typen nicht gemischt
auftreten. (vgl. eql)

>(suche '(1 2 3 4 5) 4)
t

>(suche '("alpha" "beta" "gamma") "delta")
()

Einige Sortieralgorithmen basieren auf der Suche, so z.B.

Sortieren durch direkte Auswahl.

Dabei wird in der Liste zunächst das kleinste Element gesucht,
anschließend das zweitkleinste usw. Die so ermittelten Werte
werden zu einer aufsteigend sortierten Liste zusammengefaßt :

		Ausgangsliste			Ergebnisliste
		(6 7 6 3 9 8)                   ()
		(6 7 6 9 8)                     (3)
		(7 6 9 8)                       (3 6)
		(7 9 8)                         (3 6 6)
		(9 8)                           (3 6 6 7)
		(9)                             (3 6 6 7 8)
		()                              (3 6 6 7 8 9)




; StraightSelection

(defun sucheKleinstes (liste merke); merke ist bisher kleinstes
  (cond ((null liste) merke)
	((< (car liste) merke)
	 (sucheKleinstes (cdr liste)(car liste)))
	(t (sucheKleinstes (cdr liste) merke))))

(defun entferneKleinstes (liste kleinstes)
  (cond ((eql (car liste) kleinstes) (cdr liste))
	(t (cons (car liste)
		 (entferneKleinstes (cdr liste) kleinstes)))))

(defun StraightSelection (liste &aux merke)
  (cond ((null liste) nil)
	(t (setq merke (sucheKleinstes (cdr liste) (car liste)))
	   (cons merke (StraightSelection
			 (entferneKleinstes liste merke))))))

Gesucht wird hier mit der Funktion sucheKleinstes. Sie erhält
beim Aufruf die zu durchsuchende Liste ab dem zweiten Element und
getrennt davon das erste Element. Dieses stellt das zur Zeit
kleinste Glied dar. Nun werden fortlaufend rekursiv die
restlichen Glieder mit dem bisher kleinsten verglichen. Ist ein
Glied noch kleiner, so trifft der zweite Fall der cond-Primitive
zu, und ab sofort wird mit diesem Glied weitergearbeitet.
Nachdem alle Glieder berücksichtigt wurden, trifft der erste
cond-Fall ein, und der Wert des kleinsten Gliedes wird
zurückgegeben. Die Funktion entferneKleinstes erstellt die Kopie
einer Liste, jedoch fehlt in ihr das zu übergebende kleinste
Glied genau einmal. Mit sucheKleinstes kann so auch das
zweitkleinste, drittkleinste etc. Element berechnet werden, indem
mit entfereneKleinstes das vorangehende Ergebnis gerade aus der
Liste entfernt wird.
Die Funktion StraightSelection sortiert schließlich die Liste,
indem sie fortlaufend von den beiden anderen Funktionen Gebrauch
macht.

Das Gegenstück zur direkten Auswahl ist das direkte Einfügen.

Hier wird die Ausgangsliste Glied für Glied ausgelesen. Die
ausgelesenen Werte werden an die richtigen Stellen  der
entstehenden sortierten Liste eingefügt.

		Ausgangsliste			Ergebnisliste
		(6 7 6 3 9 8)                   ()
		(7 6 3 9 8)                     (6)
		(6 3 9 8)                       (6 7)
		(3 9 8)                         (6 6 7)
		(9 8)                           (3 6 6 7)
		(8)                             (3 6 6 7 9)
		()                              (3 6 6 7 8 9)

; Insertsort

; inssort sortiert element in liste ein
; liste muß dabei bereits sortiert sein

(defun inssort (element liste)
   (cond ((eq liste nil) (cons element nil))
			 ;element ist <= allen anderen in liste
	 (t (cond ((>= element (car liste))
			 ;muß hier element einsortiert werden ?
		     (cons (car liste)
			   (inssort element (cdr liste))))
		  (t (cons element liste))))))

; sort iteriert diesen Vorgang für alle Elemente einer Liste

(defun sort (unsortierte_Liste &aux sortierte_Liste)
   (setq sortierte_Liste nil) ;initialisieren
   (while (not (eq unsortierte_Liste nil)) ;Liste durchlaufen
     (setq sortierte_Liste
	   (inssort (car unsortierte_Liste) sortierte_Liste))
     (setq unsortierte_Liste (cdr unsortierte_Liste)))
   sortierte_Liste ;Die sortierte Liste wird zurückgegeben
)

Die Funktion sort liest nacheinander die Elemente der
Ausgangsliste und fügt diese mit inssort in die entstehende
sortierte Liste ein.
Entsprechend durchläuft inssort die sortierte Liste bis zu der
Stelle, an der das neue Element stehen muß. Dabei wird beim
Durchlaufen rekursiv bereits die Liste mit dem neuen Element
erzeugt.

Zu den einfachen Sortieralgorithmen zählt auch das

Sortieren durch direktes Austauschen, auch Bubblesort genannt.

Bei dieser Sortiermethode werden benachbarte Listenglieder dann
ausgetauscht, wenn sie in falscher Reihenfolge stehen. Diese
Vertauschungstests werden nacheinander in einem Durchlauf auf
alle benachbarten Gliederpaare der Liste angewendet. Beginnt man
dabei vorne, so steigt das größte Element wie eine Blase an das
Ende der Liste, daher der Name Bubblesort. Nach weiteren
Durchläufen sind auch die nächstgrößeren Glieder an den richtigen
Stellen angelangt, und schließlich ist die Liste sortiert.

Beim ersten Durchlauf entwickelt sich die Liste also so:

		(5 3 6 3 1 4)   Die Unterstriche deuten Vergleiche an.
		(3 5 6 3 1 4)   Das größte Element, hier die 6, wandert
		(3 5 6 3 1 4)   an die letzte Position.
		(3 5 3 6 1 4)   Beim nächsten Durchlauf müssen nur noch
		(3 5 3 1 6 4)   die ersten 5 Glieder betrachtet werden.
		(3 5 3 1 4 6)

In ALisp kann der Algorithmus wie folgt definiert werden:

(defun Durchlauf (liste) ;liste muß hier mind. 1-elementig sein
  (cond ((null (cdr liste))
	   (setq sortierteListe
			  (cons (car liste) sortierteListe)) nil)
	((> (car liste)(cadr liste)) ;Vertauschung nötig
	 (cons (cadr liste)
			(Durchlauf (cons (car liste)(cdr (cdr liste))))))
	(t (cons (car liste)(Durchlauf (cdr liste))))
  )
)

(defun Sort (liste)
  (cond ((null liste) nil)
	(t (Sort (Durchlauf liste)))))

(defun BubbleSort (liste)
  (setq sortierteListe nil)
  (Sort liste)
  sortierteListe)

Die Funktion Durchlauf durchläuft die Liste einmal und vertauscht
dabei gegebenenfalls Nachbarn. Das so gewonnene letzte Element
wird abgespalten und vor das bisherige Ergebnis sortierteListe
angefügt. Sort iteriert diesen Vorgang, bis die Ausgangsliste
leer ist. In der Funktion BubbleSort wird schließlich die
Ergebnisliste initialisiert, Sort aufgerufen und das Ergebnis
zurückgegeben.

Bei dieser Implementation treten ev. sinnlose Durchläufe auf,
z.B. wenn die Liste bereits sortiert ist. Denn nachdem bei einem
Durchlauf überhaupt keine Vertauschungen erforderlich waren, ist
die Sortierung eigentlich bereits beendet.


Übungen

18. Erweitern Sie den Algorithmus um diese Abbruchbedingung.




Das meistbenutzte Sortierverfahren geht auf C.A.R Hoare zurück :

Quicksort

Beim Quicksort wird zunächst willkürlich ein Element aus der
Liste herausgenommen. Dann werden zwei Teillisten unter Ausschluß
dieses Glieds gebildet. In die erste werden alle Listenglieder
aufgenommen, die kleiner oder gleich dem Element sind. Die zweite
beherbergt alle größeren. Auf diese beiden Listen wird rekursiv
der Algorithmus erneut angewendet. Die sortierte Liste setzt sich
dann aus der sortierten ersten Teilliste, dem ausgewählten
Element und der sortierten zweiten Teilliste zusammen.

Wir wählen für die Aufteilung das erste Glied der Liste. Dann
verdeutlicht die folgende Grafik den Sortiervorgang.


Aufteilung der Listen bei Quicksort:

				     (5 4 5 8 4 2 9 3 6)
				     /	      : 	\
				   <= 5       : 	> 5
				   /	      : 	  \
			   (4 5 4 2 3)        :        (8 9 6)
			  /	:    \	      :        /  :  \
		       <= 4	:    > 4      :     <= 8  :  > 8
			/	:	\     :      /	  :	\
		 (4 2 3)        :      (5)    :    (6)    :     (9)
		 /    : 	:	  :   :     :	  :	 :
	      <= 4    : 	:	  :   :     :	  :	 :
	       /      : 	:	  :   :     :	  :	 :
	  (2 3)       :         :         :   :     :     :      :
	   :  \       : 	:	  :   :     :	  :	 :
	   :  > 2     : 	:	  :   :     :	  :	 :
	   :	 \    : 	:	  :   :     :	  :	 :
	   :	(3)   :         :         :   :     :     :      :
	   :	 :    : 	:	  :   :     :	  :	 :
	  (2     3    4         4         5   5     6     8      9)

;Quicksort

(defun kleiner (liste mitte)
 (cond ((null liste) nil)
       ((< (car liste) mitte) (cons (car liste)
				  (kleiner (cdr liste) mitte)))
       (t (kleiner (cdr liste) mitte))))

(defun grösser (liste mitte)
 (cond ((null liste) nil)
       ((>= (car liste) mitte)(cons (car liste)
				  (grösser (cdr liste) mitte)))
       (t (grösser (cdr liste) mitte))))


(defun Quicksort (liste)
  (cond ((or (null liste)(null (cdr liste))) liste) ;fertig
	(t (append (Quicksort (kleiner (cdr liste)(car liste)))
		   (cons (car liste)
		   (Quicksort (grösser (cdr liste)(car liste))))))))

Die Funktion kleiner sucht aus liste alle die Glieder heraus, die
kleiner oder gleich dem Wert mitte sind. Sie werden zu einer
Liste verkettet zurückgegeben.	Entsprechend baut grösser die
Liste der Elemente, die größer als mitte sind, zusammen.
Die Funktion Quicksort muß sich dann nur noch jeweils ein Element
heraussuchen - hier das erste - und kann sich dann der Funktionen
größer und kleiner bedienen.

Wir haben jetzt vier Sortierverfahren kennengelernt. Welches soll
man nun tatsächlich benutzen ?

Bis auf Quicksort sind die Rechenzeiten der Programme im
mittleren Fall, d.h. bei vollkommen unsortierten Listen,
proportional zum Quadrat der Länge der Listen. Bei Quicksort
hingegen ist die Rechenzeit nur Proportional dem Logarithmus zur
Basis 2 der Listenlänge, multipliziert mit der Listenlänge. Damit
verhält sich Quicksort bei großen Datenmengen sehr viel besser
als die anderern Verfahren, die Rechenzeit wächst fast linear mit
der Listenlänge. Tatsächlich schlägt Quicksort prinzipiell nahezu
alle, auch die hier nicht betrachteten Sortierverfahren. Aber bei
kleinen Datenmengen fallen die bisher vernachlässigten
Proportionaltotätskonstanten ins Gewicht. So ergibt sich bei
Probeläufen mit 10 Listenelementen das folgende Bild :

			  aufwärts   abwärts	zufällig gefüllte
			  sortierte  sortierte	Liste

direkte Auswahl 	    4		7		 7
direkter Austausch	    5		5		 7
direktes Einfügen	    4		2		 3
Quicksort		    8		8		 4

(Angaben in Sekunden)

Quicksort schneidet bei den sortierten Listen deshalb so schlecht
ab, weil stets das erste Listenelement im Beispielprogramm zum
Vergleich herangezogen wird. Damit aber ist eine der beiden
Teillisten leer, bei jeder Rekursion wird nur ein Element
abgespalten.

Bubblesort, also direkter Austausch, würde mit der
vorgeschlagenen zusätzlichen Abbruchbedingung im ersten Fall
wesentlich besser abschneiden. Dennoch dürfte Bubblesort bei
längeren Listen der schwächste Algorithmus zum Sortieren
überhaupt sein.
Das Sortieren durch direktes Einfügen bietet sich für kleine
Listen besonders an. Im Gegensatz zur direkten Auswahl sind hier
stets weniger Vergleiche nötig : Bei direkter Auswahl muß die
restliche Eingabeliste immer komplett durchlaufen werden, um das
zur Zeit kleinste Element zu finden. Dabei genügt beim direkten
Einfügen das Auffinden des Platzes für das aktuelle Glied. Danach
muß in der bereits sortierten Liste nicht weitergesucht werden.

Die in der Tabelle angegebenen Rechenzeiten erscheinen für das
Sortieren so kleiner Datenbestände viel zu hoch. Sie müssen aber
bedenken, welchen Aufwand der Interpreter bei der Abarbeitung der
Funktionen treiben muß. So werden ja stets bei Zuweisungen auch
Listen komplett kopiert. Daneben muß bei der Programmausführung
auf alle möglichen Fehlerarten geachtet werden. Eine
Compilersprache hat es hier leichter. Sie kann bereits während
der Übersetzung des Quelltextes viele Fehlerquellen ausschließen.


Übungen

19. Optimieren Sie den Quicksort-Algorithmus, indem nicht stets
    das erste Listenelement für Vergleiche herangezogen wird,
    sondern die Auswahl zufällig geschieht.



III.2. Beispiele aus der Mathematik

Symbolische Differentiation

Zunächst möchten wir ein Programm entwickeln, das Funktionen
differenzieren kann. Dabei beschränken wir uns auf gebrochen
rationale Funktionen, es treten also nur die Verknüpfungen +, *,
- und / auf.
Sie kennen aus Ihrer Schulzeit die folgenden Regeln :

Seien f und g (gebrochen) rationale Funktionen. Dann gilt

(1)             (f+g)' = f' + g'
(2)             (f-g)' = f' - g'
(3)             (f*g)' = f' * g + f * g'
(4)             (f/g)' = (f' * g - f * g')/g2

Und die Ableitung der Funktion f zu f(x)=Konstante ist 0 (5), die
Ableitung zu f(x)=x ist die konstante Funktion f'(x)=1 (6).

Mit diesen sechs Regeln läßt sich jede gebrochen rationale
Funktion differenzieren, da auftretende Potenzen auf wiederholte
Multiplikation zurückzuführen sind, dafür aber eine Regel
angegeben ist.

Wir arbeiten mit Lisp, also sollen die Funktionsterme in
Präfixnotation vorliegen.
Übersetzen wir die Regeln, so erhalten wir sofort diese ALisp-
Funktion, die Terme in der veränderlichen x erwartet:

; diff leitet einen Term nach x ab (ohne Vereinfachungen):

(defun diff (term)
    (cond ((listp term) ; Liste
      (cond ((eq (car term) '+) ; Regel (1)
	       (list '+ (diff (nth 2 term))(diff (nth 3 term))))
	    ((eq (car term) '-) ; Regel (2)
	       (list '- (diff (nth 2 term))(diff (nth 3 term))))
	    ((eq (car term) '*) ; Regel (3)
	       (list '+ (list '* (diff (nth 2 term))
				 (nth 3 term))
			(list '* (nth 2 term)
				 (diff (nth 3 term)))))
	    ((eq (car term) '/) ; Regel (4)
	       (list '/ (list '- (list '* (diff (nth 2 term))
					  (nth 3 term))
				 (list '* (nth 2 term)
					  (diff (nth 3 term))))
			(list '* (nth 3 term) (nth 3 term))))
	    ;hier ev. weitere Regeln einfügen
      ))
      ((atom term)
	(cond ((eq term 'x) 1) ; Regel (6)
	      (t 0))) ; Regel (5)
   )
)

Sie sehen : Das Lispprogramm besteht nur aus den 6 Regeln. Der
Algorithmus ergibt sich daraus von selbst. Wenn Sie so wollen,
haben wir hier ein Beispiel deklarativer Programmierung.

>(diff '(/ x (+ 1 x)))
(/ (- (* 1 (+ 1 x))(* x (+ 0 1)))(* (+ 1 x)(+ 1 x)))

Dieses Ergebnis kann noch wesentlich vereinfacht werden. Daher
wollen wir den Algorithmus um eine entsprechende Funktion
erweitern:

(defun simplify (term &aux a)
    (cond ((atom term) term)
	  (t (setq a (list (car term)(simplify (nth 2 term))
				     (simplify (nth 3 term))))
	     (cond ((eq (car a) '+)
		     (cond ((eq (nth 2 a) 0) (nth 3 a))
			   ((eq (nth 3 a) 0) (nth 2 a))(t a)))
		   ((eq (car a) '-)
		     (cond ((eq (nth 3 a) 0) (nth 2 a))(t a)))
		   ((eq (car a) '*)
		     (cond ((or (eq (nth 2 a) 0)
						  (eq (nth 3 a) 0)) 0)
			   ((eq (nth 2 a) 1) (nth 3 a))
			   ((eq (nth 3 a) 1) (nth 2 a))(t a)))
		   ((eq (car a) '/)
		     (cond ((eq (nth 3 a) 1) (nth 2 a))
			   ((eq (nth 2 a) 0) 0)(t a)))))
    )
)

simplify vereinfacht, indem bei Operationen zunächst beide
Operanden rekursiv vereinfacht werden. Dann werden die so
gewonnenen Ergebnisse je nach Operator mit 0 und 1 verglichen. So
wird z.B. (* 0 <Term>) zu 0, (* 1 <Term>) zu <Term> etc.
Mit diesen Vereinfachungen wird auch das Ergebnis des obigen
Beispiels lesbarer :

>(simplify (diff '(/ x (+ 1 x))))
(/ (- (+ 1 x ) x) x )( * (+ 1 x )(+ 1 x)))


Übungen

20. Zur Übung können sie noch einige Vereinfachungsregeln
    hinzufügen, beispielsweise die Zusammenfassung von
    (* (+ 1 x)(+ 1 x)) zu (quad (+ 1 x)), wobei quad definiert
    ist als (defun quad (x) (* x x))

    Daneben lassen sich auch die Ableitungsregeln nicht
    gebrochen-rationaler Funktionen in der Funktion diff
    ergänzen.

Das Gegenstück zu diff, eine Funktion zum Integrieren läßt sich
leider nicht so einfach niederschreiben, da z.B. bei gebrochen
rationalen Funktionen eine Partialbruchzerlegung durchgeführt
werden muß.


Der Gauß-Algorithmus

In diesem Abschnitt gehe ich davon aus, daß Sie Grundkenntnisse
auf dem Gebiet der linearen Algebra besitzen. Andernfalls lassen
Sie die folgenden Seiten einfach aus.
Das hier dargestellte Programmsystem ist die einfachste Variante
des Gauß-Algorithmus. In der Praxis wird man LR-Zerlegungen oder
speziellere Verfahren wie die Cholesky-Zerlegung einsetzen.

Lineare Gleichungssysteme (LGS) lassen sich systematisch mit dem
sog. Gauß-Algorithmus lösen. Dabei wird ausgenutzt, daß die
folgenden Operationen die Lösungsmenge des Systems nicht
beeinflussen :

(1) Multiplikation einer Gleichung mit einer Zahl
(2) Ersetzen einer Gleichung durch die Summe dieser Gleichung mit
    einer weiteren.
(3) Vertauschen von Gleichungen

Als Beispiel diene das folgende Gleichungssystem :

				3x + 6y -9z = 3
				5x + 8y - z = 3
				2x +  y     = 2

Ohne Informationsverlust läßt es sich auch als Matrix der
Koeffizienten schreiben, eine Matrix ist hier eine Liste von
Zeilenlisten, eine Zeilenliste verkörpert eine Gleichung :

		       ( (3   6   -9    3)
			 (5   8    1    3)
			 (2   1   19    2) )

Nun wird das LGS mit den Operationen vereinfacht. Dazu versuchen
wir möglichst in jeder Spalte nur eine Eins und sonst Nullen zu
erzeugen.
Im ersten Schritt multiplizieren wir die erste Gleichung, also
die erste Zeile, mit 1/3 und subtrahieren diese neue Gleichung
fünf mal von der zweiten und zweimal von der dritten Gleichung:

			  ( (1   2   -3    1)
			    (0  -2   16   -2)
			    (0  -3   25    0) )

Nun sieht bereits die erste Spalte wie gewünscht aus, fahren wir
mit der zweiten fort. Also wird sie mit -1/2 multipliziert,
zweimal von der ersten abgezogen und dreimal zur dritten addiert.

			  ( (1   0   13   -1)
			    (0   1   -8    1)
			    (0   0    1    3) )

Die dritte Spalte wird vereinfacht, indem von der ersten
Gleichung 13 mal die dritte abgezogen und zu der zweiten 8 mal
die dritte addiert wird:

			  ( (1   0    0   -40)
			    (0   1    0    25)
			    (0   0    1     3) )

Nun läßt sich sofort die Lösung des LGS ablesen, denn die Matrix
verkörpert nur

				x = -40
				y =  25
				z =   3

Existiert die Lösung eines LGS nicht, so wird beim Gauß-
Algorithmus irgendwann eine Gleichung der Form (0 0 0 0...0 z)
mit z ungleich 0 entstehen, also ein Widerspruch.
Ist die Lösung eines LGS nicht eindeutig, so bleiben Zeilen
übrig, in denen nicht nur eine 1 steht.
In jedem Fall aber kann die Lösungsmenge schnell an der mit dem
Algorithmus vereinfachten Matrix abgelesen werden.

In unserem Beispiel hatten wir eine Erweiterungsspalte, das ist
die Spalte der Werte rechts vom Gleichheitszeichen. Manchmal ist
es nützlich, ein Gleichungssystem mit verschiedenen
Erweiterungsspalten zu berechnen. Dafür ist in der Funktion gausz
(s.u.) extra ein Parameter vorgesehen, der die Anzahl dieser
Spalten definiert. Außerdem kann gewählt werden, ob
Zwischenschritte der Berechnung ausgegeben werden sollen, oder ob
nur das Endergebnis erscheint. Die Variable zwischen wird für bei
gewünschter Zwischenschrittausgabe auf t gesetzt.

(setq zwischen nil)

; gauz wendet das Gaussche Eliminationsverfahren auf ein
; Gleichungssystem an, dabei : m - Gleichungsanzahl,
; n - Spaltenzahl, erw - Zahl der Erweiterungsspalten

(defun gausz (matrix m n erw &aux i j aktzeile merke)
 (setq aktzeile 1)(setq determinante 1)
 (setq i 1) ; alle Variablenspalten durchgehen
 (setq j (- n erw)) (cond ((> j m) (setq j m)))
 (count j
   (cond ((eql (nth i (nth aktzeile matrix)) 0) ; hier steht 0
      (setq j (+ aktzeile 1))
      (while (<= j m)
	(cond ((eql (nth i (nth j matrix)) 0) (setq j (+ j 1)))
	      (t (cond (zwischen
		  (princ "Vertausche die Gleichungen" aktzeile
				     "und" j ":")
		 ))
		 (setq determinante (* determinante -1))
		 (setq merke (nth aktzeile matrix))
		 (setq matrix (exchange aktzeile matrix (nth j
											matrix)))
		 (setq matrix (exchange j matrix merke))
		 (setq j (+ m 2))
		 (cond (zwischen
		  (terpri)(princ matrix)(terpri)))
      )))
   ))
   (cond ((not (eql (nth i (nth aktzeile matrix)) 0)) ; hier
										    ; keine 0
    (setq matrix (zeilenmult matrix aktzeile
		 (/ 1 (nth i (nth aktzeile matrix))) m n))
    ; führende 1 herbeischaffen
    (setq j 1)
    (count m
      (cond ((and (not (eql j aktzeile))(not (eql
						(nth i (nth j matrix))0)))
	  ; Gleichung - xyz * Gleichung aktzeile
       (setq matrix (abziehen matrix j aktzeile
				 (nth i (nth j matrix)) m n))
      )) (setq j (+ j 1)))(setq aktzeile (+ aktzeile 1))))
   (setq i (+ i 1))
 )
 matrix)

(defun zeilenmult (matrix zeile wert m n &aux i neuzeile)
  (cond ((not (eql wert 1))
   (cond (zwischen
     (princ "Multipliziere Gleichung" zeile "mit" wert ":")
     (terpri)))
   (setq determinante (/ determinante wert))
   (setq neuzeile nil) ; multiplizierte Zeile erstellen
   (setq i n)
   (count n (setq neuzeile (cons (* (nth i (nth zeile matrix))
							  wert)
				 neuzeile))
	    (setq i (- i 1)))
   (setq matrix (exchange zeile matrix neuzeile));einbauen
   (cond (zwischen (princ matrix)(terpri)))
  ))
  matrix)

(defun abziehen (matrix zeile1 zeile2 faktor m n &aux i hilf
			  neuzeile)
  (cond (zwischen
    (princ "Subtrahiere" faktor "* Gleichung" zeile2 "von" zeile1
		 ":")
    (terpri)))
  (setq neuzeile nil) ; veränderte Zeile erstellen
  (setq i n)
  (count n (setq neuzeile (cons
     (- (nth i (nth zeile1 matrix))(* (nth i (nth zeile2 matrix))
	     faktor)) neuzeile))
	   (setq i (- i 1)))
  (setq matrix (exchange zeile1 matrix neuzeile))
  (cond (zwischen (princ matrix)(terpri)))
  matrix) ;einbauen

(defun anzahl (liste)
  (cond ((null liste) 0)
	(t (+ (anzahl (cdr liste)) 1))))

(defun solve (matrix)
  (gausz matrix (anzahl matrix) (anzahl (car matrix)) 1))


Der eigentliche Gauß-Algorithmus trägt auch im Programm den Namen
gausz. Hier wird versucht, in jeder Spalte bzw. Zeile (ohne den
Erweiterungsteil der Matrix) Einsen und Nullen nach dem oben
beschriebenen Verfahren zu erzeugen. Dazu sucht sich das Programm
in der aktuellen Spalte die erste Gleichung, deren Koeffizient
hier nicht Null ist und tausch diese gegebenenfalls so, daß
später die Anordnung der Einsen in der Matrix Diagonalgestalt
hat. Dann wird diese Gleichung multipliziert, daß der Koeffizient
zur Eins wird. Anschließend wird die Gleichung noch von den
anderen entsprechend abgezogen.
Für die Multiplikation einer Zeile bzw. Gleichung und für die
Addition eines Vielfachen einer Gleichung mit einer anderen
stehen die Funktionen abziehen und zeilenmult bereit.
anzahl ermittelt die Anzahl der Glieder einer Liste. So können
die Ausmaße einer Matrix in der Funktion solve bestimmt werden.
solve schließlich erwartet als Eingabe die Matrix eines LGS, wie
sie oben beschrieben ist. In solve wird gausz daher auch mit
einer Erweiterungsspalte aufgerufen.

Mehrere Erweiterungsspalten benötigt man beim Invertieren von
Matrizen mit dem Gauß-Jordan-Algorithmus. Hier bilden die
Erweiterungsspalten eine Einheitsmatrix, die an die zu
invertierende Matrix gesetzt wird. Nach Beendigung des Gauß-
Algorithmus ist die ursprüngliche Matrix zu einer Einheitsmatrix
geworden, und die Erweiterungsspalten bilden nun die gesuchte
Inverse. Im Prinzip werden also mehrere Gleichungssysteme gelöst,
die sich aus der Definition der Matrizenmultiplikation ableiten.

Die Implementierung des Algorithmus zur Invertierung beschränkt
sich also auf einen Aufruf der Funktion gausz. Jedoch muß vorher
an die Ausgangsmatrix die Einheitsmatrix angehängt und nach der
Berechnung wieder abgetrennt werden. Dazu dienen die folgenden
Funktionen stavec und halv. stavec generiert die Zeilen der
Einheitsmatrix, und half nimmt sie später wieder weg.
Die Hauptfunktion ist inverse. Hier wird mit stavec und half die
eingegebene Matrix zurechtgelegt und gausz aufgerufen.

(defun stavec (n pos &aux liste i) ;erzeugt n-gliedrige Liste mit
; einer 1 an der Position pos
  (setq liste nil)(setq i 1)
  (count n (cond ((eql i (+ (- n pos) 1)) (setq liste
					     (cons 1 liste)))
		 (t (setq liste (cons 0 liste))))
	   (setq i (+ i 1)))
  liste)

(defun half (liste m) ; halbiert eine Liste
  (cond ((eql m 0) liste)
	(t (half (cdr liste) (- m 1)))))

(defun inverse (matrix &aux n i)
  (setq m (anzahl matrix))
  (setq i 1)
  (count m (setq matrix (exchange i matrix
			   (append (nth i matrix) (stavec m i))))
	   (setq i (+ i 1)))
  (setq matrix (gausz matrix m (* m 2) m))
  (setq i 1)
  (count m (setq matrix (exchange i matrix
			   (half (nth i matrix) m)))
	   (setq i (+ i 1)))
  matrix)

Der Rang einer Matrix ist die Anzahl der linear unabhängigen
Zeilen bzw. Spaltenvektoren. Er entspricht der Anzahl der Zeilen,
in denen nach dem Gauß-Algorithmus noch Zahlen ungleich Null
stehen. Die Funktion rank ermittelt den Rang der zu übergebenden
Matrix, indem sie zunächst gausz aufruft und dann mit der
Funktion nichtleer die nichtleeren Zeilen zählt :

(defun nichtleer (vektor) ; prüft, ob ein Nullvektor vorliegt
  (cond ((null vektor) nil)
	((eql (car vektor) 0) (nichtleer (cdr vektor)))
	(t t)))

(defun rank (matrix &aux m i rang) ; bestimmt den Rang einer
				   ; Matrix
  (setq m (anzahl matrix))
  (setq matrix (gausz matrix m (anzahl (car matrix)) 0))
  ;Elementarumformungen
  (setq i 1)(setq rang 0)
  (count m (cond ((nichtleer (nth i matrix)) (setq rang
										(+ rang 1))))
	   (setq i (+ i 1)))
  rang)

Soll eine Folge von Vektoren auf lineare Unabhängigkeit geprüft
werden, so können die Vektoren als Zeilen einer Matrix aufgefaßt
werden. Ergibt sich für diese Matrix als Rang die Anzahl der
Vektoren, so sind sie linear unabhängig, andernfalls nicht. Die
Zeilenvektoren, die als Ergebnis des dabei aufgerufenen Gauß-
Algorithmus entstehen, erzeugen den gleichen Raum wie die
ursprüngliche Vektorenfolge.

Äußerst unbeliebt (weil arbeitsintensiv und fehleranfällig) ist
die Determinantenberechnung für Matrizen, also die ideale Aufgabe
für einen Computer.
Sie haben vielleicht bemerkt, daß in der Funktion gausz bereits
die Variable determinante auftritt.
Parallel zur Vereinfachung der Matrix wird bereits die
Determinante errechnet. Denn es gelten die folgenden Regeln :

(1) Wird eine Zeile einer Matrix mit einer Zahl multipliziert, so
    ergibt sich die neue Determinante ebenso durch Multiplikation
    der alten mit dieser Zahl.
(2) Die Addition einer Zeile mit einem Vielfachen einer anderen
    Zeile ändert die Determinante nicht.
(3) Werden zwei Zeilen vertauscht, so ändert sich das Vorzeichen
    der Determinante.

Ist die Determinante ungleich Null, so muß die Matrix symmetrisch
und die Zeilen müssen linear unabhängig sein. Also entsteht in
diesem Fall beim Gauß-Algorithmus immer eine Einheitsmatrix als
Ergebnis - und deren Determinante ist gerade 1.
Bei der Determinantenberechnung beschränkt sich also auf die
Rückgabe des Wertes der Variablen determinante, falls der Rang
der Matrix mit deren Ausmaßen übereinstimmt:

(defun det (matrix &aux m) ; berechnet die Determinante einer
					  ; Matrix
  (setq m (anzahl matrix))
  (cond ((not (eql m (anzahl (car matrix)))) 0)
	((not (eql m (rank matrix))) 0)
	(t determinante)))
; die Variable determinante wird bei der Berechnung des Rangs
; gefüllt

Zum Abschluß definiere ich noch die Funktion zwischenschritte,
mit der die Anzeige von Zwischenschritten bei allen Berechnungen
ein- oder ausgeschaltet wird :

(defun zwischenschritte () (setq zwischen (not zwischen)))

Einige Beispiele mögen den Umgang mit den eben definierten
Funktionen illustrieren :

>(solve '((3 6 -9 3)(5 8 1 3)(2 1 19 2)))
(( 1  0  0  -40)(0  1  0  25)(0  0  1  3))

>(rank '((3 6 -9 3)(5 8 1 3)(2 1 19 2)))
 3

>(det '((3 6 -9 3)(5 8 1 3)(2 1 19 2)))
 0

>(det '((3 6 -9)(5 8 1)(2 1 19)))
 -6

>(inverse '((3 6 -9)(5 8 1)(2 1 19)
(( -151/6  41/2  -13)( 31/2  -25/2  8)( 11/6  -3/2  1 ))

>(inverse '((-151/6 41/2 -13)(31/2 -25/2 8)(11/6 -3/2 1)))
(( 3  6  -9 )( 5  8  1 )( 2  1  19 ))

>(det '((1 2 3)(6 4 5)(9 8 7)))
 30

>(solve '((1 2 3)(6 4 5)(9 8 7)))
(( 1  0  -1/4)( 0  1  13/8 )( 0  0  -15/4 ))

>(inverse '((1 2 3)(6 4 5)(9 8 7)))
(( -2/5  1/3  -1/15 )( 1/10  -2/3  13/30 )( 2/5  1/3  -4/15 ))


Übungen

21. Schreiben Sie eine Funktion, die zwei Matrizen multipliziert.


III.3.	Debugging

Bei der Erstellung komplizierterer Programme verliert man leicht die
Übersicht, was bei der Abarbeitung eigentlich geschieht.
Einmal kann hier der Menüpunkt Trace angewählt werden, der zur Laufzeit
für das Anzeigen aller Funktions/Macro-Aufrufe sorgt.
Andererseits aber befindet sich im Lisp-Verzeichnis dieser Diskette das
Programm trace.lsp, das die Funktion mein-trace bereitstellt.
Sie kommentiert jede Anweisung einer Funktionsabarbeitung detailliert im
Dialogfenster. Da mein-trace ein Macro ist, wird die Analyse einer
Funktion f so aufgerufen:

	       (mein-trace (f <Parameterliste von f>))

-wobei f normalerweise durch (f <Parameterliste von f>) gestartet wird.

Die Einrückung der Textdarstellung in der mein-trace-Ausgabe gibt die
Schachtelungstiefe der zugehörigen Anweisungen an.



IV. Ein Prolog-Interpreter in Lisp
----------------------------------


Als Krönung der Einführung in ALisp möchte ich mit Ihnen nun
einen Prolog-Interpreter programmieren. Das resultierende Lisp-
programm wird überraschend einfach und kurz sein und damit die
Mächtigkeit dieser Sprache eindrucksvoll beweisen.
Daneben werden hier natürlich auch die Grundzüge von Prolog
erläutert. Damit kennen Sie dann beide KI-Sprachen.


IV.1. Die Sprache Prolog

Der Name Prolog steht hier in keiner Verbindung zum Auftaktrennen
einer Radtour und hat auch nichts mit Dramen zu tun. Vielmehr ist
auch Prolog hier ein Kunstwort, das sich aus Programmieren in
Logik ergibt.
Dieser Name trifft dann auch wirklich den Kern der Sprache, die
der mathematischen Prädikatenlogik angelehnt ist.
Eine einfache Sprachversion ist zunächst nur in der Lage,
Aussagen auf Richtigkeit zu prüfen, oder für Aussageformen
Lösungsmengen zu ermitteln. Dafür steht dem Prolog-Interpreter
eine Datenbasis und darauf aufbauende Regeln zur Verfügung.
Dieses Wissen ist mit den Programmen anderer Sprachen
vergleichbar, aber in Prolog müssen keine Lösungsalgorithmen
gefunden werden. Hier werden nur alle für die Lösung eines
Problems nötigen Informationen angegeben. Prolog ist somit eine
deklarative Sprache. Dagegen sind z.B. Pascal, Modula oder C
imperative Sprachen. Hier müssen sich die Programmierer um die
Lösungsverfahren kümmern.

Die Ideen zu Prolog gehen vor allem auf Kowalski und Colmerauer
zurück. Die Sprache wurde 1972 in Marseille zuerst implementiert
und wurde von der Fachwelt nicht weiter beachtet. Als aber in
Japan das 5th Generation-Projekt auf Prolog basieren sollte, war
das weltweite Interesse geweckt. Heute ist Prolog neben Lisp die
wichtigste Sprache der KI.

Definieren wir uns einige Fakten :

vater(otto,hans).
vater(otto,ute).
vater(hans,karl).
mutter(ute,anna).

Damit soll ausgedrückt werden, daß Otto Vater von Hans und Ute,
Hans Vater von Karl und Ute Mutter von Anna ist.
Das Ende eines Fakts (und später einer Regel) wird mit einem
Punkt markiert. Die Aussage des Fakts drückt sich in seinem Namen
aus, der vor den geklammerten Daten steht. Innerhalb der Klammern
dürfen beliebig viele, durch Kommata getrennte Daten stehen.

Jetzt ist der Wissensdurst des Interpreters erst einmal gestillt,
und wir können ihm Fragen stellen :

?- vater(otto,ute).
t

Auf die Frage, ob Otto Vater von Ute ist, also ob die Aussage
vater(otto,ute) wahr ist, antwortet Prolog mit t, bestätigt also
die Aussage.
Denn der Interpreter findet genau diese Aussage in der Liste
seiner Fakten. Dagegen wird

?- vater(otto,karl).

mit nil beantwortet. In der Datenbasis gibt es keine passende
Information. Da der Interpreter großspurig annimmt, seine
Datenbank würde die ganze Welt komplett beschreiben, ist
vater(otto,karl) also falsch.

Nun ist es sicher keine Kunst, in einem Datenbestand nach einem
Faktum zu suchen und den Erfolg dieser Suche mitzuteilen. Prolog
aber kann wesentlich mehr. So sind auch Variablen statt der
Konstanten in den geklammerten Listen erlaubt. In einigen Prolog-
Dialekten werden die Variablen zur Unterscheidung von Konstanten
groß geschrieben.
Auf die Frage

?- vater(otto,X)

soll Prolog die Lösungsmenge dieser Aussageform finden. Zunächst
wird

X = hans

ausgegeben, anschließend wird gefragt, ob noch weitere Lösungen
ermittelt werden sollen. Als zweite Lösung findet sich so

X = ute

Soll dann noch nach weiteren Lösungen geforscht werden, wird nur
noch nil ausgegeben.

Bei Berechnungen durchsucht Prolog den Datenbestand von oben nach
unten, wenn man sich die Daten in der Reihenfolge ihrer
Definition untereinanderstehend (z.B. ausgedruckt) vorstellt.
Zunächst wird vater(otto,hans) mit vater(otto,X) verglichen. Da
die Namen der Fakten übereinstimmen (vater), werden die Daten in
den Listen verglichen. otto paßt zu otto, aber hans scheinbar
nicht zu X. Doch X ist eine Variable und die nehmen in Prolog
gerade solche Werte an, die zu einer Übereinstimmung der Daten
führen. Daher erhält X den Wert hans, und die gefragte
Aussageform wird für diese Einsetzung wahr. Soll weitergesucht
werden, so stößt der Interpreter auf die Regel vater(otto,ute).
Hier nimmt X nun nach dem gleichen Prinzip den Wert ute an.
Danach werden keine Lösungen mehr gefunden, da entweder der Name
vater auf mutter trifft oder otto nicht an erster Stelle der
Vergleichsliste steht.
Variablen dürfen selbstverständlich auch bei der Definition von
Fakten benutzt werden:

gleich(A,A).

Mit diesem Fakt kann geprüft werden, ob z.B. zwei Konstanten
gleich sind :

?- gleich(franz,franz)
t

?- gleich(franz,jörg)
nil

Beim Test dieser Aussagen wird, nachdem in der Datenbasis das
Fakt mit dem Namen gleich gefunden wurde, A jeweils durch franz
ersetzt. Dies gilt für beide Vorkommen, d.h. das Faktum lautet
nun gleich(franz,franz). Es ist klar, daß dann bei der ersten
Frage t und bei der zweiten nil herauskommt.
Variablen sind stets nur innerhalb eines Fakts gültig, d.h. Wird
ein Variablenname in mehreren Fakten benutzt, so bezeichnet
dieser Name in jedem dieser Fakten eine andere Variable. Dies
gilt insbesondere auch für Regeln:

Eine Regel beschreibt eine Folge von Aussagen bzw. Aussageformen,
die wahr werden müssen, damit die Regel erfüllt ist. Definieren
wir Regeln, die das Geschwister-Verhältnis ausdrücken:

elternteil(A,B) :- vater(A,B).
elternteil(A,B) :- mutter(A,B).

geschwister(A,B) :- elternteil(C,A) elternteil(C,B).

Regeln werden auch als Horn-Klauseln oder einfach nur als
Klauseln bezeichnet.
Sie sehen also aus wie Fakten, denen ein :- Zeichen folgt und
dann wieder eine Liste von Aussagen bzw. Aussageformen.

Genau wenn die rechte Seite einer Regel erfüllt ist, ist auch die
linke erfüllt.

?- elternteil(ute,anna).

Diese Frage wird wahr. Zunächst wird bei der ersten Elternteil-
regel A durch ute und B durch anna ersetzt. Dann wird die Aussage
vater(ute,anna) überprüft. Diese kann aber in der Datenbesis
nicht gefunden werden. Da die rechte Seite falsch ist, wird auch
die linke, also elternteil(ute,anna) falsch. Aber die Frage wurde
ja mit wahr beantwortet. Dies liegt daran, daß es noch eine
zweite elternteil-Regel gibt. Der Interpreter sucht seine
Lösungen ja von oben nach unten. Bei der zweiten Regeln werden A
und B wie zuvor gesetzt. Jetzt aber kann die rechte Seite
mutter(ute,anne) in der Datenbasis gefunden werden, ist also
wahr. Damit wird die linke Seite wahr und die Frage wird
bestätigt.
Bei der geschwister-Regel treten auf der rechten Seite nun zwei
Aussageformen auf. Die rechte Seite ist hier genau dann erfüllt,
wenn beide Aussageformen wahr werden können, d.h. wenn
elternteil(C,A) und elternteil(C,B) gleichzeitig erfüllt sind.
Allgemein können alle Aussagen der rechten Seite als durch das
logische Und verknüpft aufgefaßt werden. Sie werden von links
nach rechts überprüft (nach der sogenannten SLD-Resolution, SLD
für Select a literal, using Linear strategy, restricted to
Definite clauses).

Zum Elternteil-Problem haben wir zwei Regeln definiert. Das
Resultat des Interpreters auf eine passende Frage ist dann wahr,
wenn eine der beiden Regeln erfüllt ist. Die einzelnen Regeln
sind also durch das logische Oder verbunden. Damit sind zwei ganz
wichtige Elemente der Logik bereits in der Such-und
Überprüfstrategie des Interpreters versteckt.

Was geschieht nun bei der Frage

?- geschwister(hans,ute).

Zunächst wird die Regel gesucht, dann werden in ihr A und B gegen
hans und ute ausgetauscht. Nun sollen elternteil(C,hans) und
elternteil(C,ute) erfüllt sein. Dazu versucht Prolog zunächst
einmal für elternteil(C,hans) eine Setzung für die Variable C zu
finden. In der Datenbasis findet sich zunächst die Regel
elternteil(A,B):-vater(A,B). B wird zu hans und die Variablen A
und C stehen nun für den gleichen Wert. Wird also für
vater(C,hans) eine Lösung gefunden, so ist auch
elternteil(C,hans) erfüllt. Die Gesamtaussage wird also wahr,
wenn vater(C,hans) elternteil(C,ute) erfüllt wird. Also wird
jetzt damit weitergearbeitet. vater(C,hans) wird für C = otto
wahr. Dies steht als Fakt in der Datenbasis. Die Gesamtaussage
wird demnach wahr, wenn elternteil(otto,ute) wahr ist. Dazu wird
wieder zunächst die erste elternteil-Regel betrachtet. Sie wird
wahr, wenn vater(otto,ute) wahr ist. Da dies ein Faktum ist, wird
letztlich die Gesamtaussage mit wahr beantwortet.

Wird mit

?- geschwister(X,Y).

gefragt, so gibt das System ja die Lösungsmenge dieser
Aussageform an :

X=hans	X=hans	X=ute	X=ute	X=karl	X=karl
Y=hans	Y=ute	Y=hans	Y=ute	Y=karl	Y=jörg

X=jörg	X=jörg
Y=karl	Y=jörg

Wir haben bislang nicht ausgeschlossen, daß X gleich Y sein darf.
Daher entspricht diese Antwort genau unseren Regeln.

Das Verfahren, mit dem der Interpreter alle Lösungen findet,
heißt Backtracking oder Tiefensuche. Das Prinzip des Backtracking
läßt sich sehr anschaulich an einem Labyrinth erklären.
Ein Spieler, der einen Weg aus dem Irrgarten finden soll, kann so
vorgehen: Wähle zunächst eine Richtung aus und gehe bis zur
nächsten Verzweigung. Wähle dort wieder eine Richtung aus und
fahre so fort, bis eine Sackgasse erreicht ist. Nun kehre zur
letzten Verzweigung zurück und gehe in eine hier bisher noch
nicht probierte Richtung. Wird wieder eine Sackgasse erreicht,
wiederholt sich der Algorithmus. Sind an einer Gabelung bereits
alle weiterführenden Wege ausprobiert, so wird zur vorangehenden
Verzweigung zurückgekehrt. Gelangt der Spieler schließlich an den
Ausgangspunkt zurück und sind dort bereits alle Richtungen
probiert, so gibt es kein Entkommen (gemeines Labyrinth !).
Andernfalls wird irgendwann der Ausgang gefunden.

Weggabelungen sind beim Prolog-System Regeln und Fakten gleichen
Namens. Der Interpreter probiert diese ja von oben nach unten.
Entsprechend verfährt er aber auch bei der Verifikation der
Aussagen auf der rechten Seite einer Regel, so daß nach und nach
ein ganz bestimmter Lösungsweg eingeschlagen wird, der aber bei
Mißlingen durch Rückkehr zur vorangehenden Gabelung korrigiert
wird. Wird tatsächlich die gefragte Aussage verifiziert, so
stellt der Interpreter die Frage, ob weitergesucht werden soll.
Wird diese mit 'ja' beantwortet, so ignoriert er einfach die
gefundene Lösung und fährt mit dem Backtracking fort.
Die Tiefensuche in Prolog ersetzt die Notwendigkeit, selbst
Lösungsalgorithmen zu schreiben. Sie ist ein allgemeines
Lösungsverfahren.
Zur Verdeutlichung, wollen wir das Backtracking bei der Frage ?-
geschwister(X,Y). schrittweise nachvollziehen :

geschwister(X,Y) ist genau dann wahr, wenn
elternteil(C,X) elternteil(C,Y) wahr ist.

elternteil(C,X) ist wahr, wenn vater(C,X) wahr ist, wir versuchen
jetzt also das Ziel
vater(C,X) elternteil(C,Y). wahrzumachen.
Die erste Aussage wird zunächst bei C=otto, X=hans wahr. Damit
versuchen wir
elternteil(otto,Y) zu verifizieren. Dies wird wahr, wenn
vater(otto,Y) wahr wird.
Dies wird sofort mit Y=hans wahr. Damit ist eine Lösung gefunden:
X=hans, Y=hans. Soll weitergesucht werden, so wird nun eine
Sackgasse angenommen und zur letzten Verzweigung zurückgekehrt.
Dies war die Auswahl vater(otto,hans), die Y=hans geliefert hat.
Als nächstes wird vater(otto,ute) hier gewählt und wieder ist
eine Lösung gefunden. X=hans, Y=ute. Bei gewünschter Weitersuche
wird zu otto kein passendes Kind mehr gefunden. Hier wurden also
alle Richtungen durchprobiert, nun wird zur vorangehenden
Weggabelung zurückgekehrt. Dort haben wir elternteil(otto,Y)
durch vater(otto,Y) ersetzt. Nun versuchen wir es mit
mutter(otto,Y). In der Datenbank finden sich jedoch keine dazu
passenden Informationen, eine Sackgasse ist erreicht. Jetzt soll
für vater(C,X) eine andere Belegung gefunden werden. Dazu wählen
wir nun C=otto und X=ute. Nun wird das Ziel
elternteil(otto,Y) weiterverfolgt. Auf diese Weise entstehen die
Ergebnisse X=ute, Y=ute und X=ute, Y=karl. Anschließend muß
wieder zurückgegengen werden, bis für vater(C,X) neue Werte
gefunden sind. Dies sind nun C=hans und X=karl usw.


Das folgende Schema strukturiert das Backtracking etwas :

geschwister(X,Y).
	elternteil(C,X) elternteil(C,Y).
		vater(C,X) elternteil(C,Y).
			elternteil(otto,Y) [X=hans]
				vater(otto,Y)
					[X=hans,Y=hans]
					[X=hans,Y=ute]
				mutter(otto,Y)
			elternteil(otto,Y) [X=ute]
				vater(otto,Y)
					[X=ute,Y=ute]
					[X=ute,Y=hans]
				mutter(otto,Y)
			elternteil(hans,Y) [X=karl] usw...


Mit Prolog lassen sich auch sehr leicht neben den Stammbäumen
beliebige gerichtete Graphen beschreiben. Ein gerichteter Graph
ist eine Menge von Punkten zusammen mit einer Menge von Pfeilen,
die einem Punkt einen weiteren zuordnen. Man kann dann z.B. die
Frage stellen, ob es von einem Punkt über eine Kantenfolge einen
Weg zu einem anderen Punkt gibt. Sei z.B der folgende Graph mit
den Punkten a, b, c, d, e, f und g gegeben.


			a------->b---->d
			|	  \    |
			c	   g<--e-->f


Er ist mit den folgenden Fakten beschrieben :

kante(a,b).
kante(b,d).
kante(d,e).
kante(e,f).
kante(e,g).
kante(g,b).
kante(a,c).


Ob man von einem Punkt A zu B gelangen kann, erfährt man mit
dieser Funktion :

weg(A,B) :- kante(A,B).
weg(A,B) :- weg(A,C) kante(C,B).

Regeln und Fakten gleichen Namens bilden in Prolog Funktionen.
Hier dient die erste Regel als Abbruchbedingung der Tiefensuche
in der Graphenstruktur, die durch die zweite Regeln eingeleitet
wird. Prolog unterstützt also rekursive Algorithmen.

?- weg(a,f)
t
?- weg(f,b)
nil


Übungen

22. Definieren Sie sich einen eigenen Stammbaum und darauf
    weitere Verwandtschaftsregeln.




IV.2. Programmierung des Interpreters

Wenden wir uns nun der Programmierung des Prolog-Interpreters zu.
Dabei beschäftigen wir uns zunächst mit dem Auffinden passender
Regeln bzw. Fakten. Erstes Indiz dafür ist der gemeinsame Namen.
Soll getestet werden, ob gleich(eins,zwei) auf das Faktum
gleich(A,A) paßt, so werden zunächst eins und A verglichen. Da A
eine Variable ist, wird A in gleich(A,A) durch eins ersetzt. Nun
wird gleich(eins,zwei) mit gleich(eins,eins) für das zeite
Listenelement verglichen. Da zwei ungleich eins, paßt die Frage
nicht auf diesen Fakt. Bei diesem sog. Pattern-Matching (bzw.
Unifikation) gelten die folgenden Regeln :

- Werden zwei Konstanten verglichen, so müssen sie
  übereinstimmen, andernfalls passen die Terme nicht zusammen.
- Stößt eine Variable auf eine Konstante, so wird die Variable in
  der zugehörigen Regel (bzw. Fakt) überall durch die Konstante
  ersetzt. Dabei ist zusätzlich darauf zu achten, daß auch
  Variablen, die für denselben Wert stehen, in beiden Regeln
  angepaßt werden :
- Stoßen zwei Variablen aufeinander, so stehen diese ab sofort
  für denselben Wert.

In der Regel sollen Listen von (quasi durch Und verknüpften)
Aussagen verifiziert werden. Dabei wird stets für die erste
Aussage etwas Passendes gemäß den obigen Regeln in der Datenbank
gesucht. Nun kann ein neues Ziel konstruiert werden, indem die
rechte Seite der passenden Regel vor die Restliste der
ursprünglichen Aussagenliste gesetzt wird. Paßt ein Fakt, so
ergibt sich das neue Ziel nur das der Restliste. Ist diese leer,
wurde eine Lösung gefunden.
Durch das Pattern-Matching werden die beiden dabei in der Regel
aneinanderzuhängenden Aussagenlisten so angepaßt, daß Variablen
und Konstanten ebenfalls zusammenpassen.

Der gesamte zu entwickelnde Algorithmus besteht also aus einer
Funktion, die beliebige Aussagenlisten verifiziert, indem in der
Liste aller Fakten und Regeln zunächst etwas Passendes für die
erste Aussage gesucht wird. Daraus ergibt sich der Erfolg der
Verifikation, oder daraus wird dann mit der Restliste ein neues
Ziel, das rekursiv mit der gleichen Funktion abgearbeitet werden
kann. Ergibt sich dabei ein negatives Ergebnis, so wird in der
Liste nach dem nächsten passenden Konstrukt gesucht und
entsprechend verfahren. Ist die Liste komplett durchsucht, ergibt
sich ebenfalls der Wahrheitswert nil.

Innerhalb von Regeln sind die Aussagen mit Und verknüpft, die
Regeln, sind untereinander mit Oder verbunden. Allerdings reichen
diese beiden Logikoperatoren nicht aus, um eine Negation zu
realisieren. Negationen werden aber sicher benötigt, so dürfte es
wohl nicht möglich sein, z.B. ungleich(A,B). nur mit den bisher
bekannten Mitteln zu definieren.
Deshalb werden wir den not-Operator einfügen, der einfach vor die
betroffene Aussageform gestellt wird :
ungleich(A,B) :- not(gleich(A,B)).
Wir realisieren ihn gleich so : Kann ein durch not bezeichneter
Ausdruck durch einen Fakt ersetzt werden, so ergibt sich
insgesamt nil. Wir ein durch not bezeichneter Ausdruck durch eine
Regel ersetzt, so entstehen neue Ziele, indem die Aussageformen
der rechten Regelseite einzeln mit not versehen werden und
einzeln vor die Restliste, d.h. Liste der Aussagen, die dem not-
Ausdruck noch folgten, gesetzt werden. Hier wird der Regel von
Morgan genüge getan, die besagt:

(not (and a b)) = (or (not a) (not b))

Außerdem soll sich die doppelte Negierung natürlich aufheben.
Ein durch not bezeichneter Ausdruck wird schließlich t, wenn
nichts Passendes gefunden wurde oder wenn sich jeweils nil ergab.
Damit ist der not-Operator sinnvoll eingeführt, jedoch kann es
dann zu Unstimmigkeiten kommen, wenn die Negation eines Ausdrucks
wahr wird, aber sich im Ausdruck noch Variablen befinden.
Denn über das Prinzip des Pattern-Matching kann mitgeteilt
werden, daß zwei Variablenwerte gleich sein sollen, indem man den
Variablen den gleichen Namen gibt. Für Ungleichheit gibt es aber
keine Lösung. Variablen mit verschiedenen Namen können dennoch
gleiche Werte annehmen. Das Problem läßt sich an der ungleich-
Definition festmachen :

ungleich(A,B) :- not(gleich(A,B)).

test(A,B) :- ungleich(A,B) geschwister(A,B).

Die Frage ?- test(X,Y). wird so beantwortet wie
?- geschwister(X,Y)., obwohl bei den Ergebnissen X offensichtlich
teilweise gleich Y ist. Vertauscht man in test jedoch geschwister
und ungleich, so erhält man das erwartete Ergebnis, da A und B
bereits mit Konstanten belegt sind, wenn ungleich geprüft wird.
Daher sollten Sie bei Programmen für den hier entstehenden
Prolog-Interpreter darauf achten, Aussagen mit not-Operator stets
an das Ende der Aussagenlisten zu setzen.

Kommen wir aber nun endlich zur Realisierung.

Dazu passen wir die Prolog-Notationen dem Lispsystem etwas an.
So wird aus ungleich(A,B) :- not(gleich(A,B)). die Liste

((ungleich (A)(B)) (not gleich (A)(B)))

Regelkopf und Aussagen auf der rechten Seite der Regel werden zu
einer Liste verbunden. Bei Fakten ist die rechte Seite leer :

((vater otto hans))

Variablen werden zu einelementigen Listen, die den entsprechenden
Symbolnamen enthalten. Dadurch lassen sie sich beim
Interpretieren leicht von Konstanten unterscheiden und mit
Indizes versehen (s.u.).


; Ein kleiner Prolog-Interpreter...

(forbid)
(terpri)(princ "AProlog (c) 1990 Steffen Goebbels")(terpri)
(defun match (prädikat1 prädikat2 &aux nein)
   (setq nein nil)
   (cond ((eq (car (car prädikat1)) 'not)
	  ; not entfernen :
	  (setq prädikat1 (cons (cdr (car prädikat1))
						  (cdr prädikat1)))
	  (setq nein t)))
   (cond ((eq (car (car prädikat1)) (car (car prädikat2)))
	  ;Regeln gehören zur selben Funktion
	  (cond ((anpassen 2)
		 (setq prädikat1 (cdr prädikat1))
		 (setq prädikat2 (cdr prädikat2))
		 (cond ((null prädikat2)
			(cond (nein '(nil)) ;entgültig !
			      (t (cond ((null prädikat1)
					    (VarAusgabe))
				       (t (main prädikat1))))))
		       (nein (deMorgan prädikat2 prädikat1))
		       (t (main (append prädikat2 prädikat1)))))
		(t nil)))
	 (t nil)))

(defun anpassen (pos &aux i j)
  (setq i (nth pos (car prädikat1)))
  (setq j (nth pos (car prädikat2)))
  (cond ((and (null i) (null j)) t) ; paßt !
	((and (atom i)(atom j))
	 (cond ((eq i j) (anpassen (+ pos 1)))
	       (t nil))) ; Konstanten müssen gleich sein !
	((and (listp i)(atom j))
	   (setq prädikat1 (austauschen i j prädikat1))
	   (setq prädikat2 (austauschen i j prädikat2))
	   (set (car i) j)
	   (anpassen (+ pos 1)))
	((and (atom i)(listp j))
	   (setq prädikat1 (austauschen j i prädikat1))
	   (setq prädikat2 (austauschen j i prädikat2))
	   (set (car j) i)
	   (anpassen (+ pos 1)))
	(t (setq prädikat1 (austauschen j i prädikat1))
	   (setq prädikat2 (austauschen j i prädikat2))
	   (set (car j) i)
	   (anpassen (+ pos 1)))))

(defun austauschen (so ta prädikat)
  (cond ((null prädikat) nil)
	(t (cons (ersetzeTerm so ta (car prädikat))
	   (austauschen so ta (cdr prädikat))))))

(defun ersetzeTerm (so ta term)
  (cond ((null term) nil)
	((equal (car term) so) (cons ta (ersetzeTerm so ta
						(cdr term))))
	(t (cons (car term) (ersetzeTerm so ta (cdr term))))))

; damit gleichnamige Variablen verschiedener Terme richtig ;
zugeordnet werden
(defun kennzeichneTerm (term id)
 (cond((null term) nil)
      ((atom (car term)) (cons (car term)(kennzeichneTerm
						  (cdr term) id)))
      (t(cons (cons (car (car term)) (list id))
	      (kennzeichneTerm (cdr term) id)))
  )
)
(defun kennzeichnePrädikat (prädikat id)
  (cond ((null prädikat) nil)
	(t (cons (kennzeichneTerm (car prädikat) id)
		 (kennzeichnePrädikat (cdr prädikat) id)))))
(defun kennzeichneDataBase (DataBase id)
  (cond ((null DataBase) nil)
	(t (cons (kennzeichnePrädikat (car DataBase) id)
		 (kennzeichneDataBase (cdr DataBase)
					       (+ id 1))))))

(defun deMorgen (liste1 liste2) ; vgl. oben
  (cond ((null liste1) nil) ;Alle oder-Alternativen haben nicht
					   ;geklappt
	((eq (car (car liste1) 'not)) ; not und not hebt sich auf
	 (cond ((main (cons (cdr (car liste1)) liste2)) t)
	       (t (deMorgen (cdr liste1) liste2))))
	(t (cond ((main (append liste2
			   (list (cons 'not (car liste1))))) t)
		 (t (deMorgen (cdr liste1) liste2))))))

(defun main (prädikat &aux i flag)
  (setq i 1)(setq flag nil)
  (while (and (not (null (nth i NewDataBase))) (null flag))
    (setq flag (match prädikat (nth i NewDataBase)))
    (setq i (+ i 1)))
  (cond ((and (listp flag) (not (null flag))) nil)
	(t (cond ((eq (car (car prädikat)) 'not)
		  (cond ((null (cdr prädikat)) (VarAusgabe))
			(t (main (cdr prädikat)))))
		 (t flag)))))

(defun generiereVarListe (prädikat)
 (cond ((null prädikat) nil)
       ((listp (car prädikat)) (cons (car (car prädikat))
				      (generiereVarListe
					     (cdr prädikat))))
       (t (generiereVarListe (cdr prädikat)))))

(defun VarAusgabe (&aux i)
  (setq i 1)
  (princ "t")(terpri)
  (while (not (null (nth i VarListe)))
    (princ (nth i VarListe) ":=" (eval (nth i VarListe)))(terpri)
    (setq i (+ i 1)))
  (princ "Weitersuchen (j/n) ?")
  (eq (read) 'n))

(defun prolog (prädikat)
  (setq VarListe (generiereVarListe (cdr prädikat)))
  (main (list prädikat)))

(defun init () (setq NewDataBase
				 (kennzeichneDataBase database 1)))
(princ "Nach Veränderungen der Datenbasis ist (init)
aufzurufen")(terpri)
(princ "Fragen an das System werden mit (prolog <Prädikat>)
gerichtet.")(terpri)

;---- Datenbasis ----

(setq database '(
  ((vater otto hans))((männlich hans)) ; Otto ist Vater von Hans
  ((vater otto ute)) ((weiblich ute))
  ((vater hans karl))((männlich karl))
  ((vater hans jörg))((männlich jörg))
  ((mutter ute anna))((weiblich anna))
  ((gleich (a) (a)))
  ((ungleich (a) (b)) (not gleich (a) (b)))
  ((elternteil (a) (b)) (vater (a) (b))) ; a Eleternteil von b
  ((elternteil (a) (b)) (mutter(a) (b)))
  ((geschwister (a) (b)) (elternteil (c) (a))(elternteil (c) (b))
			 (ungleich (a) (b)))
  ((kind (a)(b)) (vater (b)(a))) ; a ist Kind von b
  ((kind (a)(b)) (mutter (b)(a)))

  ((onkel (a)(b)) (männlich (a))(geschwister (c) (a))
			   (kind (c) (b)))
  ((tante (a)(b)) (weiblich (a))(geschwister (c) (a))
			   (kind (b) (c)))

))

(init)
(allow)

Die Datenbasis des Interpreters wird als Liste aller Regeln und
Fakten unter dem Namen database geführt und kann
selbstverständlich erweitert oder geändert werden. Danach ist
jedoch die Funktion (init) aufzurufen, die eine leicht
modifizierte Kopie der Liste für die weitere Bearbeitung erstellt
(s.u.).
Fragen werden an das System mit der Funktion prolog gerichtet,
z.B. (prolog '(onkel (x)(y))). Hier entfallen weitere
Listenklammern (d.h. (prolog '((onkel (x)(y))) ),
da diese Funktion nur eine Aussage erwartet.
Außerdem dürfen bei unserem Primitiv-Interpreter die
Variablennamen in den Fragen nicht bereits Namen von Variablen
innerhalb der Datenbasis sein. Hier empfehlen sich die
Anfangsbuchstaben x,y,z für Fragen.

Stellen Sie dem System doch mal ein paar Fragen.

Bitte wundern Sie sich aber nicht, daß die Anwortzeit mehrere
Minuten und länger ist : Backtracking ist zeitaufwendig, damit
ist Prolog langsam. Andererseits ist Lisp auch nicht gerade
schnell. Beides zusammen führt dann zum Wunsch nach einer 68030-
Karte, die ich mir aber auch nicht leisten kann...

Besprechen wir nun die einzelnen Funktionen :

match :

Hier wird geprüft, ob eine Aussageform mit einem Regelkopf oder
einem Faktum zusammenpaßt. Dazu wird zunächst ein vorangestelltes
not gegebenenfalls entfernt. Dann werden die Namen der Aussagen
verglichen. Stimmen Sie überein, wird die Funktion anpassen
aufgerufen, die das Passen der gegebenenfalls vorhandenen
Variablen und Konstanten im Regelkopf (Fakt) prüft und dabei
bereits die Terme der linken Seiten für eine Zusammenfassung
vorbereitet. Ist diese Funktion erfolgreich, so werden die
verglichenen Köpfe entfernt. Gemäß der Definition der not-
Operation wird hier nun weiter verfahren. Ergibt sich damit
definitiv das Ergebnis nil, wird das durch die Rückgabe der Liste
mit dem einizen Element nil extra gekennzeichnet.
Wurde not nicht benutzt, so wird geprüft, ob noch zu
verifizierende Aussagen übrig sind. Falls ja, werden diese durch
den Aufruf von main in Angriff genommen. Andernfalls wird
VarAusgabe aufgerufen, um den Erfolg der Berechnung mitzuteilen.

anpassen :

Hier werden die drei Regeln von oben auf die anzupassenden
Aussagen angewendet. Konstanten müssen dabei übereinstimmen,
Variablen bekommen den Wert von Konstanten. Treffen zwei
Variablen aufeinander, wird einer der Variablennamen durch den
anderen ersetzt. Dabei wird der 'ältere' Name bevorzugt.
Ersetzt wird grundsätzlich in beiden Aussagen bzw.
Aussagenfolgen. Daher dürfen zunächst beide Objekte keine
gemeinsamen Variablennamen besitzen. Sonst kommt es beim Ersetzen
zu Mißverständnissen. Die Funktion (init) sorgt aber dafür, daß
alle Veriablen einen Index erhalten, der sich aus der zugehörigen
Regel ergibt. So gibt es hier keine Probleme. Mit austauschen
werden hier die nötigen Veränderungen an den beiden Objekten
vorgenommen. Dabei ist zu beachten, daß Vergleiche, die in
anpassen nach einem Aufruf von austauschen geschehen, sich
bereits auf die veränderten Daten beziehen.
Weiterhin wird in anpassen auch die Ausgabe von Variablenwerten
bei der Lösungsdarstellung vorbereitet. Dabei wird bei jeder
Wertzuweisung, die eine Variable erhält, ihr Name als Lisp-
Variable eingerichtet, deren Wert dem der Zuweisung entspricht.
Dies vereinfacht die Ergebnisausgabe ungemeint, führt aber dazu,
daß Variablen in Fragen einen Namen tragen müssen, der sich nicht
bereits in der Datenbasis befindet. Sonst können andere
Zuweisungen die gewünschten Ergebnisse wieder überschreiben.

austauschen, ersetzeTerm :

Mit diesen Funktionen werden Variablen rekursiv in Listen von
Aussagen ersetzt.

kennzeichneTerm, kennzeichnePrädikat, init :

Diese Funktionen machen die Symbolnamen der Datenbasis eindeutig.
Variablen werden durch Listen gekennzeichnet. Daher liegt es
nahe, ihnen ein zweites Listenelement als Index zuzuordnen.
Später wird mit der Funktion equal verglichen, die ja Listen als
Parameter akzeptiert.

main :

Hier wird die Datenbasis abgesucht und fortlaufend match
aufgerufen. Daneben wird der not-Operator unterstützt.
main sorgt für das unterschiedliche Verzweigen an Weggabelungen,
um beim Bild des Labyrinths zu bleiben.

generiereVarListe :

Hier wird bei Anfragen eine Liste aller in der Frage enthaltener
Variablen erstellt, damit diese bei einer Ergebnisfindung
ausgegeben werden können.

VarAusgabe

bewerkstelligt gerade diese Ausgabe. Außerdem wird hier die Frage
nach dem Weitersuchen gestellt.

prolog

schließlich organisiert die Fragestellung und ruft zur
Bearbeitung main auf.


Um das Verständnis dieses doch schon etwas umfangreicheren
Programms zu verbessern bieten sich zwei Verbesserungen an :



Übungen

23. Beheben Sie den Mißstand, daß in den Fragestellungen die
    Variablennamen von denen in der Datenbasis verschieden sein
    müssen.

24. Führen Sie die Grundrechenoperationen als Teil des
    Interpreters ein. Sollen Ausdrücke wie (+ 1 3 2 (a)) etc.
    erlaubt sein und wie Zahlenkonstanten bewertet und verglichen
    werden. D.h. bei einem Verglich müssen alle Operandvariablen
    bereits durch Zahlenwerte ersetzt sein. Dann wird der gesamte
    Wert ermittelt und so getan, als hätte er hier bereits vorher
    als Konstante gestanden.

Weiterhin sollten Sie bei Programmläufen in Prolog die Lisp-
Funktionsaufrufe anzeigen lassen. So erkennen Sie genau den
Backtrackingmechanismus.



Ausblicke : Prolog und die KI

Prolog eigenet sich hervorragend für die Entwicklung von
Expertensystemen. Sie haben die Aufgabe, auf einem kleinen Gebiet
das Wissen eines menschlichen Experten zu besitzen und daraus
Entscheidungen und Antworten zu finden. So gibt es z.B. in der
Medizin Diagnosesysteme für Tropenkrankheiten.
Expertensysteme bestehen also wie Prolog-Programme aus einer
Wissensbasis, einem Mechanismus, dieses Wissen für Anfragen zu
benutzen und der Benutzerdialogschnittstelle.
Jedoch treten bereits bei der Definition des Wissens große
Probleme auf. Schließlich verfügen wir Menschen über Erfahrungen,
die sich nicht ohne weiteres in Regeln fassen lassen. Außerdem
ist es außerdem nicht einfach, Wissen aus einem Experten
herauszuholen. Die erklären oft erst einmal mit Beispielen, statt
mit formaler Logik.



Anhang
------


A. Befehlstabelle

allow		Kap.II.4	and		Kap.II.2.4
append		Kap.II.6	ascii		Kap.II.3.2
atan		Kap.II.3.1	atom		Kap.II.2.4
cadr		Kap.II.1	car		Kap.II.1
cast		Kap.II.3.1	cdr		Kap.II.1
chr		Kap.II.3.2	clear		Kap.II.5
close		Kap.II.4	cond		Kap.II.2.2
cons		Kap.II.1	cos		Kap.II.3.1
count		Kap.II.2.3	defmacro	Kap.II.2.1
defun		Kap.II.2.1	div		Kap.II.3.1
do		Kap.II.2.3	draw		Kap.II.5
ellipse 	Kap.II.5	eq		Kap.II.2.4
eql		Kap.II.2.2	equal		Kap.II.2.4
eval		Kap.II.1	exchange	Kap.II.6
exp		Kap.II.3.1	fill		Kap.II.5
float		Kap.II.3.1	forbid		Kap.II.4
free		Kap.II.6	graphic 	Kap.II.5
help		Kap.II.6	kill		Kap.II.6
killfile	Kap.II.4	killq		Kap.II.6
list		Kap.II.1	listp		Kap.II.2.4
load		Kap.II.4	log		Kap.II.3.1
mod		Kap.II.3.1	nofloat 	Kap.II.3.1
not		Kap.II.2.4	nth		Kap.II.1
null		Kap.II.2.4	open		Kap.II.4
or		Kap.II.2.4	polygon 	Kap.II.5
princ		Kap.II.2.2	princdat	Kap.II.4
progn		Kap.II.6	quote		Kap.II.1
random		Kap.II.5	read		Kap.II.4
readdat 	Kap.II.4	rgb		Kap.II.5
set		Kap.II.1	setq		Kap.II.1
sin		Kap.II.3.1	sqrt		Kap.II.3.1
strcat		Kap.II.3.2	strlen		Kap.II.3.2
substr		Kap.II.3.2	terpri		Kap.II.2.2
text		Kap.II.5	varlist 	Kap.II.6
while		Kap.II.2.3


B.Fehlermeldungen


ALisp unterscheidet zwischen Fehlern und Warnungen. Bei Warnungen
wird die Auswertung nicht abgebrochen, bei Fehlern ist eine
sinnvolle Weiterarbeit jedoch nicht möglich.

Warnungen :

String unbegrenzt	: Es fehlt das abschließende
Anführungszeichen. Dieses wird am Ende der Eingabe ergänzt.

Klammer [)] überflüssig : Es wurde eine Klammer eingelesen, zu
der es bislang kein Gegenstück gibt. Die Klammer wird ignoriert.

Punkt [.] falsch gesetzt : Die vorgeschlagene Punktepaarstruktur
ist nicht erlaubt und wird durch nil ersetzt.

Klammer [)] fehlt	: Am Ende der Eingabe ist eine Klammer noch
nicht geschlossen. Dies geschieht nun automatisch.

Symbol noch nicht definiert	: Der Symbolname ist bislang noch
unbenutzt. Sein Wert wird als nil angenommen.

Zuviele Argumente	: Beim Aufruf einer Funktion wurden zuviele
Parameter übergeben. Die überflüssigen werden ignoriert.

Nicht genug Argumente für Lambda-Term	: Hier wurden nun zuwenig
Parameter bereitgestellt. Die Fehlenden werden als nil gedeutet.

&aux oder &rest zuviel angegeben : Beide Schlüsselworte dürfen
jeweils nur einmal bei einer Funktionsdefinition benutzt werden.
Kommen beide vor, so muß zunächst &rest stehen.

syntaktisch falsche Zahl angegeben	: Der brauchbare Teil der Zahl
wird benutzt.

Zahl zu groß	: bereits bei der Eingabe der Zahl wird der
gültige Wertebereich überschritten. Ersatzweise wird hier 0
eingesetzt.

Bruch wurde approximiert	: Bei Umwandlungen zwischen den
Zahltypen gab es Probleme.

Daten konnten nicht geschrieben werden	: z.B. ist die
Zieldiskette voll.

Die Evaluierung wurde Abgebrochen	: Diese Warnung wird stets
ausgegeben, wenn Sie einen Programmablauf abbrechen, damit Sie
dies später im Dialogfenster nachvollziehen können.

Klammer (]) erwartet    : Eine komplexe Zahl ist nicht korrekt
formuliert. Die Klammer wird ergänzt.

Klammer (]) überflüssig : Diese Klammer gehört zu keiner
komplexen Zahl, sie wird ignoriert.


Fehlermeldungen :

Nicht genug Parameter	: Eine Primitive erhält nicht genug
Parameter.

Parameter ungeeignet	: Es wird ein spezieller Datentyp bei
einer Primitive gewünscht, der aber nicht vorliegt.

Zuviele Parameter	: - Gegenstück zu Parameter ungeeignet

'dos.library' konnte nicht geöffnet werden      : Diese
Systemblibiothek existiert nicht. Der Fehler sollte nie
auftreten, da diese Bibliothek sich im ROM befindet.

Quelltext konnte nicht geladen werden	: Beim Nachladen einer
Programmdatei treten Schwierigkeiten mit dem Speichermedium auf.

Quelltext zu lang	: Ein Programmmodul darf max. 40000 Zeichen
umfassen, vgl Kap.II.4.

dynamisch verwalteter Speicher ist voll : Während der Auswertung
hat sich der Computerspeicher restlos gefüllt. ALisp muß
verlassen werden, da wichtige Lispstrukturen unvollständig
bleiben. Bereits beim Start von ALisp kann eine ähnliche
Nachricht ausgegeben werden. Dann laufen im Hintergrund bereits
zuviele andere Tasks, oder zuviele Fenster sind geöffnet.

Parameter bezeichnet keine Liste	: eine Primitive erwartet
vergeblich als Parameter eine Liste.

Liste der Parameter falsch	: Die Parameterliste bei einem
Lambda- oder einem Macro-Term ist formal unsinnig.

Grafikmodus bereits eingeschaltet	: Es wurde (graphic)
ausgeführt, obwohl der Grafikbildschirm bereits eingeschaltet
ist.

'intuition.library' kann nicht geöffnet werden  : Auch dieser
Fehler kann eigentlich nicht auftreten.

'graphics.library' kann nicht geöffnet werden: s.o.

Der Grafikscreen kann nicht geöffnet werden	: Der Speicher im
Chip-Memory reicht für das Grafikfenster nicht mehr aus.

Grafikmodus nicht eingeschaltet : Grafikbefehle sollen
ausgeführt werden, obwohl das Grafikfenster nicht geöffnet ist.

Wert außerhalb [-190;190] bzw.

Wert außerhalb [-218;218] bzw.

Bildschirmgrenze überschritten	: deuten an, daß die
Koordinaten eines Grafikbefehls außerhalb des dargestellten
Bereichs liegen.

Division durch Null	: selbsterklärend

Zahl zu groß für ASCII	: Beim chr-Befehl wurde der Wertebereich
nicht eingehalten.

Liste beginnt nicht mit einem Befehl	: Es wurde eine Liste
interpretiert, die weder mit einer Primitive noch mit einem
Lambda-/MacroTerm beginnt.

Wert außerhalb des Definituionsbereichs von sqrt oder log	:
Diese Befehle benötigen nicht negative bzw. positive Zahlen.

Komponenten müssen zu (reellen) Zahlen auswerten        : Zwei in
eckige Klammern eingeschlossene Ausdrücke werten nicht zu Zahlen
aus, d.h. es entsteht nicht die durch die Klammern angedeutete
komplexe Zahl.



C. Der Quelltext des Lisp-Interpreters

Im Verzeichnis Moduln der Programmdiskette befindet sich der
komplette C-Quelltext (Aztec C 3.4) des Lisp-Interpreters,
aufgeteilt in neuen Moduln.
Wenn Sie sich in C auskennen, können Sie den Interpreter nach
eigenen Bedürfnissen ändern oder erweitern. Dazu möchte ich hier
kurz einen Überblick des Programmaufbaus geben. Bei mehr als 5000
Programmzeilen ist eine genaue Dokumentation in diesem Rahmen
jedoch nicht möglich.
Im folgenden beziehe ich mich mit Namen direkt auf Daten und
Funktionen in Interpreter.

Die grundlegenden Datenstrukturen

Alle Lisp-Daten werden auf dem Heap angelegt. Dazu gibt es einige
Verkettungsstrukturen. Zur Identifizierung erhält jede Struktur
eine Typkennung, die sich stets in der Komponente knotentyp
wiederfindet.

atom

- nimmt alle Lisp-Atome als Zeichenkette auf. Zahlen werden
jedoch verschlüsselt : zeichenkette[0]=='æ' dient als Kennung und
zeichenkette[1] kann die Werte 'B' für Bruch- oder 'F' für
Fließkommazahl enthalten.
Um mit Zahlknoten leichter arbeiten zu können, gibt es für Brüche
die Struktur bruch und für Fließkommazahlen die Struktur dezimal.
Beide sind aber Spezielfälle von atom. Wahrheitswerte werden
nicht mit Knoten festgehalten. NIL wird durch einen Nullzeiger
und t (TRUE) durch den Zeiger 'wahr' dargestellt. Zu jeder
Primitive existiert ein fest angelegter Knoten, so daß auch hier
nur Zeiger verwaltet werden müssen.
Atome erhalten die Typkennung 2.

paar

- ist ein Punktepaar-Knoten, d.h. ein Paar von Zeigern auf
weitere Strukturen vom Typ paar oder auf Atom-Knoten. Mit dieser
Struktur werden Listen und Bäume verkettet. Typkennung : 1
Mit paar werden aber auch Real- und Imaginärteil komplexer Zahlen
verbunden. Dabei wird die Typkennung 4 benutzt.

varlist

- ist ein Knoten zum Aufbau eines binären Variablenbaums (siehe
unten). Folglich existieren Zeiger auf den rechten/linken
Teilbaum. Ein weiterer Zeiger weist auf einen atomaren Knoten,
der den Namen der Variable aufnimmt. Der letzte Zeiger bezeichnet
den Wert des Symbols. Wegen der Gültigkeitsbereiche von Variablen
kann ein Symbol mehrfach belegt sein. Daher werden die
verschiedenen Werte in einer stackähnlichen Liste verwaltet, d.h.
der jüngste Symbolwert führt die Liste an. Die Wurzel des
Variablenbaums ist symbolliste. Typkennung : 3


Die Funktionen

Modul 1 :

Zur Speicherverwaltung

Vom System wird ein 32K-großer Bereich angefordert, der nun
selbstständig verwaltet wird. Dazu werden Marken eingeführt: Zu
Beginn jedes Eintrags im Bereich steht ein Zeiger, der auf den
nächsten Eintrag bzw. auf den nächsten Freiraum weist. Diese
Zeiger deuten nur auf gerade Adressen. So kann das untere Bit als
Kennung benutzt werden, ob das nachfolgende Segment frei, oder ob
es mit Daten belegt ist (gesetzt = belegt). Das Ende des
selbstverwalteten Speichers wird durch den Zeiger 0xfffffffe
markiert. Reicht der angeforderte Speicher nicht aus, so wird ein
weiterer 32K-Block initialisiert. Zur Verkettung dieser Blöcke
wird die Adresse des neuen Blocks mit 0x80000001 AND-verknüpft
und an die Stelle des alten 0xfffffffe- Zeigers gesetzt. Das Feld
segmente verwaltet die 32K-Blöcke.
Da Knoten des Typs paar immer die gleiche Speichergröße belegen,
wird extra für sie eine andere Speicherverwaltung eingeführt.
Dabe wird zunächst ein ca. 30K großes Segment reserviert, indem
eine Freispeicherliste eingeführt wird, d.h. eine lineare Liste,
die alle für paare vorgesehenen Zellen verbindet. Sind alle
Einheiten eines solchen Segments besetzt, so wird auch hier
dynamisch je ein weiteres hinzugefügt.

Mit den Befehlen neu und NPaar wird Speicher für Atome und
Variablenverkettungsknoten (bei neu) und Punktepaare (bei NPaar)
bereitgestellt. Bein neu muß demnach die Größe des gewünschten
Speichers mitgeteilt werden.
Der Befehl dispose kann wie in Turbo-Pascal auf alle reservierten
Knoten angewendet werden.
Für die Pufferung von Ein- und Ausgaben werden zusätzlich
ebenfalls jeweils 32K reserviert.

Da bei der Abarbeitung eines Lisp-Programms sehr viele
unterschiedlich große Knoten anfallen, muß eine Garbage-
Collection implementiert sein, die sich auf die Speichersegmente
der Atome bezieht. Sie gliedert sich in zwei Teile:
Tritt ein akuter Speichermangel auf, so werden zunächst
benachbarte freie Speichereinheiten zusammengefaßt. (Funktion
angliedern) Gelengt der Interpreter auf die 0-te Rekursionsebene,
so kann eine komplette Garbage-Collection durchgeführt werden, da
nun keine Zeiger auf gespeicherte Objekte mehr auf dem Stack
liegen können. Dabei werden alle unnützen Freiräume in den 32K-
Segmenten durch Umkopieren behoben. Die Referenzen der
verschobenen Daten werden in allen Knoten und Kopfzeigern
geändert.

Ein-/Ausgabe von Listen

Mit den Funktionen output und input können Listen ein- und
ausgegeben werden. Sie stützen sich auf listout, leerweg, atomin
und listin ab.
Die Ausgabe kann in eine Datei, auf den Drucker und auf den
Bildschirm gelangen. datprint sorgt für den richtigen Datenfluß.
Die Prozedur edit ruft Funktionen zur Eingabe von der Tastatur
auf.


Modul 2

Variablenverwaltung

Die Funktionen suchsymbol, searchsymbol, initsymbol und delsymbol
lesen, schreiben oder ändern im Variablenbaum. rekaus und vlist
geben alle gespeicherten Symbolnamen aus.

ALisp-Primitive

Die Namen der Lisp-Befehle werden in initbefehl festgelegt. Hier
werden sie auch alphabetisch sortiert, damit spätere Suchen binär
und damit schneller geschehen können. Die Anzahl der Befehle muß
im Macro anzahl festgelegt sein. Dieses findet sich sowohl in
Modul 2 als auch in Modul 1. Die Anzahl muß stimmen!
Die Funktion befehl prüft, ob ein Befehl vorliegt.

Auswertung von Lisp-Ausdrücken

evaluate ist die Kernprozedur des Interpreters. Hier wird
geprüft, ob ein Atom oder ob eine Liste ausgewertet werden soll.
Bei Atomen werden als Ergebnis der Auswertung diese ohne
Veränderung wieder zurückgegeben. Nur Symbole bilden eine
Ausnahme: Hier wird ihr Wert mitgeteilt, bei Primitiven deren
Nummern.
Soll eine Liste ausgewertet werden, so muß das erste
Listenelement zu einem Lambda- oder Macro- Term auswerten oder
aber eine Primitive sein. Die zu den Primitiven gehörenden
Bearbeitungsprozeduren werden nun über eine Sprungtabelle
erreicht.

main ist das Hauptprogramm. Hier werden Parameter beim Aufruf des
Interpreters gelesen und hier liegt auch die
Eingabe-Auswertung-Ausgabe - Schleife, die das Grundprinzip von
Lisp-Interpretern ist.

Modul 3

Zunächst findet sich hier eine Tabelle aller Fehlermeldungen.
Dann folgt die Funktion genug_parameter, die überprüft, ob eine
Lisp-Primitive genug Parameter erhält. Danach folgen die
grundlegenden Primitiven. Ihre Implementation ist für sich
betrachtet jeweils leicht zu durchschauen. Deshalb möchte ich
hier nur den prinzipiellen Aufbau eines Befehls besprechen.

Soll ein neuer Befehl hinzugefügt werden, so müssen die beiden
anzahl-Macros
um 1 erhöht werden. In Modul2 wird die Realisierungsprozedur als
extern gekennzeichnet. Der Name des neuen Befehls wird an die
Tabelle in initbefehl gehängt und der Aufruf der Prozedur wird an
das Ende der Sprungtabelle in evaluate geschrieben. evaluate
übergibt nun einen Zeiger auf die Liste aller Parameter, die mit
atom und paar aufgebaut ist. Bei der Abarbeitung dieser Liste muß
dafür gesorgt werden, daß keine hängenden Zeiger entstehen, d.h.
wenn die Listenelemente nicht zu neuen Strukturen verarbeitet
werden, sollten sie gelöscht werden.
Jede Befehlsfunktion muß einen Zeiger auf ein Atom oder auf eine
Liste zurückgeben. Soll eine Primitive ohne Rückgabewert
definiert werden, so ist der Zeiger leeres_atom zurückzugeben.


Beispiel der Implementierung einer Befehlsfunktion XY


struct atom *XY(parameter)
struct paar *parameter;
{  if(genug_parameter(parameter,2,3))
   {  struct atom *hilf;
      struct paar *merke;
      hilf=evaluate(parameter->CAR);
      merke=parameter;parameter=parameter->CDR;dispose(merke);
      [...]
      return(leeres_atom);
   }
   else
   {  delete(parameter);
      return(-1L);
   }
}


Die Primitive erwartet mindestens zwei und höchstens 3 Parameter.
Ist diese Voraussetzung nicht erfüllt, so wird die Parameterliste
gelöscht. Dazu dient delete, delete löscht stets einen kompletten
Lisp-Baum - dispose hingegen löscht genau einen Knoten.
Ein Zeiger mit dem Wert -1L weist immer auf einen Fehler hin.
Stimmen die Voraussetzungen, so wird der erste Parameter
ausgewertet, und anschließend wird die Parameterliste
entsprechend verkürzt. Mit hilf liegt nun sein Wert für weitere
Berechnungen ebenfalls in Form der Lisp-Strukturen vor.
Entsprechend können auch die restlichen Parameterinformationen
gewonnen werden.

In Modul3 werden auch Zahlenformate umgewandelt. Mit den Befehlen
getfloat und getint können aus Zahlknoten Ganzzahl- oder
Fließkommazahlen gelesen werden. Weiterhin ist hier die
Bruchrechnung implementiert.

Modul 4

Hier finden sich die Lisp-Kontrollstrukturen. Die zugehörigen
Funktionen sind aufgebaut wie Befehlsfunktionen. Die Umsetzung
wird leicht verständlich, wenn man die Definition dieser
Programmelemente berücksichtigt.

Noch eine Bemerkung zu den Schleifen : Bei jedem
Schleifendurchlauf wird eine Kopie des Schleifenrumpfes erstellt,
die dann abgearbeitet wird. Dadurch benötigen Schleifen etwa
ebensoviel Speicherplatz wie die entsprechenden rekursiven
Lösungen.

Modul 5

Die Stringbefehle sind denen von Basic und XLisp nachempfunden.

Modul 6

In diesem Modul sind alle Grafikbefehle definiert. Wird der
Grafikmodus eingeschaltet, so erscheint ein neues Fenster. Dazu
wird aber, falls nötig, noch ein Speicherbereich für den
Fill-Befehl im Chip-Mem angelegt.

Modul 7

Hier sind die Requester für Druckerausgaben und für die
Bearbeitung von Variablen definiert.

Modul 8

Die Benutzerschnittstelle macht Gebrauch von den vielfältigen
Möglichkeiten des Amiga-Betriebssystems. Soll ALisp auf andere
Rechner portiert werden, so
wird sich hier die Hauptarbeit ergeben :
Zunächst werden die Pulldownmenüs definiert, anschließend das
Arbeitsfenster und Mauszeiger. nprint gibt Texte im Dialogfenster
aus, rprint stellt sie zusätzlich noch in einer Warnfarbe dar.
coninit bindet die Benutzeroberfläche ins System ein. menu fragt
die Menüs ab. cursorcontrol steuert den Cursor im
Eingabefenster, escape prüft den Menüpunkt "Evaluierung
abbrechen" und newcon liest schließlich aus dem Eingabefenster
einen Text ein und verbindet die anderen
Interaktionsmöglichkeiten. conreinit schließt die
Benutzeroberfläche.
In diesem Modul wird der Filerequester der ARP.library geöffnet.
Ist die Bibliothek nicht vorhanden, wird ersatzweise ein
einfacher Textrequester mit req aufgerufen.

Modul 9

Hier ist der Editor realisiert. Als Arbeitsspeicher belegt er ein
Feld der Größe maxZeilen * 80, indem für jede Zeile 80 Bytes zur
Verfügung stehen.
Dabei nehmen die Bytes 0-77 die Zeichen auf, 78 ist 0 und 79
dient als Merker beim Anzeigen von geöffneten Klammern.
Außerdem gibt es noch die Liste zei->len, in der die aktuelle
Anfangsadresse jeder belegten Zeile gespeichert ist. Beim
Einfügen oder Löschen von Zeilen wird dann nur diese
Referenzliste geändert. Nicht benutzte Zeilen sind in einer
Freispeicherliste organisiert, die mit den jeweils ersten vier
Bytes der freien Zeilen aufgebaut ist.
Die Funktionen transfer1 und transfer2 verbinden den
Arbeitsspeicher mit der Außenwelt, indem sie seinen Inhalt in den
über textpuffer bezeichneten Speicherbereich als ASCII-Datei
übertragen, bzw. diesen Vorgang umkehren.
Beim Laden und Speichern wird dann auch über den
textpuffer-Bereich operiert.
Die Funktion transform dient der Umwandlung der RAWKEY-Codes der
Tastatur in ASCII-Zeichen.

Zur Compilierung :

Das Programm erwartet Integer-Zahlen der Länge 4 !!! Bytes. Bei
vielen Zeigerzuweisungen treten Typkonflikte auf, die aber vom
C-Compiler korrekt behandelt werden.
Die Mathe - Library m.lib muß !!! hinzugelinkt werden.



Viel Spaß mit ALisp...