Loading AI tools
Programmiersprache Aus Wikipedia, der freien Enzyklopädie
Der Begriff Functional Programming System (abgekürzt FP-System) bezeichnet ein von John W. Backus entwickeltes Konzept funktionaler Programmiersprachen.[1] Backus ging dabei von der Beobachtung aus, dass gängige Programmiersprachen Computerprogramme als ein kleinteilige serialisierte Datenmanipulation darstellen, da sie gedanklich vom von-Neumann'schen Maschinenmodell ausgehen. Daraus resultieren laut Backus zwei Probleme. Zum einen, dass von-Neumann-Programme schwer parallelisierbar sind. Zum anderen, dass es schwer ist, über die Eigenschaften von Von-Neumann-Programmen formal zu argumentieren oder sie zu transformieren. Das Functional Programming System adressiert diese Probleme durch Konstruktion eines Programms aus einer Komposition . Dabei werden größere Mengen strukturierter Daten von einer Funktion zur nächsten weiter gereicht, was technisch eine Parallelisierung der Verarbeitung ermöglicht. Backus zog auch in Betracht, diese Arbeitsweise zur Grundlage einer neuen Computerarchitektur zu machen, die diese Möglichkeit ausnutzt.
In einer Rede anlässlich der Verleihung des Turing Awards an Backus im Jahr 1977 stellte dieser die Idee von FP-Systemen vor. Der Vortragstitel lautete: Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs.[2] In einem weiteren Aufsatz legte sich Backus auf den Begriff Function-Level Programming fest.[3]
Backus gibt mit der Berechnung des Skalarprodukts ein instruktives Beispiel für die Anwendung des Functional Programming System.
Die Funktion („Inner Product“), die das Skalarprodukt zweier Vektoren bestimmt, ist zusammengesetzt aus der verketteten Berechnung der drei Funktionen und (in dieser Reihenfolge), was wie folgt als Funktionskomposition ausgedrückt wird:
Dabei ist eine Funktion, die eine Matrix transponiert. Dieser Zusammenhang wird in FP beispielsweise für eine Matrix so notiert:
Die Symbole und bezeichnen Funktionale. Diese übernehmen andere Funktionen um neue Funktionen zu bilden. In der Form übernimmt die zweistellige Multiplikationsfunktion und liefert eine Funktion, die auf alle Elemente einer übergebenen Liste von Paaren anwendet. Das Berechnungsergebnis ist dann die Liste der einzelnen Produkte. In modernen Programmiersprachen heißt das Funktional meistens map
. Backus nennt sie auch ApplyToAll
.
Die Funktion schließlich entspricht grob der Funktion reduce
oder fold
in üblicher funktionaler Programmierung. Backus nennt sie Insert
und meint damit, dass der Ausdruck eine Funktion darstellt, die in einer übergebenen Liste die Operation zwischen je zwei Elemente einfügt. Es gilt also
.
Die Berechnung der Skalarprodukt-Funktion angewendet auf die beiden Vektoren und kann dann so verstanden werden:
Der Rechenprozess stellt also eine Verarbeitungspipeline ohne inneren Zustand dar, der die Eingabe in drei getrennten Arbeitsschritten in die Ausgabe überführt. Die Arbeitsschritte selbst können für sich in unterschiedlichem Grad parallelisiert werden. Auch die Erstellung einer Hardware-Pipeline für das Programm wäre möglich.
Backus verwendet eine lose an mathematische Konventionen angelehnte Notation und ergänzt diese um McCarthy'sche bedingte Ausdrücke sowie eine rekursive Darstellung für WHILE-Schleifen. Entscheidend ist, dass jede Entität eine Funktion darstellt und damit mit dem Kompositionsoperator verträglich ist.
Die Vektorprogrammiersprache APL hatte einen entscheidenden Einfluss auf das Combinator based functional programming system von John Backus, das ohne Lambda-Variablenliste auskommt; stattdessen werden Selektoren (Zahlen) für das Herauspicken von Werten aus einer Sequenz verwendet.
1:<x1,…,xn> → x1 i:<x1,…,xi,…,xn> → xi
Combining … | … Form | |
---|---|---|
Applikation | f : x | = f(x) |
Komposition | (f o g) : x | = f(g(x)) |
Konstruktion | [ f1 , f2 , … , fn ] : x | = < f1:x , f2:x , … , fn:x > |
Kondition | (p → f ; g) : x | = wenn p:x = T dann f:x sonst wenn p:x = F dann g:x sonst ⊥ |
Konstante | ~x : y | = wenn y = ⊥ dann ⊥ sonst x |
Insert | (/ f) : <x1 , x2 , … , xn> | = f:<x1 , f:<x2 , … f:<xn-1 , xn>>> |
Apply to All | (α f) : <x1 , x2 , … , xn> | = < f:x1 , f:x2 , … , f:xn > |
Binary to Unary | bu f x | |
While-Schleife | (while p f) : x | = wenn p:x = T dann (while p f):(f:x) sonst wenn p:x = F dann x sonst ⊥ |
und die Definition von monadischen Funktionen:
Def Name ≡ Term
Mit ⊥ meinte Backus den Wert „Bottom“, ein Wert wie „undefiniert“ oder „Ausnahme“. T und F sind die Werte für „wahr“ und „falsch“.
Ein Team aus John Backus, John Williams und Edward Wimmers entwickelte 1989 am IBM Almaden Research Center den Nachfolger FL (Function-Level Programming). Mit diesem Konzept soll man Programme umstellen können so bequem wie man in der Mathematik Gleichungen umstellen kann, dazu musste referenzielle Transparenz gewährleistet sein. Das soll einer neuen Dimension von Programmoptimierung dienen (EFL). Backus wollte mit FL aus der „damaligen Informatik“ eine Ingenieurs-Disziplin machen. Wiederum einige Weiterentwicklungen von FL sind J (Einsatzgebiet wie APL) und PLaSM, eine Programmiersprache für Geometrie.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.