Warum Lisp? Wie man Computern das Ableiten beibringt

Worum geht's

Der Mathematiker Wladimir Arnold soll einmal beklagt haben, dass Leibniz herausgefunden habe, wie man Analysis Leuten beibringt, die sie überhaupt nicht verstehen. Edmund Weitz, Professor an der HAW Hamburg und Autor von Common Lisp Recipes sowie Konkrete Mathematik (nicht nur) für Informatiker, greift dieses Bonmot in seinem Vortrag Wie man Computern das Ableiten beibringt oder: Warum Lisp? auf und zieht eine überraschende Konsequenz: Wenn Differenzieren so mechanisch ist, dass auch ein "dummer" Computer es schafft, dann sollten wir genau das einmal demonstrieren - und dabei sehen, warum Lisp für diese Aufgabe wie geschaffen ist.

Dieser Artikel fasst Weitz' Argumentation in eigenen Worten zusammen und zeigt am Ende, wie man dieselbe Idee in Python nachbauen kann. Direkt in dieser Seite eingebettet findest du editierbare Code-Blocks - klick einfach Run, dann läuft das Lisp-Programm hier in deinem Browser (via Pyodide + einem 120-Zeilen-Lisp-Interpreter nach Peter Norvig). Änderungen am Code sind willkommen, alles bleibt lokal in deinem Tab.

(+ 1 (* 2 3))

Quelle: Edmund Weitz, HAW Hamburg, 29.07.2020. Die Originalfolien und Bücher findest du auf weitz.de. Dieser Artikel ist eine Aufarbeitung, kein Transkript - die Beispiele sind aus seinem Vortrag übernommen, die Erklärungen meine eigenen.

Numerische vs. symbolische Mathematik

Bis Ende der 1950er Jahre wurden Computer ausschließlich für das benutzt, was ihr Name verspricht: rechnen. Numerische Verfahren liefern Näherungswerte - eine Zahl als Antwort auf eine Zahl als Eingabe. Man gibt 0.5 rein, kriegt 0.4794 raus.

Symbolische Mathematik ist etwas völlig anderes. Da gibt man \(\sin(x)\) rein und erwartet als Antwort \(\cos(x)\) - keine Zahl, sondern einen Ausdruck. Heute machen das Systeme wie Mathematica, Maple oder SymPy auf Knopfdruck. 1958 gab es nichts dergleichen.

John McCarthy, der später den Begriff "Artificial Intelligence" prägte, formulierte damals genau die Frage, um die es uns hier geht: Wie bringen wir Computern symbolisches Rechnen bei? Seine Antwort, festgehalten im allerersten der legendären AI Memos des MIT, war eine neue Programmiersprache: Lisp.

Programme als Daten: Homoikonizität

McCarthys Schlüsselbeobachtung war, dass mathematische Ausdrücke - und überhaupt Programmcode - sich am natürlichsten als Baumstrukturen darstellen lassen. Den Ausdruck \(a + 7 \cdot x\) zerlegt jeder Compiler dieser Welt in einen Syntaxbaum:

       (+)
      /   \
     a    (*)
         /   \
        7    x

Solche Bäume speichert man als verkettete Listen. McCarthy entschied sich, die Listen-Notation selbst zur Programmsyntax zu machen - aus \(a + 7x\) wird (+ a (* 7 x)). Das mag auf den ersten Blick hässlich aussehen, hat aber einen verblüffenden Effekt:

Lisp-Programme sind ihre eigenen Syntaxbäume.

Diese Eigenschaft heißt Homoikonizität ("Selbstdarstellung"). Mehr als 60 Jahre nach Lisp's Erfindung haben nur sehr wenige andere Sprachen diese Eigenschaft. Sie ist der Grund, warum Lisp die Sprache der Wahl für Metaprogrammierung ist: ein Programm, das andere Programme manipuliert, kann beide Seiten - Daten und Code - mit denselben Werkzeugen anfassen, weil sie identisch strukturiert sind.

