Выполнение подвыражения один раз

Question

ОК, так что это беспокоило меня какое-то время, поэтому я подумал, что приду и спрошу кого-нибудь, кто мог бы действительно узнать ответ.

Пусть у меня есть следующие функции:

foobar x y = expensive x + cheap y 

Предположим, далее, что часть программы занимает foobar 5 в качестве входных данных, и выполняет эту функцию миллионы раз в тугой петлей. Понятно, что я хочу, чтобы expensive 5 был вычислен один раз, а не миллион раз.

Я мог бы оставить код, как это, или я мог бы изменить его

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

Это оставляет мне интересно ...

• Является GHC достаточно умен, чтобы устранить дублированную работу сам? (I.e., делает ли первая версия делать то, что я хочу?)

• Если нет, делает ли вторая версия на самом деле проблему? (Т.е., будет Оптимизатор просто превратить его обратно в тот же код, как первый вариант?)

Answer 1

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, который прояснил несколько вещей, но оставил меня немного неудовлетворенным. Насколько я понимаю, определение того, как и когда делать inline или eta-expand/уменьшать вещи (и при столь тонком изменении поведения/семантики строгости) действительно сложно для компилятора, поэтому GHC в значительной степени зависит от того, как вы синтаксически определили вашу функцию ,

Я думаю, короткий ответ, что GHC может превратить свою первую функцию на второй, но единственный способ быть уверенным, чтобы написать свои функции, так что синтаксис дает компилятор подсказки о том, как вы хотите вещи быть направленным, чтобы получить доступ, который вы хотите, а затем предоставить INLINE прагмы. Вот еще interesting discussion of this issue

Answer 2

Наглядно мой ответ был бы нет и да. Но позвольте мне ответить на ваш вопрос, попробовав его. Рассмотрим этот код:

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 

поэтому компилятор был достаточно умен, чтобы оптимизировать оригинальную версию, а также. Но почему? Потому что он ввел определение foobar в main, а затем заметил, что он может плавать выражение 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).

Answer 3

Чтение одной из различных бумаг STG, похоже, что это так называемый преобразование полной лень. Кажется, что [в то время, когда была написана статья) GHC делает применять это преобразование, но не все время, так как это может привести к утечке пространства.

Canonical пример:

foo x = map f [1..1000000] 

Если мы превращаем это в

foo x = map f big 

big = [1..1000000] 

теперь у нас один гигантский CAF торчать навсегда - что, вероятно, не то, что программист предназначен! (Я лично был укушен именно таким образом, на самом деле ...)