アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで

7.3

 

SKI

コンビネータ計算

221

SKICall#reduce

は、簡約方法がわかっている部分式（たとえば、

3

つの引数で呼び出され

る

S

コンビネータ）を再帰的に探して、

#call

を使って適切な規則を適用していきます。

これで完成です。これ以上簡約できなくなるまで簡約を繰り返すことで、SKI 式を評価することがで

きます。たとえば、2つの引数の順序を入れ替える

S[K[S[I]]][K]

という式を、シンボル

x

と

y

を引

数にして呼び出すと、以下のようになります。

>>

swap = SKICall.new(SKICall.new(S, SKICall.new(K, SKICall.new(S, I))), K)

=> S[K[S[I]]][K]

>>

expression = SKICall.new(SKICall.new(swap, x), y)

=> S[K[S[I]]][K][x][y]

>>

while expression.reducible?

puts expression

expression = expression.reduce

end; puts expression

S[K[S[I]]][K][x][y]

K[S[I]][x][K[x]][y]

S[I][K[x]][y]

I[y][K[x][y]]

y[K[x][y]]

y[x]

=> nil

SKI計算は、3つの単純な規則によって驚くほど複雑な振る舞いを生み出します。この振る舞いは非

常に複雑で、実のところ、万能であることがわかっています。