Church-Kodierung
Unter Church-Kodierung versteht man die Einbettung von Daten und Operatoren in den Lambda-Kalkül. Die bekannteste Form sind die Church-Numerale, welche die natürlichen Zahlen repräsentieren. Benannt sind sie nach Alonzo Church, der Daten als Erster auf diese Weise modellierte.
Church-Numerale
Definition
Die Grundidee zur Kodierung beruht auf den Peano-Axiomen, wonach die natürlichen Zahlen durch einen Startwert – die 0 – und einer Nachfolger-Funktion definiert sind. Demnach sind die Church-Numerale wie folgt definiert:
- 0 ≡
λf.λx. x - 1 ≡
λf.λx. f x - 2 ≡
λf.λx. f (f x) - 3 ≡
λf.λx. f (f (f x)) - ...
- n ≡
λf.λx. fn x
Rechnen mit Church-Numeralen
Im Lambda-Kalkül sind arithmetische Funktionen durch korrespondierende Funktionen über Church-Numerale darstellbar. Diese Funktionen können in funktionalen Programmiersprachen direkt durch Übertragen der Lambda-Ausdrücke implementiert werden.
Die Nachfolger-Funktion wird wie folgt definiert:
- succ ≡
λn.λf.λx. f (n f x)
Die Addition zweier Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} ist die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} -malige Anwendung der Nachfolger-Funktion auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} :
- plus ≡
λm.λn.λf.λx. m f (n f x)
Die Multiplikation zweier Zahlen und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} ist die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} -malige Anwendung der Addition Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (+n)} auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} :
- mult ≡
λm.λn.λf.λx. m (n f) x
Die Vorgänger-Funktion:
- pred ≡
λn.λf.λx. n (λg.λh. h (g f)) (λu. x) (λu. u)
Boolesche Ausdrücke
Analog zu den natürlichen Zahlen lassen sich auch (zweiwertige) Wahrheitswerte im Lambda-Kalkül modellieren.
- true ≡
λx.λy. x - false ≡
λx.λy. y
Daraus lässt sich auch eine einfache Kontrollstruktur (IF THEN ELSE) ableiten:
- ifthenelse ≡
λb.λx.λy.b x y
Dabei ist die Variable Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} als Bedingung zu verstehen, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} als „THEN“ und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y} als „ELSE“.
