Massive Squad

In der Vertiefungs-Vorlesung Theorethische Informatik II haben wir uns seit Ende Januar zwei Wochen lang mit Funktionaler Programmierung in Scheme beschäftigt. Funktionale Programmierung ist ein anderer (aber genauso alter) Ansatz wie Imperative Programmierung.

Imperative Programmiersprachen haben sich aus der direkten Maschinenprogrammierung entwickelt: Der Prozessor eines Computers kann nur einen bestimmten kleinen Umfang von Befehlen, wie Daten aus dem Hauptspeicher laden, einfache arithmetisch-logische Funktionen (+, *, /, and, or, not, shift…) anwenden und Daten dann wieder im Hauptspeicher ablegen (natürlich schon etwas mehr, besonders bei einem CISC). Solche Programmierung wird immer noch für Embedded Systems oder der Geschwindigkeit halber für Teilprobleme von Computerspielen oder Echtzeitanwendungen verwendet. Assembler ist eine solche hardware-nahe Sprache. Imperativ heißen sie deshalb, weil einzelne Maschinenbefehle aneinander gereiht werden, um ein Problem zu lösen. Reine Maschinenprogrammierung ist jedoch umständlich und unflexibel, da sie nur für die entsprechende Maschine gilt. Ende der 1950ern wurde mit FORTRAN die erste Imperative Hochsprache entwickelt, die eine Abstraktionsschicht über die Maschinensprache einführte. Befehle waren immer noch imperativ, aber es waren für ein einfaches

x := x+1

nicht mehr drei Maschinenbefehle nötig, sondern nur eine Zeile. Die meisten heute verwendeten Programmiersprachen sind Imperative Programmiersprachen (C, C++, Java, Pascal, Perl, PHP, Ruby, Python…), selbst wenn sie erweiterten Konzepten wie Objektorientierung folgen.

Funktionale Programmiersprachen verfolgen dagegen einen anderen Ansatz. Wie “Funktional” schon sagt, handelt es sich bei Funktionalen Programmiersprachen um eine Ansammlung von Funktionen, die ineinander geschachtelt oder aneinander gereiht werden können. Die Theorie hinter Funktionalen Programmiersprachen kommt aus der Mathematik, in der ständig mit Funktionen ohne Seiteneffekte umgegangen wird. Funktionen ohne Seiteneffekte?

f(x) := x+1

liefert für immer die gleiche Eingabe (das gleiche x) das gleiche Ergebnis. So soll sich auch die Funktionale Programmierung im Idealfall verhalten. Das obige Beispiel x := x+1 verändert dagegen den Wert des x. Die Therie hinter den Funktionalen Programmiersprachen ist der λ-Kalkül (λ: griechischer Buchstabe Lambda) von Alonzo Church aus den 1930ern. Diese von der Definition sehr einfache Kalkül sagt im Prinzip, dass man aus einem mathematischen Term eine Funktion bilden kann. Funktionale Programmiersprachen (wie LISP (die erste funktionale Programmiersprache), Haskell, ML, dem LISP Dialekt Scheme…) setzen bei ihrer Realisierung auf den λ-Kalkül. Man kann mit solchen funktionalen Sprachen genauso gut programmieren wie mit imperativen Sprachen, es ist nur etwas ungewöhnlich, denn Funktionen verhalten sich wie primäre Datentypen (Zahlen, Buchstaben, Wahrheitswerte).

Wer mir bis hierher folgen konnte, darf jetzt etwas in Scheme eintauchen.

Einstieg

Am einfachsten gelingt der Einstieg in Scheme mit einer Integrierten Entwicklungsumgebung (IDE). Dazu haben wir die Umgebung PLT Scheme verwendet – eine kleine aber mit Syntaxprüfung und Debugger vollständige Entwicklungsumgebung die weder übermäßig Speicherplatz noch Ressourcen verbraucht.

