Funktionale Programmiersprache

In einer funktionalen Programmiersprache werden Berechnungen als Auswertung mathematischer Funktionen verstanden. Im Unterschied dazu werden in prozeduralen (oder imperativen) Programmiersprachen Berechnungen als Befehlssequenzen dargestellt, die nacheinander abgearbeitet werden. Die mathematische Grundlage der funktionalen Programmierung ist der λ-Kalkül (Aussprache: Lambda-Kalkül).

Anders ausgedrückt:

Ein funktionales Programm ist eine Abbildung von Eingabedaten auf Ausgabedaten, wohingegen ein imperatives Programm eine Arbeitsanweisung für eine Maschine ist. (Pepper)
In einem funktionalen Programm wird die Reihenfolge der Berechnungsschritte in der Regel nicht festgelegt, während ein imperatives Programm ohne die Reihenfolge der Abarbeitungsschritte gar nicht verstanden werden kann.
Funktionale Programmiersprachen erlauben es, Funktionen (wie Daten) als Argumente und Rückgabewerte anderer Funktionen zu behandeln. Dadurch ist es einfach, Operatoren auf Funktionen zu definieren. Dies macht funktionale Programme oft kürzer und abstrakter, erfordert jedoch oft eine Umgewöhnungszeit für Programmierer, die den imperativen Programmierstil gewohnt sind.

Konzepte

Rein funktionale Programmiersprachen

Rein (engl. pure) funktionale Programmiersprachen fassen Programme als mathematische Funktion auf: Ein Ausdruck hat dort während der Programmausführung immer den gleichen Wert. Es gibt keine Zustandsvariablen, die während einer Berechnung geändert werden. Man bezeichnet diese Eigenschaft als Werttreue (engl. referential transparency). Sie vereinfacht Korrektheitsbeweise von Algorithmen wesentlich. Um erwünschte Wirkungen (Benutzerinteraktion, Eingabe/Ausgabe-Operationen) beschreiben zu können, sind meist besondere Vorkehrungen notwendig. Die meisten funktionalen Programmiersprachen erlauben allerdings Wirkungen und sind daher keine reinen funktionalen Programmiersprachen (Ausnahme: Haskell, Clean).

Funktionen höherer Ordnung

Man unterscheidet Funktionen erster Ordnung und Funktionen höherer Ordnung. Bei Funktionen höherer Ordnung sind Funktionen selbst Werte. Dies erlaubt es insbesondere, Funktionen als Ergebnisse oder Parameter anderer Funktionen zu verwenden. Ein typisches Beispiel ist der Ableitungsoperator: Eingabe ist eine differenzierbare Funktion, Ausgabe ist die Ableitung dieser Funktion. Ein Beispiel aus der Informatik ist map, um eine beliebige, übergebene Funktion f auf jedes Element einer Liste anzuwenden. Definition in Haskell:

map f [] = []   
map f (x:xs) = f x : map f xs

In der ersten Zeile wird das Ergebnis für eine leere Liste [] zurückgegeben; die zweite Zeile wendet die Funktion f auf das erste Listenelement x an und führt dann einen Rekursionsschritt für die restliche Liste xs durch.

Bedarfsauswertung und strenge Auswertung

Funktionale Sprachen kann man auch nach ihrer Auswertungsstrategie unterscheiden: Bei strenger Auswertung (engl. eager bzw. strict evaluation) werden die Argumente von Funktionen zuerst ausgewertet. Dagegen werden bei der nicht-strikten Auswertung zunächst die Ausdrücke als ganzes übergeben und dann ausgewertet.

Man könnte zum Beispiel $(3+5)^{2}$ auf zwei Arten berechnen, wobei die Gleichung im ersten Fall strikt ausgewertet wird, da erst die Argumente der Potenz-Funktion berechnet werden. Im zweiten Fall werden diese Argumente erst bei Bedarf ausgewertet, also nachdem die Potenzfunktion aufgelöst wurde:

$(3+5)^{2}=8^{2}=8\cdot 8=64$
$(3+5)^{2}=(3+5)\cdot (3+5)=8\cdot 8=64$

