FAQ der Newsgroup de.comp.lang.funktional vom 5.10.2004

Inhaltsverzeichnis

1 Einleitung

Dieser Text ist eine Liste von häufig gestellten Fragen und Antworten der Newsgroup de.comp.lang.funktional und bietet weitere Informationen zu Büchern und anderen Internetquellen.

1.1 Charta der Newsgroup de.comp.lang.funktional

Thema dieser unmoderierten Gruppe sind alle Aspekte funktionalen Programmierens.

Zu den funktionalen Programmiertechniken zählen unter anderem seiteneffektfreie Funktionen, Funktionen höherer Ordnung, Closures und Funktionen als first-class-values. Einige Sprachen unterstüzten dieses Programmierparadigma besonders gut, z.B. Haskell, Clean, Erlang, Scheme, OCaml und Lisp. Erwünscht sind in dieser Newsgruppe insbesondere Diskussionen zur Praxis des funktionalen Programmierens, aber auch zu den theoretischen Grundlagen, zu funktionalen Konzepten und Idiomen, sowie Ideen und Techniken, wie man funktionale Sprachen implementiert. Auch Ankündigungen von neuen funktionalen Sprachen, Tutorials und Veranstaltungen dazu sind willkommen.

1.2 Organisatorisches

Die aktuelle Version ist im Web erhältlich:

http://www.frank-buss.de/funktional/faq.html

Die Beiträge dieser Newsgroup (und anderer) werden bei Google archiviert:

http://groups.google.de/groups?group=de.comp.lang.funktional

Dieses FAQ basiert zur Zeit größtenteils auf der FAQ für comp.lang.functional von Mark P. Jones und Graham Hutton und wird von Frank Buß verwaltet. Hinweise und Verbesserungsvorschläge sind immer willkommen. Bitte jeweils angeben, ob man in die Liste der mitwirkenden Personen aufgenommen werden möchte.

Einige Übersetzungen, besonders im Glossar/Wörterbuch, basieren auf Einträgen aus FOLDOC: The Free On-line Dictionary of Computing, Editor Denis Howe und Wikipedia

An der deutschen Fassung haben folgende Leute mitgewirkt: Klaus Aehlig, Stefan Matthias Aust, Frank Buß, Thomas Fischbacher, Thomas Gerlach, Thomas Huehn, Marco Lange, Marco Schmidt, Falko Spiller

2 Übersicht

Dieser Abschnitt beantwortet allgemeine Fragen zum Thema funktionalen Programmierens und gibt Bücher- und Website-Tipps.

2.1 Funktionale Sprachen

Was ist eine "funktionale Programmiersprache"?

Es gibt keine allgemein anerkannte Defintion, was genau zu einer funktionalen Sprache alles gehört, aber hier eine Defintion, um was es in der Newsgroup geht:

Als Funktionales Programmieren bezeichnet man einen Programmierstil, der auf der Auswertung von Ausdrücken den Schwerpunkt legt, statt auf der Ausführung von Befehlen. Die Ausdrücke dieser Sprachen setzen sich aus Funktionen zusammen, um einfache Werte zu kombinieren.
Als Beispiel betrachten wir die Aufgabe, die ganzen Zahlen von 1 bis 10 zu summieren. In imperativen Sprachen, wie C, würde man das als Schleife ausdrücken, und eine bei jedem Durchlauf den Schleifenzähler i und die Summe total aktualisieren: 
int sum(int i) {
  int total = 0;
  for (; i > 0; i--) {
     total += i;
  }
  return total;
}
sum(10);

In einer funktionalen Sprache würde man dieselbe Aufgabe ohne Seiteneffekte, also ohne Variablenaktualisierung lösen. In Haskell zum Beispiel kann das Ergebnis durch die Auswertung dieses Ausdrucks berechnet werden: 

sum [1..10]

[1..10] ist dabei ein Ausdruck, der die Liste der ganzen Zahlen von 1 bis 10 repräsentiert und sum ist eine Funktion, die zum Summieren beliebiger Elemente einer Liste verwendet werden kann.

Dieselbe Idee kann in (strikt) funktionalen Sprachen wie SML oder Scheme verwendet werden, aber im allgemeinen wird das als explizite Schleife, oft rekursiv, ausgedrückt. Dennoch werden die Werte der beteiligten Variablen während der Abarbeitung nicht geändert:

SML:

let fun sum i total =
  if i=0 then
    total
  else
    sum (i - 1) (total + i)
in
  sum 10 0
end;

Scheme:

(define (sum i total)
  (if (zero? i)
    total
    (sum (- i 1) (+ total i))))
(sum 10 0)

Man kann meistens auch in imperativen Sprachen funktional Programmieren (und umgekehrt). Es ist dann Ansichtssache, die Sprache zu den funktionalen Sprachen zu zählen. Hier das Summenbeispiel in C, mit einer Rekursion und ohne temporäre Variable gelöst: 

int sum(int i, int total) {
  if (i) {
    return sum(i - 1, total + i);
  } else {
    return total;
  }
}
sum(10, 0);

Dabei darf man aber die maximal erlaubte Rekursionstiefe nicht überschreiten (compilerabhängig).

In funktionalen Sprachen sind Funktionen üblicherweise gleichberechtigte Datentypen, d.h. Funktionen können Funktionen als Argumente übergeben bekommen und auch Funktionen als Ergebnis des Funktionsaufrufs liefern. Solche Funktionen werden auch Funktionen höherer Ordnung (higher-order functions) genannt. Als Beispiel für ein Funktionsargument hier eine allgemeinere Version der Summe in Haskell:

mySum f i total = if i > 0 then f i nextRecursion else total
  where nextRecursion = mySum f (i - 1) total

Der Parameter f wird dabei als Funktion betrachtet. Da "+" auch nur eine Funktion ist, kann es z.B. so aufgerufen werden:

mySum (+) 10 0

Mit der passenden Funktion als Parameter hat man aber auch viele andere Möglichkeiten, z.B. die Fakultät zu berechnen (1*2*3...*10):

mySum (*) 10 1

In den mitgelieferten Bibliotheken von funktionalen Sprachen sind solche allgemeinen Funktionen meist enhalten, sodaß man in Haskell die mySum-Funktion nicht selbst definieren braucht, sondern das auch so schreiben könnte:

