[c++] C ++ 함수가 특정 변수의 값을 변경할 것인지 결정할 수있는 컴파일러를 빌드하는 것이 불가능한 이유는 무엇입니까?

나는 책에서이 줄을 읽었습니다.

실제로 C ++ 함수가 특정 변수의 값을 변경할지 여부를 결정할 수있는 컴파일러를 빌드하는 것은 불가능합니다.

이 단락은 const-ness를 확인할 때 컴파일러가 보수적 인 이유에 대해 이야기하고있었습니다.

왜 그런 컴파일러를 만드는 것이 불가능합니까?

컴파일러는 항상 변수가 재 할당되었는지, 상수가 아닌 함수가 호출되는지, 아니면 상수가 아닌 매개 변수로 전달되는지 확인할 수 있습니다.



답변

왜 그런 컴파일러를 만드는 것이 불가능합니까?

같은 이유로 주어진 프로그램이 종료되는지 여부를 결정하는 프로그램을 작성할 수 없습니다. 이것은 중지 문제 로 알려져 있으며 계산할 수없는 문제 중 하나입니다.

명확 하게 말하면 함수가 어떤 경우에 변수 변경하는지 확인할 수있는 컴파일러를 작성할 수 있지만 함수가 변수를 변경 (또는 중지) 할 것인지 여부를 안정적으로 알려주 는 컴파일러를 작성할 수 없습니다. 가능한 모든 기능.

다음은 간단한 예입니다.

void foo() {
    if (bar() == 0) this->a = 1;
}

컴파일러는 코드를보고 foo변경 여부 를 어떻게 결정할 수 a있습니까? 실행 여부는 함수 외부의 조건, 즉 bar. 중지 문제를 계산할 수 없다는 증거에는 그 이상이 있지만 연결된 Wikipedia 기사 (및 모든 계산 이론 교과서)에서 이미 잘 설명되어 있으므로 여기서 올바르게 설명하지 않겠습니다.


답변

그러한 컴파일러가 존재한다고 상상해보십시오. 편의를 위해 전달 된 함수가 주어진 변수를 수정하면 1을 반환하고 함수가 수정하지 않으면 0을 반환하는 라이브러리 함수를 제공한다고 가정 해 보겠습니다. 그러면이 프로그램은 무엇을 인쇄해야합니까?

int variable = 0;

void f() {
    if (modifies_variable(f, variable)) {
        /* do nothing */
    } else {
        /* modify variable */
        variable = 1;
    }
}

int main(int argc, char **argv) {
    if (modifies_variable(f, variable)) {
        printf("Modifies variable\n");
    } else {
        printf("Does not modify variable\n");
    }

    return 0;
}


답변

“변수 를 수정하는 실행 경로가 있음 이 입력이 주어지면 변수를 수정하거나 수정 하지 않을 것 “과 혼동하지 마십시오 .

전자는 불투명 한 술어 결정 이라고 하며 결정하기가 거의 불가능합니다. 중지 문제로 인한 감소를 제외하고는 입력이 알 수없는 소스 (예 : 사용자)에서 올 수 있음을 지적 할 수 있습니다. 이것은 C ++뿐만 아니라 모든 언어에 해당 됩니다.

그러나 후자의 명령문 은 모든 최적화 컴파일러가 수행하는 구문 분석 트리를 보면 확인할 있습니다. 그들이하는 이유는 순수 함수 (그리고 참조 적으로 투명 함의 일부 정의를 위한 참조 적으로 투명한 함수 ) 는 쉽게 inlinable하거나 컴파일 타임에 값을 결정하는 것과 같이 적용 할 수있는 모든 종류의 멋진 최적화를 가지고 있기 때문입니다. 그러나 함수가 순수한지 알기 위해서는 변수를 수정할 있는지 알아야 합니다.

따라서 C ++에 대한 놀라운 진술로 보이는 것은 실제로 모든 언어에 대한 사소한 진술입니다.


답변

“C ++ 함수가 특정 변수의 값을 바꿀지 여부”의 핵심 단어는 “will”이라고 생각합니다. C ++ 함수 특정 변수의 값 변경할 있는지 여부를 확인하는 컴파일러를 빌드하는 것은 확실히 가능 합니다. 변경이 일어날 것이라고 확신 할 수는 없습니다.

void maybe(int& val) {
    cout << "Should I change value? [Y/N] >";
    string reply;
    cin >> reply;
    if (reply == "Y") {
        val = 42;
    }
}


답변

주어진 함수가 특정 변수를 수정할지 여부를 컴파일 타임에 알고리즘 적으로 알 수 없다는 것을 설명하기 위해 중지 문제를 호출 할 필요가 없다고 생각합니다.

대신, 함수의 동작은 종종 컴파일러가 미리 알 수없는 런타임 조건에 의존한다는 점을 지적하는 것으로 충분합니다. 예

int y;

int main(int argc, char *argv[]) {
   if (argc > 2) y++;
}

컴파일러 y는 수정 여부를 어떻게 확실하게 예측할 수 있습니까?


답변

이는 수행 될 수 있으며 컴파일러는 일부 함수에 대해 항상 수행합니다. 예를 들어 간단한 인라인 접근 자 또는 많은 순수 함수에 대한 사소한 최적화입니다.

불가능한 것은 일반적인 경우에 그것을 아는 것입니다.

시스템 호출이나 다른 모듈에서 오는 함수 호출 또는 잠재적으로 재정의 된 메서드에 대한 호출이있을 때마다 해커가 스택 오버플로를 사용하여 관련없는 변수를 변경하는 적대적인 인수를 포함하여 모든 일이 발생할 수 있습니다.

그러나 const를 사용하고, 전역을 피하고, 포인터에 대한 참조를 선호하고, 관련없는 작업에 대한 변수 재사용을 피해야합니다. 이렇게하면 공격적인 최적화를 수행 할 때 컴파일러의 수명이 더 쉬워집니다.


답변

이를 설명하는 데는 여러 가지 방법이 있으며 그 중 하나는 중지 문제입니다 .

계산 가능성 이론에서 중단 문제는 “임의의 컴퓨터 프로그램에 대한 설명이 주어지면 프로그램 실행이 완료되는지 또는 계속 실행되는지 결정”과 같이 설명 할 수 있습니다. 이것은 프로그램과 입력이 주어지면 프로그램이 해당 입력으로 실행될 때 결국 중지 될 것인지 또는 영원히 실행될 것인지를 결정하는 문제와 동일합니다.

Alan Turing은 1936 년에 가능한 모든 프로그램 입력 쌍에 대한 정지 문제를 해결하는 일반적인 알고리즘이 존재할 수 없음을 증명했습니다.

다음과 같은 프로그램을 작성하면 :

do tons of complex stuff
if (condition on result of complex stuff)
{
    change value of x
}
else
{
    do not change value of x
}

x변화 의 가치가 있습니까? 이를 확인하려면 먼저 do tons of complex stuff부품으로 인해 조건이 발생하는지 여부를 확인해야합니다. 그것은 컴파일러가 할 수없는 일입니다.