|
Funktionale Sprachen sind charakterisiert durch:
- Programm:
- Ausdrücke (Formeln) ohne Speicherplatzbezeichner (Variablen), d.h. im funktionalen Stil also Funktionsdefinitionen.
- Berechnung:
- Transformation von Formeln bzw. Termen, wobei Methoden der Unifikation, des Pattern Matching und der Substitution angewandt werden. Der Lambda-Kalkül dient als abstraktes funktionales Berechnungsmodell, konkret werden Term- und Graphreduktionssysteme benutzt.
- Semantik:
- operational als Auswertungsmechnismus des Programms, denotational als Beschreibung von Objekten über semantischen Bereichen und deklarativ als Anwendung von Ableitungsregeln.
- Werte:
- unstrukturierte Elementarobjekte und mit Hilfe von Konstruktoren gebildete strukturierte Objekte. Wertbereiche dieser Objekte sind Ordnungsstrukturen. Existenz von Fixpunkten rekursiver Gleichungen.
Sprachen
LISP (McCarthy 1960)
- Listen als Basisstruktur
- Bedingte Ausdrücke als Programme und Daten
- Imperative Anteile
Die erste Funktionale Sprache LISP (LIST PROCESSING) wurde Anfang der 60er Jahre von John McCarthy entwickelt. LISP war die erste Sprache, die weit von den Prinzipien der damaligen, durch die Sprache FORTRAN geprägten Programmierung abwich. Eine der bedeutendsten Ansprachen für die funktionale Programmierung und gegen den imperativen Programmierstil hielt John Backus 1977 anläálich der Verleihung des "Turing Award" an ihn. Er machte die imperative Programmierung für die Software-Krise verantwortlich und schlug als Alternative eine funktionale Sprache vor.
FP (Backus 1078)
- Variablenfreie Ausdrücke
- Polymorphes Typkonzept
- Nutzerdefinierte Datenstrukturen
- Pattern Matching
Miranda (Turner 1985)
- Bedingt rekursive Gleichungen
- Nutzerdefinierte Funktionale
Als Resultat einer Folge von Sprachentwicklungen stellte er 1985 Miranda vor. Miranda zeichnet sich durch die Verwendung von bedingten rekursiven Gleichungen zur Definitionen von Funktionen und Funktionen höherer Ordnung aus.
Haskell (Hudak 1989)
- Vollständige formale Semantik
Gegenüberstellung der konventionellen und funktionalen Sprachen
Das Spektrum der Programmiersprachen erstreckt sich von dem imperativen Programmiersprachen, in denen Programme im wesentlichen Abfolgen von Befehlen an Rechner beschreiben, bis zu den funktionalen Programmiersprachen, in denen Programme eher Problembeschreibungen als Ausführungsanweisungen an einem Rechner sind. In den imperativen Sprachen, zu denen Sprachen wie FORTRAN, PASCAL etc. zählen, beschreiben Programme Berechnungen als Serie von lokalen Speichertransformationen eines von Neumann Rechners. Beispielsweise bewirkt die Wertzuweisung X:= X+3 die lokale Modifikation des Inhaltes der Speicherzelle, die der Variablen X zugeordnet ist. Die Programmierung erfolgt rechnernah, was auf die evolutionäre Entwicklung dieser Sprachen aus rechnernahen zurückzuführen ist. Also ist ein Programm in der imperativen Programmiersprache eine Arbeitsanweisung für eine Maschine. Was das Programm tut, hängt vom Zustand der Maschine ab. Diese ändert sich im Laufe der Zeit an die der Programmierer denken muß, wenn er sein Programm verstehen will. Funktionale Programmiersprachen wie LISP, MIRANDA etc. zeichnen sich demgegenüber dadurch aus, daß sie auf einer rein mathematischen Theorie fundieren. Die Programmierung erfolgt in diesen Sprachen rechnerunabhängig auf einem höheren Abstraktionsniveau. In der funktionalen Programmiersprachen ist ein Programm eine Ein-/ Ausgaberelation, d.h., sie ist eine Abbildung von Eingabedaten auf zugehörige Ausgabedaten. Das in der funktionalen Programmiersprache geschriebene Programm liefert zu jedem Zeitpunkt ein und das selbe Ergebnis und ist somit "zeitlos".
Der Kernunterschied zwischen imperativen und funktionalen Programmiersprachen ist, wie der Name schon sagt, daß in den funktionalen Programmiersprachen jedes Programm eine Funktion darstellt. Dies ist auch der Ansatz von John Backus. Er versieht diese "Funktionswelt" mit einer assoziierten Algebra, d.h.: Funktionale, Funktionen und ihre Verknüpfungen genügen gewissen einfachen mathematischen Rechenregeln. Auf diese Art wird das Verhalten eines Programms ohne Bezug auf die Maschine mathematisch analysierbar. Diese Vorstellung von John Backus kommt unserer Ansicht nach in den in der Folgezeit entwickelten funktionalen Sprachen nur wenig zur Geltung. Die funktionalen Programmiersprachen sind wenig populär. Die auch relativ neu entwickelten objektorientierten Programmiersprachen, wie zum Beispiel C++, JAVA stehen zur Zeit sehr im Trend. Der Grund dafür liegt unserer Meinung nach in dem hohen, abstrakten, mathematischen Niveau, auf dem die funktionalen Programmiersprachen formuliert sind, was wir auch beim Lesen des Textes von John Backus feststellen konnten.
Kernvorstellung
- Referentielle Transparenz:
- Der Wert eines Ausdruckes hängt nur von seiner Umgebung und nicht vom Ausführungszeitpunkt ab. Ein Ausdruck kann überall durch einen wertgleichen Ausdruck ersetzt werden (Substitutionsprinzip). Es existieren keine Seiteneffekte, wie sie bei imperativen Sprachen durch Änderungen von Speicherbelegungen entstehen können.
- Reduktionsprinzip:
- Ersetzung einer Funktionsapplikation durch die definierende Seite unter Anwendung von Parametersubstitution.
- Determiniertheit:
- Jede Applikation eines Funktionssymbols hat höchstens ein Ergebnis, welches durch eine Folge von Ersetzungsschritten hergeleitet wird.
- Parallelität:
- Nebenläufige Auswertbarkeit unabhängiger Funktionsapplikationen in einem Ausdruck (Programm).
- Objektstrukturen:
- Funktionale (Funktionen höherer Ordnung), polymorphe Typen (Typzuordnung unabhängig von der Art der Argumente), unendliche Datenstrukturen. Implementierungsansätze, die funktionale Sprachen mittels virtueller Maschine auf zumeist imperativen Rechnerarchitekturen umsetzen, sind z.B. die SECD-Maschine (Landin 64), die Stack- Maschine, die G-Maschine (Johnson 80), Graphreduktion u. a.
|