FP (Programmiersprache) - FP (programming language)

FP
Paradigma Funktionsebene
Entworfen von John Backus
Erstmals erschienen 1977
Dialekte
FP84
Beeinflusst von
APL
Beeinflusst
FL , Haskell

FP (kurz für Functional Programming ) ist eine Programmiersprache, die von John Backus entwickelt wurde , um das Programmierparadigma auf Funktionsebene zu unterstützen . Es ermöglicht das Erstellen von Programmen aus einer Reihe allgemein nützlicher Grundelemente und das Vermeiden benannter Variablen (ein Stil, der auch als stillschweigende Programmierung oder "punktfrei" bezeichnet wird). Es wurde stark von APL beeinflusst, das Anfang der 1960er Jahre von Kenneth E. Iverson entwickelt wurde .

Die FP-Sprache wurde 1977 in Backus ' Turing Award- Artikel "Kann Programmierung vom von Neumann-Stil befreit werden?" Mit dem Untertitel "Ein funktionaler Stil und seine Programmalgebra" eingeführt. Das Papier weckte das Interesse an funktionaler Programmierforschung und führte schließlich zu modernen funktionalen Sprachen (die größtenteils auf dem Lambda-Kalkül- Paradigma beruhen ) und nicht auf dem von Backus erhofften Paradigma auf Funktionsebene. In seinem Turing Award Paper beschrieb Backus, wie sich der FP-Stil unterscheidet:

Ein FP-System basiert auf der Verwendung eines festen Satzes von Kombinationsformen, die als funktionale Formen bezeichnet werden. Diese und einfache Definitionen sind die einzigen Mittel, um aus bestehenden Funktionen neue Funktionen zu erstellen. Sie verwenden keine Variablen oder Substitutionsregeln und werden zu Operationen einer zugehörigen Algebra von Programmen. Alle Funktionen eines FP-Systems sind von einem Typ: Sie ordnen Objekte Objekten zu und verwenden immer ein einziges Argument.

FP selbst fand außerhalb der Wissenschaft nie viel Verwendung. In den 1980er Jahren schuf Backus eine Nachfolgesprache, FL , die ein internes Projekt bei IBM Research war.

Überblick

Die Werte , die FP-Programme ineinander abbilden, umfassen eine Menge, die bei der Sequenzbildung geschlossen wird : 

if x1,...,xn are values, then the sequence 〈x1,...,xn〉 is also a value

Diese Werte können aus einer beliebigen Menge von Atomen erstellt werden: Boolesche Werte, Ganzzahlen, Realzahlen, Zeichen usw.: 

boolean   : {T, F}
integer   : {0,1,2,...,∞}
character : {'a','b','c',...}
symbol    : {x,y,...}

⊥ ist der undefinierte Wert oder der untere Wert . Sequenzen sind bodenschonend : 

〈x1,...,⊥,...,xn〉  =  ⊥

FP-Programme sind Funktionen f , die jeweils einen einzelnen Wert x einem anderen zuordnen: 

f:x represents the value that results from applying the function f 
    to the value x

Funktionen sind entweder primitiv (dh mit der FP-Umgebung bereitgestellt) oder werden durch programmbildende Operationen (auch als Funktionale bezeichnet ) aus den Grundelementen erstellt .

Ein Beispiel für eine primitive Funktion ist die Konstante , die einen Wert x in die Funktion x̄ mit konstantem Wert umwandelt . Funktionen sind streng : 

f:⊥ = ⊥

Ein weiteres Beispiel für eine primitive Funktion ist die mit 1 , 2 , ... bezeichnete Selektorfunktionsfamilie , wobei: 

i:〈x1,...,xn〉  =  xi  if  1 ≤ i ≤ n
              =  ⊥   otherwise

Funktionen

Im Gegensatz zu primitiven Funktionen arbeiten Funktionale mit anderen Funktionen. Beispielsweise haben einige Funktionen einen Einheitswert , z. B. 0 für die Addition und 1 für die Multiplikation . Die funktionelle Einheit erzeugt ein solcher Wert , wenn sie einer angelegten Funktion f , die man hat: 

unit +   =  0
unit ×   =  1
unit foo =  ⊥

Dies sind die Kernfunktionen von FP: 

composition  f∘g        where    f∘g:x = f:(g:x)

construction [f1,...,fn] where   [f1,...,fn]:x =  〈f1:x,...,fn:x〉

condition (h ⇒ f;g)    where   (h ⇒ f;g):x   =  f:x   if   h:x  =  T
                                             =  g:x   if   h:x  =  F
                                             =  ⊥    otherwise

apply-to-all  αf       where   αf:〈x1,...,xn〉  = 〈f:x1,...,f:xn〉

insert-right  /f       where   /f:〈x〉             =  x
                       and     /f:〈x1,x2,...,xn〉  =  f:〈x1,/f:〈x2,...,xn〉〉
                       and     /f:〈 〉             =  unit f

insert-left  \f       where   \f:〈x〉             =  x
                      and     \f:〈x1,x2,...,xn〉  =  f:〈\f:〈x1,...,xn-1〉,xn〉
                      and     \f:〈 〉             =  unit f

Gleichungsfunktionen

Zusätzlich dazu, dass eine Funktion durch Funktionale aus Primitiven konstruiert wird, kann eine Funktion rekursiv durch eine Gleichung definiert werden, wobei die einfachste Art ist: 

f ≡ Ef

Dabei ist E f ein Ausdruck, der aus Primitiven, anderen definierten Funktionen und dem Funktionssymbol f selbst unter Verwendung von Funktionalen aufgebaut ist.

FP84

FP84 ist eine Erweiterung von FP um unendliche Sequenzen , vom Programmierer definierte Kombinationsformen (analog zu denen, die Backus selbst zu FL , seinem Nachfolger von FP, hinzugefügt hat ) und eine verzögerte Auswertung . Im Gegensatz zu FFP, einer anderen von Backus 'eigenen Variationen von FP, unterscheidet FP84 klar zwischen Objekten und Funktionen: Das heißt, letztere werden nicht mehr durch Sequenzen der ersteren dargestellt. Die Erweiterungen von FP84 werden erreicht, indem die FP-Einschränkung aufgehoben wird, dass die Sequenzkonstruktion nur auf Nicht- Objekte angewendet werden darf: In FP84 wird das gesamte Universum von Ausdrücken (einschließlich derer, deren Bedeutung ⊥ ist) während der Sequenzkonstruktion geschlossen .

Die Semantik von FP84 ist in einer zugrunde liegenden Algebra von Programmen enthalten, einer Reihe von Gleichungen auf Funktionsebene , die zum Manipulieren und Überlegen von Programmen verwendet werden können.

Verweise

  • Einfachheit der Einfachheit halber opfern: Wo ziehen Sie die Grenze? John H. Williams und Edward L. Wimmers, IBM Almaden Research Center, Tagungsband des fünfzehnten jährlichen ACM SIGACT-SIGPLAN-Symposiums über Prinzipien von Programmiersprachen, San Diego, CA, Januar 1988.

Externe Links