Ironischerweise hatte McCarthy diese Klammer-Schreibweise nur als internes Zwischenformat gedacht. Die User entschieden anders. Im Rückblick: glücklicherweise.

Klammern stören weniger als man denkt. Wer professionell mit Lisp arbeitet, sieht sie nach kurzer Eingewöhnung gar nicht mehr - Editor-Einrückung übernimmt die Strukturierung. C- und Java-Programmierer beschweren sich auch nicht über ihre geschweiften Klammern und Semikolons.

Crashkurs Lisp

Lisp ist eine Sprachfamilie, keine einzelne Sprache - Common Lisp, Scheme, Clojure, Emacs Lisp und ein paar mehr. Die Beispiele hier sind Common Lisp, das gängigste Dialekt für professionelle Anwendungen. Älter als Java um 35 Jahre, falls man sich daran orientieren mag.

Die wichtigsten Bauteile:

Cons-Zellen sind Paare von Zeigern. Aus Cons-Zellen baut man Listen:

(cons 1 (cons 2 (cons 3 nil)))

(list 1 2 3)

car und cdr (historische Namen, heißen auch first und rest) holen die beiden Komponenten:

(car (quote (5 6 7)))

(cdr (quote (5 6 7)))

Symbole sind atomare Einheiten - keine Zeichenketten. Beim Vergleich zählt nicht der Inhalt, sondern die Identität.

