(sort-by): Lisp sortiert

(init)

Anfang Dezember 2021 verfasste Ralf Hersel den Artikel "Python sortiert" auf dieser Plattform, in dem er erläutert, wie man in Python eine mehrdimensionale Liste nach einem Feld seiner Wahl sortiert. Ich merkte an, dass sich für so etwas eigentlich eher Lisp anböte (immerhin bedeutet bereits sein Name "List Processor"), woraufhin ich gebeten wurde, selbst einen Artikel darüber zu schreiben, wie man dasselbe Problem in Lisp lösen könne.

Hier ist er nun, dieser Artikel. Aber zunächst ein wenig Geschichte, denn ich mag Geschichte.

(show-history)

Lisp ist, nachdem ein Jahr früher, im Jahr 1957, erstmals spezifizierten Fortran die zweitälteste höhere Programmiersprache, die bis heute überliefert ist. Ihr geistiger Vater, der Turing-Award-Preisträger John McCarthy, war einer der Autoren desjenigen Dokuments, das den Begriff der "künstlichen Intelligenz" einführte, und selbst in diesem Bereich tätig. Jahrzehntelang, an manchen Hochschulen bis heute, war Lisp insofern die dominante Sprachfamilie, was die Erforschung künstlicher Intelligenz betrifft. Lisp wurde vom Lambda-Kalkül inspiriert, das an dieser Stelle zu erklären selbst mir übertrieben scheint.

Bis in die 1980er Jahre hinein wurde die Forschung an künstlicher Intelligenz auch finanziell stark gefördert. Federführend war hierbei ein Team am Massachusetts Institute of Technology (MIT), das ab 1973 mit der Entwicklung von Lisp-Maschinen begann, also Computern, die allein dem Zweck dienten, möglichst effizient Lisp und darin geschriebene Programme auszuführen. Da Computer in der heutigen Form noch nicht existierten, war damit allerdings auch ein lukrativer Markt verbunden, weshalb ab Ende des Jahrzehnts die Firmen Symbolics und Lisp Machines entstanden, die versuchten, mit diesem markttauglichen Konzept Geld zu verdienen. Symbolics hielt dabei länger durch; bis in die 2010er Jahre hinein ist überliefert, dass das US-amerikanische Verteidigungsministerium das Unternehmen für fortlaufende Wartungsverträge bezahlte. Der wirtschaftliche Zwist zwischen den beiden Unternehmen und, damit verbunden, auch im jetzt in miteinander konkurrierende Gruppen zerfallenen AI Lab am MIT führte letztendlich dazu, dass Richard Stallman das GNU-Projekt ins Leben rief, das zum Ziel haben sollte, eine freie Version von Lisp auf einer freien Alternative zu Unix auszuführen und damit gedankenverwandten Hackern eine Plattform zu geben, die frei von wirtschaftlichen Interessen sein sollte. Vor diesem historischen Hintergrund ist es wenig erstaunlich, dass viele GNU-Anwendungen, von GNU Emacs (das Emacs Lisp einsetzt) bis hin zum Betriebssystem Guix (das Guile Scheme einsetzt), eine Variante von Lisp als Scriptsprache verwenden.

Inzwischen gibt es neben historischen Lisp-Dialekten wie Emacs Lisp, das vom in den 1960er Jahren im Project MAC ("Project on Mathematics and Computation") am MIT entwickelten Maclisp inspiriert worden ist, sowie einigen Hobbysprachen die vier bedeutsamen Sprachvarianten Common Lisp, Racket, Scheme und Clojure, auf deren Unterschiede ich weiter unten etwas genauer eingehe. Betrachtet man Lisp nicht als starre Syntaxregel, sondern als Funktionskatalog, so könnte man übrigens vortrefflich darüber streiten, ob nicht auch Ruby und Python annehmbare Varianten von Lisp seien, aber diese Diskussion ist recht akademisch und darum hier ohne Wert.

(show-basics)

