UP | HOME

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.

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.

Übergeben wir nun dieser Funktion unser obiges Beispiel1

[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:

1
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.

Autor: Patrick M. Krusenotto

Datum: Oktober 2014

Generiert mit Emacs 26.3 (Org mode 9.1.9)

comments powered by Disqus