“DrScheme”, wie die IDE des Packets heißt, ist in zwei Bereiche geteilt: im oberen Bereich werden die Definitionen geschrieben (festlegung von globalen Variablen, definition von Funktionen), im unteren Bereich erscheinen die Ausgaben. Im unteren Bereich kann aber auch interpretativ programmiert werden. DrScheme interpretiert alle Eingaben (auch die Definitionen im oberen Bereich), es gibt aber durchaus auch Möglichkeiten Scheme Code zu Compilieren. Bevor man jedoch loslegen kann, muss man eine der von der IDE unterstützen Sprachen auswählen. In der Vorlesung haben wir Revised 5 Report Scheme (R5RS) verwendet, das im Vergleich zum aktuellen Revised 6 Report Scheme einen geringeren aber dennoch ausreichenden Sprachumfang besitzt. Der komplette R5RS umfasst gedruckt gerade mal 50 A4 Seiten. Scheme ist also eine sehr überschaubare Sprache.

In Scheme werden alle Ausdrücke voll geklammert und in Prefix-Notation geschrieben. Leerzeichen sind zwischen den Argumenten notwendig, die Anzahl der Nichtdruckbaren Zeichen (Leerzeichen, Tabstopps, Zeilenumbrücke) spielen jedoch keine Rolle. Alle Ausdrücke werden (in der Regel) sofort ausgewertet und es erfolgt in der Regel Call-By-Value – das heißt, Variablen werden nicht durch Zeiger auf den Speicherbereich übergeben (in C++ häufig) sondern deren tatsächlicher Wert wird übergeben – wie bei mathematischen Funktionen. Aber beginnen wir mit einigen einfachen Beispielen.

Einfache Datentypen und Funktionen

Willkommen bei DrScheme, Version 4.1.4 [3m].
Sprache: R5RS; memory limit: 128 megabytes.
> "hello world" ;string
"hello world"
> 4 ;Zahlen
4
> #c ;char
#c
> #t ;true
#t
> #f ;false
#f
> 'x ;symbol
x

Primäre Datentypen werden also zu ihrem Wert ausgewertet. Jetzt können wir anfangen einfache arithmetische Funktionen zu benutzen. Symbole sind etwas besonderes, was in anderen Programmiersprachen weniger vorkommt: Symbole sind vergleichbar mit den Symbolen aus der Mathematik (f(x) := x +1, x ist ein Symbol). Symbole sind sozusagen Platzhalter für andere Ausdrücke, und werden bei Funktionen benutzt. Die Prefix-Notation mag am Anfang verwirrend sein, erweist sich nach etwas Eingewöhnung als durchaus praktisch.

> (- 1 1)
0
> (* 2 4)
8
> (+ (+ 1 1) (* 5 2) (/ 10 2)) ;Liste von Ausrücken als Argument
17
> (+ 1 2 3 4 5 6) ;Liste von Zahlen als Argument
21
>

Hier sieht man, dass die eingebauten Funktionen oft nicht auf eine bestimmte Anzahl von Argumenten festgelegt sind, sie nehmen eine Liste von Argumenten an. Scheme verwendet mehr oder minder nur Listen als Datenstrukturen. Auch der Ausdruck (+ 1 2) ist eine Liste aus den drei Elementen +, 1 und 2, wobei es sich bei dem ersten Element der Liste, dem +, um ein Symbol handelt. Dies zeigt dem Scheme Interpreter, dass es sich um eine Funktion handelt – und folglich die restlichen Elemente der Liste Argumente für diese Funktion sind. Damit werden wir jetzt eigene Funktionen definieren. Da Funktionen wie auch Zahlen und Zeichenketten primäre Datentypen sind, können (und müssen) wir sie an eine Variable binden, um sie verwenden zu können.

> (define x 4)
> x
4
> (define (square x) (* x x))
> (square x)
16
> (square 5)
25
> (square (square 5))
625
>

define bindet an das erste Argument, das (unausgewertete) zweite Argument. Dabei kann das Symbol, an das der Ausdruck gebunden wird auch eine Liste sein – somit wurde an x der Ausdruck 4 gebunden, an (square x) der Ausdruck (* x x). Wird der Ausdruck (square x) ausgewertet, wird das x, wie von mathematischen Funktionen erwartet, durch das ausgewertete Argument ersetzt.

Lambda

Nun können Ausdrücke jedoch wieder selbst Funktionen zurückliefern, da Funktionen ja primäre Datentypen sind, was in imperativen Programmiersprachen nur schwer möglich ist. Dazu dient lambda, das seinen Namen aus dem λ-Kalkül bezieht.

