Zuerst einmal aber etwas Mathematik. Wir wollen zuerst einmal das "kanonische Beispiel" angehen, die Berechnung der Fakultät. Sie beschreibt Zahlen der Form 1 * 2 * 3 * 4 * 5 .... * n und man kann sie also etwas genauer als rekursive Funktion schreiben:
fak(n) = n * fak(n-1) mit fak(0)
Man sieht also: Man kann eine Fakultät von n berechnen, wenn man die Fakultät von n-1 kennt, und diese mit n multipliziert.
In Python kann man die Fakultät wie folgt definieren (wer etwas programmieren kann sollte diesen Code lesen können):
def fak(n):
if n == 1:
return 1
else:
return n*fak(n)
In Scheme schreibt definiert man die Fakultät ganz ähnlich.
(define (fak n)
(if (= n 1)
1
(* n (fak (- n 1)))))
Vergleicht man beide Schnipsel fallen 4 Dinge auf:
- Scheme-Code wird mit Klammern strukturiert, für den Programmierer anschaulich ist jedoch die Einrückung!
- Funktionsaufrufe werden als (f x) geschrieben statt f(x)
(- n 1) bedeutet n-1 der Operator ist also eine Funktion - Es gibt kein return (Im Zweifelsfall ist alles ein Rückgabewert)
- Der if-Ausdruck schaut genau wie ein Funktionsaufruf aus.
(if bedingung wennja sonst)
scheme@(guile-user)> (fak 3)
$1 = 6
es lässt sich auch überraschend einfach als Taschenrechner verwenden, etwa wie hier:
scheme@(guile-user)> (+ 4 (* 3 2))
$2 = 10
Überaschend einfach (errinnert ihr Euch noch daran, wieviel Jahre Eure Lehrer im Mathematikunterricht benötigt haben, Euch die Punkt vor Strich Regel beizubringen?)
Die wahre Magie der REPL macht sich aber erst durch Zusatzbefehle bemerkbar. Wir wollen nähmlich erfahren, wie genau die Fakultät die wir oben definiert haben berechnet wird. Dazu verfolgen wir den Befehlsaufruf mit ,trace (Guile):
scheme@(guile-user)> ,trace (fak 5)
trace: (fak 5)
trace: | (fak 4)
trace: | | (fak 3)
trace: | | | (fak 2)
trace: | | | | (fak 1)
trace: | | | | 1
trace: | | | 2
trace: | | 6
trace: | 24
trace: 120
Hier sieht man also, dass die Lösung der Fakultät in der Berechnung der kleineren Fakultäten liegt. Erst wird die Fakultät von 1 berechnet (1), daraus die von 2 (2), dann die von 3 (3), usw.
Performance!
Dieser Ansatz hat jedoch einen gravierenden Nachteil. Denn mit jedem Funktionsaufruf wird der Stack vergrößert! Jeder Funktionsparameter n wird auf den Stack gelegt, dass Zwischenergebnis (* 5 (fak 4)) wird berechnet, was bedeutet, dass (fak 4) bestimmt werden muss, also insgesamt (* 5 (* 4 (fak 3))), usw. Das sieht mit ,trace zwar hübsch aus, ist aber ineffizient. Für große n kommt so das Programm schnell an seine Grenzen. Daher stellt sich die Frage Kann man das Programm so verändern, dass sich die Funktionsberechnungen nicht so aufstauen wie hier?Man könnte nun eine Schleife schreiben (keine Sorge, kommt noch) aber es gibt da auch andere Möglichkeiten, und hier zeigt sich nun ein interessanter Vorteil von Scheme.
(define (accumulating-fak accumulator countdown)
(if (= countdown 0)
accumulator
(accumulating-fak (* accumulator countdown)
(- countdown 1))))
Diese Funktion ruft man mit (accumulating-fak 1 n) auf, und erhält die n-te Fakultät. Der Verlauf des Programms wird spätestens dann klar, wenn man auf einem Blatt Papier mal das Verhalten für die Fakultät von 5 durchspielt.
(accumulating-fak 1 5) ->
(accumulating-fak (* 1 5) (5-1 )) ->
(accumulating-fak 5 4) ...
Und weil das von Hand so langsam geht, können wir wieder mit ,trace dem Interpreter bei der Arbeit zuschauen.
scheme@(guile-user)> ,trace (accumulating-fak 1 5)
trace: (accumulating-fak 1 5)
trace: (accumulating-fak 5 4)
trace: (accumulating-fak 20 3)
trace: (accumulating-fak 60 2)
trace: (accumulating-fak 120 1)
trace: (accumulating-fak 120 0)
trace: 120
Hier sieht man, dass der Parameter Akkumulator mit jedem Aufruf wächst, während der parameter Counter noch die fehlenden Multiplikationen angibt.
Was hier geschieht (und erfahrene C/Java/... Programmierer verwundern wird) ist, dass wir eine Rekursion haben, sich aber keine Funktionsaufrufe aufstauen. Weil accumulating-fak direkt das Ergebnis des nächsten Rekursiven Aufrufs zurückgibt, kann der Interpreter optimieren. Dies nennt sich Tail-Recursion. In vielen Sprachen (wie Python) gibt es diese nicht, man ist also gezwungen zu Schleifen zu greifen.
Schleifen
Nun will ich anhand von C zeigen, wie man die Fakultät ohne die Rekursion berechnet. Das ist an sich nicht schwierig und ich müsste das daher eigentlich nicht nochmal hier aufführen, aber ich möchte an dem Beispiel noch ein paar andere Dinge klarmachen. Hier also der Schnipsel (habe verzichtet es in eine Funktion zu packen, da wir ja auch nicht rekursiv arbeiten hier):int accumulator = 1;
for (int i=1; i < n; ++i) {
accumulator *= i;
}
Dies entspricht einer sehr effizienten Berechnung der Fakultät. Die Variable result wird mit Zahlen aufsteigend bis n multipliziert. Dabei ändert sich der Wert von result in jedem Schritt (Die Variable accumulator in der Scheme Funktion ändert sich zwar von Funktionsaufruf zu Funktionsaufruf, aber strenggenommen ist es bei jedem Funktionsaufruf ja auch eine neue Variable, also bleibt sie in jedem Funktionsaufruf konstant, währrend sie sich im C Quelltext ändert).
die Operationen *= und ++ sind übrigens deshalb so notiert, weil für sie direkt Befehle der CPU existieren. C ist sehr nahe an der Hardware.
Nun gibt es prinzipiell auch die Möglichkeit den Code von oben umzuschreiben:
int accumulator = 1;
int i=1;
while ( i < n ) {
accumulator *= i;
++i;
}
Wie man hier sieht, ist die For-Schleife nur eine Abkürzung für eine einfachere while-Schleife. Schemer nennen sowas gerne Syntax-Zucker. Weitaus weniger Bekannt dürfte aber die folgende Variante sein:
int accumulator = 1;
int i=1;
loopstart:
accumulator *= i;
++i;
if (i < n)
goto loopstart;
Die Variante mit goto dürfte einige Überraschen. Aber diese Variante ähnelt sehr dem, was im Prozessor tatsächlich ausgeführt wird wenn man auf die Schleifen zurückgreift. Der Grund warum man kaum Code mit goto Befehlen sieht ist, dass Programme leicht unübersichtlich werden, wenn man willkürlich herumspringen kann. Die Schleifen while und for sind da Strukturierter, sie abstrahieren den bedingen Sprung mit goto zu einer Aussage wie "solange dies gilt" oder "von 1 bis n".
Dennoch wird der große Unterschied zur Denkweise in Scheme deutlich: Hier hatten wir formuliert: Eine Fakultät von n ist n mal die Fakultät von n-1. [*]
Die Strategie die dort verwendet wird ist: löse einen Basisfall (fak 1) -> 1 und führe die anderen Fälle auf den Basisfall zurück.
Zu Abstrakt?
Kann es also sein, dass Scheme zu Abstrakt ist? Was ist für unsere Gehirne natürlicher, die Rekursive Definition oder die über die Schleife?Auf den ersten Blick erscheint uns sicher die Schleife vertrauter. Unzählige hat ein C-Java-C++-Programmierer schon geschrieben. Aberdann erinnert man sich vielleicht daran, wie man Lösungswege findet, bevor man am Code tippen ist.
Teile-und-Herrsche-Algorithmen zum Beispiel Teilen ein Problem solange in Teilprobleme auf, bis sie an Basisfällen zu 1 oder 2 Elemente kommen, für die die Lösung direkt klar ist. Dann werden die Teillösungen zusammengefügt. Dies entspricht im Grunde dem Ansatz der sich auch im Scheme Code wiederfindet.
Wer also die Fakultät über die Schleifen berechnet, der hat im Grunde im Kopf die Rekursionsgleichung für die Fakultät gelöst, also mehr Mathematik betrieben, bevor er eine Zeile Code schreiben konnte, als bei der Formulierung in der "mathematischeren" Programmiersprache.
Ausblick
Ich hoffe, dass mit diesem Tutorial ein erster Einblick in Scheme gewonnen wurde. Im Grunde wurde hier erst einmal funktionelles Programmieren vorgestellt und gezeigt, dass man Sprachelemente wie Schleifen oder Funktionsaufrufe Zerlegen und Umformen kann.Tail-Recursion allein wäre sicherlich aber noch kein Grund allein Lisp oder Scheme zu lernen. Spannende Features gibt es zuhauf:
- Warum ist die Scheme-Syntax so anders? Wie wäre es mit Syntax-Zucker?
- Makros und Lisp/Scheme als programmierbare Programmiersprache
- Das mächtige Lambda
PS: Klammern
Der Klammerdjungel bei Scheme-Programmen ist für viele am Anfang unübersichtlich und verwirrt. Dabei ist die Lösung recht einfach. Für Lisper sind Klammern vielmehr Einrückhilfen für einen guten Editor. Mit dem Typischen Einrückschema braucht man die Klammern im Grunde eigentlich kaum zu beachten, bzw. nicht mehr als in anderen Programmiersprachen. Deswegen werden auch die schließenden Klammern einfach direkt hintereinander ans Zeilenende gestellt. Kompakt auf einem Haufen stören sie nicht.
