運行一次子表達式

好的，所以這一直困擾着我一段時間，所以我想我會來問問一個實際上可能知道答案的人。運行一次子表達式

假設我有以下功能：

foobar x y = expensive x + cheap y

假設，進一步的計劃的一部分需要foobar 5作爲輸入，並在緊密循環執行此功能數百萬次。顯然，我想要expensive 5計算一次，而不是一百萬次。

我可以離開的代碼，因爲它是，我也可以將其更改爲

foobar x = let k = expensive x in \ y -> k + cheap y

這讓我不知道...

是GHC足夠聰明，通過消除重複工作本身？（也就是說，第一個版本是否做我想要的東西？）
如果不是，第二個版本是否真的解決了這個問題？（即，將優化器只是其轉換回相同的代碼作爲第一個版本？）

來源

2013-07-27 MathematicalOrchid

這不會改變語義，'map（foo 5）[]; foo a b = undefined a + b'如果您強制評估地圖上的'foo 5'，您將不必要地炸掉 – jozefg

@jozefg'let'不會強制評估。它是在第一次需要時進行評估（然後希望共享所有進一步的用途）。 –

Is GHC smart enough to eliminate the duplicated work by itself? (I.e., does the first version do what I want already?)

我覺得問這個的另一種方式是：將GHC直列foobar x y使expensive x之間共享計算？

我問了一個similar question已經清理了一些東西，但讓我有點不滿意。據我所知，確定如何以及何時內聯或擴展/減少事物（並且在微妙地改變嚴格行爲/語義時）對編譯器來說非常棘手，因此GHC嚴重依賴於如何在語法上定義函數。

我想簡短的答案是，GHC 可能改變你的第一個功能到第二，但可以肯定的唯一方式是寫你的功能，這樣的語法讓你想如何的事情編譯器提示內聯以獲得您想要的共享，然後提供INLINE編譯指示。這裏的另一個interesting discussion of this issue

來源

2013-07-27 17:43:04 jberryman

所以，主要答案是「如果你在乎哪一個，你應該明確地寫第二個版本」（？） – MathematicalOrchid

@MathematicalOrchid我認爲這可能是正確的。 – jberryman

是的，這是正確的。 – augustss

直覺我的回答會是沒有和是。但讓我通過試用來回答你的問題。考慮以下代碼：如果我們運行

import Debug.Trace 

expensive :: Int -> Int 
expensive x = trace ("expensive evaluated for " ++ show x) $ x 
{-# NOINLINE expensive #-} 

cheap :: Int -> Int 
cheap x = x 
{-# NOINLINE cheap #-} 

foobar x y = expensive x + cheap y 

foobar' x = let k = expensive x in \ y -> k + cheap y 

part f = sum [f i| i<-[0..10]] 

main = do 
    print $ part (foobar 5) 
    print $ part (foobar' 5)

這樣做的結果是

$ ./Test 
expensive evaluated for 5 
110 
expensive evaluated for 5 
110

所以編譯器很聰明，優化原來的版本也是如此。但爲什麼？因爲他在main中內嵌了foobar的定義，因此會注意到它可能會將expensive 5中的表達式浮出呼叫part。如果我們禁用內聯爲foobar和foobar'（或可選地不使用-O），它不工作了：

$ ./Test 
expensive evaluated for 5 
expensive evaluated for 5 
expensive evaluated for 5 
expensive evaluated for 5 
expensive evaluated for 5 
expensive evaluated for 5 
expensive evaluated for 5 
expensive evaluated for 5 
expensive evaluated for 5 
expensive evaluated for 5 
expensive evaluated for 5 
110 
expensive evaluated for 5 
110

因此，雖然GHC可以在某些情況下做正確的事情，你應該經常檢查，如果它是如果你想依靠它的話。無論是使用工具如Debug.Trace，或通過查看核心（-ddump-simpl）。

來源

2013-07-27 18:27:59

讀了各種STG論文之一，看來這就是所謂的完全懶惰轉型。看起來[在撰寫論文時] GHC 確實應用了這種轉換，但並不是所有的時間，因爲它可能導致空間泄漏。

典型的例子：

foo x = map f [1..1000000]

如果我們將其轉化成

foo x = map f big 

big = [1..1000000]

我們現在有一個巨大的CAF掛撒手人寰 - 這可能不是程序員的預期！（我本人一直以這種確切的方式咬人，實際上......）

來源

2014-01-31 15:42:43 MathematicalOrchid

運行一次子表達式

回答

相關問題