Herbert Prähofer ist Professor für Informatik an der Johannes Kepler Universität Linz, Österreich. Seine Forschungsschwerpunkte liegen im Bereich der Methoden der Softwareentwicklung und des Software Engineerings, mit aktuellen Schwerpunkten im Bereich statischer Programmanalyse und Produktlinien-Engineering. Er ist Autor und Ko-Autor von über 100 Publikationen in wissenschaftlichen Zeitschriften, Konferenzbänden und Büchern. Seit 2007 ist er im Studium Informatik für die Ausbildung in funktionaler Programmierung zuständig und hält dazu Vorlesungen »Prinzipien von Programmiersprachen«, »Objekt-funktionale Programmierung in Scala« und »Funktionale Programmierung in Java«.
Zu diesem Buch – sowie zu vielen weiteren dpunkt.büchern – können Sie auch das entsprechende E-Book im PDF-Format herunterladen. Werden Sie dazu einfach Mitglied bei dpunkt.plus+: www.dpunkt.plus |
Eine umfassende Einführung
Herbert Prähofer
herbert.praehofer@jku.at
Lektorat: Melanie Feldmann
Copy-Editing: Geesche Kieckbusch, Hamburg
Satz: III-satz, www.drei-satz.de
Herstellung: Stefanie Weidner
Umschlaggestaltung: Helmut Kraus, www.exclam.de
Bibliografische Information der Deutschen Nationalbibliothek
Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar.
ISBN:
Buch 978-3-86490-757-9
PDF 978-3-96088-984-7
ePub 978-3-96088-985-4
mobi 978-3-96088-986-1
1. Auflage 2020
Copyright © 2020 dpunkt.verlag GmbH
Wieblinger Weg 17
69123 Heidelberg
Hinweis:
Dieses Buch wurde auf PEFC-zertifiziertem Papier aus nachhaltiger Waldwirtschaft gedruckt. Der Umwelt zuliebe verzichten wir zusätzlich auf die Einschweißfolie.
Schreiben Sie uns:
Falls Sie Anregungen, Wünsche und Kommentare haben, lassen Sie es uns wissen: hallo@dpunkt.de.
Die vorliegende Publikation ist urheberrechtlich geschützt. Alle Rechte vorbehalten. Die Verwendung der Texte und Abbildungen, auch auszugsweise, ist ohne die schriftliche Zustimmung des Verlags urheberrechtswidrig und daher strafbar. Dies gilt insbesondere für die Vervielfältigung, Übersetzung oder die Verwendung in elektronischen Systemen.
Es wird darauf hingewiesen, dass die im Buch verwendeten Soft- und Hardware-Bezeichnungen sowie Markennamen und Produktbezeichnungen der jeweiligen Firmen im Allgemeinen warenzeichen-, marken- oder patentrechtlichem Schutz unterliegen.
Alle Angaben und Programme in diesem Buch wurden mit größter Sorgfalt kontrolliert. Weder Autor noch Verlag können jedoch für Schäden haftbar gemacht werden, die in Zusammenhang mit der Verwendung dieses Buches stehen.
5 4 3 2 1 0
Gewidmet meiner Frau Edith und
meinen Kindern Ulrich und Lea
Vorwort
1Einleitung
1.1Elementare Konzepte und Begriffe
1.2Funktionale Programmierung in Java
2Sprachliche Grundlagen
2.1Java Generics
2.1.1Typparameter
2.1.2Typconstraints
2.1.3Ko- und Kontravarianz
2.1.4Typinferenz bei Generics
2.1.5Schwachstellen der Generics in Java
2.2Default-Methoden
2.3Lambda-Ausdrücke
2.3.1Formen von Lambda-Ausdrücken
2.3.2Typ eines Lambda-Ausdrucks
2.3.3Ausnahmen bei Lambda-Ausdrücken
2.3.4Closures
2.4Funktionale Interfaces
2.5Methodenreferenzen
2.6Zusammenfassung
3Programmieren ohne Seiteneffekte
3.1Reine Funktionen
3.1.1Iteration vs. Rekursion
3.1.2Referentielle Transparenz und Ersetzungsprinzip
3.1.3Funktionen mit Gedächtnis
3.2Funktionale Ausnahmebehandlung mit Optional
3.3Funktionale Listen
3.3.1Beispielanwendung
3.4Paare und Tupel
3.5Zusammenfassung
4Programmieren mit Funktionsparametern
4.1Listenverarbeitung mit Funktionen höherer Ordnung
4.2Flexible Programmschnittstellen
4.3Algorithmen
4.3.1Tiefensuche
4.3.2Verallgemeinerung der Suche
4.4Entwurfsmuster
4.4.1Strategie
4.4.2Kommando
4.4.3Besucher
4.5Eingebettete und bedingte Ausführung
4.5.1Eingebetteter Code
4.5.2Bedingte Ausführung
4.5.3Fallunterscheidungen
4.5.4Typtests
4.6Auswertung nach Bedarf
4.6.1Faule Iteratoren
4.6.2Unendliche Folgen
4.6.3Faule Iteration über die Knoten eines Graphen
4.7Zusammenfassung
5Kombination von Funktionen
5.1Flüssige Schnittstellen
5.2Funktionskomposition
5.2.1Aufrufketten beim funktionalen Interface Function
5.2.2Logische Verknüpfungen bei Predicate
5.2.3Bilden von Vergleichsketten mit Comparator
5.2.4Beispiel-Workflows
5.3Kombinator-Parser
5.3.1Parser und Parser-Ergebnisse
5.3.2Kombinationsoperatoren
5.3.3Parser für Boolesche Ausdrücke
5.4Domänen-spezifische Sprachen
5.4.1Fallbeispiel Zustandsmaschinen
5.5Zusammenfassung
6Funktoren, Monoide und Monaden
6.1Funktoren
6.1.1Funktor Optional
6.1.2Gesetze und Eigenschaften
6.2Monoide und Reduktion
6.2.1Monoide
6.2.2Reduktion
6.2.3Monoide in Java
6.2.4Reduzierbare Strukturen
6.2.5Anwendungsbeispiele zur Reduktion mit Monoiden
6.3Monaden
6.3.1Monade Optional
6.3.2Monade Parser
6.3.3Gesetze
6.3.4Bedeutung von Monaden
6.3.5MonadPlus: Monade mit monoider Kombination
6.4Zusammenfassung
7Streams
7.1Grundlagen von Streams
7.1.1Ein erstes Beispiel
7.1.2Externe vs. interne Iteration
7.1.3Bedarfsauswertung
7.2Klassen von Streams
7.3Stream-Operationen
7.3.1Erzeuger-Operationen
7.3.2Zwischenoperationen
7.3.3Terminal-Operationen
7.4Collectors
7.4.1Interface Collector
7.4.2Vordefinierte Collectors
7.4.3Downstream Collectors
7.4.4Eine eigene Collector-Implementierung
7.5Anwendungsbeispiele
7.5.1Ergebnisauswertung mit Streams
7.5.2Wortindex zu einem Text
7.6Hinweise
7.6.1Einmal-Iteration
7.6.2Begrenzung von unendlichen Streams
7.6.3Zustandslose und zustandsbehaftete Operationen
7.6.4Reihenfolge von Operationen
7.6.5Kombinationen von Operationen
7.7Interne Implementierung
7.7.1Beispiel
7.8Zusammenfassung
8Parallele Streams
8.1Erzeugen von parallelen Streams
8.2Parallele Ausführung
8.2.1Spliterators
8.2.2Ausführung durch Fork/Join-Pool
8.2.3Konfiguration des Fork/Join-Thread-Pools
8.3Bedingungen bei paralleler Ausführung
8.3.1Parallele Ausführung und Seiteneffekte
8.3.2Parallele Ausführung und zustandsbehaftete Berechnungen
8.3.3Eigenschaften der Parameter von reduce
8.3.4Paralleles Sammeln
8.4Laufzeit
8.5Zusammenfassung
9Asynchrone Funktionsketten
9.1Eine Lösung mit parallelen Streams
9.2Asynchrone Lösung mit Futures
9.3CompletableFuture
9.4Asynchrone Programmschnittstellen
9.5CompletableFuture als Promise
9.6Kombination von CompletableFutures
9.6.1Beispiel
9.7Zusammenfassung
10Reaktive Streams
10.1Grundlagen
10.1.1Kontrakt von Observable
10.1.2Erzeugen von Observables
10.1.3Anmelden und Abmelden von Observer
10.2Varianten
10.2.1Single
10.2.2Completable
10.2.3Maybe
10.3Hot und Cold Observables
10.3.1ConnectableObservable
10.3.2Beispiel Echtzeitdaten
10.4Operationen
10.4.1Abbildungen
10.4.2Filtern und Teilmengen
10.4.3Reduktion
10.4.4Sammeln
10.4.5Operationen mit Zeit
10.4.6Kombinationen
10.4.7Konvertierungen
10.4.8Seiteneffekte
10.5Nebenläufigkeit
10.5.1Serialisierung von nebenläufigen Ereignissen
10.5.2subscribeOn und Scheduler
10.5.3observeOn
10.6Fehlerbehandlung
10.6.1Fehlerereignisse auslösen
10.6.2Auf Fehler reagieren
10.7Rückstau und Flusskontrolle
10.7.1Reduktion der Menge der Ereignisse
10.7.2Flowables
10.8Testen reaktiver Streams
10.9Zusammenfassung
11Testen mit und von Funktionen
11.1Funktionsparameter bei JUnit 5
11.2AssertJ: Eine DSL für Unit-Tests
11.3Eigenschaftsbasiertes Testen nach QuickCheck
11.3.1Generatoren von Zufallswerten
11.3.2Tests
11.3.3Shrinken der Werte
11.4Zusammenfassung
12Weiterführende Konzepte
ABibliografie
BLaufzeitexperimente Parallele Streams
Index
Dieses Buch gibt eine Einführung in die funktionale Programmierung in der Sprache Java. Wir kennen Java als eine Sprache, die auf dem objektorientierten Programmierparadigma beruht und wir sind gut mit dieser Art der Programmierung vertraut. Und wir wissen, dass die in Java 8 eingeführten Lambda-Ausdrücke die Grundlage für eine funktionale Programmierung bilden. Aber rechtfertigt dieses neue Sprachfeature ein Buch mit 300 Seiten?
Wie wir sehen werden, unterscheidet sich funktionale Programmierung grundsätzlich von unserer gewohnten Welt der imperativen und objektorientierten Programmierung. Schon die Ursprünge sind gänzlich unterschiedlich. Während imperative Programmierung als Abstraktion von Maschinencode und objektorientierte Programmierung aus der Motivation, Dinge der Realität abzubilden, entstanden sind, wurde funktionale Programmierung auf Basis einer mathematischen Theorie, dem Lambda-Kalkül, geschaffen. Mehr erfahren Sie dazu in Kapitel 1 dieses Buches.
Für eine funktionale Programmierung muss man sich daher auf andere Denkweisen, Prinzipien und Programmiermuster einlassen. Dieses Buch will diese Denkweisen, Prinzipien und Programmiermuster mit ihrer Ausgestaltung in Java und die darauf aufbauenden Techniken und Systeme vermitteln. Es orientiert sich dabei stark an den vielfältigen Ideen, Konzepten und Anwendungen, die die Forschung zur funktionalen Programmierung in 60 Jahren hervorgebracht hat. In dem Sinne kann das Buch auch als ein Versuch gesehen werden, dieses vielfältige Wissen auf eine Programmierung in Java zu übertragen. Das Buch verfolgt daher sehr explizit das Ziel, nicht nur die Sprachkonzepte und die neuen Systeme und Bibliotheken zu beschreiben, sondern ganz besonders auch die grundlegenden Ideen und Prinzipien zu vermitteln und damit ein tieferes Verständnis für die funktionale Programmierung zu schaffen.
Das Buch hat seinen Ursprung in Lehrveranstaltungen zur funktionalen Programmierung, die ich seit mehreren Jahren an der Johannes Kepler Universität Linz halte. Dazu gehört eine Speziallehrveranstaltung zur funktionalen Programmierung in Java und eine Lehrveranstaltung zu den Prinzipien der funktionalen Programmierung, die sich auf die Konzepte der rein-funktionalen Sprache Haskell stützt. Eine weitere wichtige Erfahrung, die in dieses Buch eingeflossen ist, war die Beschäftigung und das Arbeiten mit der Programmiersprache Scala. Scala sehe ich als Vorbild für einen Sprachentwurf, der objektorientierte und funktionale Konzepte systematisch vereint. In diesem Sinne war Scala in vielerlei Hinsicht auch Vorbild für die Gestaltung der funktionalen Konzepte in Java.
Das Buch richtet sich an Softwareentwickler bzw. Studenten der Informatik, die bereits Erfahrung mit objektorientierter Programmierung in Java haben und sich in das neue Paradigma der funktionalen Programmierung einarbeiten wollen. Die umfassende Behandlung des Themas sollte den Erwerb von fundierten Kenntnissen der funktionalen Programmierung in Java ermöglichen. Das Buch kann aber auch verwendet werden, um sich gezielt Kenntnisse von spezifischen Techniken anzueignen. Der folgende Abschnitt »Pfade durch das Buch« informiert über mögliche Kapitelfolgen beim Lesen.
Das Buch eignet sich auch besonders als begleitendes Lehrbuch zu Vorlesungen zum Thema funktionale Programmierung in Java. Des Weiteren würde ich das Buch als ergänzendes Lehrbuch zu einer Lehrveranstaltung zu fortgeschrittenen Programmiertechniken in Java oder zu einer sprachunabhängigen Einführung in die funktionale Programmierung empfehlen.
Das Buch teilt sich konzeptionell in drei Teile: Im ersten Teil, der die Kapitel 1 und 2 umfasst, werden die Grundlagen zu einer funktionalen Programmierung gelegt. Der zweite Teil umfasst die Kapitel 3 bis 6 und vermittelt wichtige Prinzipien der funktionalen Programmierung in Java. Im dritten Teil mit den Kapiteln 7 bis 11 werden wichtige Techniken, Systeme und Bibliothekskomponenten beschrieben. Das Buch schließt in Kapitel 12 mit einem Blick auf die derzeitigen Grenzen der funktionalen Programmierung in Java und mögliche zukünftige Entwicklungen.
Im Einzelnen behandeln die Kapitel folgende Themen:
Abhängig von Interesse und Vorkenntnissen bieten sich mehrere Varianten für die Abfolge der Kapitel dieses Buches an. Auch ein Lesen einzelner Themen ist möglich. In den einzelnen Kapiteln sind des Öfteren Verweise zu Inhalten und Beispielen aus früheren Kapiteln gegeben, die man dann eventuell zielgerichtet nachlesen kann.
Des Weiteren beinhaltet Kapitel 5 zwei Abschnitte mit fortgeschrittenen Anwendungsbeispielen. Diese Abschnitte können bei der Erstlektüre übersprungen werden, ohne dass das Lesen der folgenden Kapitel beeinträchtigt wird. Auf diese Möglichkeit wird bei den Abschnitten in der Form von Fußnoten hingewiesen.
Im Folgenden sind mehrere mögliche Kapitelfolgen angegeben.
Es ist offenkundig, dass ein Lesen der Kapitel 1 bis 12 empfohlen wird, wobei eventuell die gekennzeichneten Abschnitte mit fortgeschrittenen Themen ausgespart werden können. Mit dem Lesen der Kapitel 3 bis 6, in denen die allgemeinen Prinzipien der funktionalen Programmierung vermittelt werden, soll auch ein Verständnis für die Gestaltung der in den Kapiteln 7 bis 11 dargestellten Techniken und Systeme geschaffen werden.
Ein weiterer Pfad bietet sich an, wenn man primär an den bekannten Techniken und Systemen und weniger an den allgemeinen Prinzipien der funktionalen Programmierung in Java interessiert ist. Hier besteht die Möglichkeit, mit Kapitel 1 und 2 die Grundlagen zu erwerben und dann mit den Techniken und Systemen in den Kapiteln 7 bis 11 fortzufahren. Bei Verweisen zu Inhalten aus früheren Kapiteln kann man diese zielgerichtet nachlesen.
Das Buch bietet auch die Möglichkeit, sich einzelne Techniken zu erarbeiten. Man startet wieder mit Kapitel 1 und 2 zu den Grundlagen und kann dann:
In diesem Buch gelten folgende Konventionen bezüglich Schriftarten und Schreibweisen.
Für alle Programmbeispiele wird ein Fixpunkt-Font verwendet. Ebenso werden Bezeichner von Programmelementen innerhalb des Fließtextes in Fixpunkt-Font gesetzt. Wird aber der Begriff allgemein verwendet, wird er mit normaler Schriftart geschrieben. Zum Beispiel wird der Begriff String für Zeichenketten mit normaler Schriftart geschrieben, wird aber die Klasse String explizit genannt, wird für den Klassennamen der Fixpunkt-Font verwendet.
Besondere Begriffe werden bei der Einführung kursiv geschrieben.
Größere Programmbeispiele, besonders Code von Klassen, werden mit Unterschrift versehen und mit der Kategorie Listing nummeriert. Kürzere Anweisungsfolgen werden ohne Nummerierung direkt in den Fließtext eingefügt.
Wenn immer möglich und sinnvoll, werden im Buch deutsche Begriffe verwendet. Bei manchen Begriffen wird aber auf englische Bezeichner zurückgegriffen. So wird zum Beispiel Map und nicht Abbildung für Programmkomponenten verwendet, die eine Abbildung von Schlüssel auf Werte realisieren. Englische Bezeichner werden dann großgeschrieben, zum Beispiel Streams. Zusammensetzungen aus englischen und deutschen Wörtern werden mit Bindestrich verbunden, zum Beispiel Fixpunkt-Font. Elemente von Programmen werden wie in Java mit Groß- und Kleinschreibung geschrieben, zum Beispiel CompletableFuture.
Das Buch gibt an einigen Stellen Zusatzinformationen, Anmerkungen und Hinweise, die über das unmittelbare Thema funktionale Programmierung in Java hinausgehen. Diese sind durch graue Blöcke besonders gekennzeichnet.
Der Sourcecode zu allen Programmbeispielen kann von der Webseite zu diesem Buch
www.dpunkt.de/fpinjava
heruntergeladen werden. Es finden sich hier mehrere Maven-Projekte. Der Code ist in Packages analog zu den Abschnitten des Buchs organisiert.
Zu diesem Buch haben eine Reihe von Personen beigetragen, bei denen ich mich hier ausdrücklich bedanken möchte.
Ich möchte zuerst meiner Lektorin beim dpunkt.verlag, Frau Melanie Feldmann, für die gründliche und kompetente Lektoratsarbeit danken. Auch möchte ich den anonymen Gutachtern für ihr wertvolles Feedback danken.
Mein besonderer Dank gilt dem Leiter des Instituts für Systemsoftware, Professor Hanspeter Mössenböck, der mir an seinem Institut die Möglichkeit und das Umfeld geboten hat, mich so eingehend mit dem Thema funktionale Programmierung zu beschäftigen. Ich danke ihm auch für das Herstellen des Kontakts zum dpunkt.verlag. Mein Dank geht auch an meine Kollegen am Institut für die immer angenehme und fördernde Arbeitsatmosphäre. Meine Kollegen Kevin Feichtinger und Daniel Hinterreiter waren sehr hilfreich, indem sie erste Versionen von Kapiteln dieses Buches lasen und mir wichtige Rückmeldungen gaben. Meinem Kollegen Professor Paul Grünbacher danke ich für die vielen Jahre der freundschaftlichen Zusammenarbeit und für sein wertvolles Feedback zur Verbesserung der Einleitung zu diesem Buch. Bedanken möchte ich mich auch bei den Kollegen aus dem Oracle-Team, Dr. Roland Schatz und Dr. Lukas Stadler, die mir zu allen Details zur Sprache Java und ihrer Ausführung immer äußert kompetent helfen konnten.
Meinem ehemaligen Kollegen und Freund Dr. Alexander Fried danke ich ganz besonders für seinen Beitrag zur Gestaltung an und seine Mitarbeit bei unserer gemeinsamen Lehrveranstaltung »Functional Programming in Java«. Ich danke ihm auch, dass er mich immer ermutigt hat, das Buchprojekt in Angriff zu nehmen.
Schließlich möchte ich mich bei einer Reihe von Studenten bedanken, die durch ihre hervorragenden Studienarbeiten wertvollen Input zu diesem Buch geliefert haben. Namentlich möchte ich hier nennen (in alphabetischer Reihenfolge): Christoph Burghuber, Christoph Gerstberger, Marcel Homolka, Florian Latifi, Daniel Schneider und Florian Schrögendorfer.
Herbert Prähofer
Linz, April 2020
Mit der Version 8 wurden auch in Java Lambda-Ausdrücke eingeführt. Auf den ersten Blick erscheinen diese neben den vielen anderen Sprachfeatures von Java nur als ein weiterer kleiner Zusatz. Tatsächlich bedeutet aber ihre Einführung und die damit einhergehende Unterstützung eines funktionalen Programmierstils einen revolutionären Wandel in der Art, wie man Programme in Java gestalten kann. Funktionale Programmierung verspricht eine Programmgestaltung, die in deklarativer Form, auf hohem Abstraktionsniveau, knapp und präzise und für eine parallele Ausführung geeignet ist. Funktionale Programmierung ist grundsätzlich unterschiedlich zur imperativen Programmierung, sie steht aber nicht im Gegensatz zur objektorientierten Programmierung. Wie Brian Goetz es in seinem Vorwort zu [56] ausdrückt, arbeitet Objektorientierung mit einer Abstraktion entlang der Daten, die funktionale Programmierung erlaubt aber eine Abstraktion von Verhaltensstrukturen. Damit ergänzen sich die beiden Paradigmen zu einer neuen Qualität der Programmgestaltung.
Funktionale Programmierung hat besonders in den letzten Jahren viel Aufmerksamkeit erhalten. Dabei ist funktionale Programmierung kein neues Paradigma. Tatsächlich ist die erste funktionale Programmiersprache Lisp fast so alt wie die erste imperative Programmiersprache Fortran. Die Entwicklung der theoretischen Grundlagen zur funktionalen Programmierung, der Lambda Kalkül [17], reicht sogar bis in die 1930er-Jahre zurück. Heute wird funktionale Programmierung von den meisten Programmiersprachen unterstützt.
Mehrere Entwicklungen sind wohl dafür verantwortlich, dass die funktionale Programmierung, die über so viele Jahre ein mehr oder weniger akademisches Nischendasein fristete, jetzt vom Mainstream der Programmierwelt aufgegriffen wurde:
Und gerade die funktionale Programmierung wird als Mittel gesehen, diesen Herausforderungen zu begegnen.
Funktionale Programmierung beruht auf mathematischen Funktionen. In der Mathematik ist eine Funktion eine Abbildung einer Menge von Elementen des Definitionsbereichs D in eine weitere Menge von Elementen des Wertebereichs Z:
f : D → Z, x y
Jedem Element des Definitionsbereichs wird ein eindeutiger Wert des Wertebereichs zugeordnet. Praktisch heißt dies, dass eine Funktion bei gleichem Argumentwert immer den gleichen Ergebniswert liefern muss. Eine Funktion kann damit weder ein Gedächtnis haben, noch darf sie Seiteneffekte verursachen. Der einzige Mechanismus, der durch eine Funktion zur Verfügung gestellt wird, ist die Anwendung der Funktion auf Argumente, für die die Funktion ein eindeutiges Resultat liefert. Man spricht dann von rein-funktionaler Programmierung.
Eine rein-funktionale Programmierung beruht daher ausschließlich auf Funktionsdefinition und Funktionsanwendung. Die so vertrauten Konzepte der veränderlichen Variablen und Wertzuweisungen gibt es nicht, tatsächlich gibt es überhaupt keine veränderlichen Daten. Funktionale Programmierung unterscheidet sich damit grundsätzlich von imperativer Programmierung, die immer mit Zuweisungen von Werten an Variablen und Verändern eines Programmzustands arbeitet.
Funktionale Programme haben im Vergleich zu Programmen mit Seiteneffekten eine Reihe von günstigen Eigenschaften. Eine Funktion ist in sich abgeschlossen, weil sie nur von den Argumenten abhängt. Sie kann daher als eine Einheit angewendet, verstanden, getestet und verifiziert werden. Eine Funktionsanwendung steht ausschließlich für den Wert, den sie berechnet, und sie kann folglich zu jedem Zeitpunkt durch seinen Wert ersetzt werden. Das macht funktionale Programme unabhängig von einem Kontrollfluss und Funktionsanwendungen können in beliebiger Reihenfolge, parallel oder nach Bedarf erfolgen.
Aber ist dieses Modell, mit Funktionen mit Rückgabewerten und mit Funktionsanwendungen zu arbeiten, nicht viel zu restriktiv? Ist funktionale Programmierung damit im Vergleich zur imperativen Programmierung weniger mächtig und flexibel? Wie im wegweisenden Artikel von John Hughes mit dem Titel »Why functional programming matters« [32] eindrucksvoll argumentiert wird, liegt die Mächtigkeit der funktionalen Programmierung in der besseren Modularität und Kombinierbarkeit von Funktionen. Dadurch, dass Funktionen in sich abgeschlossen und nicht von einer Umgebung abhängig sind, können Funktionen frei kombiniert werden.
Besonders bemerkenswert ist auch, dass gerade John Backus, der mit der Entwicklung von Fortran [7] und mit seiner Mitarbeit bei der Definition von Algol 60 [6] ganz wesentlich zur Entwicklung der imperativen Programmiersprachen beigetragen hat, zu den Schwächen der imperativen Programmierung und zur Mächtigkeit der funktionalen Programmierung sehr früh grundlegende Einsichten gab. In seiner Ansprache zur Verleihung des Turing Awards hat er sich mit sehr drastischen Worten gegen die imperative Programmierung gewandt und eine funktionale Programmierung propagiert. Aus der begleitenden Publikation mit dem vielsagenden Titel »Can Programming Be Liberated From the von Neumann Style? A Functional Style and Its Algebra of Programs« [8] ist dazu folgende Aussage entnommen:
Conventional programming languages are growing ever more enormous, but not stronger. Inherent defects at the most basic level cause them to be both fat and weak: their primitive word-at-a-time style of programming inherited from their common ancestor–the von Neumann computer, their close coupling of semantics to state transitions, their division of programming into a world of expressions and a world of statements, their inability to effectively use powerful combining forms for building new programs from existing ones, and their lack of useful mathematical properties for reasoning about programs.
Backus sieht also die Schwäche der imperativen Programmierung in der engen Anlehnung an das Verarbeitungsmodell des von Neumann-Rechners. Und er vermisst mächtige Kombinationsoperatoren zur Gestaltung von Programmen auf höherer Ebene. Der Artikel propagiert dann einen funktionalen Programmierstil mit Operatoren zur Kombination von funktionalen Bausteinen. Er schreibt dazu:
An alternative functional style of programming is founded on the use of combining forms for creating programs. [...] Associated with the functional style of programming is an algebra of programs whose variables range over programs and whose operations are combining forms.
Backus hat damit früh den Weg der Entwicklung funktionaler Sprachen vorgezeichnet. Sehr anschaulich ist auch das Beispiel im Artikel, mit dem imperative Programmierung und funktionale Programmierung verglichen werden. Eine imperative Lösung des Skalarproduktes von Vektoren, folgend mit zwei Listen a und b mit Länge n, gestaltet sich in Java folgendermaßen:
int c = 0;
for (int i = 0; i < n; i++) {
c = c + a.get(i) * b.get(i);
}
Die Lösung baut auf der Wertzuweisung auf. Das Ergebnis wird in der Variablen c akkumuliert. In jedem Schleifendurchlauf wird in einer Wertzuweisung ein nächster Wert für c berechnet und gespeichert. Die Berechnung ist, wie Backus es kritisiert, »word-at-a-time style«.
Die im Artikel dann vorgeschlagene Lösung, übersetzt auf die heute übliche Form funktionaler Sprachen, sieht im Gegensatz dazu folgendermaßen aus:
map2((x, y) -> x * y).andThen(reduce((r, x) -> r + x))
Die Operationen beziehen sich nicht auf einzelne Elemente, sondern auf die Vektoren als Ganzes. Sie sind mit Verknüpfungsoperationen in der Form von Lambda-Ausdrücken parametrisiert. Mit map2 werden die Elemente zweier Vektoren paarweise mit der angegebenen Verknüpfungsoperation verknüpft. Die Operation reduce verknüpft die Elemente eines Vektors zu einem einzelnen Wert. Mit andThen werden Funktionen in Serie geschaltet. Somit werden in obiger Definition zuerst die Elemente von zwei Vektoren multipliziert und schließlich alle Produkte addiert. Das entspricht exakt der mathematischen Definition des Skalarprodukts. Im Gegensatz zur obigen imperativen Lösung ist diese Definition deklarativ und auf hoher Ebene. Die Operationen beziehen sich nicht auf einzelne Elemente, sondern auf die Datenobjekte selbst. Die Operationen haben keine Seiteneffekte und sind rein-funktional.
In diesem Beispiel sehen wir auch bereits die wesentlichen Konzepte, die funktionale Programmierung kennzeichnen:
Die erste funktionale Sprache Lisp wurde von John McCarthy als eine Implementierung des Lambda-Kalküls entwickelt und bereits im Jahre 1960 veröffentlicht [51]. Wenn man bedenkt, dass Fortran als erste imperative höhere Sprache von John Backus 1957 eingeführt wurde, ist funktionale Programmierung also nur rund drei Jahre jünger. Bemerkenswert ist auch, dass diese erste Version von Lisp bereits Lambda-Ausdrücke, Funktionen höherer Ordnung und Listenverarbeitung hatte, Dinge die fast 60 Jahre später wieder sehr aktuell sind.
Seit dieser frühen Zeit wurde die funktionale Programmierung stetig weiterentwickelt. Lisp hat sich über viele Versionen und Varianten in den 1980er- und Anfang der 1990er-Jahre als die Sprache der Künstlichen Intelligenz etabliert. Die Sprachvarianten CommonLisp [81] und Scheme [83] werden auch heute noch verwendet, und mit der Sprache Clojure [44] gibt es einen populären Nachfolger, der auf der Java VM läuft.
Lisp-Sprachen sind dynamisch typisiert, das heißt, Werte tragen ihren Typ, und die Typprüfung wird zur Laufzeit durchgeführt. Robin Milner hat mit der Einführung der Sprache ML den Grundstein für statisch typisierte funktionale Sprachen gelegt [53]. Bei dynamisch-typisierten Sprachen können Funktionen mit beliebigen Datentypen arbeiten. Milner erkannte, dass man bei statischer Typisierung eine vergleichbare Flexibilität mit Typparametern erreichen kann. Gleichzeitig wurde ein Typinferenz-Algorithmus zur statischen Typprüfung eingeführt. In Standard ML, einer Weiterentwicklung von ML, wurden basierend auf der Sprache HOPE [12] polymorphe algebraische Datentypen verwendet, die auch heute noch die Basis für die Typsysteme funktionaler Sprachen bilden.
Ein weiterer wichtiger Entwicklungsschritt der funktionalen Programmierung war beginnend mit den frühen 1980er-Jahren die Erforschung von Sprachen mit nicht-strikten Auswertungsverfahren [85][86]. Bei strikten Auswertungsverfahren, wie wir diese von Java und anderen Programmiersprachen kennen, werden die Ausdrücke für die Parameter vor einem Prozeduraufruf evaluiert und die Werte übergeben. Bei einer nicht-strikten Auswertung [67] können die Ausdrücke vorerst nichtevaluiert übergeben werden, um schließlich im Kontext der aufgerufenen Funktion evaluiert zu werden. Dies führte zur Einführung von nicht-strikten funktionalen Programmiersprachen, wie zum Beispiel Miranda [87], und zur Entwicklung von effizienten Ausführungskonzepten [46][65].
Wie in [31] zu lesen ist, gab es um 1987 eine Vielzahl von Sprachentwicklungen mit nicht-strikten Auswertungsverfahren, die ganz ähnliche Ziele verfolgten. Eine Gruppe von Forschern beschloss daher, als Grundlage für Forschung und Entwicklung funktionaler Programmierkonzepte einen gemeinsamen Sprachentwurf zu schaffen. Damit wurde die Sprache Haskell geboren und der Sprachentwurf Haskell 1.0 im Jahre 1990 vom Haskell Committee veröffentlicht [30]. Haskell ist heute der State of the Art für funktionale Programmierung. Die funktionalen Programmierkonzepte, die wir in Java heute sehen, haben im Wesentlichen ihr Vorbild in Haskell. Um für dieses Buch einen entsprechenden Hintergrund zu schaffen, werden wir daher im folgenden Abschnitt die elementaren Konzepte und die wichtigsten Begriffe der funktionalen Programmierung, wie sie sich in Haskell darstellen, einführen.
Die wichtigsten Konzepte der funktionalen Programmierung sind: Lambda-Ausdrücke und Funktionsobjekte, polymorphe algebraische Datentypen mit Typinferenz, Pattern Matching sowie nicht-strikte Bedarfsauswertung. Diese Konzepte werden im Folgenden kurz eingeführt. Im Laufe des Buches werden wir uns intensiv mit der Umsetzung dieser Konzepte in Java beschäftigen.
Lambda-Ausdrücke repräsentieren Funktionen mit formalen Argumenten und einem definierenden Ausdruck. Die beiden Seiten sind üblicherweise mit einem Pfeilsymbol1 getrennt. Der definierende Ausdruck legt den Funktionswert fest und hat keine Seiteneffekte. Folgendes Beispiel zeigt einen Lambda-Ausdruck mit Argument x und definierendem Ausdruck x + 1:
x -> x + 1
Lambda-Ausdrücke sind in Programmiersprachen Literale für die Erzeugung von Funktionsobjekten. Funktionsobjekte können wie andere Werte an Variablen zugewiesen, als Parameter übergeben und Ergebnis von Funktionen sein. Im Sprachgebrauch der funktionalen Programmierung sagt man, Funktionsobjekte sind first class. Mit diesem einfachen Prinzip lassen sich Funktionen mit Funktionen als Parameter bilden, sogenannte Funktionen höherer Ordnung2. Ebenso kann man Funktionen schreiben, die aus einfacheren Funktionen komplexere Funktionen erzeugen. Zum Beispiel kann man eine Funktion andThen definieren, die aus zwei Funktionen f und g eine Funktion erzeugt, die zuerst auf das Argument x die Funktion f und auf das Ergebnis die Funktion g anwendet:
andThen f g = x -> g (f x)
Bei den Variablen, die im definierenden Ausdruck eines Lambda-Ausdrucks vorkommen, unterscheidet man gebundene und freie Variablen. Gebundene Variablen sind Argumente des Lambda-Ausdrucks, freie Variablen sind nicht Argument des Lambda-Ausdrucks und müssen damit im Kontext des Lambda-Ausdrucks gebunden sein. Im folgenden Lambda-Ausdruck ist x gebunden und y frei:
x -> x + y
Freie Variablen sind für die Bildung von Funktionsobjekten kritisch und wir werden sie im Abschnitt 2.3.4 über Closures noch ausführlich behandeln.
Das Typsystem der statisch-typisierten funktionalen Sprachen beruht auf Algebraischen Datentypen. Algebraische Datentypen orientieren sich an Konzepten der Mengentheorie und erscheinen in einer abstrakteren Form als die Datentypen imperativer und objektorientierter Sprachen. Sie bauen auf Mengendefinitionen durch Enumeration und dem Kartesischen Produkt auf. Durch Kombination von Enumeration und Produkttypen ergeben sich sogenannte Variantentypen (engl.: variant types oder union types). Folgendes Beispiel eines Datentyps Expr zur Repräsentation von Booleschen Ausdrücken zeigt das Prinzip. Der Typ Expr definiert Varianten Lit, Var, Not, And und Or (die Varianten sind durch Oder-Striche getrennt). Jede Variante ist ein Produkttyp und besteht aus dem Namen der Variante, dem sogenannten Datentag, und den Typen für die Felder:
data Expr =
Lit Bool |
Var String |
Not Expr |
And Expr Expr |
Or Expr Expr
Die obige Datendefinition ist zudem rekursiv, da die Varianten Not, And und Or Felder vom Typ Expr haben. Auf diese Weise können hierarchische Strukturen gebildet werden.
Wir werden dieses Beispiel zur Repräsentation Boolescher Ausdrücke mehrmals in den Fallbeispielen zur funktionalen Programmierung in Java wieder aufgreifen und mit obiger Definition eines Algebraischen Datentyps vergleichen.
Typparameter dienen zur Definition von Funktionen und Datentypen, bei denen bestimmte Typen unbestimmt sind. Man spricht in der funktionalen Programmierwelt, von wo das Konzept auch ursprünglich stammt [53][13], von einem parametrischen Polymorphismus. Bei Java und anderen Sprachen ist das Konzept unter dem Begriff Generizität bekannt. Generizität ist für eine funktionale Programmierung von besonderer Bedeutung und wir werden daher bei den sprachlichen Grundlagen zur funktionalen Programmierung im nächsten Kapitel das Thema Generizität von Java detailliert behandeln.
Funktionale Programmiersprachen verwenden Typinferenz. Darunter versteht man, dass der Typ eines Ausdrucks einer Variablen oder die Signatur einer Funktion automatisch abgeleitet wird und nicht vom Programmierer angegeben werden muss. Bei Lambda-Ausdrücken werden üblicherweise die Typen der Argumente und des Rückgabewertes nicht angegeben, sondern durch Typinferenz abgeleitet. Zum Beispiel sind bei unserem einfachen Lambda-Ausdruck
x -> x + y
keine Typen für den Parameter x, die freie Variable y oder den Rückgabewert angegeben. Darüber hinaus ist der Operator + überladen und somit die Typen der Operanden nicht eindeutig. In Java könnten die Typen für Argument und Ergebnis beliebige Zahlen als auch Zeichenketten sein.
Bei imperativen Sprachen wird üblicherweise nur für Ausdrücke der Typ durch den Compiler automatisch bestimmt, aber nicht für Variablen und Funktionsdefinitionen. Bei funktionalen Sprachen ist das aber auch für Variablen und Funktionsdefinitionen möglich. Der sogenannte Hindley-Milner-Algorithmus [53][27] ist in der Lage, für einen beliebigen Ausdruck und Funktionsdefinitionen den allgemeinsten Typ abzuleiten, der alle gegebenen Einschränkungen erfüllt.
Mit der Einführung von Lambda-Ausdrücken wurde die automatische Typinferenz in Java wesentlich erweitert und wir werden diese im nächsten Kapitel bei den Themen Generizität und Lambda-Ausdrücke diskutieren.
Eine wesentliche Eigenschaft der Algebraischen Datentypen ist, dass sie grundsätzlich unveränderlich sind. Auch Datenstrukturen wie Listen, Mengen oder Maps sind unveränderlich. Man spricht von funktionalen oder persistenten Datenstrukturen3.
Die bekannteste funktionale Datenstruktur ist die funktionale Liste. In Haskell ist diese als Algebraischer Datentyp folgendermaßen definiert:
data [a] = [] | a : [a]
Der Typbezeichner ist [a] mit dem Typparameter a. Die Variante [] bezeichnet die leere Liste. Die Variante : ist eine Liste mit dem ersten Element vom Typ a und der Restliste vom Typ [a] (der Datentag : ist dabei in Infix-Notation angegeben). Listen sind also rekursive Strukturen mit einem Element und einer Restliste, wobei am Ende immer die leere Liste steht. Man kann damit durch Voranstellen von Elementen aus bestehenden Listen neue Listen erzeugen, aber bestehende Listen nicht verändern. Für weitere persistente Datenstrukturen gibt es sehr effiziente Verfahren, die zum Beispiel auch einen direkten Zugriff ermöglichen. In [61] ist eine umfassende Behandlung dieses Themas zu finden.
In diesem Buch werden wir mit einer persistenten Listenimplementierung analog zum obigen Algebraischen Datentyp arbeiten. Wir führen diese in Abschnitt 3.3 ein, erweitern sie im Laufe der folgenden Kapitel und verwenden sie bei mehreren Fallbeispielen.
Eng verbunden mit den Algebraischen Datentypen ist Pattern Matching. Es handelt sich dabei um eine Kontrollstruktur, mit der auf Basis von Mustern die Varianten eines Datentyps unterschieden werden. Stimmt ein gegebener Wert mit einem Muster überein, ergibt sich das Ergebnis durch den dazugehörigen Ausdruck. Muster werden analog zu den Konstruktoren der Varianten gebildet. Mit dem Datentag erfolgt zuerst die Unterscheidung der Varianten. Für die Felder können Werte oder Variablen angegeben werden. Bei Werten erfolgt ein Vergleich auf Gleichheit, bei Variablen wird der Feldwert an die Variable gebunden.
Betrachten wir dazu wieder unseren Algebraischen Datentyp Expr von oben. Folgende Haskell-Funktion mkString verwendet Pattern Matching, um eine String-Repräsentation für einen Expr-Wert zu erstellen:
mkString e =
case (e) of
Lit True -> "true"
Lit False -> "false"
Var name -> name
Not sub -> "(! " ++ mkString(sub) ++ ")"
And left right -> "(" ++ mkString(left) ++ " && " ++
mkString(right) ++ ")"
Or left right -> "(" ++ mkString(left) ++ " || " ++
mkString(right) ++ ")"
Mit einem case-Ausdruck werden für einen Expr-Wert e die möglichen Varianten unterschieden. Man sieht, dass die Muster in den Fallunterscheidungen exakt den Varianten der Datentypdefinition entsprechen. Des Weiteren entsprechen die rekursiven Aufrufe der rekursiven Definition des Datentyps. Ein großer Vorteil von Pattern Matching ist, dass mit dem Mustervergleich nicht nur die Varianten unterschieden, sondern die Feldwerte den Pattern-Variablen zugewiesen werden. Das Datenelement wird sozusagen in die Bestandteile zerlegt. So werden zum Beispiel bei den Varianten And und Or die beiden Unterausdrücke an die Variablen left und right gebunden.
In Java gibt es Pattern Matching leider nicht. Wir werden aber sehen, dass man mit Lambda-Ausdrücken Strukturen ähnlich zu Pattern Matching schaffen kann.
Unter einer Evaluierungsstrategie versteht man die Reihenfolge, in der Ausdrücke ausgewertet werden. Aus der imperativen und objektorientierten Programmierung kennen wir ausschließlich die strikte Evaluierung. Es werden dabei die Ausdrücke für die Argumente von Funktionsanwendungen zuerst von links nach rechts vollständig evaluiert und dann die Funktion mit den konkreten Ergebniswerten aufgerufen. Dies entspricht einer call-by-value Parameterübergabe. Eine strikte Evaluierung ist bei Programmen mit Seiteneffekten auch unvermeidlich, da hier die Reihenfolge der Evaluierung der Ausdrücke und Anweisungen Einfluss auf das Ergebnis haben kann.
Arbeiten wir aber mit reinen Funktionen, hat die Reihenfolge der Funktionsanwendungen keinen Einfluss auf das Ergebnis. In der funktionalen Programmierung kann man daher auch nicht-strikte Evaluierungsstrategien einsetzen. Haskell verwendet grundsätzlich eine nicht-strikte Evaluierungsstrategie, die sogenannte Bedarfsauswertung (engl.: lazy evaluation, call-by-need) [65]. Bei der Bedarfsauswertung wird ein Ausdruck erst und nur dann evaluiert, wenn das Ergebnis gebraucht wird.
Eine Bedarfsauswertung hat zum Beispiel Vorteile, wenn unendliche oder sehr große Strukturen verarbeitet werden. Das folgende Beispiel demonstriert das Arbeiten mit unendlichen Listen. In Haskell definiert der Ausdruck [1000..] die unendliche Liste der Integers ab dem Wert 1000. Mit dem Ausdruck
head (filter isPrime [1000..])
wird die erste Primzahl aus der Liste ermittelt. Dazu werden aber von der unendlichen Liste nur die Zahlen 1000 bis zur ersten Primzahl 1009 benötigt und somit auch nur diese generiert.
Java verwendet wie gesagt ausschließlich die strikte Evaluierung. Nicht-strikte Evaluierung kann man aber, wie wir in Abschnitt 4.6 zeigen werden, mit Funktionsparametern nachbilden und damit auch unendliche Strukturen schaffen. Und auch die funktionalen Streams in Java, die wir in Kapitel 7 behandeln, arbeiten nach dem Prinzip der nicht-strikten Bedarfsauswertung.
Die Erweiterungen von Java zur funktionalen Programmierung basieren auf den elementaren Konzepten, wie wir diese im letzten Abschnitt besprochen haben. Allerdings wird zurzeit nur ein Teil der Konzepte unterstützt. So gibt es in Java weder Algebraische Datentypen noch Pattern Matching. Auf der anderen Seite stehen die Konzepte zur funktionalen Programmierung nicht isoliert, sondern sind nahtlos in die objektorientierte Welt integriert. Funktionen werden durch Java-Objekte repräsentiert und können damit mit den Mitteln der objektorientierten Programmierung behandelt werden. So kann man Funktionen in herkömmlicher Weise mit objektorientierten Methoden erzeugen, aufbauen, umformen und kombinieren.