foldl (*) 1 [1..10]

In imperativen Sprachen sind Funktionsargumente nicht üblich, aber möglich und wird in C u.a. für die stdlib-Funktion qsort verwendet (auch unter dem Begriff Callback-Funktion bekannt).

2.2 Entstehungsgeschichte

Hier zwei nützliche Hinweise zur Entstehungsgeschichte und warum funktionale Sprachen erfunden wurden:

2.3 Lehrbücher

Eine Auswahl einiger Bücher:

Programmierung

Algorithmen und Datenstrukturen

Implementierung

Es gibt eine Reihe weitere Lehrbücher, besonder im Bereich der Programmierung und Implementierung. Ein Vergleich von Büchern zum Thema funktionalen Programmierens gibt der folgende Artikel:

2.4 Zeitschriften und Tagungen

Journals

Tagungen

Für die meisten dieser Veranstaltungen werden Proceedings von ACM press oder Springer Verlag in den "LNCS (Lecture Notes in Computer Science) series" veröffentlicht.

Zusätzlich zum oben genannten ist Philip Wadler Redakteur einer Kolummne über funktionales programmieren für den "Formal Aspects of Computer Science Newsletter", der von der "British Computing Society Formal Aspects of Computing group" und "Formal Methods Europe" veröffentlicht wird.

2.5 Schulungen und Workshops

Schulungen

Workshops

2.6 Einsatz in der Lehre

Ist es sinnvoll, funktionale Sprachen in der Lehre einzusetzen?

Funktionale Sprachen werden immer öfter im Studium eingesetzt, da es die Formulierung von Konzepten auf einem hohen Abstraktionsniveau erlaubt. Viele Informatik-Lehrstühle verwenden funktionale Sprachen in den Informatik-Kursen für Studenten, einige lehren es sogar als erste Programmiersprache. Mehr Infromationen zu funktionalen Sprachen in der Lehre (mit Links zu relevanten Tagungen und Workshops) ist im Web verfügbar:

http://www.cs.kun.nl/fple/

2.7 Geschwindigkeit

Wie schnell sind funktionale Programme?

Vielfach herrscht noch die Meinung vor, Programme in funktionalen Programmiersprachen seien langsam, was mit den hohen Abstraktionsniveau der Programme und leistungsfähigen Techniken wie Funktionen höherer Ordnung, automatische Speicherverwaltung (Stichwort Garbage Collector) usw. begründet wird. Die Entwicklung der Interpreter und Compiler schreitet aber kontinuierlich voran. Hier eine Auswahl von Links zum Thema:

2.8 Anwendungen

Wo werden funktionale Programmiersprachen angewendet?

Eine Auswahl:

3 Konzepte funktionaler Sprachen

Dieser Abschnitt beantwortet einige technische Fragen zu funktionalen Programmiersprachen, mit Links zu weiterführenden Informationen im Web und Bücherempfehlungen.

3.1 Rein funktional

Was versteht man unter einer "rein funktionalen" Programmiersprache (engl. pure functional)?

Diese Frage ist immer wieder Gegenstand von Diskussionen unter funktionalen Programmierern. Bei Haskell und Miranda ist es weitgehend unstrittig, die zu den rein funktionalen Sprachen zu zählen, während das für SML und Scheme nicht zutrifft. Allerdings gibt es auch unterschiedliche Auffassungen über die exakten technischen Grundlagen für diese Unterscheidung. Hier der Versuch einer Definition:

Die Bezeichnung "rein funktional" wird oft für Sprachen verwendet, die all ihre Berechnungen durch Funktionsaufrufe durchführen, im Gegensatz zu Sprachen wie Scheme und Standard ML, die zwar hauptsächlich funktional sind, aber auch Seiteneffekte erlauben (bleibende Veränderungen außer dem Rückgabewert, die nach Auswertung einer Funktion bestehen bleiben).

Manchmal wird die Beschreibung "rein funktional" auch allgemeiner für Sprachen verwendet, die Seiteneffekte erlauben, aber nicht die Grundidee einer Funktion ändern. Typischerweise kann in solchen Sprachen die Auswertung eines Ausdrucks einen neuen Task erzeugen, der getrennt ausgeführt wird, um einen Seiteneffekt zu erzeugen. Die Auswertungs- und die Ausführungsphasen sind dabei in einer Art und Weise getrennt, daß in der Ausführungsphase die Standardeigenschaften von Ausdrücken von Funktionen nicht gefährdet werden. Ein Beispiel dafür ist der Ein-/Ausgabemechanismus von Haskell, siehe auch Monade.

Siehe auch:

3.2 Currying

Was ist "currying" und woher kommt es?

Currying wird auf Funktionen angewendet, die mehr als ein Argument habe und ist nach dem Logiker Haskell Curry benannt. Wenn Currying auf eine Funktion f, die zwei Argumente hat, angewendet wird, entsteht eine Funktion g mit einem Argument, die eine Funktion mit einem Argument zurückliefert, sodaß f(x, y) gleich (g(x))(y) ist, oder in Lisp-Notation: (f x y) ist gleich ((g x) y). Dieses Verfahren kann auch mehrfach angewendet werden, z.B. wenn vollständiges Currying auf eine Funktion f(x, y, z) angewendet wird, erzeugt das eine Funktion g, sodaß ((g(x))(y))(z) gleich f(x, y, z) ist, oder in Lisp-Notation: (f x y z) ist gleich (((g x) y) z).

In Haskell und ML wird Currying automatisch auf Funktionen angewendet, die mit zuwenig Argumenten aufgerufen werden, siehe auch Funktionen höherer Ordnung.

Currying hat seine Wurzeln im Studium mathematische Funktionen, siehe dazu auch 3.8 Lambda Kalkül. In funktionalen Sprachen kann Currying als eine Funktion beschrieben werden:

curry : ((a,b) -> c) -> (a -> b -> c)

Die inverse Operation nennt man uncurrying: 

uncurry : (a -> b -> c) -> ((a,b) -> c)

Für weitere Informationen siehe folgende Quellen:

3.3 Monade

Was ist eine Monade (engl. monad) und wofür werden sie angewendet?

