Y Combinator

December 13, 2021

現代開發者,對於函數式程式設計,多多少少都有接觸過了吧!如果程式語言支援一級函式,也就是函數本身也是個值,可以指定給變數、傳入函式或從函式中傳回,那麼在進行函數式程式設計時會方便許多,若是一級函式的語法簡潔,那麼寫來就會更加輕鬆愉快!

例如,JavaScript 支援一級函式,而且支援箭號函式(Arrow function)語法,使得撰寫一級函式輕鬆許多(雖然技術面上,箭號函式與 function 有些微不同),那麼,試著來寫個 Y Combinator 吧!

從遞迴函式開始

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

function fact(n) {
    return n < 2 ? 1 : n * fact(n - 1);
}

這樣是定義一個 fact 函式,現在要求用匿名函式來實現,那麼可以寫成:

let fact = function(n) {
    return n < 2 ? 1 : n * fact(n - 1);
};

function 又有 return,寫起來或閱讀起來就是麻煩,那麼來用箭號函式:

let fact = n => n < 2 ? 1 : n * fact(n - 1);

無盡的匿名函式

接下來要求必須是完全匿名,也就是不能有 fact 變數,只寫 n => n < 2 ? 1 : n * fact(n - 1) 顯然是不行的,因為 fact 沒有定義,怎麼辦呢?那就再來層箭號函式:

fact => n => n < 2 ? 1 : n * fact(n - 1);

這個箭號函式就合法了,只是想執行這個箭號函式時怎麼辦?誰來給這個箭號函式一個真正的遞迴函式,以便讓 fact 參數可以參考?

總之,先來看看階乘時會需要的函式是什麼,假設定義為 y 好了:

function y(f) {
    // 假設存在一個 fact
    return f(fact);
}

這邊希望 y 可以傳回函式,也就是希望 y(fact => n => n < 2 ? 1 : n * fact(n - 1)) 傳回的會是函式,此函式可以套用數值 n 來取得階乘結果,也就是相當於必須能 f(fact)(n) 來取得階乘結果,因此 fact 可以定義為:

function y(f) {
    let fact = n => f(fact)(n);
    return f(fact);
}

只是多了個變數 fact 而已,這樣算什麼呢?y 函式有沒有辦法全部用匿名函式實現?假設有個 get_fact 能做到這點,那麼就可以變成這樣:

function y(f) {
    function get_fact() {
        // 假設都用匿名函式實現 ...
    }
    return get_fact();
}

實際上,get_fact 看來像個騙子,只是把問題藏到裏頭而已:

function y(f) {
    function get_fact() {
        let fact = n => f(fact)(n);
        return f(fact);
    }
    return get_fact();
}

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

function y(f) {
    function get_fact() {
        let fact = n => get_fact()(n);
        return f(fact);
    }
    return get_fact();
}

咦?好像不用 fact 變數了,那就改成這樣:

function y(f) {
    function get_fact() {
        return f(n => get_fact()(n));
    }
    return get_fact();
}

自我指涉

只不過,get_fact 依舊是個具名的遞迴函式,這樣下去沒完沒了的,假設 get_fact 函式有個 get_fact 參數,那麼就可以把傳進來的參數再傳給自己:

function y(f) {
    function get_fact(get_fact) {
        return f(n => get_fact(get_fact)(n));
    }
    return get_fact(get_fact);
}

然後改為箭號函式版本:

function y(f) {
    let get_fact = get_fact => f(n => get_fact(get_fact)(n));
    return get_fact(get_fact);
}

接下來不需要 get_fact 變數,直接使用箭號函式:

function y(f) {
    return (get_fact => f(n => get_fact(get_fact)(n)))(get_fact => f(n => get_fact(get_fact)(n)));
}

咦?沒有變數了?只剩下參數 get_fact 了?名稱有點長,改成 x 好了:

function y(f) {
    return (x => f(n => x(x)(n)))(x => f(n => x(x)(n)));
}

順便也把 y 改成箭號函式:

let y = f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n)));

運行程式的程式

y 的實現全都是匿名函式!可以這麼使用它來產生一個可遞迴的階乘函式:

y(fact => n => n < 2 ? 1 : n * fact(n - 1))(5) // 120

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

y(fib => n => (n ==0 || n == 1) ? n : fib(n - 1) + fib(n - 2))(10) // 55

Y Combinator 看來很神奇,像是可以運行程式的程式(a program that runs programs),美國有間創投公司命名為 Y Combinator,因為他們覺得自己就類似可運行程式的程式 Y Combinator,只不過他們是間協助新創公司的公司。

至於搞 Y Combinator 做什麼?就現代程式語言來說,搞 Y Combinator 不太能有實際的作用,然而,如果想試著用箭號函式(也就是一種 lambda 表示式)來表達程式意圖的話,那麼 Y Combinator 會是必要的元素之一!