Die Grundzüge von Lisp - die unzweifelhaft als Lisp zu verstehenden Sprachen betreffend - sind schnell erläutert: Alles ist eine Liste (oder eine Liste von Listen), wobei die Anzahl an notwendigen Sonderzeichen sich in Grenzen hält: Ein Block beginnt mit ( und endet mit ). Darüber wurden mannigfaltige Scherze gemacht, von denen einige sicherlich sehr amüsant sind, sie hier zu rezipieren ergäbe aber wenig Sinn. Auch weitere Gemeinsamkeiten teilen die regulären Lisps: Funktionen jeglicher Art, auch die mathematischen, folgen der umgekehrten polnischen Notation (so schreibt man etwa, analog zu (funktion wert1 wert2), (+ 1 2 3) statt (1 + 2 + 3)) und Funktionen können zur Laufzeit umprogrammiert werden; es ist also möglich, ein Programm zu entwickeln, während man es benutzt. Das wird dadurch begünstigt, dass die meisten gängigen Implementierungen von Lisp im kompilierten Programm ihre eigene Laufzeitumgebung einbinden.

Wer den Closed-Source-Ansatz schätzt und darum nicht möchte, dass seine Anwender in seinen Programmen herumprogrammieren, der kann dieses Verhalten natürlich auch unterbinden, aber auch das würde den Rahmen dieses Artikels sprengen. Manche Lisp-Compiler, etwa SBCL (eine Implementierung von Common Lisp), ermöglichen im Übrigen auch die Nutzung als Interpreter, so dass man Lisp ebenso als Scriptsprache nutzen kann wie Shellscript, Perl und Python.

(or '(common-lisp racket scheme clojure))

Ich werde in diesem Artikel zur Lösung des eingangs geschilderten Problems aus rein zufälligen Gründen Common Lisp mit dem freien SBCL-Interpreter als Sprache verwenden. Wer tiefer in die Welt von Lisp einsteigen möchte, der hat neben verschiedenen anderen Common-Lisp-Versionen (bis hin zu den kommerziellen IDEs LispWorks und Allegro Common Lisp) die Wahl zwischen Racket, Scheme und Clojure.

Common Lisp

Common Lisp wurde in den 1980er Jahren erstmals spezifiziert. Wie sein Name schon sagt, verfolgte man mit ihm das Ziel, die konkurrierenden Versionen von Lisp (darunter Maclisp) zu vereinheitlichen. Bekanntlich funktioniert so etwas immer hervorragend. Common Lisp zeichnet sich durch eine große Standardbibliothek und ausgereifte Bibliotheken für allerlei Aufgaben aus. Zu den bekannteren in Common Lisp geschriebenen Programmen gehört das Mathematikprogramm Maxima, die Sprache eignet sich jedoch auch für das Entwickeln von Web- und Desktopanwendungen.

Scheme

Scheme, eine in den letzten Jahren wieder populär gewordene Sprache, entstand wiederum am MIT ungefähr zur gleichen Zeit wie die Lisp-Maschinen, hat aber bis heute überlebt. Es ist damit etwas älter als Common Lisp und hat die Standardisierung sicherlich auch beeinflusst. Bis heute erfolgen Aktualisierungen des Sprachstandards, seit 2013 ist R7RS die aktuellste Version.

Der Sprachumfang befindet sich indes am entgegengesetzten Ende von Lisp: Scheme ist eine minimale Sprache, vieles ist der jeweiligen Implementierung überlassen. Das macht die Entwicklung eines eigenen Scheme-Dialekts zwar vergleichsweise einfach, begrenzt jedoch mitunter die Fähigkeiten, die die jeweilige Scheme-Version beherrscht. Chicken Scheme, eine der weiter verbreiteten Implementierungen von Scheme, löst diese Herausforderung mit dem Konzept der "Eggs", wie offiziell bereitgestellte Drittanbieterbibliotheken dort heißen. Ich mag solche Wortspiele.

Racket

1995 beschloss eine Gruppe von Forschern, die sich in dem Unternehmen PLT Inc. zusammengetan hatten, eine Entwicklungsumgebung für Programmieranfänger zu entwerfen, die im Kern auf Scheme basieren sollte. Das Ergebnis, PLT Scheme, bot mit dem grafischen IDE DrScheme eine interessante Besonderheit auf und unterstützte zudem - ein Novum - weiche Typisierung (soft typing), eine Art optionales Typensystem.

Mittlerweile hat sich PLT Scheme, das seit 2010 Racket heißt, zu einer wahren Chimäre entwickelt: Da es mit seinem Makrosystem möglich ist, vollständige Programmiersprachen in Racket zu implementieren, lässt sich in Racket bereits out of the box mit einem einfachen #lang-Befehl eine Sprache zum Programmieren von GUIs, eine zum Programmieren von Webanwendungen und eine zum Schreiben der Dokumentation nutzen. Ich halte Racket insofern für einen sehr guten Einstieg für Programmieranfänger und Lisp-Interessierte, gebe aber zu bedenken, dass zu viel Komplexität auch schnell zu Überforderung führen kann. Jedenfalls geht mir das so.

Die zuvor in C geschriebenen Teile von Racket wurden inzwischen teilweise in einem Fork von Chez Scheme neu geschrieben, seitdem gibt es zwei Versionen von Racket, "BC" ("Before Scheme") und "CS" ("Chez Scheme"). Die "BC"-Version soll mittelfristig gänzlich weichen.

Clojure

Clojure nimmt in der Welt von Lisp eine Sonderstellung ein, da es auf der Java Virtual Machine läuft, womit es auch auf Java-Frameworks zugreifen kann, und auf Nebenläufigkeit optimiert ist. Es wurde erst im Oktober 2007 erstmals veröffentlicht und ist damit noch ein recht junges Projekt, jedoch ist die dahinter stehende Community mittlerweile auf stattliche Größe angewachsen. Neben der Java Virtual Machine gibt es auch Clojure-Compiler für JavaScript und für das .NET Framework, die hauptsächliche Version ist aber diejenige, die Java voraussetzt.

Interessant könnte Clojure insofern als Ergänzungssprache vor allem für Entwickler sein, die ohnehin eine dieser Plattformen einsetzen müssen. Für unser Beispiel ist es leider nicht so gut geeignet, weil zum Sortieren einfacher verschachtelter Listen keine virtuelle Maschine hochgefahren werden muss. Wirklich nicht. :-)

