Lispkurs - Zum Praktikum „KI-basierte Robotersteuerung“

Lispkurs
”
Zum Praktikum
KI-basierte Robotersteuerung“
Lorenz Mösenlechner
[email protected]
Thomas Rühr
[email protected]
Organisatorisches
Arbeit in Gruppen bis zu drei Leuten
Aufbau des Praktikums
1. Teil: KI-Aufgaben
2. Teil: Projektaufgabe
Überblick
1. Stunde: Grundlegende Lisp-Programmierung
Einführung
Interpretation von Lisp-Ausdrücken
Funktionale Programmierung
2. Stunde: Weiterführende Lisp-Konstrukte
Imperative Programmierung
Sonstiges
Teil I
Grundlegende Lisp-Programmierung
Überblick
1. Einführung
2. Interpretation von Lisp-Ausdrücken
3. Funktionale Programmierung
Warum Lisp?
Wichtigste Sprache im Bereich der KI
Effizienz
Schnelle Programmentwicklung möglich
Kurze, gut lesbare Programme
Warum nicht C?
Verschiedene Programmierstile
(funktional, imperativ, objektorientiert)
Automatische Speicherverwaltung
Dynamische Typisierung
Eingebaute Listenverarbeitung
Funktionen höherer Ordnung
Gleichförmige Syntax
Lisp kann Code zur Laufzeit erzeugen
Erweiterbarkeit
Kurze Geschichte von Lisp
1958: John McCarthy beginnt Arbeit an Lisp 1
Lisp 1.5 bis Ende der 60er Jahre
Ende der 60er Jahre:
MacLisp (Effizienz), InterLisp (Bedienbarkeit)
1975: Entwicklung von Scheme
1980: Existenz einer Vielzahl von Lisp-Dialekten, die meist
untereinander inkompatibel waren
1984: Guy Steele Jr: Common Lisp the Language
aktuell: ANSI-Standard
Was Lisp alles kann
Editoren: Multics Emacs, Gnu Emacs
KI: SHRDLU, Eliza, Student, MYCIN (eines der ersten
Expertensysteme), Macsyma
CAD: AutoCAD
Mirai (Izware): Lisp-basiertes Animationssystem (benutzt um
Gollum und andere Figuren in The Lord of the Rings“ zu
”
erschaffen)
Jak and Daxter: the Precursor Legacy (Naughty Dog
Software): 3D Spiel für Sony Playstation II
Wie sieht Lisp aus?
Arithmetik:
Listen:
Funktionen:
(+ 1 2 3 4 5 6 7 8 9)
(/ 2 4)
(∗ (+ 7 3) (- 15 27))
nil =()
b =’()
b
(cons 3 ’(2 1))
(first ’(1 2 3 4))
(rest ’(1 2 3 4))
(defun fakultaet (n)
(∗ n (fakultaet (- n 1))))
(fakultaet 5)
Was heißt eigentlich LISP“?
”
steht offiziell für
LISt Processing language“
”
Was heißt eigentlich LISP“?
”
steht offiziell für
LISt Processing language“
”
böse Zungen behaupten, es ist die Abkürzung für
Lots of Irritating Superfluous Parentheses“
”
Überblick
1. Einführung
2. Interpretation von Lisp-Ausdrücken
Atome
Listen
Daten und Code
3. Funktionale Programmierung
Die Read-Eval-Print-Schleife
read
"hören"
eval
"verstehen"
print
"antworten"
Atome
Nicht-Symbole (Konstanten)
Zahlen
Zeichen (Characters)
Zeichenreihen (Strings)
Symbole
Variablen
Alles, was nicht anders interpretiert werden kann, ist ein
Symbol.
Groß- und Kleinschreibung spielt keine Rolle.
Auswertung von Atomen
Nicht-Symbole: werden zu sich selbst ausgewertet
Symbole: zugewiesener Wert
Beispiel
x
⇒ Error: Attempt to take the value of the unbound variable ‘X’.
(setf x 4)
⇒4
x
⇒4
Listen
Form: (a b c d)
Leere Liste: ’() bzw. nil
Interne Struktur von Listen:
cons-Zelle: Paar von Zeigern
der erste heißt car
der zweite heißt cdr
Schreibweise als dotted pair“: ’(1 . 2)
”
Eine Liste wird intern als cons-Zellen dargestellt.
’(1 (2 3) 4)
(cons 1 (cons (cons 2 (cons 3 nil)) (cons 4 nil)))
’(1 . ((2 . (3 . nil)) . (4 . nil)))
Auswertung von Listen
Das erste Listenelement kann sein:
Funktionsname
1. Werte alle Argumente (d.h. Rest der Liste) aus
2. Wende Funktion auf ausgewertete Argumente an
Spezialform: Auswertung je nach Funktionalität
Makro
1. Expandiere Makro
2. Auswertung der Expansion
Verhinderung der Auswertung
Mit der Spezialform quote kann man die Auswertung eines
Ausdrucks verhindern.
Abkürzung: (quote x) entspricht ’x
Aufpassen bei Listen, die Daten enthalten!
Beispiel
x ⇒ Error:...
(quote x) ⇒ X
(1 2 3)
⇒ Error: Funcall of 1 which is a non-function.
’(1 2 3)
⇒ (1 2 3)
Zusammenhang zwischen Daten und Code
Lisp hat nur die grundlegenden Konstrukte
Atom“ und Liste“
”
”
gequotete Konstrukte werden als Daten verstanden
alles andere ist Code
Fazit
äquivalente Darstellung von Daten und Code
dadurch einfacher Übergang von Daten zu Code
insbesondere Codegenerierung zur Laufzeit möglich!
Zusammenfassung
read
Symbol
Wert des Symbols (der Variable)
Nicht−Symbol
eigener Wert
special form
entsprechende Auswertung der Argumente
Makro
1. Funktionsaufruf von macroexpand
2. Funktionsaufruf von eval
Funktion
1. eval auf dem Rest der Liste
2. Funktionsanwendung auf ausgewertete Argumente
Atom
"hören"
Ausdruck
eval
"verstehen"
Liste
print
"antworten"
Überblick
1. Einführung
2. Interpretation von Lisp-Ausdrücken
3. Funktionale Programmierung
Arithmetik
Listen
Vergleiche
Funktionen
Lokale Variablenbindung
Bedinungen
Logische Operatoren
Arithmetische Operationen
Rechnen: + - ∗ /
Vergleichen: <
Zahlen finden:
>
<= >=
=
(random 100): Zufallszahl zwischen 0 und 99
(min 2 3 4): Minimum bestimmen (genauso max)
Noch mehr Rechnen:
(1+ x) =(+
b
x 1), (1- x) =(b x 1) √
(expt x y): x y , (exp x): e x , (sqrt x): x
(round x), (truncate x), (floor x), (ceiling x)
(sin x), (cos x), (tan x), (asin x), (acos x), (atan x)
Listenoperationen (1)
Konstruktion
(cons a l) fügt Element a vorne an Liste l an
(list a1 a2 ...) konstruiert eine Liste mit den Elementen a1, a2,
...
(append l1 l2) konkateniert Listen l1 und l2
Prädikate
(null l) Ist l die leere Liste?
(listp x) Ist x eine Liste?
(member a l) Ist a ein Element der Liste l?
Listenoperationen (2)
Selektion
(first l) erstes Listenelement von l
ältere Bezeichnung: (car l)
(second l), (third l), ... (tenth l)
zweites/drittes/...zehntes Listenelement
(nth i l) i-tes Element von l
(last l) Liste mit letztem Element von l
(rest l) Liste l ohne das erste Element
ältere Bezeichnung: (cdr l)
Listenoperationen (3)
Assoziationslisten
Eine Assoziationsliste ist eine Liste von Dotted Pairs“.
”
Jedes Paar besteht aus einem Schlüssel und einem Wert.
assoc sucht nach einem bestimmten Schlüssel:
(assoc 2 ’((1 . a) (2 . b) (3 . c))) ⇒ (2 . B)
rassoc sucht nach einem bestimmten Wert:
(rassoc ’b ’((1 . a) (2 . b) (3 . c))) ⇒ (2 . B)
Gleichheitsoperationen (1)
eq vergleicht Symbole (also Zeiger)
eql vergleicht Symbole und Zahlen
equal vergleicht Ausdrücke jeden Typs
equalp ist noch allgemeiner
Strings mit verschiedener Groß- und Kleinschreibung
Zahlen verschiedenen Typs
= vergleicht Zahlen
string= vergleicht Zeichenreihen
Gleichheitsoperationen (2)
x
’x
0
’(x)
”xy”
”Xy”
0
0
y
’x
0
’(x)
”xy”
”xY”
0.0
1
eq
T
?
nil
nil
nil
nil
nil
eql
T
T
nil
nil
nil
nil
nil
equal
T
T
T
T
nil
nil
nil
equalp
T
T
T
T
T
T
nil
eq
eql
equal
equalp
Funktionen
Definition: (defun NAME PARAMLIST BODY)
Besonderheiten bei der Parameterliste
Beliebig viele Parameter:
(par-1 ... par-n &rest rest)
Optionale Parameter:
(par-1 ... par-n &optional opt-1 ... opt-m)
Schlüsselwort-Argumente:
(par-1 ... par-n &key opt-1 ... opt-m)
opt-i kann folgende Gestalt haben:
name
(name wert)
(name wert sp)
Funktionen - Beispiele (1)
rest-Parameter
(defun plus (a &rest l)
(+ a (sum-up l)))
(defun sum-up (l)
(if (null l)
0
(+ (first l) (sum-up (rest l)))))
(plus 1 2 3) ⇒ 6
Funktionen - Beispiele (2)
key-Parameter
(defun bsp (a b &key c (d a))
(list a b c d))
(bsp 1 2)
⇒ (1 2 nil 1)
(bsp 1 2 :d 3 :c 4) ⇒ (1 2 4 3)
Funktionen als Werte
Funktionen können an andere Funktionen übergeben werden.
Funktionen können als Resultat zurückgegeben werden.
Funktionen, deren Argumente oder Resultate Funktionen sind,
nennt man Funktionen höherer Ordnung.
Werte eines Symbols
Ein Symbol kann gleichzeitig
einen Variablenwert,
einen funktionalen Wert und
eine Property-List
haben.
Den funktionalen Wert erhält man
mit der Spezialform function
mit #’ als Abkürzung für function
mit symbol-function
Werte eines Symbols — Beispiele
Funktionswert eines Symbols
(function cons) =#’cons
b
=(symbol-function
b
’cons)
⇒ #<Function CONS>
Beschreibung eines Symbols
(defun x () 3)
(setf x 5)
(describe ’x)
⇒
X is a SYMBOL.
Its value is 5
It is INTERNAL in the COMMON-LISP-USER package.
Its function binding is #<Interpreted Function X>
The function takes arguments ()
Funktionen höherer Ordnung (1)
Mit funcall und apply kann man funktionale Werte auf ihre
Argumente anwenden
Diese Ausdrücke sind äquivalent
(cons 1 2)
(funcall #’cons 1 2)
(apply #’cons ’(1 2))
Statt apply und funcall kann man auch eval benutzen, was
allerdings kein guter Stil ist:
Beispiel
(eval ’(cons 1 2))
Funktionen höherer Ordnung (2)
Statt Schleifen verwendet man in Lisp gern die Funktion
mapcar. Sie wendet eine Funktion auf alle Elemente einer
(mehrerer) Liste(n) an.
Beispiele:
Beispiel
(mapcar #’1- ’(1 2 3))
⇒ (0 1 2)
(mapcar #’first ’((a b) (c d))) ⇒ (A C)
(mapcar #’+ ’(1 2 3) ’(4 5 6)) ⇒ (5 7 9)
Nochmal Symbole (1)
Mit intern kann man aus einer Zeichenkette ein Symbol
machen.
Beispiel zu function und symbol-function:
Beispiel
(function (intern ”CONS”))
⇒ Error: ‘(INTERN ”CONS”)’ is not fbound
(symbol-function (intern ”CONS”))
⇒ #<Function CONS>
Nochmal Symbole (2)
Warum will man Symbole erzeugen?
Früher
(cond ((equal x a) (fun-a))
((equal x b) (fun-b))
((equal x c) (fun-c)))
Jetzt
(funcall
(symbol-function
(intern (string-upcase (concatenate ’string ”fun-” x)))))
Anonyme Funktionen
Zu jedem Element einer Liste 5 addieren
(defun plus5 (x) (+ x 5))
(mapcar #’plus5 liste)
Dies ist allerdings die einzige Stelle in unserem Programm, wo
plus5 benötigt wird. Daher wäre es besser, wenn wir der Funktion
gar keinen Namen geben müssten.
Mit anonymer Funktion
(mapcar #’(lambda (x) (+ x 5)) liste)
Allgemeiner Aufbau einer Anonymen Funktion:
(lambda PARAMLIST BODY)
Variablenbindung mit let
let bildet einen Programmblock mit lokalen Variablen:
Beispiel
(let ( (x 40)
(y (+ 1 1)) )
(+ x y))
⇒ 42
Vergleich mit Lambda-Abstraktion:
(let ((x val)) body) und
((lambda (x) body) val)
sind äquivalent.
Variablenbindung mit let*
Bei let ist die Reihenfolge der Variablenbindung nicht
spezifiziert.
Bei let* werden die Variablen der Reihe nach gebunden.
Beispiel
(let ( (x 1)
(y (∗ 2 x)) )
(+ x y))
⇒ Error: Attempt to take the value of the unbound variable ‘X’.
(let* ( (x 1)
(y (∗ 2 x)) )
(+ x y))
⇒3
Bindung von Funktionen (1)
Mit flet und labels kann man lokal Funktionen definieren.
Der Wirkungsbereich von flet ist nur der Rumpf des
flet-Ausdrucks.
Der Wirkungsbereich von labels ist der Rumpf und die
labels-Deklaration selbst. Die mit labels deklarierten
Funktionen können sich also gegenseitig aufrufen.
Bindung von Funktionen (2)
Beispiel
(defun tail-length (liste)
(labels ( (tail-length-1 (l acc)
(if (null l)
acc
(tail-length-1 (rest l) (1+ acc)))) )
(tail-length-1 liste 0)))
Bedingungen (1)
Einfache Fallunterscheidung: (if p a b)
Wenn p erfüllt ist, mache a, sonst mache b.
Nur ein zu betrachtender Fall:
when: (when p a-1 ... a-n)
Wenn p erfüllt ist, führe a-1 bis a-n aus.
unless: (unless p a-1 ... a-n)
Wenn p nicht erfüllt ist, führe a-1 bis a-n aus.
Bedingungen (2)
Komplexere Fallunterscheidung:
(cond (p1 a1)
(p2 a2)
...
(pn an))
Logische Operatoren
Der Wahrheitswert false wird durch nil ausgedrückt.
Alles andere ist true, insbesondere die Konstante t.
Logische Operatoren: not, and, or
Besonderheiten bei and und or
lazy evaluation“
”
beliebig viele Argumente möglich:
Beispiel
(and (or nil 3 2 (and (not 4) 1 2 3)) t (not nil) (and 7 5 3 1))
interne Darstellung durch if und cond
Teil II
Weiterführende Lisp-Konstrukte
Überblick
4. Imperative Programmierung
Wertzuweisung und Seiteneffekte
Variablendeklaration
Sequentielle Komposition
Schleifen
Ein-/Ausgabe
5. Datentypen
6. Was es sonst noch gibt
Wertzuweisung
Spezialform setf
Beispiel
(setf var-1 expr-1 ... var-n expr-n)
var-i bekommt den Wert expr-i zugewiesen
Abarbeitung von links nach rechts
Beispiel
(setf x 10 y 20 z (+ x y))
Andere Möglichkeiten der Wertzuweisung: set, setq
Seiteneffekte
Veränderung beliebiger Strukturelemente
Beispiel
(setf liste ’(1 2 3 4))
(setf (second liste) 5)
liste
⇒ (1 5 3 4)
Funktionen, die setf enthalten:
(push a l) =(setf
b
l (cons a l))
(pop l) =(prog1
b
(first l)
(setf l (rest l))
(incf a) =(setf
b
a (1+ a))
(decf a) =(setf
b
a (1- a))
Variablendeklaration
Globale Variablen:
(defvar var-name init-val)
init-val ist optional
(defparameter var-name value)
(defconstant var-name value)
value muss angegeben werden und kann im Programm nicht
verändert werden
Oder let-Ausdruck mit globalen Variablen,
Funktionsdefinitionen im Rumpf.
Am besten keine globalen Variablen verwenden.
Sequentielle Komposition
Aneinanderreihung mehrerer Kommandos
(prog1 form-1 ... form-n)
form-1 bis form-n werden ausgewertet
Ergebnis des Ausdrucks ist Resultat von form-1
(progn form-1 ... form-n)
Ergebnis des Ausdrucks ist Resultat von form-n
In vielen Befehlen implizite progn-Anweisung:
defun, let, cond, when, unless
Achtung bei if !
Hier gibt es keine implizite progn-Anweisung.
Äquivalent zu finally:
(unwind-protect <body> <protection-forms>)
Schleifen
Allgemeinste Schleifen: do und loop
Weitere häufig benötigte Schleifen:
(dolist (var list res) body)
(dotimes (var upper res) body)
Beispiel
(let ((x 0))
(dolist (v ’(1 2 3) (* 3 x))
(setf x (+ x v))))
⇒ 18
Schleifen sollten nach Möglichkeit vermieden und durch
Rekursion oder Mapper ersetzt werden!
Ein-/Ausgabe
Eingabe:
(read) gibt eingelesenen Ausdruck zurück
(read-line) gibt eingelesene Zeile als String zurück
Ausgabe:
(format stream ”format-string” arg-1 ... arg-n)
Ausgabe mit format
Stream-Parameter:
Rückgabe des Format-Strings: nil
Ausgabe des Format-Strings: T
Formatierungsanweisungen
Alles mögliche: ∼a (Ascii)
Formatierte Zahlen: ∼f
Zeilenumbruch: ∼%
Beispiele
(format
(format
(format
(format
nil ”hello, world”)
t ”hello, world”)
t ”Irgendwas: ∼a, ∼a, ∼a” 25 ”hallo” ’(1 2))
t ”Zahl mit 2 Nachkommastellen: ∼,2f” 0.1234)
Ein-/Ausgabe von Dateien
Öffnen einer Datei: (open file)
Schließen eines Streams: (close stream)
Einfacher mit with-open-file
(with-open-file (stream file) body)
ist äquivalent zu
(let ((stream (open file)))
(unwind-protect
body
(close stream)))
Optionen für Ausgabe zum Überschreiben der Datei
(with-open-file (s f :direction :output :if-exists :supersede) body)
Überblick
4. Imperative Programmierung
5. Datentypen
6. Was es sonst noch gibt
Datentypen
Lisp ist dynamisch typisiert, d.h. Typinformation wird zur
Laufzeit überprüft
Auszug aus der Typhierarchie:
character
function
rational
real
t
number
symbol
integer
ratio
float
complex
string
vector
sequence
bit−vector
cons
list
null
fixnum
bignum
Typprüfung zur Laufzeit
Funktionen für die Typprüfung:
Allgemein: (typep obj typ)
Typspezifisch
Typerkennung: (type-of obj)
Beispiele
(typep 5 ’number) ⇒ T
(type-of #c(5 1)) ⇒ COMPLEX
(type-of ’nil)
⇒ NULL
(listp ’(1 2 3))
(numberp 23)
(symbolp ’a)
(ratiop 2/3)
⇒
⇒
⇒
⇒
T
T
T
T
Strukturen
defstruct Typconstruktor zum Generieren von
Record/Struktur-Typen
Beispiel
(defstruct cons-cell
car
cdr)
Generierung neuer Funktionen:
Konstruktor: make-cons-cell
Selektor: cons-cell-car, cons-cell-cdr
Typerkenner: cons-cell-p
Kopierfunktion: copy-cons-cell
Hash-tables
Common lisp unterstützt hash-tables als built-in Datentyp
Erstellen einer hash-table: make-hash-table
Look-up: get-hash
Ändern eines Eintrags:
(setf (gethash key hash-table) new-value)
Löschen eines Eintrags: remhash
Überblick
4. Imperative Programmierung
5. Datentypen
6. Was es sonst noch gibt
Makros
Mehrere Rückgabewerte
Debugging
Makros
Eigene Sprachkonstrukte erzeugen
Definition ähnlich wie bei Funktionen mit defmacro
Viele eingebaute Lisp-Makros: and, or, cond, defun
Auswertung von Makros:
1. Aufruf von macroexpand
2. Evaluierung der erhaltenen Lisp-Form
Beispiel:
Beispiel
(macroexpand ’(and a b))
⇒ (IF (NOT A) (PROGN NIL) (COND (T B)))
Mehrere Rückgabewerte
Funktionen hatten bisher einen Rückgabewert.
Für mehrere Werte hat man zwei Möglichkeiten
1. (list a-1 ... a-n) ⇒ ein Rückgabewert
2. (values a-1 ... a-n) ⇒ mehrere Rückgabewerte
Ansprechen der einzelnen Rückgabewerte:
1. mit first, second, ...
2. Bindung der Rückgabewerte
multiple-value-list
muliple-value-bind
Beispiel
(multiple-value-bind (w r) (floor 13 12) (+ w r)) ⇒ 2
Debugging
Verfolgen rekursiver Funktionen: (trace hfunctioni)
Ausschalten: (untrace hfunctioni)
Ausgaben mit (format t ...)
kleine Funktionen/Funktionsteile direkt in der Lisp-Umgebung
entwickeln
Außerdem nützlich:
(describe ’hsymboli)
(apropos ’hsymboli)
liefert alle bekannten Symbole mit hsymboli im Namen