Funktionale Programmierung hat mich bereits während des Studiums beschäftigt, allerdings eher am Rande in Lehrveranstaltungen wie „Objektorientierte Konzepte“, wo in den Übungen Haskell gepredigt wurde. Teils verwirrt, teils fasziniert von dieser Art zu denken und zu programmieren hat mich das Thema nie richtig losgelassen und erlebt gerade einen persönlichen Aufschwung durch F#. F# ist Microsoft’s funktionale .NET Programmiersprache, die wie viele Innovationen Microsoft Research entsprungen ist. Es ist explizit hervorzuheben, dass F# das .NET-Framework als Basis nutzt. Demzufolge stehen auch alle Bibliotheken zur Verfügung, welche .NET so mächtig machen. Doch genug der Vorrede, los geht es mit F#. Ein kleiner Praxistest soll an dieser Stelle erste Eindrücke vermitteln…
Los geht’s…
Die aktuelle F# CTP kann auf der zugehörigen MSDN-Seite herunter geladen werden. Hier stehen auch weitere Ressourcen zur Verfügung, die beim Einstieg in die neue Programmiersprache behilflich sind. Flux installiert lässt sich im Visual Studio bei der Erstellung eines neuen Projekts der Punkt „Visual F#“ wählen. Die ersten Zeilen Code sind bekanntlich die schwersten in jeder Programmiersprache, und doch halfen mir bereits hier meine ersten Erfahrungen in Haskell. Der große Unterschied: F# ist keine rein funktionale Programmiersprache wie Haskell, sie enthält ebenfalls imperative Elemente, welche die Ausdruckfähigkeit an einigen Stellen vereinfachen sollen. Erste Schritte waren also schnell gemacht. Mit „let“ werden Variablen deklariert und definiert, wobei es sich hierbei auch um Funktionen handeln darf. „let twice x = 2*x“ erzeugt z.B. eine Funktion „twice“, welche die Signatur „int -> int“ besitzt und zu einem übergebenen Argument seinen zweifachen Wert zurückgibt. Diese Funktion darf wieder an weitere Funktionen übergeben werden, Funktionen höherer Ordnung sind also ohne Probleme möglich. F# inferiert dabei den Typ von Variablen, d.h. ihre Signatur wird aus den angegebenen Definitionen automatisch ermittelt und so z.B. auch bei der Fehlerprüfung verwendet. Als Beispiel für eine Signatur sei „List.map“ angegeben. Deren Signatur lautet: „val map: (‚a -> ‚b) -> ‚a list -> ‚b list“. What the heck? Eigentlich ist es ganz einfach. „->“ gibt jeweils die Abgrenzung zweier Parameter an. Der Ausdruck nach dem letzten „->“ stellt den Rückgabetyp dar. Nehmen wir C# als Hilfestellung und schauen uns die Methode „Math.Pow“ an, so hat diese in C# die Signatur „double Pow(double x, double y)“ und übersetzt auf unser Schema die Signatur „double -> double -> double“. Sie würde also 2 double-Werte als Argumente nehmen und einen double-Wert zurückliefern. Aber zurück zu List.map… (‚a -> ‚b) besagt: „das erste Argument der Funktion List.map ist eine Funktion, welche ein Element des Typs a entgegennimmt und ein Element des Typs b zurückliefert“. Das zweite Argument „‚a list“ besagt, dass eine Liste mit Elementen vom Typ a erwartet wird. Der Rückgabetyp von List.map ist ‚b list, was als letzter Term der Signatur ausgewiesen ist. Was macht List.map jetzt eigentlich? Es „mapped“ Elemente einer übergebenen Liste mit Hilfe einer ebenfalls als Parameter übergebenen Funktion. Dazu wird auf jedes Listenelement des Typs a die Funktion angewendet, welche ein Element des Typs b zurückliefert. Am Ende ergibt dies eine Liste von Elementen des Typs b, welche zurückgegeben wird. Auch Lambda-Ausdrücke sind in F# kein Problem. „List.map (fun x -> 2*x) numbers“ würde z.B. von allen Elementen der Liste „numbers“ den doppelten Wert erzeugen und dies als Liste zurückliefern. Klar erkennbar sind bereits hier u.a. das funktionale Paradigma, Typsicherheit und Polymorphismus, auch wird bereits hier die Ausdrucksmächtigkeit erkennbar, wenn man bereit ist sich auf funktionale Programmierung einzulassen…
Quicksort in F#
Beim Stöbern bin ich auf eine F#-Implementierung des Sortieralgorithmus Quicksort gestoßen, welche ich euch nicht vorenthalten wollte:
let lt x = List.filter (fun xi -> xi < x)
let geq x = List.filter (fun xi -> xi >= x)
let rec qs = function
| [] -> []
| x::xs -> (xs |> (lt x >> qs)) @ [x] @ (xs |> (geq x >> qs))
That’s it… Über z.B. „printfn „sorted: %A“ (qs [3;1;9;5;2;10;8;6;7;4])“ kann die Sortierung getestet werden. Zunächst werden zwei Funktionen „lt“ und „geq“ definiert, welche jeweils eine Element x übergeben bekommen. Sie liefern genau die Funktionen zurück, welche für einen weiteren übergebenen Wert xi berechnen, ob x kleiner oder größer gleich xi ist. „let rec qs …“ definiert eine rekursive Funktion qs, welche eine Liste als Argument übergeben bekommt. Mit „|“ wird der Wert der Liste geprüft und anhand dessen der Funktionswert bestimmt. Ist die Liste leer („[ ]“), so wird auch nur eine leere Liste zurückgeliefert. Ansonsten wird die Argumentliste mittels „x::xs“ in den Kopf x und die Restliste xs zerlegt und mit diesen beiden Elementen wird der folgende Term definiert. Dieser ist zunächst in 2 Teile aufgeteilt, die mit „@“ voneinander getrennt sind. Im mittleren steht mit [x] eine Einerliste, welche nur das Pivotelement des Quicksort-Durchlaufs enthält. Links davon wird die Teilliste von xs erzeugt, welche alle Elemente kleiner als x enthält, rechts davon entsprechend die Teilliste mit allen Elementen größer gleich xs. Mit „(xs |> (lt x >> qs))“ werden über den Pipe-Operator |> die Elemente aus xs ausgewählt, die kleiner als x sind (die Liste xs wird mittels Pipe weitergeleitet an lt und qs) und für diese Teilliste wird qs rekursiv aufgerufen (>> stellt die Verkettung zweier Funktionsaufrufe dar). Da mit jedem Aufruf von qs die Liste um mind. 1 Element kleiner wird, terminiert der Algorithmus in endlich vielen Schritten. Ok, an die Syntax muss man sich erst einmal gewöhnen, aber mal ehrlich… wie viele Zeilen hättet ihr in C# gebraucht?
Ja und?
Jetzt könnte man sagen: ja fein, F# ist eine neue funktionale Programmiersprache, hat das .NET Framework unter sich liegen und lässt sich auch recht flexibel verwenden… doch warum in aller Welt sollte mich das kümmern? Funktionale Programmiersprachen gibt es schon seit Ewigkeiten und mit C# komme ich gut zurecht, was will ich mit F#? Die Antwort auf diese Frage ist nicht leicht und zudem recht komplex. Zunächst einmal gibt es derzeit keine sehr guten Gründe, um F# wirklich intensiv zu lernen. Im Arbeitsleben ist diese Sprache noch nicht angelangt und somit eher eine Spielwiese zum Lernen funktionaler Programmierung und zum Erfreuen von enthusiastischen Programmierern. Es ist nicht abzusehen und auch nicht das Ziel von Microsoft, dass F# bestehende Sprachen wie C# ablöst. Ein großer Aspekt für die funktionale Programmierung ist das Problem der parallelen Programmierung. Viele Jahrzehnte lang haben wir sequentiell programmiert und imperative Programmiersprachen eigneten sich hierzu hervorragend. Doch mit dem Aufkommen von Multicore-Prozessoren wird die Notwendigkeit nach der Parallelisierung von Aufgaben immer größer und hier stoßen imperative Programmiersprachen an ihre Grenzen. Funktionale Programmiersprachen hingegen sind zunächst nebenwirkungsfrei und damit grundlegend für eine Parallelisierung geeignet. Variablen sind immutable (unveränderlich), womit Programmteile ohne Probleme verteilt bearbeitet werden können. Funktionale Programmierung kann damit einen Ausweg aus dem Dilemma der Parallelisierung von Programmen weisen. Wichtig dabei ist meiner Meinung nach, dass kein kompletter Paradigmenwechsel vollzogen wird. Funktionale Programmierung ist schwer und teilweise kompliziert, wenn man lange Zeit imperativ programmiert hat. Imperative Programmiersprachen geben einem Programmierer mehr Flexibilität mit dem Nachteil, dass es Wechselwirkungen geben kann, was gerade bei komplexen Softwareanwendungen häufig zu erheblichen Problemen führt. Aber funktionale Elemente werden meiner Meinung nach Einzug in Sprachen, Bibliotheken und Muster halten und somit bestehende Programmiersprachen wie C# bereichern. F# ist dabei auf einem guten Weg, da es eine hohe Ausdrucksmächtigkeit besitzt und performanter agiert als viele seiner funktionalen Kollegen. Erste Elemente von F# sind bereits in C# eingeflossen, es bleibt abzuwarten welche noch folgen werden…
So far for now… Matthias