Das Konzept einer Monade kommt aus der Kategorientheorie und kann im Detail in jedem Standardlehrbuch zu diesem Thema nachgelesen werden. Von Interesse für die funktionale Programmierung sind Monaden, weil neuere Fachartikel zeigen, wie dieses Konzept für viele Programmieraufgaben, wie Ein-/Ausgabe, Änderungen von Zuständen, Continuations und Ausnahmebehandlung, in rein funktionalen Programmiersprachen, wie Haskell, eingesetzt werden können.

3.4 Parser

Wie kann ich einen Parser (Übersetzer) in einer funktionalen Programmiersprache schreiben?

Ein Parser ist ein Programm, daß eine Liste von Eingabe-Tokens (überlicherweise Zeichen) in einen Wert des passenden Typs umwandelt. Ein einfaches Beispiel wäre eine Funktion, die einen aus einer Folge von Ziffern bestehenden String in eine ganze Zahl umwandelt. Ein komplexeres Beispiel wäre die Übersetzung von Quelltext in eine abstrakte interne Darstellung, als Vorstufe für die Implementierung eines Compilers oder Interpreters. Es gibt zwei übliche Verfahren, einen Parser in einer funktionalen Sprache zu schreiben:

Einen Parser-Generator verwenden

Einige Implementierungen funktionaler Sprachen unterstützen Tools, die einen Parser aus einer Grammatik generieren.

Kombinatoren zum Parsen verwenden

Mit dieser Technik werden Parser durch Funktionen dargestellt und Kombinatoren dargestellt, die in geeigneter Weise zu höheren Funktionen kombiniert werden, was zu Parsern führt, die sehr ähnlich wie die zu implementierende Grammatik aussehen. Parser die nach diesem Verfahren programmiert sind können Backtracking verwenden.

3.5 Strikte Auswertung

Was bedeutet es, wenn eine funktionale Programmiersprache "strikt" oder "nicht-strikt" ist?

Das bezieht sich auf die Auswertung von Argumenten einer Funktion. Strikt (engl. strict oder auch eager) bedeutet, daß die Argumente vor Aufruf der Funktion ausgewertet werden, bei nicht-strikter Auswertung (engl. auch lazy-evaluation) werden die Argumente erst bei Bedarf ausgewertet. Das kann zu unterschiedlichen Laufzeitverhalten führen, da bei strikter Auswertung beispielsweise ein Fehler oder eine Endlosschleife bei der Auswertung eines Arguments auftreten kann, der bei träger Auswertung nicht auftreten würde, wenn das entsprechende Argument nie ausgewertet wird. ML und Scheme sind strikte Sprachen, Haskell und Miranda nicht-strikt.

Die Vor- und Nachteile strikter Programmiersprachen werden immer wieder gerne diskutiert. Es ist jedoch auch möglich, beide Varianten in einer Sprache unterzubringen, wie es in einigen Versionen der funktionalen Sprache Hope realisiert wurde.

Hier ein Beispiel für verzögerte Auswertung in Haskell:

take 10 [2*x | x <- [0..]]

Die Funktion take liefert die ersten n Elemente einer Liste. Als Liste haben wir mit [2*x | x <- [0..]] alle geraden Zahlen, bei 0 beginnend, definiert (0, 2, 4, ...). Als Ergebnis bekommen wir also die Liste [0,2,4,6,8,10,12,14,16,18]. Wenn die Auswertung strikt wäre, dann würde das Programm nie enden, da zunächst die unendliche Menge aller geraden Zahlen berechnet werden würde.

3.6 Seiteneffektfrei

Was ist ein Seiteneffekt und was bedeutet es, wenn eine Sprache seiteneffektfrei ist?

Rein funktionale Sprachen wie Haskell sind im Gegensatz zu imperativen Sprachen, wie C oder Java, frei von Seiteneffekten. Hier ein Beispiel für eine Java-Methode, die nicht seiteneffektfrei ist:

boolean incrementHour(Date d){
    int hour = d.getHours();
    if (hour < 23) {
        d.setHours(hour + 1);
        System.out.println("incremented.");
        return true;
    } else {
        return false;
    }
}

Diese Methode kann den übergebenen Wert ändern und etwas auf die Standardausgabe ausgeben. Bei seiteneffektfreien Funktionen dagegen ist der einzige Effekt der Rückgabewert der Funktion, es werden keine globalen Variablen oder die übergebenen Parameter geändert. Mit Seiteneffekten erzielt man Wirkungen außerhalb des funktionalen Ablaufs, sie können deshalb zu schwer verfolgbaren Fehlern führen.

Damit auch rein funktionale Sprachen etwas auf die Standardausgabe ausgeben oder Dateien einlesen können, sind die seiteneffektbehafteten Teile vom rein funktionalen Teil des restlichen Programms streng getrennt, z.B. per Monade. Alle Teile des Programms, die mit seiteneffektbehaftet sind, kann man damit leicht identifizieren, im Gegensatz z.B. zu Java, womit man prinzipiell ebenfalls seiteneffektfrei programmieren kann, was aber nicht von der Sprache ausdrücklich unterstützt wird.

3.7 Funktionen höherer Ordnung

Was ist eine Funktion höherer Ordnung?

Funktionen höherer Ordnung sind solche, die als Argument Funktionen akzeptieren oder Funktionen zurückgeben.

Eine Funktion, die eine Funktion als Argument erwartet ist in Haskell z.B. map. Als erstes Argument wird eine Funktion erwartet, die ein Argument erwartet. Das zweite Argument von map ist eine Liste. Bei Aufruf der map-Funktion wird eine neue Liste erstellt, indem die übergebene Funktion jeweils einzeln auf alle Elemente der übergebenen Liste angewendet wird. Z.B. ergibt map ((*) 2) [1,2,3,4] die Liste [2,4,6,8].

Das Argument ((*) 2) ist auch ein Beispiel für automatisches Currying. Da der (*)-Operator (der durch die Klammerung von einem Infix-Operator zu einem Prefix-Operator wird) zwei Argumente benötigt, wird automatisch per Currying eine Funktion zurückgeliefert, die einen weiteren Parameter, die jeweiligen Listenelemente im map-Beispiel, erwartet.

3.8 Typinferenz

Was ist Typinferenz?

Typinferenz bedeutet, daß der Compiler oder Interpreter die Typen der Argumente und Rückgabewerte von Funktionen selbst schließen kann, ohne das der Programmierer die explizit angeben braucht. Diese Spracheigenschaft bieten viele funktionale Sprachen, z.B. kann man in Haskell eine Funktion so definieren:

