Есть ли напечатанный лыжный исчисление?

Question

Большинство из нас знают переписку между комбинаторная логика а также Lambda Calculus. Анкет Но я никогда не видел (может быть, я не выглядел достаточно глубоко) эквивалент «напечатанных комбинаторов», соответствующих просто напечатанному исчислению Lambda. Такая вещь существует? Где можно найти информацию об этом?

Answer 1

Выразительная полнота типизированных комбинаторов по сравнению с просто напечатанным исчислением Lambda было продемонстрировано. Анкет Для каждого невыраженного комбинатора нужно целую семью напечатанных комбинаторов. Например, есть

• $ 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))} $

Для всех комбинаций простых типов $ alpha, beta $ и $ gamma $.

В качестве альтернативы просто подумайте о типах как схемах типов (или полиморфных типах) и введите их в Хаскелл и вуаля: комбинаторы.