Lambda算子5b：How of Y

 其實是 這篇文章的意譯。有些東西省了。添了點私貨。就有了下面的文章。 雖然Y相當神奇。對它的推導也不完全是天外飛仙般無迹可尋。基本上我們為了解決讓沒有名字的函數能自我引用，一步一步抽象出了Y。是以知道Y的推導過程對我們程式員還是很有意義的：畢竟程式設計的過程也是抽象的過程。看看當年的老大們怎麼從紛繁的表象裡抽象出一般規律，對我們日後的思考應該大有好處。為了老大們能夠試驗，我就用JavaScript了。整個推導的過程非常像程式設計時的重構。我們提出一個粗略的解決方案，然後仔細觀察，找出可以抽象的地方，進行抽象。得到一個更普适的結果後，繼續重複重構的步驟，直到得到最優解。估計看這篇文章的人都知道怎麼玩兒小小JavaScript吧？再說有個浏覽器就有了測試環境。廢話少說，看代碼。我們還是以階乘函數為例。先看通常的寫法：  

1: function fact(n){
2:         if(n == 0){
3:                 return 1;
4:         }
5: 
6:         if(n > 0){
7:                 return n * fact(n - 1);
8:         }
9: }      

上面的JavaScript函數定義内部調用自己。這種調用可行的前提是我們用函數名指代函數定義。也就是說， fact這個名字綁定的函數定義就是上面的函數體。如果我們不能通過名字來調用函數怎麼辦呢（就跟lambda算子一樣）？也許有老大會問：為什麼增加這個限制呢？不是自虐麼？理由很簡單：理論需要探求事物本質。記得奧卡姆剃刀吧？如無必要，毋增實體。函數名到底是必需元素，還是句法糖？這種研究方法也有實際的意義：再複雜的系統也是在簡單但完備的基礎上搭建起來的。強大的程式設計工具，總是基于于層層疊加的抽象，而最低級的抽象層總是非常簡單。簡單意味着透徹，簡單意味着健壯。簡單意味着靈活。簡單意味着經濟。問題是，到底簡單到什麼地步？怎麼保證系統不至于簡單到一無所用的地步？這和邏輯學家建立系統時總是要證明系統的正确性和完備性一個道理。而找到了Y，我們也就明白了，原來函數名綁定并非本質。   嗯，繼續。函數 fact是遞歸的基本形式。既然我們不能直接在函數體内通過函數名調用另一個函數，我們至少可以把想調用的函數通過參數傳進去。于是我們得到 fact2:

09: fact2 = function(himself, n){
10:         return function(n){
11:                 if(n < 2){
12:                         return 1;
13:                 }
14: 
15:                 return n * (something_expression_with_himself);
16:         }
17: }      

  我用JavaScript裡的匿名函數來強調lambda函數不具名的特征。這裡用fact2純粹為了友善。變量fact2本身并沒有參與運算。如果我們這樣調用：fact2(fact2, 3)，那fact2這個函數不就可以調用自身了麼？這也就是前面提到的自我引用的技巧：加一層抽象，進而把自己通過參數傳給自己。現在我們要解決的就是，到底something_expression_with_himeself是什麼東西。因為fact2和himself都必須遞歸調用自己，something_expression_with_himself從直覺上應該是himself(himself， n-1)開始。看到沒有？函數體和調用方式不變，但n變成n-1了。和遞歸一緻了哈：

19: fact3 = function(himself, n){
20:         if( n < 2 ){
21:                 return 1;
22:         }
23: 
24:         return n * himself(himself, n-1);
25: }      

    在你的JavaScript console裡試驗一下：fact3(fact3, 3) 的确傳回6。什麼，沒有JavaScript console? 老大啊，上網的銀能不用FireFox麼？用了FireFox的程式員能不用FireBug麼？快去下載下傳吧。   下載下傳完了？那我們繼續。記得lambda算子裡的函數隻接受一個參數吧？可是fact3接受兩個函數。是以我們要撒一點“咖喱”：

17: fact4 = function(himself){
18:         return function(n){
19:                 if( n < 2 ){
20:                         return 1;
21:                 }
22: 
23:                 return n * himself(himself)(n-1);
24:         }
25: }      

  運作一下三。看見才能相信哈。fact4(fact4)(3) = 6, fact4(fact4)(4) = 24, fact4(fact4)(5)=120。。。。   現在的問題是，我們要把這個具體例子的遞歸方法抽象出來。現在我們需要把和自我引用無關的細節同自我引用本身分開。因為我們關心的是怎麼運用自我引用來解決遞歸問題。我們可以先解決分離himself和n有關的代碼。這樣做是因為管理n的代碼隻與求階乘有關，不是我們關心的重點。好比分離架構邏輯和業務邏輯。于是我們得到函數fact5。

37: fact5 = function(h){
38:         return function(n){
39:                 var f = function(q){
40:                         return function(n){
41:                                 if(n < 2){
42:                                         return 1;
43:                                 }
44: 
45:                                 return n * q(n-1);
46:                         }
47:                 }
48: 
49:                 return f(h(h))(n);
50:         }
51: }      

  運作幾個例子增強點信心哈：fact5(fact5)(3) = 6, fact5(fact5)(4)=24。。。   注意函數f其實不用嵌在fact5裡面。是以我們可以寫成：

37: fucntion f(q){
38:         return function(n){
39:                 if(n < 2){
40:                         return 1;
41:                 }
42: 
43:                 return n * q(n-1);
44:         }
45: }
46:       

47: function fact5(h){
48:         return function(n){
49:                 return f(h(h))(n);
50:         }
51: }      

現在就可以看出兩件事了：一是新的函數 f不過是參數化的階乘函數 ―― 遞歸部分變成參數（也是一個函數） q了。第二，我們可以把f進一步抽象出來，剝離具體的階乘部分，于是得到了Y：

69: function Y(f){
70:          g = function(h){
71:                 return function(x){
72:                         return f(h(h))(x);
73:                 }
74:          }
75: 
76:          return g(g);
77: }      

現在我們可以用Y來實作階乘了：

79: fact6 = Y(
80:         function(h){
81:                 return function(n){
82:                         if(n < 2){
83:                                 return 1;
84:                         }
85: 
86:                         return n * h(n-1);
87:                 }
88:         }
89: );       

試一下，比如fact6(3) = 6, fact6(4) = 24。。。。   長出一口氣。連寫了4個小時，終于把關于Y的東西寫完了。下面可以談更寬泛的組合算子了。主要是S，K，和I三個算子。有個 變态程式設計語言unlambda就是靠解析SKI為生的。