nextChar c = chr (ord c + 1)

Als Typ für das Argument c ermittelt dann Haskell automatisch Char und als Rückgabewert ebenfalls Char, weil ord als Argument einen Wert vom Typ Char erwartet und chr einen Wert vom Typ Char zurückliefert. Wenn man es per nextChar 'a' aufruft, bekommt man als Ergebnis 'b', versucht man dagegen nextChar "test" aufzurufen, bekommt man eine Fehlermeldung, daß der Typ nicht stimmt.

3.9 Hindley/Milner Typsystem

Was ist das Hindley/Milner Typsystem und worin bestehen die Vor- und Nachteile?

Das Hindley/Milner Typsystem ist ein rein statisches Typsystem, das Grundlage vieler funktionaler Sprachen ist. Eine Besonderheit ist, daß man ganz auf die explizite Angabe von Typen verzichten kann, da die per Typinferenz automatisch vom System erschlossen werden können, was in den meisten Fällen sinnvoll ist und Fehler schon während der Compilierzeit erkennen läßt.

Es gibt aber auch einige wenige Situationen, in denen man aus verschiedenen Gründen Techniken anwenden will, die zwar an sich völlig in Ordnung wären (insbesondere, einer Funktion sich selbst übergeben), aber nicht gehen, weil das Typsystem einem das verbietet - obwohl man genau weiss, was man macht, und es sinnvoll wäre. In LISP dagegen sind z.B. solche nicht-typisierbaren Funktionen möglich.

3.10 Lambda Kalkül

Was ist der Lambda Kalkül?

Dem Begriff der "Funktion" können in der Mathematik verschiedene Konzepte zugrundeliegen. Noch zu Zeiten Eulers hatten die Mathematiker eine eher vage intuitive Vorstellung davon, was eine Funktion denn nun genau sein solle, was einiges an Konfusion verursacht hatte. Uns fehlt heute ein wenig der Sinn für derartige Verwirrungen, weil wir in der Schule frühzeitig mit dem Funktionsbegriff vertraut gemacht wurden, der sich letztendlich durchgesetzt hat, und der in seiner heutigen Formulierung wohl auf Dirichlet zurückgeht. Hierbei wird eine Funktion über ihren Graphen definiert, d.h. mit einer eine eindeutige Abbildung beschreibenden Teilmenge der Menge aller möglichen Wertepaare aus dem Produkt einer gegebenen Urbildmenge und einer Bildmenge identifiziert, oder anders ausgedrückt: eine Funktion ist der Spezialfall einer Beziehung (Relation) zwischen Urbildern und Bildern, die es erlaubt, jedem Urbild eindeutig ein Bild zuzuordnen. Eine natürliche Verknüpfung von Funktionen ist hier die Hintereinanderausführung (Komposition).

Es gibt einen weniger populären aber ebenfalls ungemein nützlichen Funktionsbegriff, der die Idee der Funktion als Definition einer Berechnungsvorschrift in den Vordergrund rückt - und damit natürlich auch das Konzept der Berechenbarkeit als solcher.

Wenn wir ganz unvoreingenommen an die Frage herangehen, welche Berechnungsvorschriften im allgemeinsten Sinn wir uns überhaupt vorstellen können, darunter etwa auch Vorschriften wie "nimm eine Zahl und addiere zwei hinzu", so stellen wir fest, dass es eine Klasse von solchen "klaren Vorschriften wie etwas zu tun ist" im allgemeinsten Sinne gibt, die dadurch besticht, dass in jenen Vorschriften nicht von Zahlen, nicht von Addition, Multiplikation oder anderen speziellen Rechenoperationen die Rede ist, sondern ganz allgemein nur von Funktionen und Werten. Ein natürliches einfaches Beispiel wäre gerade eben der Begriff der Hintereinanderausführung von Funktionen als solcher. In Worten lautet die Vorschrift: die Komposition zweier Funktionen f und g ist die Abbildung, die jedem x den Wert zuordnet, den die Funktion f an der Stelle annimmt, die der Wert der Funktion g an der Stelle x ist. Diese Vorschrift definiert eine Abbildung von zwei Funktionen auf eine Funktion. Wir können diese Vorschrift jetzt selbst als Funktion betrachten, deren Wert eine Funktion ist. Es ist zweckmäßig, auch Funktionen als Werte zu bezeichnen, und auch vollwertig als solche anzusehen. (Das mag vielleicht im ersten Moment etwas ungewohnt erscheinen, aber es spricht nichts dagegen.)

Solche ganz abstrakten Vorschriften, die wir als Funktionen betrachten wollen, und in denen nur von Funktionen die Rede ist, wollen wir Kombinatoren nennen. Es ist vielleicht ganz natürlich, hier zunächst einmal skeptisch zu sein, ob es nicht ein großer Fehler sein könnte, solche Vorschriften auch als Funktionen zu bezeichnen, da die normale Sprechweise den Gedanken nahelegen würde, derartige Vorschriften in andere derartige Vorschriften einzusetzen, insbesondere eine Funktion auf sich selbst anzuwenden. Wenn man diesen Gedanken jedoch konsequent weiterführt, stellt sich heraus, dass hierbei gewissermassen "fast aus dem Nichts" eine Theorie entsteht, in der nur von Funktionen und Funktionsauswertung die Rede ist, die aber mächtig genug ist, um jede Berechnung zu formalisieren. Der Lambda-Kalkül (auch λ-Kalkül geschrieben), schlicht wie er ist, ist mächtig genug, um jedes Programm, das eine Turingmaschine ausführen kann, in einen Kombinator zu übersetzen, der dieselbe Berechnung vermittelt. Während jedoch das Konzept einer Turingmaschine stark von Gedanken an reale Zustandsmaschinen beinflußt wird, ist es im Lambda-Kalkül möglich, über Berechnungen zu sprechen, ohne jemals an etwas anderes als Funktionen denken zu müssen, was wesentlich natürlicher erscheint als sich von Maschinenzuständen (und Sprüngen zwischen ihnen), Speicherzuständen und künstlichen nervigen Details vom eigentlichen Problem ablenken zu lassen.

