Ich lerne Lisp

Die ganzen Design-Geschichten haben auch vor den Farbeinstellungen meines Emacs nicht halt gemacht. Da ich da jetzt mit der Konfiguration in Kontakt gekommen bin, habe ich angefangen, mich generell intensiver mit Emacs zu befassen. Einerseits wage ich den Einstieg in org-mode (dazu wird vielleicht irgendwann auch ein Artikel folgen), andererseits nehme ich das zum Anlass, mich endlich mal gezielt mit Lisp zu befassen.

Heutiges Tagesziel: Ich schreibe mir ein Quicksort in Lisp. Hilfsmittel: Die Einführung für Nicht-Programmierer, das Referenz-Manual und natürlich Google.

Und um zu üben, dokumentiere ich das ganze in Form eines org-mode-Dokuments mit eingebettem Sourcecode und Inline-Anzeige der Ergebnisse. HTML-Export ist auch da – wenn ich das dann sinnvoll ins Blog importiert bekomme, werde ich wohl meinen Workflow umstellen und alle zukünftigen Blogartikel im Emacs schreiben. Aber: Abwarten. (Spoiler: Es hat geklappt, Artikel dazu folgt irgendwann.)

Ziel ist also Quicksort. Den Weg dahin teile ich mir in Dinge ein, von denen ich denke, dass ich sie brauchen werde, angefangen bei einem Hello World.

Hello World

Wenn ich diesen Code ausführe

kommt der Wert des letzten Ausdruckes zurück:

Hello World

Das ist ein Hello World ohne Bildschirmausgabe. Das Ergebnis des „Programms“ ist einfach der Rückgabewert des letzten Ausdruckes (kennt man aus Perl, wo jedes Modul mit 1; aufhört, weil das require sonst ein false sieht und das für eine Fehlermeldung hält). Mit org-mode als „Ent­wick­lungs­um­ge­bung“ ist das sehr praktisch, weil man das direkt anzeigen kann, ohne erst die Extrarunde über „Ergebnis in Text umwandeln, Text nach STDOUT ausgeben, STDOUT ins org-mode-Dokument einlesen“ zu gehen. Das funktioniert aber natürlich auch, wenn man :results output benutzt:

"Hello World"

Variablen

Variablen, Funktionen und so weiter sind allesamt Symbole. Zu setq habe ich jetzt gar keine Definition gelesen, da bin ich drüber gestolpert und es tut, was ich erwarte:

7

Listenoperationen

Generell werden Listen und Arrays unterschieden. Listen sind wohl der „Normalfall“ und Arrays werden nur in bestimmten Situationen benutzt. Strings sind Sonderfälle von Arrays. Vektoren ebenfalls; bei ihnen kann man direkt auf ein beliebiges Element zugreifen, während eine Liste jedes Mal vom Beginn bis zum gewünschten Element durchlaufen werden muss, denn Listen sind intern als linked list implementiert. Wichtige Begriffe dabei: CAR ist der Pointer auf den Inhalt eines Listenelementes (sog. cons cell), CDR ist der Pointer auf das nächste Listenelement.

Jetzt kommt dieses komische Quoting zum Tragen, da muss ich doch mal nachlesen…

((1 2 3) (4 5 6) (1 2 3))

Mit car und cdr kommt man an die entsprechenden Teile einer Liste, das werde ich für den Quicksort noch brauchen:

((b c d e f) a)

Mit nth und nthcdr holte man sich den n-ten Eintrag aus einer Liste. Wie üblich, geht die Element-Zählung bei 0 los:

(2 (4 5))

setcar und setcdr verändern eine Liste - naheliegenderweise:

(1 2 3)

Ein Selbstbezug in einer Liste (endlose Rekursion) wird übrigens folgendermaßen dargestellt:

((na . #0) batman)

Vergleiche

eq implementiert das selbe (Pointer-Vergleich), während equal das gleiche implementiert (Wert-Vergleich). t ist true und nil (die leere Liste) ist false.

t

t

nil

t

if implementiert wie gewohnt ein if in der Form if Bedingung Then-Zweig Else-Zweig:

richtig

Funktionen

Functionen werden mit defun deklariert (es gibt auch noch Makros und defalias, aber das habe ich mir nicht weiter angeguckt). Es folgen die Parameterliste, optional eine Beschreibung und der auszuführende Code. In der Parameterliste kann mit &optional und &rest gesteuert werden, ob Parameter optional sind und ob alle zusätzlichen Parameter in einer Liste zusammengefasst werden sollen (Perl würde letzteres als sub foo($$@) umsetzen).

117

Die Parameter der Funktion sind automatisch lokal. Braucht man weitere lokale Variablen, muss man innerhalb der Funktion let* statt setq benutzen. Lustigerweise hat let* den Scope seiner Variablen (also den eigentlichen Code) „im Bauch“, was bei genauerer Betrachtung total logisch ist und die Programmstruktur fördert. Warum der Befehl aber so ein lustiges Sternchen im Namen hat, weiß ich nicht.

3

Mehr Listenfunktionen

Das reicht jetzt schon fast für ein Quicksort, aber ich brauche noch eine „Filterfunktion“ für eine Liste, um alle Elemente kleiner/größer dem Pivot-Element zu bekommen. mapcar bearbeitet alle Elemente einer Liste und gibt die Ergebnisliste zurück, ganz so wie map() in Perl:

(2 3 4 5 6)

Das ist mit einem Stück statischen Code die 1+ natürlich langweilig, also muss da richtiger Code übergeben werden, der jedes Listenelement bearbeitet. Trara, jetzt habe ich eine Lambda-Funktion am Hals. Das klang immer super kompliziert, aber ich glaube, ich kann mir auch das wieder von Perl herleiten: Das ist eine anonyme Codereferenz, die ich einer anderen Funktion mitgebe, damit sie die jeweils auf Daten aufruft. Beispiel wäre das oben schon genannte map() in der Form map { $hash{$_} } keys(%hash) (was alle Values aus einem Hash liefern würde – ja, dafür gibt es values(%hash), aber das ist ja auch nur ein schlechtes Beispiel). Ein anderes bekanntes Beispiel ist sort { $a <=> $b } @array.

Also quadrieren wir mal ein paar Zahlen:

(1 4 9 16 25)

Das kann man dann mit einem if koppeln und unpassende Werte durch nil ersetzen, die man später mit delq aus der Liste entfernt:

(rock paper scissors spock)

Außerdem ich muss Listen zusammenknoten können – mit list habe ich bisher nur neue Listen von Listen erstellt, das reicht nicht aus. Dafür gibt es append, das quasi die oberste Listenebene seiner Argumente auspackt und sie dann in eine gemeinsame Liste packt:

(1 2 3 4 5 a b c (A1 A2) (B1B2))

Quicksort

Schaun wir doch mal:

(-7 -1 0 2 3 6 9)

Gewonnen!

Das geht natürlich alles schöner, aber für „heute selbst zusammengefrickelt“ finde ich das ganz ok.