不動點

December 15, 2021

在正式討論不可運算的函式之前,倒是可以重新瞭解一下〈Y Combinator〉,在那一連串如同魔術般的推導過程之後,得到了像是密宗文字般的 f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))),是的,它可以達到想要的遞迴效果,然而,到底這串文字是什麼東西?

Y Combinator

Y Combinator〉的推導過程,老實說是有點作弊,為了讓事情一開始不要太複雜,用到了 JavaScript 的一些特性,但也讓推導過程稍微迂迴了一些,現在已經玩過這麼多次的 lambda 演算了,就來全部用箭號函式重做一遍,也許就能瞭解到什麼。

同樣地,假設想要解決 let fact = n => n < 2 ? 1 : n * fact(n - 1) 這個遞迴函式,然而不使用 let,為了能綁定 fact 這個名稱,就讓 fact 成為參數,也就是 fact => n => n < 2 ? 1 : n * fact(n - 1)

現在的問題是,誰來給這個箭號函式一個真正的遞迴函式,以便讓 fact 參數可以參考?若真的存在 get_R,可產生需要之函式,遞迴函式就可以這麼解決:

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

問題在於 get_R 從哪來,若希望 get_R 從參數來:

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

問題顯然沒有解決,只是將 get_R 來源問題繼續往右推而已,那就不要馬上用 get_R 來呼叫,將 get_R => f(get_R()) 當成是引數,傳入另一個匿名函式:

(f => 
    (p => p())(get_R => f(get_R()))
)(fact => n => n < 2 ? 1 : n * fact(n - 1))

左邊 p() 呼叫沒有傳入,這樣的話右邊 get_R 不會有值,那就將 p 當成是 p 呼叫時的引數:

(f => 
    (p => p(p))(get_R => f(get_R(get_R)))
)(fact => n => n < 2 ? 1 : n * fact(n - 1))

接著套用 p

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

get_R 名稱有點長,改成 x 好了:

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

f => (x => f(x(x)))(x => f(x(x))) 就是 Y Combinator 了!咦?長得跟〈Y Combinator〉裏不一樣?哪裏導錯了呢?

Y?Z?

沒有導錯!這才是 lambda 演算裏的 Y Combinator,只不過,試著執行上頭的程式並傳入一個數字的話,遞迴卻不會終止,最後達到 JavaScript 環境的遞迴堆疊上限,產生錯誤訊息才停止。

原因在於 JavaScript 的執行環境中,會先執行 x(x),結果值傳入 f,而不是令整個 x(x)fact 參考,在判定 n < 2 之後才執行,這問題跟〈是的!不是!〉是類似的,因為 JavaScript 並不支援惰性求值,若要能有這個效果,必須自行實現。

也就是令 x(x) 成為 n => x(x)(n),JavaScript 還是會先執行,然後結果是產生一個 n => x(x)(n) 函式物件,只有在 n < 2 時才會呼叫此函式物件,這樣就能避免堆疊錯誤。

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

f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))) 就長得跟〈Y Combinator〉中最後的結果一樣了,這個形式是 Y Combinator 的衍生,稱為 Z Combinator,本質上還是 Y Combinator,因此在具備一級函式特性的程式語言中,雖然實現出來的其實是 Z Combinator,然而,多還是以 Y Combinator 來稱呼它。

固定點

總之,就還是都稱呼它們為 Y Combinator 吧!現在重點來了,在導證過程中,出現的 (p => p(p))(get_R => f(get_R(get_R))) 代表了什麼呢?get_R 實際上存在嗎?你真的找出來 get_R 嗎?不!沒有!

Y Combinator 從沒有真正產生 get_R,它只是一再地拖延,從沒給予真正的 get_R,那套用函式之後,Y Combinator 到底給了你什麼?因為一路上都是使用〈Y Combinator〉的成果,就還是以 f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))) 來試試看吧!

在套用 f 之後:

(x => f(n => x(x)(n)))(x => f(n => x(x)(n)))

繼續套用 x

f(n => (x => f(n => x(x)(n)))((x => f(n => x(x)(n))))(n))

也就是傳入 f 的其實是:

n => (x => f(n => x(x)(n)))((x => f(n => x(x)(n))))(n)

如果在 f 中用某個數字套用 n

(x => f(n => x(x)(n)))((x => f(n => x(x)(n))))

繼續套用 x

f(n => (x => f(n => x(x)(n)))((x => f(n => x(x)(n))))(n))

現在傳入 f 的其實是:

n => (x => f(n => x(x)(n)))((x => f(n => x(x)(n))))(n)

發現了嗎?無論怎麼套用,最後傳入 f 的一定是 n => (x => f(n => x(x)(n)))((x => f(n => x(x)(n))))(n),你找到了 f 的不動點(Fixed-point)。

若有個函式 f(x),有個值 vf(v) 結果仍為 vv 就是 f(x) 的不動點,例如,0 和 1 是函式 f(x) = square(x) 的不動點,因為 f(0) 為 0,f(1) 為 1。

Y Combinator 可以為 f 產生不動點,也就是 n => (x => f(n => x(x)(n)))((x => f(n => x(x)(n))))(n),無論執行再多次,還是得到 n => (x => f(n => x(x)(n)))((x => f(n => x(x)(n))))(n),這就是 Y Combinator 可以拖延,從不面對 get_R 真正來源的原因,每當你試圖呼叫傳入 f 的函式,它就傳給你 n => (x => f(n => x(x)(n)))((x => f(n => x(x)(n))))(n),如此 x 值從何而來就不重要了。

如果你想打破砂鍋問到底,若是人力運算,算到死它都不會交代 x 從何而來(也就不可能回答 x 是否存在),如果是現代的電腦計算,就是看什麼時候堆疊錯誤發生,那就別打破砂鍋問到底了,適可而止,給個邊界,不再執行傳入 f 的函式,就可以停止這個循環,這就是遞迴的停止條件設定了。

分享到 LinkedIn 分享到 Facebook 分享到 Twitter