Als Beispiel hier die Darstellung der natürlichen Zahlen per Funktionen. Man kann eine natürliche Zahl n durch eine Funktion ausdrücken, die eine beliebige Funktion n mal auf ein Argument anwendet. Hier die ersten drei Zahlen (in Haskell-Syntax): 

zero = \f x -> x
one = \f x -> f x
two = \f x -> f (f x)

Man kann dann Funktionen defininieren, um mit diesen Zahlen zu rechnen: 

successor = \ x y z -> y ((x y) z)

add = \n m s z -> n s (m s z)

Zwei Kombinatoren, mit denen zusammen jede Berechnung ausgedrückt werden kann, sind die Konstanzfunktion K [K a x = a] und die Verschmelzungsfunktion S [S a b c=(a c) (b c)].

4 Sprachen

Dieser Abschnitt bietet eine kurze Übersicht über veschiedene Programmiersprachen, die funktionale Programmierparadigmen unterstützen, mit Querverweisen zu weiterführender Literatur und Internet-Links. Die untenstehende Tabelle klassifiziert die Sprachen in strict / nicht-strikt und sequentiell / parallel (also ohne oder mit Multithread-Unterstützung), was sinnvoll sein kann, wenn man für einen bestimmten Anwendungsfall eine Sprache sucht. Bei Sprachen, die es in verschiedenen Ausführungen mit mehreren Klassifikationen gibt (siehe die Kurzbeschreibung zu der jeweiligen Sprache für mehr Informationen), wurde die übliche Variante für die Klassifizierung gewählt.

  sequentiell parallel
strikt ASpecT
Caml
FP
J
Mercury
ML
OPAL
Scheme
XSLT 		Erlang
NESL
Oz
Pizza
Sisal
nicht-strikt Gofer
Haskell
Hope
Hugs
Miranda 		Clean
Id

Einige der Sprachen sind nur rein experimentelle Sprache oder für einen Spezialfall entwickelte Sprachen, wie ASpecT, die in der Praxis kaum eingesetzt werden oder auch nicht zum produktiven Einsatz geeignet sind. Häufig verwendet wird dagegen Haskell, Scheme und OCaml, was aber nur eine exemplarische Aufzählung ist, da einige Sprachen ständig weiterentwickelt werden und teilweise sehr vollständige Bibliotheken bieten. Um die für sich oder sein Projekt ideale Sprache auszuwählen, sollte man immer auf die Webseite der jeweiligen Systeme vorbeischauen, um den aktuellen Stand selbst zu beurteilen.

4.1 ASpecT

ASpecT ist eine strikte funktionale Sprache, die an der Universität zu Bremen ursprünglich als Implementierung für algebraische Spezifikationen und abstrakte Datentypen entwickelt wurde. Das System wurde so benutzerfreundlich wie möglich entworfen, mit Überladefunktionalität und Quelltext-Debugger. Aus Effizienzgründen verwendet das System call-by-value und Referenzzähler für die Speicherverwaltung.

Im Laufe der Jahre wurden immer mehr Eigenschaften hinzugekommen, wie subsorting, functionals und eingeschränkte Polymorphie. Der ASpecT Compiler übersetzt den funktionalen Quelltext nach C, das mit normalen C compilern in schnelle und effiziente ausführbare Dateien übersetzt werden kann. ASpecT wurde unter anderem nach Sun3, Sun4, Dec VAX, IBM RS6000, NeXT, Apple A/UX, PC (OS/2, Linux), Amiga und Atare ST/TT portiert. Der ASpecT Compiler kann hier geladen werden:

http://www-rn.informatik.uni-bremen.de/home/ftp/tzi/BISS/agbkb/ASpecT/
Die aktuell wichtigste Anwendung von ASpecT ist das interaktive Graphen-Visualizierer-System daVinci. Version 2.0.x von September 1996 bestand aus 34.000 Zeilen ASpecT. 12.000 Zeilen C und 8.000 Zeilen Tcl/TK Quelltext. daVinci ist ein X11 programm, das es für Unix für Sun, HP, IBM, DEC, SGI und Intel PCs gibt. Mehr Information hier:
http://www.Informatik.Uni-Bremen.DE/~davinci.

4.2 Caml

Caml ist ein am INRIA entwickelter ML Sprachdialekt, der nicht ganz dem ML-Standard entspricht, aber dafür einige Erweiterungen im Bereich der Strukturierung durch seperate Compilierungen, Module und Objekte einführt. Es gibt zwei verschiedene Implementierungen:

Die ältere Implementierung, Caml Light, zeichnet sich durch die kleine Größe, wenig Speicherbedarf, einfache seperate Compilierung, ein C-Interface und portable Grafikfunktionen aus und läuft auf vielen Unix-Systemen, Macintosh und sogar alten 486'er Rechnern mit Windows 3.1.

Die neuere und umfangreichere Implementierung ist Objective Caml (früher unter Caml Special Light bekannt). Es hat folgende Neuerungen gebenüber Caml Light:

Objective Caml ist für Linux/Unix, MacOS X und Windows 95/98/NT/2K/XP verfügbar, mit Native-Compiler für Alpha, Sparc, Pentium, Mips, Power und HPPA. Hier gibt es beide Versionen und mehr Informationen (in englisch und französisch):

http://pauillac.inria.fr/caml/

In Objective Caml ist z.B. das P2P-Programm MLDonkey geschrieben.

4.3 Clean

Das Concurrent Clean System ist eine Prorgammierumgebung für die funktionale Sprache Concurrent Clean, die an der Universität Nijmegen in den Niederlanden entwickelt wurde. Das System ist zur Zeit eine der schnellsten Implementierungen einer funktionellen Sprache. Durch Verwendung des sogeannten "Uniqueness Typing" systems ist es möglich, rein funktionale interaktive Programme zu schreiben, einschließlich GUI-Anwendungen mit Fenstern, Menüs und Dialogen. Es ist auch möglich, Real-Life Anwendungen zu schreiben, die mit nicht-funktionalen Systemen zusammenarbeiten.

Mittlwerweile gibt es die Version 2 des Clean Systems, das eine ausgereifte funktionale Programmierumgebung bietet, mit unter anderem folgenden Eigenschaften:

Concurrent Clean gibt es für PCs (Micorsoft Windows, Linux), Macintosh (Motorla, PowerPC) und Sun4s (Solaris, SunOS):

