Y at-il un calcul typé SKI?

Question

La plupart d'entre nous connaissent la correspondance entre et la logique combinatoire lambda-calcul . Mais je ne l'ai jamais vu (peut-être que je ne l'ai pas regardé assez profond) l'équivalent de « combinateurs typés », ce qui correspond au calcul lambda simplement typé. Est-ce que cette chose exist? Où pourrait-on trouver des informations à ce sujet?

Answer 1

L'intégralité expressive des combinateurs tapées par rapport au calcul lambda simplement typé a été démontré . Pour chaque combinateur typées, il faut toute une famille de combinateurs tapées. Par exemple, on a

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

pour toutes les combinaisons de types simples $ \ alpha, \ beta $ et $ \ gamma $.

Sinon, il suffit de penser des types comme systèmes de type (ou types polymorphes) et les entrer dans Haskell et le tour est joué: combinators .