Lisp
Lisp ist eine funktionale Programmiersprache.
Syntax
Die Syntax von Lisp ist im Gegensatz zu der anderer Programmiersprachen sehr einfach. Zahlen und Zeichenketten folgen den Gepflogenheiten anderer Sprachen:
5.234
"Dies ist eine Zeichenkette."
Symbole, als den anderen elementaren Datentypen gleichgestellt, gibt es in gängigen anderen Programmiersprachen nicht. Symbole haben ihre Entsprechung in den Bezeichnern anderer Programmiersprachen, dass heisst Variablen- oder Prozedurnamen. Symbole können Werte haben.
dies-ist-ein-symbol
Listen sind von Klammern umschlossen. Die einzelnen Elemente (die nicht vom gleichen Typ sein müssen) sind durch Leerzeichen voneinander getrennt.
(dies ist eine liste "mit" 7 Elementen)
nil
()
Die leere Liste kann durch nil oder () dargestellt werden.
Alle Strukturen, die man aus Zahlen, Zeichenketten, Symbolen und Listen aufbauen kann, nennt man S-Expressions ("Symbolic Expressions").
Damit ist die Syntax von Lisp im wesentlichen beschrieben, es stellt sich die Frage, wie S-Expressions ausgewertet werden.
Auswertung
Der Wert von Zahlen und Zeichenketten ist jeweils die Zahl oder Zeichenkette selbst.
Der Wert eines Symbols ist diesem in einer Umgebung (Environment) zugeordnet, oder nicht. Der Versuch, den Wert eines ungebundenen Symbols zu bestimmen, löst eine Ausnahme aus.
Der Wert der leeren Liste nil ist wiederum die leere Liste. Anderenfalls wird der Wert des ersten Listenelements bestimmt, dieser Wert muss eine Funktion sein. Abhängig von der Funktion werden die weiteren Elemente der Liste ausgewertet oder nicht ausgewertet als Argumente an die Funktion übergeben. Der Wert der gesamten Liste ergibt sich als Wert der Funktionsanwendung auf die Argumente.
> (+ 2 3 4)
9
Hier ist das Symbol + an eine Funktion gebunden, die die ausgewerteten restlichen Elemente der Liste summiert.
Der folgende Abschnitt führt weitere, vordefinierte Funktionen ein.
Grundfunktionen
Die Funktion quote schützt ihr Argument von der Auswertung.
> (quote (+ 2 3 4))
(+ 2 3 4)
Die Funktion eval wertet ihr Argument zwei mal aus und ist das Gegenstück zu quote.
> (eval (quote (+ 2 3 4)))
9
Die Funktion setq bindet ein Symbol an einen Wert. Das erste Argument von setq wird nicht ausgewertet.
> (setq a (* 2 3))
6
> (* a 4)
24
Mit bound? kann überprüft werden, ob ein Symbol einen zugeordneten Wert hat.
> (bound? (quote a))
t
> (bound? (quote hgftzh))
nil
Die Funktion intern wandelt eine Zeichenkette in ein gleichnamiges Symbol.
> (intern "abc")
abc
Es stehen die Funktionen +, -, * und / für jeweils beliebig viele Argumente zur Verfügung. Die Funktion rem berechnet den Divisionsrest. Zur Bestimmung des ganzzahligen Anteils einer Zahl dient die Funktion floor. Random erzeugt ganzzahlige Zufallszahlen zwischen 0 einschließlich und dem Wert des Arguments ausschließlich.
> (+ 2 3 4)
9
> (+)
0
> (- 9 5)
4
> (- 9 2 3)
4
> (- 9)
-9
> (-)
0
> (* 2 3 4 5)
120
> (*)
1
> (/ 120 5)
24
> (/ 120 5 4 3)
2
> (/ 3)
0.3333
> (rem 5 2)
1
> (floor (/ 23 4))
5
> (random 50)
15
Die Funktion write-to-string schreibt ihr Argument in eine Zeichenkette.
> (write-to-string (list (quote a) 2))
"(a 2)"
Das Gegenstück zu write-to-string ist read-from-string, diese Funktion liest eine S-Expression aus einer Zeichenkette.
> (read-from-string "(b 3)")
(b 3)
Mit concatenate können zwei Zeichenketten konkateniert werden.
> (concatenate "Das ist eine " "längere Zeichenkette.")
"Das ist eine längere Zeichenkette."
Ein Teil einer Zeichenkette lässt sich mit substring ermitteln. Das zweite Argument von substring ist die Position des gewünschten Teils. Das erste Zeichen der Zeichenkette hat die Position 1. Das dritte Argument ist die Länge der gewünschten Teilzeichenkette.
> (substring "abcdef" 2 2)
"bc"
Die Position einer Teilzeichenkette innerhalb einer längeren Zeichenkette kann mit search-string gesucht werden.
> (search-string "lange" "dies ist eine lange zeichenkette" 1)
15
String-length ermittelt die Länge einer Zeichenkette.
> (string-length "abc")
3
Weitere Funktionen für Zeichenketten sind string-upcase, string-downcase und string-trim.
> (string-upcase "Dies ist eine lange Zeichenkette")
"DIES IST EINE LANGE ZEICHENKETTE"
> (string-downcase "Dies ist eine lange Zeichenkette")
"dies ist eine lange zeichenkette"
> (string-trim " abc ")
"abc"
Mit der Funktion cons wird eine Liste an ihrem Anfang um ein Element erweitert.
> (cons (quote a) (quote (b c)))
(a b c)
Die Funktion first ermittelt das erste Element einer Liste. Aus historischen Gründen ist car ein alternativer Name der Funktion.
> (first (quote (a b c)))
a
Die Funktion rest liefert alle Listenelemente bis auf das erste. Der historische Name ist cdr.
> (rest (quote (a b c)))
(b c)
Last liefert das letzte Element einer Liste.
> (last (quote (a b c))
c
Eine Liste in umgekehrter Reihenfolge erhält man mit reverse.
> (reverse (quote (c b a)))
(a b c)
Mit list können beliebig viele Elemente zu einer Liste zusammengefasst werden. Die Funktion wertet ihre Argumente aus.
> (list 1 2 3 4)
(1 2 3 4)
Während list seine Argumente zu den Elementen einer Liste macht, erwartet append Listen als Argumente und liefert die konkatenierte Liste als Resultat.
> (append (quote (1 2)) nil (list 3 4 5))
(1 2 3 4 5)
Mit list-length wird die Länge einer Liste ermittelt.
> (list-length (quote (a b c)))
3
Das Prädikat list? überprüft, ob es sich bei seinem Argument um eine Liste handelt.
> (list? (cons 1 nil))
t
> (list 2)
nil
Das Prädikat tail? liefert den Wert t, wenn das erste Argument eine Liste ist, die das Ende der List ist, die als zweites Argument übergeben wurde.
> (tail? (quote (c)) (quote (a b c)))
t
Um eine Funktion auf alle Elemente einer Liste anzuwenden und die entstehenden Resultate wiederum als Liste zu erhalten, benutzt man mapcar.
> (mapcar (lambda (x) (+ x 1)) (quote (2 3 4)))
(3 4 5)
Mit sort kann eine Liste sortiert werden. Die gewünschte Reihenfolge wird durch eine Vergleichsfunktion festgelegt.
> (sort (quote (2 1 4 3)) less?)
(1 2 3 4)
Ob ein Element in einer Menge enthalten ist, überprüft member?.
> (member? (quote c) (quote (a b c d)))
(c d)
> (member? (quote x) (quote (a b c d)))
nil
Hinzufügen kann man ein Element mit adjoin.
> (adjoin (quote c) (quote (a b c d)))
(a b c d)
> (adjoin (quote x) (quote (a b c d)))
(x a b c d)
Zwei Mengen können mit union vereinigt werden.
> (union (quote (a b c d)) (quote (b d e f))
(c a b d e f)
Mit assoc können Name-Wert-Paare aus einer Assoziationsliste anhand des Namens gefunden werden.
> (setq alist
(quote
((eins 1 one)
(zwei 2 two)
(drei 3))))
((eins 1 one) (zwei 2 two) (drei 3))
> (assoc (quote zwei) alist)
(zwei 2 two)
> (assoc (quote vier) alist)
nil
Mit acons kann eine Assoziationsliste um einen Eintrag erweitert werden.
> (acons (quote vier) 4 alist)
((vier 4) (eins 1 one) (zwei 2 two) (drei 3))
Pairlis erweitert eine Assoziationsliste um mehrere Einträge.
> (pairlis
(quote (vier fünf))
(quote (4 5))
alist)
((fünf 5) (vier 4) (eins 1 one) (zwei 2 two) (drei 3))
Das Prädikat null? überprüft, ob sein Argument den Wert nil hat.
> (null? nil)
t
> (null? 1)
nil
> (null? (list 1 2 3))
nil
Mit type-of kann der Typ des übergebenen Arguments bestimmt werden.
> (type-of 2)
rational
> (type-of "abc")
string
> (type-of (quote abc))
atom
> (type-of (list 1 2 3))
list
> (type-of nil)
list
> (type-of (lambda (x) x))
lambda
Eq? entscheidet, ob seine beiden Argumente gleich sind. Zahlen, Zeichenketten, Symbole und Listen sind als Argumente zulässig.
> (eq? 1 2)
nil
> (eq? (list 1 2 3) (quote (1 2 3)))
t
Mit less? können Zahlen, Zeichenketten und Symbole verglichen werden.
> (less? 3 2)
nil
> (less? "a" "x")
t
> (less? (quote a) (quote x))
t
Die Funktion lambda erzeugt Funktionen. Beide Argumente von lambda werden nicht ausgewertet. Das erste Argument ist eine Liste von Symbolen, die Parameter der erzeugten Funktion. Das zweite Argument ist der Rumpf der Funktion.
> ((lambda (x) (* x x)) 9)
81
Zusammen mit setq kann man mit lambda also neue, benannte Funktionen erzeugen.
> (setq square (lambda (x) (* x x)))
(lambda (x) (* x x))
> (square 8)
64
Eng mit der Funktionsdefinition verknüpft ist die Deklaration von lokalen Variablen mit let.
(let ((symbol-1 expr-1)
(symbol-2 expr-2)
...
(symbol-n expr-n))
body)
Let definiert die lokalen Variablen symbol-1 bis symbol-n und belegt diese mit den Werten, die sich durch die Auswertung von expr-1 bis expr-n ergeben. Der Rumpl body wird in einer Umgebung ausgeführt, in der die lokalen Variablen definiert sind. Der Wert von body wird zum Wert des gesamten let-Ausdrucks.
> (let ((x 2) (y 3)) (+ x y))
5
Der let-Ausdruck ist semantisch äquivalent zu einem Term mit lambda.
((lambda (symbol-1 ... symbol-n) body) expr-1 ... expr-n)
Ähnlich wie let arbeitet letrec. Die Struktur eines wohlgeformten letrec-Ausdrucks ist die gleiche wie für let. Der Unterschied besteht daran, in welcher Umgebung die Terme expr-1 bis expr-n ausgewertet werden. Während bei let die Auswertung in der Umgebung erfolgt, aus der der let-Ausdruck aufgerufen wurde, erfolgt bei letrec die Auswertung in der Umgebung, in der die neuen lokalen Variablen definiert werden. Mit letrect ist es deswegen möglich, lokale Variable mit sich gegenseitig oder rekursiv aufrufenden Funktionen zu belegen.
If wertet sein erstes Argument aus. Wenn dieser Wert ungleich nil ist, wird das zweite Argument ausgewertet, ansonsten das dritte. Die leere Liste nil stellt den Wahrheitswert falsch dar, alle anderen Werte den Wahrheitswert wahr. Es wird das Symbol t verwendet, wenn kein anderer Wert ungleich nil nahe liegt, um den boole'schen Wert true auszudrücken. Viele Lisp Prädikate liefern anstelle des Werts t einen anderen sinnvollen Wert ungleich nil.
> (if t "wahr" "falsch")
"wahr"
Mit cond können mehrfache Fallunterscheidungen ausgedrückt werden. Ein Cond-Ausdruck hat im allgemeinen folgende Struktur:
(cond (expr-11 [expr-12])
(expr-21 [expr-22])
...
(expr-n1 [expr-n2]))
Die in eckigen Klammern eingeschlossenen Ausdrücke expr-12, expr-22, ..., expr-n2 sind optional. Die Auswertung eines Cond-Ausdrucks erfolgt so, dass zunächst expr-11 ausgewertet wird. Wenn sich der Wert nil ergibt, wird expr-21 ausgewertet usw. Wenn auch expr-n1 den Wert nil ergibt, ist der Wert des gesamten Cond-Ausdrucks nil. Wenn ein expr-i1 einen Wert ungleich nil ergibt, ist das der Wert des gesamten Cond-Ausdrucks, wenn der optionale Teil expr-i2 fehlt. Ansonsten wird expr-i2 ausgewertet und das Resultat dieser Auswertung ist das Resultat des gesamten Ausdrucks.
Das Prädikat and liefert die Und-Verknüfung mehrerer Ausdrücke, indem die Ausdrücke expr-1, expr-2, ..., expr-n von links nach rechts ausgewertet werden, bis eine Auswertung den Wert nil ergibt oder expr-n ausgewertet wurde. Der Wert des gesamten And-Ausdrucks
(and expr-1 expr-2 ... expr-n)
ist der Wert des letzten ausgewerteten Ausdrucks expr-i.
> (and 1 2 nil 3)
nil
> (and 1 2 3 4)
4
> (and)
t
Das Prädikat or verknüpft mehrere Ausdrücke mit oder, indem die Ausdrücke expr-1, expr-2, ..., expr-n von links nach rechs ausgewertet werden, bis eine Auswertung einen Wert ungleich nil ergibt oder expr-n ausgewertet wurde. Der Wert des gesamten Or-Ausdrucks
(or expr-1 expr-2 ... expr-n)
ist der Wert des letzten ausgewerteten Ausdrucks expr-i.
> (or nil 2 nil 4)
2
> (or nil nil nil nil)
nil
> (or)
nil
Die Ausnahmebehandlung basiert auf den beiden Funktionen catch und throw. Beide erwarten zwei Argumente und werten diese aus. Beim ersten Argument handelt es sich um ein Symbol, dass zur Unterscheidung der Ausnahmen dient. Beim Catch-Ausdruck
(catch symbol expr-1)
wird expr-1 ausgewertet. Wenn keine Ausnahme auftritt, ist der Wert von expr-1 der Wert des gesamten Ausdrucks. Wenn innerhalb von expr-1 ein Teilterm der Form
(throw symbol expr-2)
gefunden wird, wird die Auswertung von expr-1 abgebrochen. Der Wert des Catch-Ausdrucks ist in diesem Fall der Wert des Ausdrucks expr-2 (vorausgesetzt die Symbole in catch und throw sind die gleichen). System-Ausnahmen, wie Division durch Null, werden mit dem Symbol error ausgelöst. Anstelle eines Symbols ist beim ersten Argument von catch auch nil erlaubt. In diesem Fall fängt catch alle Ausnahmen auf, ungeachtet des bei throw übergebenen Symbols.
> (catch (quote exception) (+ 9 8))
17
> (catch
(quote exception)
(+
(throw (quote exception) "hallo welt")
8
7))
"hallo welt"
> (catch (quote error) (+ 3 (/ 2 0)))
"divide by zero"
Beispiel
In diesem Beispiel wird die etwas umfangreichere Funktion maze mit drei Parametern definiert.
Die Funktion erhält die Repräsentation eines Labyrinths als erstes Argument, einen Startpunkt und einen Endpunkt als weitere Argumente. Die Funktion berechet einen Weg vom Startpunkt durch das Labyrinth zum Endpunkt und gibt diesen als Resultat zurück. Wenn kein Weg gefunden werden kann, wird die Ausnahme failed ausgelöst (nach "Lisp - Eine Einführung in die Programmierung", H. Stoyan, G. Görz, Springer (1986), ISBN 3-540-16914-8, Kapitel 7.1.6).
Das Beispiel benutzt letrec, um eine Reihe von lokalen Hilfsfunktionen zu deklarieren. Im Rumpf von letrec wird die Funktion erzeugt, die an das Symbol solve-maze gebunden wird.
(setq solve-maze
(letrec
((explore-maze
(lambda (structure agenda end-node)
(cond
((empty-agenda? agenda)
(throw (quote failed) nil))
((eq? end-node (path-destination (first-agenda agenda)))
(first-agenda agenda))
((explore-maze
structure
(schedule-agenda
(rest-agenda agenda)
(fork-path structure (first-agenda agenda)))
end-node)))))
(fork-path
(lambda (structure path)
(if (visited-place-twice? (place-list path))
nil
(mapcar
(lambda (place) (append-place place path))
(reachable-places structure (path-destination path))))))
(visited-place-twice?
(lambda (places)
(member? (first places) (rest places))))
(reachable-places
(lambda (structure place)
(let
((edges (assoc place structure)))
(if (null? edges)
nil
(cdr edges)))))
(the-empty-path (lambda () nil))
(append-place cons)
(path-destination car)
(place-list identity)
(place-list-in-order reverse)
(empty-agenda? null?)
(first-agenda car)
(rest-agenda cdr)
(schedule-agenda append)
(make-agenda
(lambda (place)
(cons
(append-place place (the-empty-path))
nil))))
(lambda (structure start-node end-node)
(if (eq? start-node end-node)
(the-empty-path)
(place-list-in-order
(explore-maze structure
(make-agenda start-node)
end-node))))))
Die Orte im Labyrinth werden durch Symbole dargestellt. Das Labyrinth an sich wird durch eine Assoziationsliste repräsentiert, die zu jedem Ort die von dort direkt erreichbaren Orte als Liste aufführt.
(setq structure
(quote ((in x a)
(x in)
(a in b c)
(b a)
(c a d e)
(d c)
(e c f l)
(f g e h)
(g f)
(h f i j)
(i h)
(j l h out)
(k l)
(l e j k))
)
)
Der zugrundeliegende Algorithmus, der den Weg durch das Labyrinth bestimmt, ist eine breite-zuerst Suche in einem gerichteten Graph. Bei einer breite-zuerst Suche werden mehrere Pfade gleichzeitig untersucht. Die Datenstruktur, die die mehreren Pfade aufnimmt, heisst hier Agenda. Zur Verwaltung der Agenda sind mehrere Hilfsfunktionen deklariert:
make-agenda - erzeugt eine initiale Agenda mit einem Pfad,
empty-agenda? - überprüft, ob die Agenda leer ist,
first-agenda - liefert den ersten Pfad in der Agenda,
rest-agenda - alle Pfade der Agenda, bis auf den ersten,
schedule-agenda - fügt weitere Pfade in die Agenda ein.
Auch für die Arbeit mit Pfaden sind Hilfsfunktionen vereinbart:
the-empty-path - erzeugt einen leeren Pfad,
append-place - erweitert einen Pfad um einen Ort,
path-destination - liefert den Ort am Ende des Pfads,
place-list - liefert die Orte auf dem Pfad als Liste,
place-list-in-order - liefert die Orte auf dem Pfad in deren Reihenfolge.
Die eigentliche Arbeit wird von der Hilfsfunktion explore-maze erledigt. Explore-maze überprüft zunächst, ob die Agenda noch unbearbeitete Pfade enthält. Wenn nein, ist die Suche fehlgeschlagen.
Ansonsten wird der erste Pfad aus der Agenda darauf überprüft, ob er im gewünschten Zielort endet. Wenn das der Fall ist, werden die Orte auf dem Pfad als Resultat zurückgegeben.
Wenn der Endpunkt noch nicht erreicht wurde, wird der erste Pfad der Agenda erweitert. Das Erweitern eines Pfades übernimmt die Hilfsfunktion fork-path. Dabei entstehen neue Pfade, die mit schedule-agenda in Agenda eingefügt werden.
Fork-path testet den zu erweiternden Pfad zunächst mit visited-place-twice? darauf, ob er einen Ort mehrfach enthält. Wenn das der Fall ist, wird der Pfad nicht erweitert.
Anderenfalls werden die von Endpunkt des Pfades direkt erreichbaren Orte durch einen Aufruf von reachable-places bestimmt. Für jeden erreichbaren Ort wird mit append-place ein neuer Pfad erstellt.
Der Beispielaufruf, der einen Weg von in nach out sucht, hat folgendes Ergebnis:
> (solve-maze structure (quote in) (quote out))
(in a c e l j out)