(sort-by)

Es folgt nun die kommentierte Fassung eines Common-Lisp-Programms zur schlüsselweisen Sortierung der Namensliste aus Ralf Hersels Artikel nach der zweiten Spalte, dem Alter.

Hier der Code:

;; In Lisp beginnen Kommentare mit einem Semikolon.
;; Ich selbst mache gern zwei. Die sieht man besser.

;; Wir definieren erst mal unsere Liste. Wie oben
;; geschrieben: Klammern sind in Lisp meist rund.
;; Auch Kommata wären hier nur Platzverschwendung:

(defparameter *the-list* (list
                          '("Emilie" 10 "w")
                          '("Anna" 18 "w")
                          '("Fritz" 25 "w")
                          '("Dieter" 34 "m")
                          '("Beate" 43 "w")
                          '("Caesar" 54 "m")))

Das einfache Anführungszeichen oben - ' - ist eine Kurzform der Funktion (quote), man könnte also auch (quote ("Anna" 18 "w")) schreiben. Es bedeutet, dass die folgende Liste nicht evaluiert werden soll; andernfalls würde Lisp versuchen, als erstes Element der Liste das Ergebnis der Funktion "Emilie" - Anführungszeichen sind in Funktionsnamen ebenso erlaubt wie fast alle anderen Sonderzeichen - zu verwenden. Da es diese Funktion nicht gibt, wäre das natürlich ein Fehler. ;-) Andererseits ließe sich das Programm, wie ihr vielleicht schon vermutet habt, so leicht ergänzen: Listen müssen nicht bloß aus fixen Werten bestehen, sondern können nahezu alles aufnehmen.

Es ist guter Stil, globale Variablen, die mit (defvar) oder (defparameter) definiert worden sind, mit "Ohrwärmern" - also * - zu umschließen. Daran halte ich mich auch in diesem Code.

Zum Sortieren von Listen kennt Common Lisp die Funktion sort. Diese erwartet außer der zu sortierenden Liste auch ein Sortierprädikat und - optional - den zu sortierenden Schlüssel. Unter einem "Prädikat" versteht man in diesem Fall die Vergleichsfunktion. In Racket enden diese in der Regel mit einem Fragezeichen, in Common Lisp mit einem "p" (für "predicate"). Ein Beispiel, das auch in der verlinkten HyperSpec (die Sprachreferenz für Common Lisp) zu finden ist, ist char-lessp, das ein positives Ergebnis zurückliefert, falls der erste Vergleichsbuchstabe im Alphabet vor dem zweiten Vergleichsbuchstabe steht; es wird also alphabetisch aufsteigend sortiert.

Nun haben wir hier das Problem, dass wir nicht so genau wissen, ob wir Zahlen oder Wörter sortieren wollen, weil das vom Eingabeparameter abhängt. char-lessp wird mit Zahlen nicht funktionieren, dafür muss der aus der Mathematik genutzte Ziffervergleich < genutzt werden:

(sort '(2 4 3 5 1) #'<)
(1 2 3 4 5)

Also brauchen wir erst ein eigenes Prädikat, das bei der Sortierung zwischen Zahlen und Strings unterscheidet und "ist kleiner als" zurückgibt. Klar, kein Problem:

;; Zum Definieren einer Funktion verwendet man in
;; Common Lisp "defun", also "define function":

(defun string-or-digit-lessp (x y)
    ;; Wenn x und y Zahlen sind, Zahlenvergleich,
    ;; sonst Stringvergleich durchführen. (Die
    ;; Rückgabewerte brauchen kein "return" - die
    ;; letzte Zeile eines Codepfads in einer Lisp-
    ;; Funktion ist immer automatisch ihr Rück-
    ;; gabewert.)
    (if (and (numberp x) (numberp y))
        (< x y)
        (string-lessp x y)))

Da wir den zu sortierenden Schlüssel unserer Sortierfunktion als Parameter übergeben, können wir ihn auch der Funktion sort übergeben. Diese hätte als optionalen (und darum zu benennenden) Parameter :key aber keinesfalls die Spaltennummer (in unserem Beispiel 2), sondern einen Designator, also abermals eine Funktion, die den key zurückgibt. Theoretisch könnten wir uns jetzt eine komplizierte Lösung ausdenken, die mit cadr, cadar und so weiter elegant die Liste traversiert, aber ich mag tatsächlich einfache Antworten, obwohl dieser Artikel schon länger geworden ist als erhofft: Ich nehme nth, das das "n"te Element einer Liste zurückgibt.

;; Globale Variable *col* definieren, damit
;; Lisp nicht über nicht definierte Variablen
;; klagt:
(defvar *col* 0)

(defun get-nth (from-list)
  ;; *col* wird von (sort-by) gefüttert:
  (nth *col* from-list))

(defun sort-by (n)
  ;; Da - Programmierer kennen das - die Zählung
  ;; bei 0 beginnt, ist "Spalte 2" die dritte Spalte
  ;; und nicht etwa die zweite. Das könnten wir
  ;; beim Aufruf schon korrigieren, aber es spricht
  ;; auch nichts dagegen, das hier in der Funktion
  ;; zu machen:
  (setf *col* (- n 1))
  (sort *the-list* #'string-or-digit-lessp :key #'get-nth))

Testen wir das Ergebnis mal:

% sbcl --load sort-list.lisp
(sort-by 2)
;; Ausgabe:
(("Emilie" 10 "w") ("Anna" 18 "w") ("Fritz" 25 "w") ("Dieter" 34 "m")
 ("Beate" 43 "w") ("Caesar" 54 "m"))

Tadah!

Da die Liste *the-list* bekanntlich zur Laufzeit geändert werden kann: Probiert doch mal aus, sie jetzt einfach im noch laufenden SBCL umzudefinieren, dann ruft noch mal sort-by auf. :-)

Ich hoffe, dieser Artikel hat euch zumindest ein wenig neugierig gemacht. Feedback ist gern gesehen.