Gibt es eine einfach typisierte kombinatorische Logik, da es einen untypisierten Lambda-Kalkül und einen einfach typisierten Lambda-Kalkül gibt (wie zum Beispiel in Benjamin Pierces Buch Types and Programming Languages beschrieben)?
Zum Beispiel scheinen natürliche Typen für die Kombinatoren S, K und ich zu sein
S : (a -> b -> c) -> (a -> b) -> a -> c
K : a -> b -> a
I : a -> a
Dabei sind a, b und c Typvariablen, die sich über eine Reihe von Typen T erstrecken. Nun könnten wir vielleicht mit einem einzelnen Basistyp beginnen, Bool. Unsere Menge von Typen T ist dann Bool zusammen mit allen Typen, die unter Verwendung der drei Muster gebildet werden können
(a -> b -> c) -> (a -> b) -> a -> c
a -> b -> a
a -> a
wo a, b, c in T.
Es würde zwei neue Konstanten in der Sprache geben.
T : Bool
F : Bool
Diese Sprache besteht also aus den Symbolen S, K, I, T und F zusammen mit Klammern. Es hat einen Basistyp Bool und die "Funktionstypen", die aus den Kombinatormustern S, K und I erstellt werden können.
Kann dieses System zum Laufen gebracht werden? Gibt es zum Beispiel eine gut typisierte Wenn-Dann-Sonst-Konstruktion, die nur aus S, K, I, T, F gebildet werden kann?
quelle
Antworten:
Kurze Anmerkung, erlaube ich parametrischen Polymorphismus (System F) in diesem System , so dass
S
,K
undI
kann alle Arten arbeitet über.Beachten Sie, dass wir ohne Pattern Matching nicht schreiben können,
if
egal was wir tun. Wir haben absolut keine Operationen mit Booleschen Werten. Es gibt keine Möglichkeit zu unterscheidenTrue
vonFalse
. Versuchen Sie es stattdessenLassen wir es
Bool = a -> a -> a
zur Klarheit.Jetzt geht es nur noch darum, einige Lambda-Kalkülausdrücke für Kombinatoren zu kompilieren, was ziemlich trivial ist.
quelle