FP-System

Dieser Artikel wurde aufgrund von inhaltlichen Mängeln auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen und beteilige dich an der Diskussion! (+)
Begründung: Artikel besteht hauptsächlich aus nicht erklärten Beispielen und Weblinks. Die wenigen Textabsätze lassen kein Konzept erkennen. --Raphael Kirchner 15:31, 20. Nov. 2010 (CET)

FP-System (Functional Programming System) bezeichnet ein von John Backus entwickeltes Konzept funktionaler Programmiersprachen.^[1]

In einer Rede anlässlich der Verleihung des Turing Awards an John 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]

Zahlen als Selektoren

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

Feste Anzahl von Kombinatoren / Funktionalen Formen

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“.

Funktionales Programm für das Innere Produkt mit Kombinatoren

Def IP = (/ +) o (α ×) o Trans

IP : <<1,2,3>,<6,5,4>>
= (/ +) o (α ×) o trans : <<1,2,3>,<6,5,4>>
= (/ +) o (α ×) : (trans : <<1,2,3>,<6,5,4>>)
= (/ +) : ((α ×) : <<1,6>,<2,5>,<3,4>>)
= (/ +) : <×:<1,6>,×:<2,5>,×:<3,4>>
= (/ +) : <6,10,12>
= +:<6,+:<10,12>>
= 28

Weiterentwicklung von FP-Systemen

Ein Team aus John Backus, John Williams und Edward Wimmers entwickelten 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 eine referentielle 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.

FP-Implementierungen

• INTERACTIVE FP^[4], Hilfeseite^[5] dazu
• FP-Compiler^[6], der sich selbst nach C compiliert
• Fp Interpreter in Lisp^[7]
• PLaSM (Programming Language for Solid Modeling), eine funktionale Programmiersprache für die Anwendung im CAD, die an der Roma Tre University entwickelt wird.^[8]

Literatur

• Wolfram-Manfred Lippe: Funktionale und Applikative Programmierung: Grundlagen, Sprachen, Implementierungstechniken. 1. Auflage. Springer, Berlin 2009, ISBN 978-3540890911 (Google Books).
• Alberto Paoluzzi e.a.: Geometric Programming for Computer-Aided Design. 1. Auflage. Wiley, Chichester 2003, ISBN 978-0471899426 (Google Books).

Siehe auch

• Algebraische Programmiersprache

Einzelnachweise

1. ↑ Lippe 2009, S. 73
2. ↑ Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs Stanford University, 1978 (PDF-Datei; 2,87 MB)
3. ↑ Function Level Programs as Mathematical Objects (PDF-Datei)
4. ↑ INTERACTIVE FP
5. ↑ INTERACTVE FP - Help
6. ↑ Furry Paws, ein FP-Compiler (englisch)
7. ↑ fp-interpreter-in-lisp
8. ↑ PLaSM functional language for computing with geometry. Alberto Paoluzzi (Universität Rom III), abgerufen am 27. November 2010. 

Weblinks

• Kritik am Backus-Aufsatz von Edsger W. Dijkstra (PDF-Datei; 143 kB)
• John Backus: Function Level Programming and the FL Language, 1987 (Video)
• The FL Project: Design of a Functional Language (PDF-Datei)
• FP (englisch)
• Skripts to FP-Systems