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

四處皆通用

|

231

class SKICall

def reducible?

left.reducible? || right.reducible? || combinator.callable?(*arguments)

end

def reduce

if left.reducible?

SKICall.new(left.reduce, right)

elsif right.reducible?

SKICall.new(left, right.reduce)

else

combinator.call(*arguments)

end

end

end

SKICall#reduce

的運作是透過遞迴的方式尋找我們知道如何化簡的子運算

式（例如以 3 個引數呼叫

S

組合器），然後再以

#call

套用適當的規則。

就是這樣！我們現在可以反覆化簡它們來估算 SKI 運算式，一直到無法再化簡。例如

以符號

x

和

y

呼叫這個運算式

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

，交換了它自己 2 個引數的順序：

>> 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 ...