Klassisches Lisp-Beispiel: Ableitung einer Funktion

In diesem Beipiel lernen Sie eine der ersten Anwendungen des symbolischen Rechnens in der Geschichte der Computerprogrammierung kennen: Das Ableiten einer einstelligen Funktion. Sämtliche hierzu erforferlichen Lisp-Funktionen (es sind nicht viele!) werden dabei erläutert. Nach dem Lesen dieser Darstellung werden Sie bereits mit einigen grundsätzlichen Elementen von Common Lisp vertraut sein.

Eine Funktion über der Variablen \(x\), die mit den vier Grundrechenarten beschrieben werden kann, kann allein mit folgenden sechs Regeln naxh \(x\) abgeleitet werden:

\begin{align} (a)' &= 0 \\ (x)' &= 1 \\ (f+g)' &=f'+g'\\ (f-g)' &=f'-g'\\ (f\times g)' &=f'\times g+f\times g'\\ \left(\frac{f}{g}\right)' &= \frac{f'\times g-f\times g'}{g^2}\\ \end{align}

Wendet man diese Regeln auf die Berechnungsvorschrift einer Funktion \(f\) an, und zwar rekursiv über ihren Aufbau, so erhält man in endlich vielen Schritten die Berechnungsvorschrift der abgeleiteten Funktion \(f'\). In diesem kleinen Beispiel können neben der gebundenen Variablen (meist \(x\)) alle freien Variablen, und alle Zahlen verwendet werden.
Wir verwenden zur Darstellung der Funktion die Präfix-Notation oder polnische Notation, da diese allgemein leichter zu bearbeiten ist, was auch der Grund der Lisp-Väter gewesen ist, diese für Lisp vorzusehen. Sie hat außerdem den Vorteil, dass wir zu einem späteren Zeitpunkt die Ableitung von \(f\) in Lisp übernehmen, kompilieren und berechnen können.

die Funktion

\begin{equation} f(x)=\frac{x^2+3}{a-x} \end{equation}

wird in Lisp wie folgt definiert:

(defun f(x) (/ 
             (+ (* x x) 3) 
             (- a x)))

Was wir nun haben wollen, ist eine Lisp-Funktion diff, die aus einer Berechnungsvorschrift für \(f\) und dem Namen \(v\) einer Variablen, nach der wir ableiten wollen, die Berechnungsvorschrift für \(f'\) errechnet und zurückgibt. Also:

\begin{equation} diff(f,v) = f'dv \hspace{10mm} \forall f: \mathbb{R} \rightarrow \mathbb{R} \hspace{10mm} \forall v \in var \end{equation}

Dieses Lisp-Programm diff besteht in Common Lisp nur aus zehn Zeilen! Ich möchte nicht sehen, wieviele Zeilen in C oder Java daraus würden, denn ich vermute, unter 100 Zeilen ist da nichts zu machen.

 1: (defun diff (e v)
 2:   (if (atom e)
 3:       (if (eq e v) 1 0)
 4:       (destructuring-bind (op e1 e2) e
 5:         (case op 
 6:           (+    `(+ ,(diff e1 v) ,(diff e2 v)))
 7:           (-    `(- ,(diff e1 v) ,(diff e2 v)))
 8:           (*    `(+ (* ,(diff e1 v) ,e2) (* ,e1 ,(diff e2 v))))
 9:           (/    `(/ (- (* ,(diff e1 v) ,e2) (* ,e1 ,(diff e2 v)))
10:                     (* ,e2 ,e2)))))))

Ich werde jetzt die Arbeitsweise dieser Funktion erklären. Eventuell wirken die Kommas und Backquotes(`) noch etwas verwirrend, aber es wird sich alles aufklären. Im Grunde wurden nur die 6 Ableitungsregeln von oben in Lisp übersetzt.

Zeile 1 besagt, dass eine Funktion diff definiert wird (defun = define function), die die Parameter e und v übernimmt. Dabei ist e eine Berechnungsvorschrift und v ein Variablenname.
Zeile 2 macht eine Fallunterscheidung. Wir müssen zuerst klären, ob wir in e eine Liste oder oder ein Symbol bekommen haben. Dazu gibt es die Funktion atom, die hier feststellt, ob sich hinter e ein atom (wie 88, 3.141, a, x, blubbernase, etc) verbirgt. Salopp gesagt sind Atome in Lisp Symbole und Zahlen.
if bekommt in Lisp drei Argumente:
1. Die Bedingung ,hier (atom e)
2. Den wert, den (if ...) hat, wenn die Bedingung wahr ist, hier die ganze Zeile 3, die ihrerseits ein (if...) ist.
3. Den Wert den if hat, wenn (atom e) falsch ist, der else-Fall. Das ist hier der Rest, der mit (destructuring-bind... beginnt bis zum Ende der ganzen Definition.
Zeile 3: Falls der Ausdruck e also ein Atom ist, müssen wir nur noch bestimmten, ob es sich dabei um das Variablensymbol in der Variablen v handelt (nach der leiten wir ab!), oder nicht. Im ersten Fall ist das Ergebnis 1 sonst 0. eq ist eine Funktion, die das Ergebnis "wahr" liefert, falls beide Argumente identisch sind, sonst liefert sie "falsch".

Damit sind die ersten beiden Ableitungsregeln von oben schon korrekt umgesetzt. Jetzt gibt es noch vier verschiedene Fälle, nämlich die, dass die Berechnungsvorschrift eine der vier Rechenoperatonen +, -, *, / verwendet. Wir müssen also jetzt den Term, den wir bekommen haben und der nur eine Liste sein kann, in ihre Bestandteile zerlegen, damit wir diese getrennt ableiten können.

Das Zerlegen besorgt destructuring-bind. Es übernimmt drei Argumente:
1. Eine Variablenliste, hier (op e1 e2)
2. Eine Liste, die zerlegt werden soll. Hier enthalten in unserem e.
3. Eine Berechnung, die mit den so belegten Variablen durchgeführt werden soll. Hier ist das alles, was auf (case... folgt. Als Berechnungsergebis liefert destructuring-bind hier dann das Ergebnis von case.
Die Zerlegung erfolgt hier so, dass das erste Element von e an die Variable op gebunden wird, das zweite Element an e1 und das dritte Element an e2. Wenn e die Liste (+ (- 2 x) a) enthält, dann bekommt op das Symbol +, e1 die Liste (- 2 x) und e2 das Symbol a.
Nun zum case-Verteiler in den Zeilen 5 – 10. Wir unterscheiden vier Fälle, nämlich die Operator-Symbole + - * /. Der case-Verteiler übernimmt pro Fall eine Liste, deren erstes Element der Inhalt von op ist, und deren zweites Element die Berechnungsvorschrift ist, die dann anzuwenden ist.
Die Berechnungen der vier Fälle deren jeder eine Zeile beansprucht, beginnt hier mit einem sogenannten Backquote (`). Das Backquote hat folgende Bedeutung: Der dahinter stehende Ausdruck wird nicht ausgewertet, sondern so, wie er dort steht, das bedeutet literal übernommen. Allerdings gibt es gewissermaßen als Gegenspieler des Backquote das Komma. Ein Teilausdruck, vor dem ein Komma steht, wird von Lisp doch ausgewertet. Angewendet auf die Zeile 6, die den Fall \(f+g\) bearbeitet, bedeutet das: Wir erhalten als Berechnungsergebnis eine Liste, die mit dem Symbol + beginnt. Das zweite und dritte Element sind die Ableitungen von e1 und e2. Wenn wir also diff mit den Argumenten (+ x b) und x aufrufen, so erhalten wir das Ergebnis (+ 1 0), denn die Berechnung (diff 'x 'x) ergibt 1 und die Berechnung (diff 'b 'x) liefert 0.

Übergeben wir nun dieser Funktion unser obiges Beispiel¹

[2]> (diff '(/ (+ (* x x) 3) (- a x)) 'x)

Dann erhalten wir das algebraisch vollkommen korrekte Ergebnis:

(/ (- (* (+ (+ (* 1 X) (* X 1)) 0) (- A X)) 
      (* (+ (* X X) 3) (- 0 1))) 
   (* (- A X) (- A X)))

Leider ist diese Berechnungsvorschrift noch nicht vereinfacht. Dazu wäre es erforderlich, z.B. in einem zweiten Durchlauf Teilausdrücke wie (* (* 1 x) (* x 1)) zu (* 2 x) zu vereinfachen um schließlich zu einer möglichst kurzen Berechnungsvorschrift zu gelangen.

Den Lisp-Compiler indes interessiert das alles aber wenig und es ist daher ohne Probleme möglich über eine Makrodefinition wie diese hier (die Sie jetzt nicht verstehen müssen),

[10]> (defmacro defdiff (name var expr) 
            `(defun ,name (,var) ,(diff expr var)))
DEFDIFF

Lisp dazu zu bringen, seine "selbst aufgestellte" Berechnungsvorschift als Funktion zu kompilieren:

[3]> (defdiff f-strich x (/ (+ (* x x) 3) (- a x)))
F-STRICH

Dieses \(f'\) können wir uns auch berechnen lassen. Vorher müssen wir allerdings noch den Parameter \(a\) belegen. Dies geschieht z.B. mit

[4]> (setf a 7)
7

Nun berechnen wir \(f'(5)\):

[5]> (f-strich 5)
12

Und erhalten den Wert \(12\).

Mit diesem Instrumentarium wäre es z.B möglich, das Newton-Raphson-Verfahren zu implementieren, mit dem Nullstellen von Reellen Funktionen bestimmt werden können. Dieses iterative Verfahren benötigt nämlich zu seiner Berechnung die Ableitung einer Funktion:

\begin{equation} x_{n+1}=x_{n}-\frac{f(x_n)}{f'(x_n)} \end{equation}

Fußnoten:

Wenn Sie es bisher noch nicht getan haben, dann installieren Sie über diesem Link: GNU CLISP for Windows oder über Ihre Linux-Disto das System CLISP, mit dem Sie das Beispiel auch praktisch ausprobieren können.