FP

Ein Beispiel für eine streng funktionale Programmiersprache ist FP (J. Backus "Can programming be liberated from the von-Neumann style?", Comm. ACM 21(1978,8) 613ff). Ein FP-System besteht aus

• einer Menge σ von Objekten,
• einer Menge F von Basisfunktionen,
• einer Menge FF von Funktionalen und optional
• einer Menge von Definitionen und
• einer Menge von Applikationen.

Die Menge σ der Objekte ergibt sich durch die folgende rekursive Definition aus der Menge A der Atome:

• Alle Atome sind Objekte.
• ⊥ (undefiniert) ist ein Objekt, aber kein Atom.
• Jede Sequenz <x1, x2, ...xn> von Objekten xi ∈ σ \ ⊥ ist ein Objekt.
• Die leere Sequenz ∅, T (true) und F (false) sind Atome und Objekte.

Die Menge F der Funktionen ist abhängig von der Wahl der Menge A der Atome. Wählt man A als die Menge der natürlichen Zahlen vereinigt mit {∅, T, F} ist folgende Menge F sinnvoll:

identische Funktion
id

arithmetische Grundfunktionen
+, -, *, /

Vergleichsoperatoren
=, >, >=, ...

Boolesche Operatoren
and, or, not

Selektionsfunktionen für Sequenzen
1, 2, 3, ...

Erstes und weitere Elemente einer Sequenz
hd, tl

Prüfung auf leere Sequenz, Atom
null, atom

Spezielle Funktionen für Sequenzen
distl, distr

Zu Beschreibung der Wirkung der Funktionale wird die Notation f : x für die Anwendung der Funktion f auf das Argument x verwendet. Die Menge der Funktionale FF ist fest vorgegeben:

Komposition
f o g : x = f : (g : x)

Konstruktion
[f1, ..., fk] : x = <f1 : x, ..., fk : x>

Alternative
(f → g; h) : x = if f : x then g : x else h : x

Konstanten
x : y = x, falls y <> ⊥

insert
/f : <x> = x
/f : <x1, x2, ..., xn> = f : <x1, /f : <x2, ..., xn>>
\f : <x> = x
\f : <x1, x2, ..., xn> = f : < \f : <x1, x2, ..., xn-1>, xn>

apply
α f : <x1, x2, ..., xn> = <f : x1, f : x2, ..., f : xn>


Beispiel

Die Länge einer Sequenz kann mit der Funktion len

len = null → 0; (/ +) o (α 1)

ermittelt werden. Es ist

len : <a, b, c>

die Definition von len wird eingesetzt

= null → 0; (/ +) o (α 1) : <a, b, c>

da <a, b, c> nicht die leere Sequenz ist

= (/ +) o (α 1) : <a, b, c>

nach der Definition der Komposition

= (/ +) : ((α 1) : <a, b, c>)

nach der Definition von apply

= (/ +) : <1 : a, 1 : b, 1 : c>

nach der Definition für konstante Funktionen

= (/ +) : <1, 1, 1>

Regel für /

 = + : <1, /+ : <1, 1>>
 = + : <1, + : <1, /+ : <1>>>
 = + : <1, + : <1, 1>>

Rechenregel für +

 = 3