서브 표현식을 한 번 실행하십시오

Question

좋아요, 그래서 이것은 잠시 나를 괴롭 히고 있습니다. 그래서 저는 실제로 와서 대답을 알 수있는 누군가에게 물어볼 것이라고 생각했습니다.

가정하자 I는 다음과 같은 기능을 가지고

가

foobar x y = expensive x + cheap y 

가정 또한, 프로그램의 일부는 입력으로 foobar 5 취하고, 타이트 루프에서 시간의 함수 수백만을 실행한다. 분명히 나는 ​​expensive 5을 백만 번이 아니라 한 번 계산하려고합니다.

• 에 의해 중복 작업을 제거 할만큼 똑똑 GHC인가 ... 그대로

  나는 코드를 떠날 수, 또는 나는

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

  이 궁금 나에게 잎으로 변경할 수 그 자체? (즉, 첫 번째 버전이 이미 원하는대로 작동합니까?)

• 아니요, 두 번째 버전이 실제로 문제를 해결합니까? (즉, 옵티마이는 첫 번째 버전과 같은 코드로 다시 변환 할 것인가?)

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에게 물었습니다. 내가 이해할 때, 인라인 또는 η- 확장/축소 할 때 (그리고 그렇게 할 때 미묘하게 엄격 동작/의미를 변경하는)를 결정하는 것은 컴파일러에게는 매우 까다로운 일이기 때문에 GHC는 구문 론적으로 함수를 어떻게 정의했는지에 크게 의존한다 .

GHC 은 첫 번째 함수를 두 번째로 변환 할 수 있지만 함수를 작성하는 유일한 방법은 구문에서 컴파일러가 사용자가 원하는 방식에 대한 힌트를 제공한다는 것입니다. 원하는 공유를 얻으려면 인라인을 적용한 다음 INLINE pragma를 제공하십시오. 여기에 또 다른 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에 인라인 화 했으므로 part이라는 호출에서 expensive 5이라는 표현식을 띄울 수 있습니다.우리는 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 이은 공간 누설을 초래할 수 있기 때문에 언제나 그런 변화를 적용하지 않는 것으로 보입니다.

정식 예 :

foo x = map f [1..1000000] 

우리는이 변환 경우

foo x = map f big 

big = [1..1000000] 

에 지금 우리가 하나의 거대한 CAF ​​영원히 주위를 어슬렁이 - 아마 프로그래머가 의도하지 않는 것을하는! (나는이 정확한 방법으로 실제로 물린 적이있다 ...)