http://www.cs.kun.nl/~clean.

Außerdem gibt es ein Buch mit Hintergrundinformationen und Beschreibung der Implementierung von Concurrent Clean:

"Functional programming and parallel graph rewriting", Rinus Plasmeijer and Marko van Eekelen, Addison Wesley, International Computer Science Series. ISBN 0-201-41663-8

4.4 Erlang

Erlang ist eine dynamisch getype, funktionale Programmiersprache mit Multithreading-Unterstützung, für große industrielle Echzeitsysteme. Die Eigenschaften von Erlang:

Erlang gibt es hier:

http://www.erlang.org/.

Im Erlang Paket sind einige Anwendungen mit kompletten Quelltext enthlaten, unter anderem:

Inets - HTTP 1.0 server und FTP client

Orber - CORBA v2.0 Object Request Broker (ORB)

ASN.1 - Compilierzeit und Laufzeit Paket für ASN.1

SNMP - erweiterbarer SNMP v1/v2 Agent und MIB Compiler

Mnesia - Verteilte Echtzeitdatenbank für Erlang

Mnemosyne - optionale Abfragesprache für Mnesia

Siehe auch:

"Concurrent programming in Erlang" (second edition), J. Armstrong, M. Williams, R. Virding, and Claes Wikström, Prentice Hall, 1996. ISBN 0-13-508301-X.

4.5 FP

FP ist eine seiteneffektfreie Sprache, die auf Kombinatoren aufbaut und hier beschrieben wird:

"Can programming be liberated from the von Neumann style?", John Backus, Communications of the ACM, 21, 8, pp.613-641, 1978.

Ein FP-Interpreter und -Compiler (nach C) gibt es hier:

ftp://gatekeeper.dec.com/pub/usenet/comp.sources.unix/volume13/funcproglang/
ftp://gatekeeper.dec.com/pub/usenet/comp.sources.unix/volume20/fpc/

Das Illinois FP System unterstützt eine geänderte Version von FP, die eine mehr Algol-artige Syntax und Struktur hat und in diesem Artikel beschrieben wird:

"The Illinois functional programming interpreter", Arch D. Robison, Proceedings of the SIGPLAN '87 Symposium on Interpreters and Interpretive Techniques, SIGPLAN notices, Volume 22, Number 7, July 1987.

4.6 Gofer

Das Gofer System stellt einen Interpreter für eine kleine Sprache zur Verfügung, die sehr auf dem aktuellen Haskell Report basiert. Insbesondere unterstützt Gofer Lazy Evaluation, Funktionen höherer Ordnung, polymorphe Typsysteme, Pattern-Matching, Überladung usw.

Gofer ist der Vorläufer vom Hugs-System, das noch mehr Kompatibilität zum Haskell Report bietet und zusätzliche Spracheigenschaften. Hier gibt es mehr Informationen dazu:

http://haskell.cs.yale.edu/hugs/

Hugs läuft auf vielen Systemen, darunter PCs, Ataris, Amigas, einige Unix-System usw.

Der Name Gofer ist abgeleitet von der Vorstellung, daß funktionale Sprachen GO(od) F(or) E(quational) R(easoning) sind und sollte nicht mit dem heutzutage kaum noch genutzten Internetdienst Gopher verwechselt werden.

4.7 Haskell

Mitte der 1980'er Jahre gab es noch keine "Standard", nicht-strikte, rein funktionale Programmiersprache. 1987 wurde ein Komitee zum Entwurf einer Sprache gegründet, das schließlich Haskell erfand. Zur Zeit ist Haskell 98 die aktuellste Version der Sprache. Mehr Informationen zur Sprache, verfügbaren Interpretern und Compilern, Mailingliste, dem Haskell Report usw., gibt es hier:

http://www.haskell.org/

http://www-i2.informatik.rwth-aachen.de/Forschung/FP/Haskell/

Eine Interpretersystem, das Haskell 98 unterstützt, ist Hugs.

4.8 Hope

Hope ist eine kleine, polymorph getype funktionale Sprache, die erstmals das Call-By-Pattern verwendetete. Ursprünglich war Hope eine strikte funktionale Sprache, aber mittlerweile gibt es Versionen mit Lazy Listen, Lazy Konstruktoren, aber strikten Funktionen. Mehr Informationen gibt es hier:

http://www.soi.city.ac.uk/~ross/Hope/.

4.9 Hugs

Hugs, das Haskell User's Gofer System, ist der Nachfolger von Gofer und gibt es hier:

http://www.haskell.org/hugs/

Hugs implementiert die Sprache Haskell.

4.10 Id

Id ist eine Datenfluss-Sprache, deren Kern eine nicht-strenge funktionale Sprache mit impliziter Parallelität ist. Es hat die üblichen Eigenschaften von funktionalen Sprachen, unter anderem ein type Hindley/Milner inference system, algebraische Typen und definitions with clauses, Pattern Matching und List Comprehensions.

4.11 J

J wurde von Ken Iverson und Roger Hui entwickelt und ist ähnlich wie APL, mit dem Unterschied, daß nur ASCII-Zeichen und keine Sonderzeichen verwendet werden. Dennoch ist die Schreibweise so gewählt, daß die Vorteile des speziellen Alphabeths von APL erhalten bleiben. J hat Eigenschaften und Kontrollstrukturen die über Standard-APL hinausgehen. Obwohl es als eine normale prozedurale Sprache verwendet werden kann, ist damit auch rein funktionale Prorgammierung möglich. Mehr Information über J gibt es hier:

http://www.jsoftware.com/

4.12 Miranda(TM)

Miranda wurde 1985/86 von David Turner mit dem Ziel entworfen, eine Standard nicht-strikte reine funktionale Sprache zu bieten und ist in den folgenden Artikeln beschrieben:

Miranda war die erste weit verbreitete Sprache mit nicht-strikter Semantik und polymorphen strengem Typing und wird an über 600 Orten eingesetzt, darunter 250 Universitäten. Es wird häufig im Zusammenhang mit dem Buch "Introduction to Functional Programming", von Bird und Wadler zu Lehrzwecken eingesetzt, das eine ähnliche Notation wie Miranda verwendet. Es hat auch einen starken Einfluss auf die weitere Entwicklung der funktionalen Programmiersprachen gehabt und war eine der wichtigste Quellen für den Entwurf von Haskell.

