Lambda算子6a: SKI組合子(上)

接以前的 Y組合子。這篇文章大緻基于 Good Math Bad Math的 文章，穿插點花邊。強烈推薦原文。   說SKI組合子前，不能不談去年紅得發紫的 Ruby On Rails。Rails裡一大子產品是 ActiveSupport。該子產品實作了很多幫助函數，大幅降低了Rails架構的程式設計強度。有興趣地話不妨讀一下它的源代碼。當然，拜Ruby強大的meta-programming支援所賜， ActiveSupport裡函數賞心悅目的程度，遠遠不是Java一個*Helper.java或者*Utils.java能比的。咳，咳，不好意思，一不小心就開始鄙視Java了。另外一個幫助函數庫是 Ruby Facets，非常有用。Rails和SKI有乜關系呢？嗯，本來沒有，可DHH和一位叫Mikael Brockman的老大聊過以後，于2005年3月在ActiveSupport裡 加入了一段代碼。于是就 發生關系老：   我們常常需要建立一個對象。比如說Person，一個Person對象有綽号，有電話号碼。一般我們會用這樣的工廠方法：

01: def create_person
02:   person = Person.new
03:   person.nick_name = "g9"
04:   person.phone = "12345"
05:   person
06: end
      

這樣寫挺好。不過好像Ruby味道不夠。畢竟我們希望把和建立Person有關的邏輯限制到一塊兒。而Ruby裡最
常用的“塊兒”，就是block了：      

08: def create_person
09:   returning Person.new do |person|
10:     person.nick_name = "g9"
11:     person.phone = "12345"
12:   end
13: end
      

上面代碼裡的returning，就是DHH在ActiveSupport裡加的代碼，讓一個普通的建立函數變得更有Ruby的
風味。從俺自己的角度看，也更符合《重構》裡強調的精神：減少代碼間的依賴。去掉無關的中間變量。
實作returning的代碼灰常簡單：      

15: class Kernel
16:   def returning(value)
17:     yield(value)
18:     value
19:   end
20: end      

也就是說，定義的函數returning把接受的參數傳給對應的block（ 隐含的第二個參數），再傳回該參數。 傳回該參數時，因為block的副作用，該參數已經被正确地更新。有了這個函數，我們可以實作而returning

函數的實作原理，就是SKI組合子裡的老二，K組合子。     組合子是 組合邏輯的基礎構成。說到組合邏輯，不得不感歎一下它的命運多舛。1920年，Moses Schönfinkel還在哥廷根大學希爾伯特研究組（那個時代的數學系學生的口号是“打起背包，到哥廷根去吧”，可見哥廷根數學系的号召力之強）花差的時候，發明了組合邏輯。可惜1929年清潔工斯大林那B上台後，Moses就再沒做過任何與組合邏輯有關的工作。他在二戰爆發前夕回到蘇聯。1942年左右默默無聞地過世，卒月不詳。俺強烈懷疑清潔工把他清洗了。後來同樣是哥廷根出身的Haskell Curry讀PhD時重新發現組合邏輯，并和他的學生Robert Feys着手把它發揚光大。可惜1933年優生學家希特勒上台，大搞不靠譜的雅利安人種淨化運動。哥廷根數學系就此風流雲散。猶太的非猶太的牛人們看到小布什那個原教旨紅脖子還沒上台，紛紛投奔新大陸。輝煌一時的歐洲數學中心開始慢慢轉到美國。這是後話，扯遠了。不世出的天才Alanzon Church隆重推出組合邏輯的函數化形式，Lambda算子理論，更是搶過組合邏輯的風頭。直到上六七十年代理論計算機科學大熱，組合邏輯才再次興盛。   SKI三個組合子其實很簡單。

1. S: S是函數應用的組合子：

   S = lambda x y z . (x z (y z))

   .
2. K: K 生成一個常數函數。當把生成的常數函數應用到任何一個參數上，都會得到K的第一個參數：

   K = lambda x . (lambda y . x)

   .
3. I: I其實是一個恒等函數：

   I = lambda x . x

初看之下，這些定義相當詭異。特别是S，應用機制很古怪 － 它沒有直接取兩個參數x和y，然後把y應用到x上。相反，它接受兩個函數x和y，以及第三個值z，然後把x應用于z。得到的結果再應用到把y應用于z得到的結果上。   不過前人選擇這樣的定義是有原因的。看看下面的推導。每一行都從上一行規約得來：

S K K x =

(K x) (K x) =

(lambda y . x) (lambda y . x) =

x

哈！I組合子完全沒有必要。我們用S和K得出了I組合子的等價物！後面我們會看到，不用任何變量，僅用S和K就能組合出任何一個lambda表達式的等價表達。再進一步，每一個lambda表達式都可以被表達為二叉樹，數的葉子就是S或K。   比如說，Y組合子有如下等式：

Y = S S K (S (K (S S (S (S S K)))) K)

，用二叉樹表示為：  

  困了。下面的明天繼續吧。