(define (plus-or-mul x)
    (if (even? x)
        (lambda (y z) (+ y z))
        (lambda (y z) (* y z))))

> ((plus-or-mul 4) 4 6) ;erstes Element der Liste ist eine Funktion
10
> ((plus-or-mul 5) 4 6) ;erstes Element der Liste ist eine Funktion
24
>

Auch wenn dieses Beispiel nicht unbedingt ein sinnvolle Funktion erfüllt, zeigt es gleich meheres: Eine einfache Fallentscheidung kann mit (if (Test) (True-case) (False-case)) getroffen werden – das benutzen hier um im Falle von einem geraden Argument (lambda (y z) (+ y z)) zurück zu geben und im Falle, dass x gerade ist (lambda (y z) (* y z)). Aber was ist nun dieses lambda? lambda erzeugt zur Laufzeit eine neue Funktion! Es wird also zur Laufzeit entschieden – je nach Argument von plus-or-mul – welche Funktion zurückgegeben wird. Diese zurückgegebene Funktion, können dann Argumente übergeben und die Funktion ausgewertet werden.

Mit (even? x) haben wir auch gleich das erste von vielen Prädikaten – Testfunktionen – gesehen. Prädikate enden immer auf ein ? und liefern einen Wahrheitswert zurück. even?, odd?, number?, function? … Es gibt selbstverständlich auch Vergleichsoperatoren für Zahlen (=, <, >…) und logische Operatoren (and, or, not) mit denen sich Tests verknüpfen lassen.

Rekursion und Iteration

(define (faculty x)
    (if (= x 1)
        1
        (* x (faculty (- x 1)))))

(define (sum x)
    (if (= x 0)
        0
        (+ x (sum (- x 1)))))

(define (fibonacci x)
    (cond ((= x 0) 0)
        ((= x 1) 1)
        (else (+ (fibonacci (- x 1)) (fibonacci (- x 2))))))