Quoting mit quote (in echtem Lisp das Apostroph-Kürzel '): ohne quote versucht Lisp, jeden Ausdruck sofort auszuwerten - das ist die REPL-Logik Read - Eval - Print - Loop. Mit quote bleibt der Ausdruck unausgewertet stehen, als Daten:

(* 6 7)

(quote (* 6 7))

Probier's: oben kommt 42 raus, unten die Liste (* 6 7) selbst - unverdaut. Genau das brauchen wir gleich für's symbolische Rechnen.

Genau das brauchen wir für symbolische Mathematik: wir wollen mit Ausdrücken wie (+ x 0) rechnen, ohne dass Lisp sofort versucht, sie auszuwerten.

Rekursion und Closures - bevor wir zum Pattern-Matching kommen

Bevor wir Ableitungs-Regeln anwenden, kurz noch zwei Bauteile, die später gebraucht werden. Erstens: Funktionen sind in Lisp Werte. Hier die Fakultät, klassisch rekursiv:

(define fact
  (lambda (n)
    (if (= n 0) 1
        (* n (fact (- n 1))))))
(fact 10)

Zweitens: Closures - eine Funktion merkt sich den Scope, in dem sie erzeugt wurde:

(define make-adder
  (lambda (n)
    (lambda (x) (+ x n))))
(define add5 (make-adder 5))
(add5 100)

add5 "weiß" noch, dass n damals 5 war, obwohl make-adder längst zurückgekehrt ist.

Pattern Matching

Der Trick beim symbolischen Differenzieren ist Mustererkennung. Weitz zeigt eine Funktion match, die zwei Listen vergleicht und Variablen bindet, wenn sie auf der linken Seite stehen. In Kombination mit Substitution bekommt man ein Transformations-System: gegeben Regelliste + Eingabeausdruck, wendet transform Regeln so lange an, bis nichts mehr passt. Schematisch:

transform '(* 1 (+ a 0))
          mit Regeln '(+ X 0) -> X  und  '(* 1 X) -> X
--> a

Hier ist nichts gerechnet. Alles, was passiert, ist Pattern Matching + Ersetzung. Genau das ist die Maschinerie, die wir für's Differenzieren brauchen.

Ableiten als Pattern-Matching

Die Ableitungsregeln aus der Schule lassen sich direkt als Transformations-Regeln formulieren - in Pseudo-Notation:

D(x, x)         -> 1                              [Variable nach sich selbst]
D(u + v, x)     -> D(u, x) + D(v, x)              [Summenregel]
D(u * v, x)     -> D(u, x)*v + u*D(v, x)          [Produktregel]
D(sin(u), x)    -> cos(u) * D(u, x)               [Kettenregel]
D(u, x)         -> 0                              [Sonst (Konstante)]

Das ist der ganze Kern. Fünf Zeilen. Das System ist vollständig für alle elementaren Funktionen, sobald man noch die Kettenregel und ein paar bekannte Ableitungen wie \(\sin' = \cos\) ergänzt.

In dieser Seite habe ich diff und simplify fertig in's Lisp-Env eingehängt, damit du direkt damit spielen kannst. Die Eingabe ist dabei eine S-Expression - genau die, die der Reader sowieso liefert, wenn du sie quotest:

(diff (quote (* x x)) (quote x))

Das Ergebnis ist roh - ohne Vereinfachung. Du siehst die Produktregel direkt: (+ (* 1 x) (* x 1)). Mit simplify wird daraus (+ x x):

(simplify (diff (quote (* x x)) (quote x)))

Etwas anspruchsvoller, mit Kettenregel:

(simplify (diff (quote (exp (* x x))) (quote x)))

Probier eigene Ausdrücke aus - z.B. (* 3 (sin x)), (/ 1 x), (log (+ x 1)). Verfügbare Operatoren: + - * /, sin, cos, exp, log. Die Antworten sind korrekt, aber hässlich: Pattern Matching liefert dir 1+1=2 perfekt, aber der Output muss erst durch Vereinfachungs-Regeln laufen, damit etwas Lesbares herauskommt. Genau das ist Weitz' Pointe: Differenzieren ist trivial. Vereinfachen ist schwer.

Genau deshalb braucht echte Computeralgebra wie Mathematica jahrzehntelange Entwicklungsarbeit - die Heuristik für "was ist eigentlich einfach?" ist hochkomplex und manchmal nicht einmal eindeutig.

Makros: der Hammer

Bis hier ist alles "nur" eine elegante Funktions-Bibliothek. Der eigentliche Knaller kommt jetzt: Makros.

Erinnerung an Homoikonizität: Lisp-Code ist Lisp-Daten. Makros nutzen das aus. Ein Makro ist eine Funktion, die zur Compile-Zeit andere Funktionen umschreibt.

(defmacro diff (expr var)
  (doit `(D ,expr ,var)))     ; doit = Input-Regeln + Differenzieren + Vereinfachen

(defun f (x)
  (diff (/ (* x x x) 3) x))    ; <-- f's Body wird durch das Makro ersetzt

Was passiert: Bevor der Compiler f übersetzt, ruft er das Makro diff auf. Das Makro nimmt die Lisp-Liste (/ (* x x x) 3), differenziert sie symbolisch, vereinfacht und liefert (* x x) zurück. Der Compiler sieht dann nur noch:

(defun f (x) (* x x))

Heißt: f ist die Ableitung. Es wird zur Laufzeit kein einziger Pattern-Match ausgeführt. Die symbolische Mathematik passiert beim Kompilieren, das fertige Programm ist eine simple Multiplikation. Wenn man die Disassembly anschaut, ist von der ganzen Lisp-Maschinerie nichts mehr übrig - nur reines Maschinen-Squaring.

Das ist die Klasse von Werkzeug, die der C-Präprozessor nicht hat. Lisp-Makros operieren auf dem Syntaxbaum, mit der vollen Sprache zur Verfügung. Weitz' Schlusswort:

Ich bin immer noch beeindruckt, wenn ich darüber nachdenke. Wenn ihr jemals mit C-Präprozessor-Makros gearbeitet habt, hoffe ich, ihr erkennt, dass Lisp-Makros auf einem ganz anderen Level sind.

Lisp in Python ausprobieren

Du musst kein Common Lisp installieren, um das alles selbst zu sehen. Peter Norvig (Director of Research bei Google, dessen Buch Paradigms of AI Programming eine direkte Inspiration für Weitz' Vortrag ist) hat schon vor Jahren gezeigt, dass man einen funktionierenden Lisp-Interpreter in unter 120 Zeilen Python schreiben kann.

Im Pyground-Showcase findest du genau das: die Datei 05_lispy.py ruft eine echte importierbare Library in lib/lispy.py auf - Tokenizer, Parser, Evaluator und Standardbibliothek, genug für Rekursion, Closures und Listen-Verarbeitung. Direkt daneben in lib/symdiff.py ein symbolischer Differenzierer im Stil von Weitz, ebenfalls als Library.

Beides kannst du in eigene Programme importieren:

from lib.lispy import run, standard_env
from lib.symdiff import diff, simplify, show

env = standard_env()
env["double"] = lambda x: x * 2          # Python-Funktion in Lisp einklinken
print(run("(double 21)", env))            # -> "42"

print(show(simplify(diff(["sin", "x"], "x"))))   # -> (cos x)

Beispiel-Output:

[3] Rekursion - Fakultät:
  (fact 10)  -> 3628800

  d/dx exp(x*x)
    roh:        (* (exp (* x x)) (+ (* 1 x) (* x 1)))
    vereinfacht: (* (exp (* x x)) (+ x x))

Die vereinfacht-Zeile zeigt, dass selbst bei nur drei trivialen Vereinfachungs-Regeln (x+0=x, 1*x=x, 0*x=0) das Ergebnis schon deutlich besser lesbar wird - aber die richtig schöne Version \(2x \cdot \exp(x^2)\) erfordert Algebra-Wissen, das wir mit drei Regeln nicht abbilden können. Genau das ist Weitz' Punkt.

Würdigung

Edmund Weitz lehrt am Department Medientechnik der HAW Hamburg und unterhaelt einen hervorragenden YouTube-Kanal mit über 64.000 Abonnenten, der weit mehr als das hier behandelte Lisp-Video umfasst - Mathematik-Grundlagen, Numerik, Lambda-Kalkül, funktionale Programmierung. Wer Spaß an klar strukturierten, ruhigen Vorlesungen mit Tiefgang hat, sollte sich dort umschauen.

Seine Bücher zum Thema:

• Common Lisp Recipes - das deutsche Lisp-Buch für Praktiker
• Konkrete Mathematik (nicht nur) für Informatiker - Mathe-Lehrbuch der etwas anderen Sorte
• Alle Bücher auf weitz.de

Empfehlungen aus dem Vortrag für Lisp-Einsteiger:

• Practical Common Lisp (Peter Seibel) - online frei lesbar
• Paradigms of AI Programming (Peter Norvig) - Klassiker, ebenfalls frei

Was du jetzt tun kannst

1. Im Pyground-Playground spielen: das Projekt PyGround Showcase hat unter 05_lispy.py den Norvig-Interpreter mit Demo-Code. Run drücken, Output in der Konsole anschauen. Eigene Lisp-Ausdrücke kannst du in der run(...)-Aufrufe einbauen.
2. Den Original-Vortrag schauen - Wie man Computern das Ableiten beibringt oder: Warum Lisp? ist 45 Minuten gut investierte Zeit, vor allem die Makro-Sektion ab 39:15.
3. Selbst schreiben: ein eigener kleiner Pattern-Matcher und ein paar Differenzierungs-Regeln passen in eine Mittagspause. Der schwerere Teil - Vereinfachung - bleibt ein offenes Forschungsproblem.

Lisp ist nicht einfach eine alte Sprache. Es ist die Familie, in der Konzepte zuerst getestet wurden, die wir heute alle benutzen: Garbage Collection, dynamische Typisierung, REPLs, Closures, Macros, Code-as-Data. Wer Lisp lernt, lernt nicht eine Sprache - sondern sieht, wo all die anderen herkommen.