Das Miranda System ist ein kommerzielles Produkt von Research Software Limited. Die zweite Version von Miranda unterstützt beliebig genaue Integerberechnungen und hat ein Modulsystem mit der Möglichkeit zu parametrieiserbaren Modulen und einem eingebauten "make"-System. Der Compiler ist mit einem Editor integriert und re-compiliert Programme automatisch bei Änderungen. Es gibt auch ein Online Referenzhandbuch.

Mehr Information erhält man per eMail (englisch):

mira-request@ukc.ac.uk

oder per Post:

Research Software Ltd, 23 St Augustines Road, Canterbury CT1 1XP, ENGLAND. Phone: (+44) 227 471844, fax: (+44) 227 454458.

Miranda wurde eine Medaille für technische Ausführung vom British Computer Society (BCS Awards, 1990) verliehen. Das Wort "Miranda" ist ein eingetragenes Warenzeichen (TM) der Firma Research Software Limited. Es gibt keine freien Implementierungen von Miranda.

4.13 Mercury

Mercury ist eine logisch/funktionale Programmiersprache, die die Klarheit und Ausdrucksstärke deklarativen Programmierens mit fortgeschrittenen statischen Analysen und Fehlererkennung kombiniert. Es ist eine stark getypte Sprache, ein Modulsystem (mit getrennter Compiliermöglichkeit), ein mode system, unterstützt algebraische Datentypen, parametrisierbaren Polymorphismus, Funktionen höherer Ordnung und ein Folgerungssystem. All das mit dem Ziel, Programmierfehler zu vermeiden und nützliche Informationen für Programmierer und Compiler in der Sprache ausdrücken zu können.

Der Mercury Compiler ist in Mercury selbst geschrieben und compiliert nach C. Mercury ist für eine Reihe von Plattformen unter Unix und Microsoft-Systemn verfügbar.

Mehr Informationen gibt es hier:

http://www.cs.mu.oz.au/mercury.

4.14 ML

ML steht für Meta-Language (Meta-Sprache) und ist eine Familie von fortgeschrittenen Sprachen mit (üblicherweise) funktionalen Kontrollstrukturen, strikter Semantik, ein strikte polymorphes Typsystem und parametrisierbare Module. Die ML Sprachfamilie beinhaltet Standard ML, Lazy ML, Caml, Caml Light und verschiedene Forschungssprachen. Implementationen sind für verschiedene Plattformen verfügbar, darunter PCs, Großrechner, viele Workstatationmodelle, Mehrprozessorsysteme und Supercomputer. Tausende von Benutzern nutzen ML-Sprachen und es wird an vielen Universitäten Studenten beigebracht.

Es gibt eine moderierte Newsgroup für Diskussionen rund um ML: comp.lang.ml . Eine FAQ gibt es hier:

http://www.faqs.org/faqs/meta-lang-faq/

Eine formale Definition der Standard ML Sprache findet man hier:

Es gibt eine überarbeitet Version von Standard ML, manchmal "Standard ML '97" genannt, um es von der Originalversion von 1990 zu unterscheiden. In der neueren Version sind kleinere Sprachänderungen eingeflossen und eine runderneuterte und erweiterte SML Basislibrary. Mehr Information zu Standard ML '97 gibt es hier:

http://cm.bell-labs.com/cm/cs/what/smlnj/sml97.html.

4.15 NESL

NESL ist eine feingranulare, strikte funktionale Sprache, die an ML angelehnt ist. Sie beinhaltet eingebaute parallel Datentypen, Sequenzen und parallele Operationen auf Sequenzen. Sie unterstützt Polymorphie, Typinferenz und Funktionen höherer Ordnung mit Einschränkungen. Aktuell gibt es keine Unterstützung für Module und die Datentypdefinitionsmöglichkeiten sind begrenzt. Außer für Ein-/Ausgabeoperationen und einige System-Utilities ist die Sprache rein funktional.

Der NESL Compiler arbeitet mit verzögerter Compilierung und erstellt Code für jeden Typ, für den eine Funktion verwendet wird. Daher braucht die Implementation keine Type-Bits und kann enige wichtige Datenlayout-Optimierungen vorhnehmen (z.B. müssen doppeltgenaue Floatingpointzahlen nicht erst in ein Objekt verpackt werden und verschachtelte Sequenzen können effzient über mehrere Prozessoren verteilt werden). Einige Benchmark-Programme, die mit unregelmäßigen und/oder dynamischen Daten arbeiten (z.B. Graphen und dünnbesiedelte Matrizen) ist es vergleichbar schnell wie Fortran oder C.

Die aktuelle Implementierung von NESL läuft auf Workstations, den Connection Machines CM2 und CM5, der Cray Y-MP und MasPar MP2.

Hier gibt es mehr Informationen:

http://www.cs.cmu.edu/afs/cs.cmu.edu/project/scandal/public/www/nesl.html

4.16 OPAL

Die Sprache OPAL wurde als Testumgebung zum Entwickeln von funktionalen Programmiersprachen entworfen. Opal verwendet Konzepte der Algebraischen Spezifikation und der Funktionalen Programmierung, was zur formalen Entwicklung von großen Softwaresystemen mit Produktionsqualität führen soll, die in einem rein funktionalen Stil geschrieben sind. Der Kern von OPAL ist streng getypt, strikte Sprache ähnlich Hope und ML. Die algebraischen Eigenschaften zeigen sich im Aussehen der Syntax und der Bevorzugung von parametrisierten Polymorphismus.

Mit OPAL erforscht man hochoptimierende Compiler für funktionale Sprachen, was zu einem effizienten Code erzeugenden OPAL Compiler geführt hat. Der Compiler ist selbst in OPAL geschrieben und gibt es für SPARCs, DECstations, NeXTs und PCs unter Linux. Mehr Information gibt es hier:

http://www.uebb.cs.tu-berlin.de/~opal/

4.17 Oz / Mozart

Oz ist eine parallele Sprache, die Nebenbedingungen unterstützt und besonders gut für Anwendungen geeignet ist, die komplexe symbolische Berechnungen erfordern. Oz ist eine Mischung aus logischen Sprachen und funktionalen Sprachen. Die Nebenbedingunen beispielsweise findet man in logischen Sprachen. Hier ein Beispiel: Man definiert in einem Oz-Programm, daß x < y ist und y < 10, dann erkennt das System automatisch einen Widerspruch, wenn man versucht x = 11 zu definieren.

