共享在實現函數式編程語言時參考什麼

共享意味着臨時數據將在多次使用時存儲。也就是說，一個函數只能評估一次它的參數。一個例子是：共享在實現函數式編程語言時參考什麼

let x = sin x in x * x

有助於分享其它什麼特徵，以及它們如何將與需要切實可行的方案來執行IO互動？

來源

2013-05-07 user1850254

數據的高速緩存重用被稱爲「memoization」，而不是「共享」。如果您有幾次包含相同子樹的樹狀數據，則將其轉化爲有向無環圖（DAG）以「共享」公共子樹;這就是我所說的分享。此外，這個問題（由於其開放性質）並不完全符合SO的格式。你能否更具體一些，舉個例子，...... – chris 2013-05-08 00:19:55

函數式編程中最清晰的共享示例來自Clean，它基於圖形重寫。在那裏，計算指的是DAG，所以我們可以查看錶達(sin x) * (sin x)作爲

(*) 
/ \ 
sin x sin x

圖重寫系統都共享一個明確的概念，所以我們可以表達計算爲

(*) 
/\ 
    \/
    sin x

指點乘法節點到同一節點，從而共享sin x的計算。術語重寫系統沒有如此明確的共享概念，但優化仍然相關。在GHC中，人們有時可以用局部變量表達共享，例如，重寫

f x = (sin x) * (sin x)

到

f x = sinx * sinx 
    where sinx = sin x

但由於兩者是語義等價，編譯器可以自由地實現通過相同的方式，有或沒有共享。根據我的理解，GHC通常會保留與局部變量一起引入的共享，有時會引入它（在第一個中增加共享），但是沒有在術語重寫系統中正式表達共享，這兩種行爲都依賴於實現（請參閱tel的評論和回答）。

由於不能共享副作用值，所以共享IO。如果我們考慮不純的語言，有

(string-append (read-line) 
       (read-line))

和

(let ((s (read-line))) 
    (string-append s s))

第一執行IO操作兩次，向用戶請求兩條線和追加兩者之間的差異;第二個「共享」IO操作，執行一次並將其附加到自身。通常，共享一個純粹的計算可以在不改變程序結果的情況下減少執行時間，同時共享一個副作用值（可能隨時間變化或與用戶交互）會改變結果。爲了編譯器自動共享計算，它需要知道它們是純的，因此減少評估數量並不重要。 Clean用獨特的類型來做這件事;一個IO操作具有類型屬性UNQ，它告訴編譯器它不應該被共享。 Haskell和IO monad的做法有些不同。

來源

2013-05-08 15:54:32 isturdy

真的，你沒有理由在你的「sinx = sin x」例子中引入共享。純度保證兩個值是否相乘是「指針相等」，表達式的最終值是相同的。現在，分享這個價值是明顯的*優化*，GHC有時會「向上浮動」來引入這種共享。也就是說，我們也可以計算'sin x'，將它複製到兩個地址，然後如果我們想要的話就乘。在Haskell的語義中，共享*是不可觀測的。 'StableName'是最接近你可以得到的，而不需要將自己與實現細節聯繫起來。 – 2013-05-08 16:53:34

True（現在已編輯）。我已經看到，通常這樣一個where子句將引入GHC中的共享，但透明地共享價值的另一面是透明地取消共享的能力（內聯「罪x」）。 – isturdy 2013-05-08 17:33:16

是的，一致認爲，GHC傾向於找到分享機會的好工作。 'let'和'where'似乎可以保證它。 – 2013-05-08 18:35:06

共享是關於一種相等的：指針相等。在Haskell的價值土地（語義解釋）中，沒有共享這樣的東西。只有當它們具有Eq的實例並且然後將「相等」定義爲二進制關係(==)時，值纔可以相等。

因此，通過引用由於實現而不是語義而存在的基礎指針相等性，共享從而逃避了語義解釋。不過，這有時會產生副作用。不幸的是，由於Haskell是由其語義解釋定義的，因此使用共享是未定義的行爲。它與特定的實現綁定在一起。少數圖書館使用共享，因此具有與GHC相關的行爲。

雖然有一個內置的共享機制。這由StableName接口暴露。我們使用makeStableName :: a -> IO (StableName a)產生StableName a對象，並且產生instance Eq (StableName a)-由此StableName引入了某種類型的對於任何類型的相等性。

StableName等於差不多指針相等。引述黑線鱈文檔

如果sn1 :: StableName和sn2 :: StableName和sn1 == sn2然後sn1和sn2被調用創建makeStableName在同一對象上。

請注意，這只是一個如果聲明，而不是當且僅當。事實上，有兩件事可以是「指針等價」，但仍然有不同的穩定名稱，有時（a）被Haskell留給GC的靈活性所迫使;（b）允許任何Haskell實現中存在的漏洞，即使存在在實施中沒有「指針平等」這樣的事情。

這些StableName s仍然沒有語義含義，但是因爲它們是在IO monad中引入的，因此它是「OK」。相反，他們可能被說成實現了一個（具有諷刺意味的）不同類型的最小（最具體的）等式關係可能的不穩定子集。

來源

2013-05-08 03:07:33

您的示例不是共享示例 - 它只是將值與自身相乘（然後將原始值丟棄）。

共享是數據結構的某些部分在較大的數據結構或不同的數據結構中出現兩次的情況。例如：

p = (1, 2) 
pp = (p, p) -- p is shared between the first and second component of pp 

xs = [1, 2, 3] 
ys = 0::1::xs 
zs = 5::xs -- ys and zs share the same tail

在內存中，這樣的共享會導致DAG結構。

來源

2013-05-08 16:34:34

共享在實現函數式編程語言時參考什麼

回答

相關問題