Diese drei Funktionen berechnen die Fakultät des Arguments, die Summe der Zahlen von 1 bis zum Argument, und die Fibonaccizahl zum Argument. Rekursion kann also sehr leicht in Scheme implementiert werden, und wird auch mehr verwendet also Schleifen. Eine weiter Funktion ist hier neu hinzugekommen: (cond ((Test) [Ausruck]) ((Test) [Ausdruck])... (else [Ausdruck]). cond entspricht in etwa einer if-else Kaskade: der Reihe nach werden die Tests ausgeführt und beim ersten erfolgreichen Test wird der Ausdruck ausgewertet, was für mehrere Bedingungen sehr praktisch ist. ( [Ausdruck] muss hier nicht ein einzelner Ausdruck sein, es kann sich uch um eine Folge von Ausdrücken handeln.) Um jetzt jedoch eine ganze Fibonacci-Folge zu erhalten, könnten wir jetzt zum Ausprobieren eine Iteration verwenden

(define (fib-sequence x)
    (do ((i 0 (+ i 1)))
        ((= i x) (display (fibonacci i)))
        (display (fibonacci i)) (display " ")))

was jedeoch von der Laufzeit nicht gerade optimal ist, aber die do-Funktion zeigt. (do ((var init step) (var init step)...) ((Test) [Final-Aussage]) [Body-Anweisung]) – sieht recht kompliziert aus, funktioniert jedoch wie eine erweiterte For-Schleife: Die Laufvariablen (hier nur i) werden im Kopf der Schleife mit einem Wert [hier 0] vorbelegt und bei jeden Schritt wird die Funktion step [hier (+ i 1)] angewandt, solange bis der Test [hier (= i x)] wahr wird. Bei jeder iteration der Schleife wird die [Body-Aussage]-Liste ausgewertet. Nach einem erfolgreichen (Test) wird, sozusagen als Final-Anweisung, die [Final-Aussage] ausgewertet.

Datenstrukturen: Listen, Paare, Vektoren

Listen haben wir, ohne es zu wirklich zu wissen, schon die ganze Zeit verwendet. Es gibt mehrer möglichkeiten Listen darzustellen. (+ 1 2) ist eine, genauer wäre die Darstellung aus mehreren Paaren (+ . (1 . (2 . ()))).

> (list? '(+ . (1 . (2 . ()))))
#t
> (pair? '(+ . (1 . (2 . ()))))
#t
> (list? '(1 . 2))
#f
> (pair? '(1 . 2))
#t

Was ist also der unterschied zwischen Paaren und Listen? Paare (auch verkettete) sind genau dann Listen, wenn das Zweite Element des Paares eine Liste ist. Die Leere Liste ist eine Liste – somit müssen Listen, aufgebaut aus Paaren, mit der leeren Liste '() enden. Was mach dieses einfache Anführungszeichen hier? Es verhindert eine Auswertung des Ausdrucks. Sonst würde aus (+ . (1 . (2 . ()))) 3 werden, was natürlich keine Liste ist!

> (list? (+ . (1 . (2 . ()))))
#f
> (+ . (1 . (2 . ())))
3

Um Listen und Paare dynamisch erzeugen zu können, werden die Funktionen cons, list und append verwendet. Der Umgang mit Listen ist gewöhnungsbedürftig und war bei mir im Praktikum am Fehlerträchtigsten.

> (cons 1 2) ;erzeugt ein Paar
(1 . 2)
> (cons 1 (cons 2 '() ) ) ;erzeugt eine Liste
(1 2)
> (list 1 2 3 4 5) ; erzeugt auch eine Liste
(1 2 3 4 5)
> (append (list 1 2 3 4 5) 256) ;hängt ans Ende der Liste ein Element an
(1 2 3 4 5 . 256) ;das ist keine Liste mehr, denn sie endet nicht auf eine leere Liste!

Mit den Funktionen car und cdr kann auf head und Tail von einem Paar zugegriffen werden.

> (car '(1 . 2))
1
> (cdr '(1 . 2))
2
> (car (cdr (cdr '( 1 2 3))))
3

In Scheme gibt es wie in anderen Programmiersprachen auch Vektoren (Arrays), diese werden aber weit weniger häufig in der funktionalen Programmierung verwendet als in der imperativen.

Dies war jetzt natürlich nur ein kleiner, schneller und vor allem unvollständiger Überblick über Scheme. Auch wenn es jetzt so aussehen mag, als könne man mit Scheme nicht so wirklich viel anfangen, gibt es einige, besoders im Mathematischem Umfeld große Programme (mit mehreren Zehntausend Zeilen Code) die Komplett in Scheme geschrieben wurden. Eingesetzt wird Schmeme aber dennoch eher im Akademischen Umfeld als in der Wirtschaft – dazu ist funktionale Programmierung wohl zu wenig verbreitet, auch wenn funktionale Konzepte immer mehr in imperative Sprachen einfließen.

Scheme Interpreter in Scheme

Zum Abschluß will ich noch ein (etwas) größeres Scheme Programm zeigen, das wir in der zweiten Woche der Vorlesung entwickelt haben: Einen Schme Interpreter in Scheme. Das bedeutet, wir haben in Scheme ein Programm geschrieben, das selbst wieder Scheme Code annimmt und auswertet. Ist das sinnvoll? Nunja, nicht unbedingt wenn man es in einer sowieso interpretierten umgebung (wie PLT Scheme) laufen läßt, aber Compiliert durchaus. Der akademische Grund war allerdings, dass das Programmieren eines Interpreters das Verstehen der Konzepte der Sprache vorraussetzt – und die Programmierung des Interpreters der Sprache in der selben Programmiersprache diesen Lerneffekt noch weiter vertieft.

Der von mir programmierte Interpreter kann jedoch nicht alles, was ich hier beschrieben habe – möglich sind einfache arithmetische Funktionen und Lambda – also so grob das Wichtigste. Jedoch ist die hier verwendete Definition von Funktionen nicht möglich: Funktionen müssen im Interpreter immer mit lambda definiert werden [also (define square (lambda (x) (* x x))) statt (define (square x) (* x x)) ].

Download Scheme-Interpreter in Scheme: scheme-interpreter.scm

Quellen und Links:

http://en.wikipedia.org/wiki/Imperative_programming
http://en.wikipedia.org/wiki/Functional_programming
http://en.wikipedia.org/wiki/Scheme_(programming_language)
http://en.wikipedia.org/wiki/Lambda_calculus
http://www.plt-scheme.org/
http://schemers.org/