SKIコンビネータ計算
非形式的には、またプログラミング言語のジャーゴンとして、木 (xy) は“関数” x に“引数” yを適用したものと考えられる。評価されるとき(すなわち関数に引数を“適用”するとき)、木は“値を返す”、すなわち別の木に変形する。当然“関数”も“引数”も“値”もそれぞれ葉もしくは二分木である。簡単のために関数適用は左結合であるものとし、無駄な括弧は省略するのが普通である。このようにしても曖昧性はない。
評価演算は次のように定義される:
(x、y および z は任意の式とする)
I(Identity combinator) は引数を返す:
Ix = x
K(Constant (独Konstant) combinator) にxだけを適用した場合、任意の引数に対してxを返す1引数の定数関数 Kxを得る:
Kxy = x
S(Substitution combinator) は3つの引数を取って、1つ目の引数に3つ目の引数を適用し、その結果に2つ目の引数に3つ目の引数を適用した結果を適用する。
SKIコンビネータ計算は型無しラムダ計算を単純化した、ひとつの計算モデルである。このモデルは、ある種のプログラミング言語と考えることができるが、人間によるソースコードの記述には適さない(難解プログラミング言語には時折採用される)。その代わり、このモデルは非常に単純なチューリング完全な言語であるため、アルゴリズムの数学理論においては重要である。また関数型言語を実行する抽象機械のモデルとして使っている例もある。
ラムダ計算におけるあらゆる演算は、SKIにおいて3つの定数記号S, KおよびI(これらをコンビネータと呼ぶ)および変数記号によって表現できる。2引数の関数適用演算のみを持つ形式言語の構文木と考えれば、定数記号と変数記号を葉とする二分木と捉えることもできる。 実際には、 I はモデルを簡単にするために導入されたものであり、SKIシステムを展開するにはSとKの2つで十分である。