컴파일러가 순수성에 대한 유형 정보 없이 순수 함수를 자동으로 감지할 수 있습니까?

컴파일러가 순수성에 대한 유형 정보 없이 순수 함수를 자동으로 감지할 수 있습니까?

그래서 저는 GCC와 같은 컴파일러가 어떠한 종류의 정보도 없이 자동으로 순수한 함수를 감지할 수 있다고 주장하는 제 친구와 논쟁하고 있습니다.그건 아닌것 같다.

D 또는 Haskell과 같은 언어는 유형 시스템에 순수성이 있으며 프로그래머는 어떤 함수가 순수한지 여부를 명시적으로 정의합니다.순수 함수는 부작용이 없으므로 매우 쉽게 병렬화될 수 있습니다.

그래서 질문은: 이것이 모두 필요한 것인가 아닌가 하는 것입니다.컴파일러가 입출력을 하거나 글로벌 변수에 자동으로 액세스하는 모든 것이 순수하지 않다고 가정하는 것만으로 메타나 유형 정보 없이 순수성을 탐지할 수 있습니까?

물론, 경우에 따라 순수한 기능을 감지할 수 있습니다.예를 들어.

int f(int x)
{
    return x*2;
}

단순한 정적 분석으로 순수한 것으로 탐지할 수 있습니다.문제는 일반적으로 이 작업을 수행하는 것이며, "내부" 상태를 사용하지만 외부적으로 순수한 인터페이스를 탐지하는 것은 기본적으로 불가능합니다.

GCC에는 경고 옵션이 있습니다. -Wsuggest-attribute=pure그리고.-Wsuggest-attribute=const그것은 후보가 될 수 있는 기능을 제안합니다.pure그리고.const 속성나는 그것이 보수적인 것을 선택하는지(즉, 많은 순수한 기능을 놓쳤지만 순수하지 않은 기능에 대해서는 그것을 절대 제안하지 않음) 사용자가 결정하도록 할지 확신할 수 없습니다.

GCC의 정의는 다음과 같습니다.pure는 "인수 및 전역 변수에만 적용"됩니다.

반환 값을 제외한 많은 함수에는 아무런 영향이 없으며 반환 값은 모수 및/또는 전역 변수에만 의존합니다.이러한 함수는 산술 연산자와 마찬가지로 공통 하위 표현 제거 및 루프 최적화의 대상이 될 수 있습니다.이러한 함수는 속성을 사용하여 선언해야 합니다.pure.

GCC 매뉴얼

엄격한 순도, 즉 모든 상황에서 동일한 주장에 대한 동일한 결과는 다음과 같이 표현됩니다.const속성, 그러나 이러한 함수는 전달된 포인터의 참조를 취소할 수 없습니다.따라서 다음과 같은 병렬화 기회를 제공됩니다.pure기능은 제한적이지만 훨씬 더 적은 기능이 가능합니다.const당신이 해스켈과 같은 언어로 쓸 수 있는 순수한 함수들과 비교해 볼 때.

그런데, 순수한 기능을 자동으로 병렬 처리하는 것은 생각보다 쉽지 않습니다. 어려운 부분은 병렬 처리할 항목을 결정하는 것입니다.비용이 너무 적게 드는 계산을 병렬화하면 오버헤드로 인해 무의미해집니다.충분히 평행하지 않으면 이점을 얻을 수 없습니다.리파와 같은 라이브러리는 사용자 코드에서 명시적인 병렬 처리 없이 백그라운드에서 많은 작업을 병렬 처리하지만, 이러한 이유로 자동 병렬 처리를 수행하는 실용적인 기능적 언어 구현에 대해서는 알지 못합니다.

또 다른 문제가 있습니다.고려하다

int isthispure(int i) {
   if (false) return getchar();
   return i + 42;
}

함수는 불순한 코드를 포함하고 있지만 실제로 순수하지만 이 코드에 도달할 수 없습니다. 자, 제를 가정해 보겠습니다.false는 대됨체로 대체됩니다.g(i)그러나 우리는 g(i)가 거짓이라는 것을 꽤 확실히 알고 있습니다(예를 들어 g는 인수가 라이크렐 수인지 확인할 수 있습니다).이 순수함을 증명하려면 컴파일러는 라이크렐 숫자가 존재하지 않는다는 것을 증명해야 합니다.

(저는 이것이 상당히 이론적인 고려 사항이라는 것을 인정합니다.또한 함수에 불순한 코드가 포함되어 있으면 그 자체가 불순하다고 판단할 수 있습니다.그러나 이것은 C타입 시스템인 IMHO에 의해 정당화되지 않습니다.)

함수가 순수한지 여부를 결정하는 것은 (GCC에 의해 사용되는 제한된 의미에서도) 정지 문제와 동일하므로, 답은 "임의의 함수에 대한 것이 아닙니다"입니다.일부 기능은 순수하고 다른 기능은 순수하지 않음을 자동으로 감지하고 나머지 기능은 "알 수 없음"으로 플래그를 지정할 수 있으므로 경우에 따라 자동 병렬화가 가능합니다.

제 경험으로 볼 때, 프로그래머들도 그런 것들을 잘 이해하지 못하기 때문에, 저는 옵티마이저뿐만 아니라, 타입 시스템이 저를 위해 그것을 추적하는 데 도움이 되기를 원합니다.

저는 C#과 C++ 성능을 비교하는 기사를 쓰면서 Visual C++이 다항식을 계산하는 함수를 부르는 동안 중간 정도의 복잡성의 순수 함수를 실제로 감지할 수 있다는 것을 발견했습니다.

저는 시계의 시간을 다 먹기 위해 루프의 다항식 함수를 불렀습니다.컴파일러는 루프가 시작되기 전에 한 번 실행되고 루프 내에서 결과를 다시 사용하도록 호출을 최적화했습니다.그러기 위해서는 부작용이 없다는 것을 알아야 합니다.

하지만 컴파일러가 함수를 순수한 것으로 표시함으로써 최적화를 수행할 수 있다는 것을 보장할 수 있다는 것은 좋은 일이며 문서화의 한 형태이기도 합니다.

언급URL : https://stackoverflow.com/questions/8760956/can-a-compiler-automatically-detect-pure-functions-without-the-type-information