为什么不可能构建一个可以确定C++函数是否会改变特定变量值的编译器？

Question

我在一本书中读到这一行:

实际上,构建一个能够实际确定C++函数是否会改变特定变量值的编译器是不可能的.

该段讨论了在检查const-ness时编译器保守的原因.

为什么不可能构建这样的编译器？

编译器总是可以检查是否重新分配了一个变量,是否正在调用一个非const函数,或者它是否作为非const参数传入...

Answer 1

为什么不可能构建这样的编译器？

出于同样的原因,您无法编写将确定任何给定程序是否将终止的程序.这被称为暂停问题,它是那些不可计算的东西之一.

为了清楚起见,您可以编写一个编译器,在某些情况下可以确定某个函数确实更改了该变量,但您不能编写一个可靠地告诉您该函数将会或不会更改该变量(或停止)的函数.每个可能的功能.

这是一个简单的例子:

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

编译器如何通过查看代码来确定是否foo会改变a？它是否确实取决于函数外部的条件,即执行bar.暂停问题不可计算的证据不止于此,但在链接的维基百科文章(以及每个计算理论教科书)中已经很好地解释了,所以我不会试图在这里正确解释它.

Answer 2

想象一下这样的编译器存在.我们还假设为方便起见,它提供了一个库函数,如果传递的函数修改给定变量则返回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;
}

Answer 3

不要混淆"将给出或将不会修​​改给定这些输入的变量",因为"具有修改变量的执行路径".

前者称为不透明谓词确定,并且很容易决定 - 除了停止问题的减少之外,您可以指出输入可能来自未知来源(例如用户).所有语言都是如此,而不仅仅是C++.

但是,后一种语句可以通过查看解析树来确定,这是所有优化编译器所做的事情.他们这样做的原因是纯函数 (以及引用透明函数,对于某些引用透明的定义)具有可以应用的各种好的优化,例如易于使用或在编译时确定其值; 但要知道函数是否纯粹,我们需要知道它是否可以修改变量.

所以,关于C++的一个令人惊讶的陈述实际上是一个关于所有语言的简单陈述.

Answer 4

我认为"C++函数是否会改变特定变量的值"中的关键词是"将".当然可以构建一个编译器来检查是否允许 C++函数更改特定变量的值,您无法肯定地说该更改将会发生:

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

Answer 5

我不认为有必要调用暂停问题来解释您在编译时无法通过算法知道给定函数是否会修改某个变量.

相反,它足以指出函数的行为通常取决于运行时条件,编译器事先无法知道.例如

int y;

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

编译器如何能够确定地预测是否y会被修改？

Answer 6

它可以完成,编译器一直在为某些函数执行它,例如,对于简单的内联访问器或许多纯函数,这是一个简单的优化.

在一般情况下,不可能知道它.

每当有来自另一个模块的系统调用或函数调用,或者对潜在的覆盖方法的调用时,任何事情都可能发生,包括一些黑客使用堆栈溢出来改变不相关的变量的恶意接管.

但是,您应该使用const,避免全局变量,更喜欢对指针的引用,避免重复使用不相关任务的变量等,这将使编译器在执行积极优化时更加轻松.

Answer 7

解释这个有多种途径,其中一个是停机问题:

在可计算性理论中,暂停问题可以表述如下:"给定任意计算机程序的描述,确定程序是否完成运行或继续运行".这相当于在给定程序和输入的情况下决定程序在使用该输入运行时最终会停止还是将永远运行的问题.

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零件是否导致条件触发 - 或者甚至更基本,是否停止.这是编译器无法做到的.

Answer 8

真的很惊讶,没有直接使用暂停问题的答案!从这个问题到停止问题的解决方案非常简单.

想象一下,编译器可以判断函数是否改变了变量的值.那么它肯定能够判断以下函数是否改变了y的值,假设在整个程序的其余部分中所有调用都可以跟踪x的值:

foo(int x){
   if(x)
       y=1;
}

现在,对于我们喜欢的任何程序,让我们将其重写为:

int y;
main(){
    int x;
    ...
    run the program normally
    ...
    foo(x);
}

请注意,如果且仅当我们的程序更改了y的值时,它是否会终止 - foo()是它在退出之前做的最后一件事.这意味着我们已经解决了暂停问题!

上述减少告诉我们的是,确定变量值是否发生变化的问题至少与暂停问题一样困难.已知暂停问题是无法计算的,所以这个问题也必须如此.