Eine Variante der nicht-strikten Auswertung ist die Bedarfsauswertung (engl. lazy evaluation), bei der Ausdrücke erst ausgewertet werden, wenn deren Wert in einer Berechnung benötigt wird. Dadurch lassen sich z.B. unendlich große Datenstrukturen (die Liste aller natürlicher Zahlen, die Liste aller Primzahlen, etc.) definieren und bestimmte Algorithmen vereinfachen sich.

Manche Berechnungen lassen sich mit strenger Auswertung, andere mit Bedarfsauswertung effizienter ausführen. Terminiert die strenge Auswertung eines Ausdruckes, so terminiert auch die nicht-strikte Auswertung.

Typisierung

Weiterhin kann man funktionale Sprachen nach ihrer Typisierung einteilen in dynamisch und statisch typisierte Sprachen, die sich dadurch ergeben, dass die Typprüfung während der Laufzeit bzw. während der Übersetzungszeit stattfinden kann. Programmiersprachen wie Haskell und SML sind statisch typisiert und unterstützen Typeninferenz (d.h. der Compiler erkennt die Datentypen automatisch). Programmiersprachen aus der Lisp-Familie sind dynamisch typisiert.

Nebenläufigkeit und Verteilung

Eine weitere Einteilung kann danach vorgenommen werden, ob die Sprache für sequentielle oder nebenläufige Ausführung entworfen wurde und ob es Unterstützung für die Verteilung auf verschiedene Rechnerknoten gibt. Ein Beispiel für eine nebenläufige, verteilte funktionale Sprache ist Erlang.

Algorithmen und Datenstrukturen

Algorithmen geben vorteilhafte Verfahren für die Lösung wichtiger Probleme an (z.B. Sortieren) und sind in der Regel gut analysiert, so dass ein Entwickler auf bewährte, einschätzbare Lösungen zurückgreifen kann. Gleiches leisten Datenstrukturen für die Organisation von Daten. Sammlungen von guten Algorithmen und Datenstrukturen haben somit eine große praktische Bedeutung.

Chris Okasaki schreibt: Auch wenn die meisten dieser Bücher [über Datenstrukturen] behaupten, dass sie unabhängig von einer bestimmten Programmiersprache sind, so sind sie leider nur sprachunabhängig im Sinne Henry Fords: Programmierer können jede Programmiersprache benutzen, solange sie imperativ ist.

Der Verzicht auf zerstörerische Zuweisungen führt dazu, dass etliche klassische Algorithmen und Datenstrukturen, die regen Gebrauch von dieser Möglichkeit machen, so nicht für funktionale Sprachen verwendet werden können und man nach neuen Lösungen suchen muss.

Gerade rein funktionale Datenstrukturen sind von ihrer Natur her anders als die gewohnten Datenstrukturen, die meist nur eine Version ihrer Daten verwalten (ephemerale Datenstrukturen), wohingegen funktionale Datenstrukturen mehrere Versionen verwalten (persistente Datenstrukturen).

Referenzen

Fethi Rabhi und Guy Lapalme: Algorithms - A Functional Programming Approach, Addison Wesley 1999, ISBN 0201596040
Chris Okasaki: Purely Functional Data Structures, Cambridge University Press 1999, ISBN 0521663504

Ein Beispiel in SML

local
  val pi = 3.14;
  val sq = fn x => x*x;
in
  val ringarea = fn (R,r) => pi*(sq R - sq r);
end;

Dieses Programm definiert eine Funktion ringarea, die die Fläche berechnet, die zwischen den beiden konzentrischen Kreisen mit den Radien R und r liegt. Dazu werden die Konstante pi und die Hilfsfunktion sq definiert. Diese werden von ringarea dann für die Berechnung benutzt.

Das Beispiel in Joy

DEFINE
   pi == 3.14;
   sq == dup *;
   ringarea == sq swap sq swap - pi *.

Man beachte, daß keine Variablennamen verwendet werden (auch pi ist eine Funktion!)

Funktionale Programmiersprachen

Siehe auch

ICFP Contest