深入理解運算原理｜從簡單的機器到無所不能的程式

四處皆通用

|

235

inc[S[K[inc]][I][zero]]

inc[K[inc][zero][I[zero]]] inc[inc[I[zero]]] inc[inc[zero]]

=> nil

果然，以名為

inc

和

zero

的符號呼叫轉換後的運算式，已經估算成

inc[inc[zero]]

，這

完全就是我們想要的。相同的轉譯也在其他任何的 lambda 演算運算式成功運作，所以

SKI 組合器演算可以完整模擬 lambda 演算，也因此必須是通用。

雖然 SKI 演算擁有 3 個組合器，但是

I

組合器實際上是多餘的。許多運算

式只包含

S

和

K

，但它們做的事情卻和

I

一樣；例如

S[K][K]

的行為：

>> identity = SKICall.new(SKICall.new(S, K), K)

=> S[K][K]

>> expression = SKICall.new(identity, x)

=> S[K][K][x]

>> while expression.reducible?

puts expression

expression = expression.reduce

end; puts expression

S[K][K][x]

K[x][K[x]]

x

=> nil

所以

S[K][K]

的行為和

I

一樣，而事實上，

S[K]

[

不論哪一種

] 形式的任何

SKI 運算式也是如此。

I

組合者是就算沒有也能活得很好的語法甜頭；只

有兩個組合器

S

和

K

才足以通用。

Iota

希臘字母 iota (

ɩ

) 是可以加到 SKI ...