タイプされたスキー計算はありますか？

Question

私たちのほとんどは、間の通信を知っています 組み合わせロジック と ラムダ計算. 。しかし、私は、単にタイプされたラムダ計算に対応する「タイピングされたコンビネーター」に相当するものを見たことがありません（たぶん私は十分に深く見えませんでした）。そのようなことは存在しますか？それについての情報はどこで見つけることができますか？

Answer 1

タイプされたLambda計算と比較したタイピングされた組み合わせの表現力のある完全性は 実証されています. 。 Untyped Combinatorごとに、タイプ化されたコンビネーターの家族全員が必要です。たとえば、1つあります

• $ 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 $。

または、タイプをタイプスキーム（または多型タイプ）と考えて、HaskellとVoilaに入力してください。 組み合わせ.