SKI組合子演算入門

題圖的PixivID為：pixiv-ID: 39597155，畫師為アンミツ（QS）

本文始發於我的博客，轉載請註明作者。

什麼是SKI組合子演算？

SKI組合子演算是一個計算系統，它是無類型版本的Lambda演算的簡約。這個系統聲稱在Lambda演算中所有運算都可以用三個組合子S、K和I來表達。

t--維基百科

通過組合子演算，我們只需要幾個預定義的組合子(S、K、I)互相apply，就可以達到圖靈完備。

定義

所謂的SKI，一般來說可以這樣定義：

I x -> x

K x y -> x

S x y z -> x z (y z)

推導

讓我們從一個簡單的lambda開始，感受一下SKI組合子的威力。

首先是常用的compose函數。假設有：

compose = g -> f -> x -> g (f x)

那麼我們可以做如下轉換：

1. 轉化g (f x)為(K g x) (f x)
2. 由於(K g x) (f x)滿足 x z (y z)的形式，所以可簡化為S (K g) f x
3. 現在compose變成了g -> f -> x -> S (K g) f x，那麼其實可以直接消去x變為g -> f -> S (K g) f
4. 同理可消去f，變為g -> S (K g)
5. 轉化S (K g)為(K S g) (K g)
6. 與步驟2同理，簡化為S (K S) K g
7. 於是得到compose = S (K S) K

所有的lambda表達式都可以用這種方式，轉化為SKI組合子。

總結一下：

1. 對於任意f = x -> x, f = I
2. 對於任意f = x -> A且A與x無關, f = K A
3. 對於任意f = x -> A B, f = S (x -> A) (x -> B)

由於所有lambda表達式都可以轉換為SKI組合子演算，所以遞歸、算數計算、布爾邏輯和數據結構這些自然也不在話下了。

轉化為SK

一個有趣的事實：

In=> x -> xn=> x -> K x _n=> x -> K x (K x)n=> x -> S K K xn=> S K Kn

這說明了其實I組合子可以用SKK來表示，所以SKI組合子演算可以轉化為SK組合子演算。

動手試試

看上去是不是很厲害的樣子，來自己動手試試這道codewars題目吧。