用 Python 實現 Y Combinator

會想要寫這個主題，主要是由於 聽說是某天很夯的 fibonacci number XD 討論中，談到了 Y Combinator，我試著用 Python 實現了一個，過程中有些想法，想要略做記錄一下。有關於 Fixed Point 與 Y Combinator 的推導，可以先參考 〈函数式编程 – FUNCTIONAL PROGRAMMING〉，如果你不想花太多時間看推導，那就來看看接下來的 Python 程式碼實作，從中瞭解如何實作 Y Combinator。

先來個簡單的開始，如何用遞迴寫個計算階乘的函式？

def fact(n):
    return 1 if(n < 2) else n * fact(n - 1)

這樣是定義一個 fact 函式，現在要求用 lambda 來實現，那麼你可以寫成 fact = lambda n: 1 if(n < 2) else n * fact(n - 1)，接下來要求必須是完全匿名，只寫 lambda n: 1 if(n < 2) else n * fact(n - 1) 顯然是不行的，因為 fact 沒有定義，怎麼辦呢？那就再來層 lambda：

lambda fact: lambda n: 1 if n < 2 else n * fact(n - 1)

這個 lambda 就合法了，只是想執行這個 lambda 時怎麼辦？誰來給這個 lambda 一個真正的遞迴函式，以便讓 fact 參數可以參考？透過一些巧妙的結合，其實有辦法產生一個真正的遞迴函式，而且是匿名的。

在 聽說是某天很夯的 fibonacci number XD 中就完成了讓 lambda n, fib: n if(n == 0 or n == 1) else fib(n - 1, fib) + fib(n - 2, fib) 可遞迴的實現，那時沒想太多，因而選擇了讓 fib 的第二個參數又帶入了匿名函式，如果現在打算也找出個函式，可以給 lambda fib: lambda n: n if(n == 0 or n == 1) else fib(n - 1) + fib(n - 2) 一個真正的遞迴函式，以便讓 fib 參數可以參考，那也是有可能的。

不過，階乘與費式數這兩個需求下的函式有沒有可能是同一個？也許是吧！總之，先來看看階乘時會需要的函式是什麼，假設定義為 y 好了：

def y(f):
    # 假設存在一個 fact
    return f(fact)

因為 f(fact)(n) 就可以得到階乘結果，那麼傳回 lambda n: f(fact)(n) 不就是階乘函式？可是 fact 變數還是沒解決啊？那就 …

def y(f):
    fact = lambda n: f(fact)(n)
    return f(fact)

很取巧對吧！只是把變數 fact 藏到 y 裏頭而已，這樣算什麼呢？y 函式有沒有辦法全部用匿名函式實現？假設有個 get_f 能做到這點，那麼就可以變成這樣：

def y(f):
    def get_f():
        # 假設都用匿名函式實現 ...
    return get_f()

實際上，get_f 看來又像個騙子，只是把問題藏到裏頭而已：

def y(f):
    def get_f():
        fact = lambda n: f(fact)(n)
        return f(fact)
    return get_f()

要騙就騙到底好了，既然 f(fact) 就是 get_f() 的傳回結果，那麼就改成這樣：

def y(f):
    def get_f():
        fact = lambda n: get_f()(n)
        return f(fact)
    return get_f()

咦？好像不用 fact 變數了，那就改成這樣：

def y(f):
    def get_f():
        return f(lambda n: get_f()(n))
    return get_f()

只不過，get_f 依舊是個具名的遞迴函式，這樣下去沒完沒了的，假設 get_f 函式有個 get_f 參數，那麼就可以把傳進來的參數再傳給自己，就像實現 聽說是某天很夯的 fibonacci number XD 時的 lambda n, fib: n if(n == 0 or n == 1) else fib(n - 1, fib) + fib(n - 2, fib)：

...
    def get_f(get_f):
        return f(lambda n: get_f(get_f)(n))
...

那麼原先的 y 實作就可以改為：

def y(f):
    def get_f(get_f):
        return f(lambda n: get_f(get_f)(n))
    return get_f(get_f)

然後改為 lambda 版本：

def y(f):
    get_f = lambda get_f: f(lambda n: get_f(get_f)(n))
    return get_f(get_f)

既然 get_f = lambda get_f: f(lambda n: get_f(get_f)(n))，那麼 return 前 get_f 變數就可以替代為：

def y(f):
    get_f = lambda get_f: f(lambda n: get_f(get_f)(n))
    return (lambda get_f: f(lambda n: get_f(get_f)(n)))(lambda get_f: f(lambda n: get_f(get_f)(n)))

既然如此，那 get_f 變數就可以不用了：

def y(f):
    return (lambda get_f: f(lambda n: get_f(get_f)(n)))(lambda get_f: f(lambda n: get_f(get_f)(n)))

咦？沒有變數了？只剩下參數 get_f 了？名稱有點長，改成 x 好了，順便也把 y 改成接受lambda

y = lambda f: (lambda x: f(lambda n: x(x)(n)))(lambda x: f(lambda n: x(x)(n)))

這就是我們想要的了，y 的實現全都是匿名函式！你可以這麼使用它來產生一個可遞迴的階乘函式：

y(lambda fact: lambda n: 1 if n < 2 else n * fact(n - 1))(5) # 120

要不要自己試著也來推導一個可傳回遞迴費式數計算的函式呢？結果其實會是相同的，也就是說，上頭這個 y 也可以用來產生計算費式數的遞迴函式，例如：

y(lambda fib: lambda n: n if(n == 0 or n == 1) else fib(n - 1) + fib(n - 2))(10) # 55

好玩對吧！Y Combinator 看來很神奇，像是可以運行程式的程式（a program that runs programs），美國有間創投公司命名為 Y Combinator，因為它們覺得自己就類似可運行程式的程式 Y Combinator，只不過它們是間協助新創公司的公司。

實用性呢？好像沒有！不過我在這過程中玩得很高興就是了，因為很久前看過 Y Combinator 這名詞出現過幾次了，只不過一直沒去細究它，直到有人在 聽說是某天很夯的 fibonacci number XD 又提到 Y Combinator，我才好奇，原先我實作的版本會跟 Y Combinator 有什麼關係，進一步地，想試著用 Python 來玩玩看！

一切都只是為了有趣！… XD