Gibt es eine typisierte SKI-Rechnung?

Die meisten von uns kennen die Entsprechung zwischen kombinatorischer Logik und Lambda-Rechnung . Aber ich habe noch nie das Äquivalent von "typisierten Kombinatoren" gesehen (vielleicht habe ich nicht tief genug geschaut), das dem einfach typisierten Lambda-Kalkül entspricht. Gibt es so etwas? Wo kann man sich darüber informieren?

reference-request logic lambda-calculus type-theory combinatory-logic Hugo Sereno Ferreira
quelle

Das könnte Sie auch interessieren: The Reader Monad und Abstraction Elimination in The Monad.Reader, Ausgabe 17 . Die Reader-Monade (oder genauer gesagt der anwendbare Funktor) ist eng mit dem typisierten SKI verwandt.

Petr Pudlák

Antworten:

Die ausdrucksstarke Vollständigkeit der typisierten Kombinatoren im Vergleich zur einfach typisierten Lambda-Rechnung wurde demonstriert . Für jeden untypisierten Kombinator benötigt man eine ganze Familie von typisierten Kombinatoren. Zum Beispiel hat man

$\mathbf{I}_{\alpha\to\alpha}$
$\mathbf{K}_{\alpha\to(\beta\to\alpha)}$
$\mathbf{S}_{\alpha\to(\beta\to\gamma)\to(\alpha\to\beta\to(\alpha\to\gamma))}$

für alle Kombinationen einfacher Typen und . $\alpha,\beta$ $\gamma$

Stellen Sie sich die Typen alternativ als Typschemata (oder polymorphe Typen) vor und geben Sie sie in Haskell und voila: combinators ein .

Dave Clarke
quelle

Ich hätte nie gedacht, dass der

Kombinator über einer Monade agiert! Ist das so?

S

$\mathbf{S}$

Hugo Sereno Ferreira

Eigentlich wurde ich darauf hingewiesen, dass

dem Operator von Applicative Functors und dem

S

$\mathbf{S}$ <*>pure

K

$\mathbf{K}$

Hugo Sereno Ferreira

ist ziemlich grundlegend, daher könnte es vielen Dingen entsprechen.

hat den gleichen Typ wie die monadisch Funktion

für Funktors

S

$\mathbf{S}$

S

$\mathbf{S}$

a p

$ap$

Λ X . α \to X

$\Lambda X.\alpha\to X$

Dave Clarke