定點組合器

Question

我是fixed-point combinators的新手，我猜他們習慣在匿名lambda上遞歸，但我並沒有真正使用它們，甚至無法將我的頭完全包裹在它們周圍。

我在Javascript中看到了一個例子Y-combinator，但一直未能成功運行它。

這裏的問題是，能有一個人給一個直觀的答案：

• 什麼是固定點組合，（不只是理論上的，但在一些實例方面，揭示究竟是什麼固定在這方面點）？
• 除Y-組合器之外，還有哪些其他類型的定點組合器？

積分：如果示例不只是一種語言，優選在的Clojure爲好。

UPDATE：

我已經能夠找到一個簡單的例子在Clojure，但仍很難理解的Y Combinator的本身：

(defn Y [r] 
    ((fn [f] (f f)) 
    (fn [f] 
    (r (fn [x] ((f f) x)))))) 

雖然例子是簡潔，我發現很難理解函數中發生了什麼。任何幫助提供將是有益的。

Answer 1

假設您想編寫階乘函數。通常情況下，你會寫它像

function fact(n) = if n=0 then 1 else n * fact(n-1) 

但是，它使用顯式遞歸。如果你想使用的Y組合子相反，你可以先抽象的事實，就像這樣

function factMaker(myFact) = lamba n. if n=0 then 1 else n * myFact(n-1) 

這需要一個參數（myFact），它被稱爲是「真正」的事實，會叫自己。我稱這種功能爲「Y-ready」，意味着它已準備好送入Y-組合器。

Y-combinator使用factMaker構建等同於「真實」事實的東西。

newFact = Y(factMaker) 

爲什麼要麻煩？兩個原因。第一個是理論上的：如果我們可以使用Y-combinator「模擬」它，我們並不需要遞歸。

第二個更實用。有時我們想用一些額外的代碼來包裝每個函數調用來做日誌記錄或分析或記憶或其他東西。如果我們試圖對「真實」事實做這個事情，額外的代碼只會被調用爲原來的調用，而不是所有的遞歸調用。但是，如果我們想在每次調用做到這一點，包括所有的遞歸調用，我們可以做這樣的事情

loggingFact = LoggingY(factMaker) 

其中LoggingY是Y組合，介紹記錄的修改版本。注意我們根本不需要改變factMaker！

所有這些都是爲什麼Y-combinator比從Y如何工作的詳細說明（因爲有許多不同的方式來實現Y）更重要。

Answer 2

要獲得關於比Y.其他定點組合程序的第二個問題有可數無窮多個標準的定點組合程序，也就是組合子fix滿足方程

fix f = f (fix f) 

也有很多contably非標準固定點組合程序，其滿足方程

fix f = f (f (fix f)) 

等標準固定點組合子是遞歸可枚舉的，但非標準都沒有。有關示例，參考資料和討論，請參閱以下網頁。 http://okmij.org/ftp/Computation/fixed-point-combinators.html#many-fixes