¿Hay un cálculo SKI escrito?
-
16-10-2019 - |
Pregunta
La mayoría de nosotros conoce la correspondencia entre y cálculo lambda. Pero nunca he visto (lo suficientemente profundo tal vez no he mirado) el equivalente de "combinadores escribir", que corresponde al cálculo lambda simplemente mecanografiado. Hace tal cosa existe? Donde se podría encontrar información al respecto?
Solución
La integridad expresiva de los combinadores mecanografiadas en comparación con el cálculo lambda, simplemente ha sido escrito demostró . Para cada combinador sin tipo, se necesita toda una familia de combinadores mecanografiadas. Por ejemplo, uno tiene
- $ \ vec {I} _ {\ alpha \ a \ alpha} $
- $ \ vec {K} _ {\ alpha \ a (\ beta \ a \ alpha)} $
- $ \ mathbf {S} _ {\ alpha \ a (\ beta \ a \ gamma) \ a (\ alpha \ a \ beta \ a (\ alpha \ a \ gamma))} $
para todas las combinaciones de tipos simples $ \ alpha, \ beta $ y $ \ gamma $.
Alternativamente, sólo piensa de los tipos como los sistemas de tipo (o tipos polimórficos) y entrar en ellos en Haskell y listo: combinadores .