λ
|
Die Assembler-Sprache der funktionalen Programmierung
|
|
Das mathematische Fundament der funktionalen Programmierung
|
| |
Geschichte
|
|
19[12][0-9]
|
Moses Schönfinkel, Haskell Curry Kombinatorische Logik
|
193[0-9]
|
Alonzo Church, Stephen Kleene λ-Kalkül
|
| |
Sprachelemente
|
Expr ::= a
| (Expr Expr)
| λ a . Expr
|
|
Dieses ist das minimale, uninterpretierte λ-Kalkül
Es gibt nur Variablen, einstellige anonyme Funktionen und Funktionsanwendungen
|
| |
Häufige Erweiterung
|
| Literal
| (Expr Op Expr)
| if Expr then Expr
else Expr
| let a = Expr
in Expr
| fix Expr
|
| |
Beispiel
|
|
| |
|
x ist eine gebundene Variablen in e
|
|
y ist eine freie Variablen in e
|
| |
Definitionen
|
|
offener Term open term
|
ein Ausdruck mit freien Variablen
|
abgeschlossener Term closed term
|
ein Ausdruck ohne freie Variablen
|
Kombinator
|
ein abgeschlossener Term
|
| |
Beispiele
|
λx.x
(λx.(x ((λy.y a) x))) y
|
|
Gebundene Variablen können umbenannt werden, ohne die Bedeutung
eines Ausdrucks zu ändern
|
|
Dieses gilt nicht für jede mögliche Umbenennung!
|
?
|
Beispiel?
|
|
|
in Haskell
|
data Expr
= Var Ident
| App Expr Expr
| Lambda Ident Expr
| ...
type Ident = String
|
| |
?
|
Berechnung aller freien Variablen?
|
|
fv :: Expr -> Set Ident
fv (Var i) = {i}
fv (App e1 e2) = fv e1 ∪ fv e2
fv (Lambda i e) = fv e \\ {i}
|
?
|
Berechnung aller gebundenen Variablen?
|
|
bv :: Expr -> Set Ident
bv (Var i) = {}
bv (App e1 e2) = bv e1 ∪ bv e2
bv (Lambda i e) = bv e ∪ {i}
|
?
|
Wo kommen in der Mathematik noch gebundene Variablen vor?
|
|
Quantoren, Summe, Produkt, Integral, ...
|