Oz war der Vorläufer vom aktuellen System, Mozart, zu dem es im Web mehr Informationen gibt:

http://www.mozart-oz.org/

4.18 Pizza

Pizza ist eine strikte Obermenge von Java, die drei funktionale Programmierparadigmen enthält:

Pizza zu Bytecode für die Java Virtual Machine compiliert, sodaß damit compilierte Klassen in jeder JVM laufen. Der Pizza Compiler ist selbst in Pizza geschrieben und da die Sprache eine Obermenge von Java ist, kann er auch als Ersatz zu Suns Java Compiler verwendet werden (mit dem Unterschied, daß der Pizza Compiler schneller ist).

Pizza wurde von Martin Odersky und Philip Wadler entworfen und von Odersky implementiert. Der Entwurf wurd in diesem Artikel beschrieben:

"Pizza into Java: translating theory into practice", Martin Odersky and Philip Wadler, 24th ACM Symposium on Principles of Programming Languages, Paris, January 1997.

Der Artikel, Downloads und weitere Informationen gibt es hier:

http://pizzacompiler.sourceforge.net/;

Pizza wurde von Gamelan als "cool" ausgezeichnet (http://www.gamelan.com).

4.19 Scheme

Scheme ist ein Lisp-Dialekt, der auf Wert auf konzeptionelle Eleganz und Einfachheit legt. Es ist in R5RS und im IEEE Standard 1178-1990 (R1995) spezifiziert. Die Spezifikation umfasst ca. 50 Seiten.

Interessant an der Sprache ist, daß sie formal über eine denotatielle Semantik (engl.: denotational semantics) im Sprachstandard definiert ist. Die Sprache ist extrem kompakt (wie jedes Lisp) und Continuations als Abstraktion der Programmausführung bietet sonst kaum eine Sprache.

Mehr Informationen gibt es im Web:

http://www.schemers.org/.

Es gibt eine moderierte Newsgroup für Diskussionen rund um Scheme: comp.lang.scheme

4.20 Sisal

Sisal, ein Akronym für Streams and Iteration in a Single Assignment Language, ist eine funktionale Sprache, die mit mehreren Zielen entworfen wurde:

Die Sisal Syntax ist modern und einfach zu lesen und sieht ähnlich wie Pascal, Modula oder Ada aus, mit modernen Konstruktionen und langen Bezeichnern. Der Hauptunterschied zwischen Sisal und herkömmlichen Sprachen besteht darin, daß man nicht explizit den Programmablauf beschreibt.

Die Sisal-Semantik ist mathematisch korrekt. Programme bestehen aus Funktionsdefinitionen und Aufrufen. Funktionen haben keine Seiteneffekte, haben nur explizit angegebene Argumente und liefern nur eindeutige Ergebnisse zurück. Es gibt keine veränderbaren Zustände in Sisal. Statt Variablen werden Bezeichner verwendet, um Werte zu bezeichnen statt Speicherzellen.

Die Sprache Sisal gibt es aktuell für einige Shared-Memory und Vector-Systeme und läuft unter Berkeley Unix(tm), einschließlich der Sequent Balance und Symmetry, der Alliant, der Cray X/MP und Y/MP, der Cray 2 und einigen weniger bekannten. Sisal ist auch für sequentiellen Systeme verfügbar, z.B. Sparc, RS/6000 und HP. Außerdem läuft es unter MS-DOS und Macintosh Unix (A/UX) und ist einfach auf andere System portierbar.

Mehr Informationen gibt es im Web:

http://tamanoir.ece.uci.edu/projects/sisal/sisal.html
http://sisal.sourceforge.net/

4.21 XSLT

XSLT ist der aus XSL (ursprünglich für XML Stylesheet Language) hervorgegangene Teil, der sich mit Transformationen (daher das T) von XML Strukturen beschäftigt. Auch wenn in XSLT Funktionen nicht als First-Class-Datatypen behandelt werden, kann es weitgehend als funktionale Programmiersprache angesehen werden, siehe auch The Functional Programming Language XSLT - A proof through examples.

5 Links

Dieser Abschnitt listet einige Internetresourcen zum Tehma funktionalen Programmierens auf.

5.1 Webseiten

5.2 Forschungsgruppen

5.3 Newsgroups

5.4 Literaturverzeichnis

5.5 Übersetzer und Pretty Printer

6 Glossar und Wörterbuch

strict / non-strict / lazy evaluation

Wird als Klassifizierung für funktionale Sprachen verwendet. Eine funktionale Sprache ist strikt, wenn alle Argumente einer Funktion vor Aufruf der Funktion ausgewertet werden. Gegenteil: non-strict: Die Argumente werden erst bei Bedarf ausgewertet. Wird meist per Lazy-Evaluation, auch träge oder verzögerte Auswertung genannt, implementiert. Bei Lazy-Evaluation wird ein Wert erst berechnet, wenn er vom Programm gebraucht wird und für weitere Abfragen gespeichert. Siehe auch 3.5 Strikte Auswertung.

Denotatielle Semantik (engl.: denotational semantics)

Eine gute englischsprachige Erklärung findet man bei Wikipedia: http://en.wikipedia.org/wiki/Denotational_semantics.

Endrekursion (engl: tail recursion)

Zitat http://de.wikipedia.org/wiki/Endrekursion: Eine rekursive Funktion ist endrekursiv, wenn der rekursive Funktionsaufruf nur am Anfang (head recursion) oder nur am Ende (tail recursion) innerhalb der Funktion benutzt wird. Die Rekursion kann in diesem Fall als eine Iteration aufgelöst werden.

Continuations

Eine kurze englischsprachige Erklärung: http://en.wikipedia.org/wiki/Continuation_passing_style. Bleibt noch zu ergänzen, daß man sich eine Continuation als eingefrorenen Stack vorstellen kann, gegenüber einer Closure, die nur ein eingefrorener Variablencontext ist.

First-Class-Value

TODO: kurze Erklärung, deutscher Begriff

Closure

http://en.wikipedia.org/wiki/Closure_%28computer_science%29

Denotator

TODO: kurze Erklärung, deutscher Begriff

Valid HTML 4.0!