为什么无法构建一个编译器来确定C++函数是否会改变特定变量的值？

Question

我在一本书中读到这句话：

可以证明，无法构建一个编译器来实际确定C++函数是否会改变特定变量的值。

该段落谈论了为什么编译器在检查常量性时会保守。

为什么无法构建这样的编译器？

编译器总是可以检查变量是否被重新赋值、是否调用了非const函数以及是否作为非const参数传递...

- Cricketer

---

我脑海中首先想到的是动态链接库。如果我在我的机器上编译代码，你在你的机器上编译代码，然后我们在运行时将它们链接起来，你的编译器怎么知道我是否修改了变量呢？ - Mooing Duck

@MooingDuck的意思就是说，编译器不单独编译函数，而是将其作为更广泛的整体进行编译，这个整体可能超出了编译器的范围。请注意，我的翻译并未改变原文的意思。 - called2voyage

“不可能”可能有点夸张 - “计算上的不可行性”（例如NP难问题）可能更为准确，但对学生来说理解起来可能比较困难。想象一下一个链表或其他抽象数据结构。如果我调用一个改变该链表/树/其他东西中一个节点的函数，编译器如何能够准确地证明哪个节点被修改了（也许更重要的是哪些节点没有被修改），同时又不需要编译一个源文件要花费三天时间呢？ - twalberg

“@twalberg，不可能并非言过其实，正如其他回答所解释的那样，停机问题在这里适用。对于一般程序，完全通过算法进行分析是不可能的。” - Fiktik

只编译有效程序的编译器并不是非常有用。 - Caleb

Answer 1

为什么无法建立这样的编译器？

出于同样的原因，你无法编写一个程序来确定任何给定程序是否会终止。这被称为停机问题，它是一些不可计算的事情之一。

需要明确的是，你可以编写一个编译器，它可以确定函数在某些情况下是否更改变量，但你无法编写一个可以可靠地告诉你每个可能的函数是否会更改变量（或停止）的编译器。

以下是一个简单的例子：

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

编译器如何仅从代码中判断出是否会改变a的值？无论它是否会改变，都取决于函数外部的条件，即bar的实现。停机问题不可计算的证明还有更多内容，但已经在链接的维基百科文章（以及每本计算理论教材）中得到了很好的解释，因此我不会在这里尝试正确地解释它。

- Caleb

---

@mrsoltys，量子计算机对于某些问题只是指数级别的加速，它们无法解决不可判定问题。 - zch

@mrsoltys提到的那些指数级复杂度的算法（如因式分解）非常适合量子计算机，但停机问题是一个逻辑困境，无论你使用什么类型的“计算机”，它都是不可计算的。 - WSBT

@mrsoltys，仅仅是为了表现聪明，是的，它会改变。不幸的是，这意味着算法既已终止又在运行中，不幸的是，你无法确定它是哪一个，除非你直接观察，从而影响实际状态。 - Nathan Ernst

好的，假设我正在执行一个程序，请问如何确定它是否会终止？ - ruakh

但如果你真正执行这个程序，而且它不终止（例如一个无限循环），你永远不会发现它不终止……你只会不停地执行一步，因为它可能是最后一步。 - MaxAxeHax

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;
}

- orlp

---

好的！【我是一个说谎者悖论】（http://en.wikipedia.org/wiki/Liar_paradox）以程序员的身份书写。 - Krumelur

实际上，这只是对 停机问题 不可判定性著名证明的一个不错的改编。 - Konstantin Weitz

在这个具体的案例中，“modifies_variable”应该返回true：至少有一条执行路径确实会修改变量。并且在调用外部的、非确定性的函数后，才会到达这个执行路径——所以整个函数是不确定性的。出于这两个原因，编译器应该采取悲观的态度，并决定它确实修改了该变量。如果修改变量的路径是在一个确定性的比较（由编译器可验证）产生false（即“1==1”）之后到达的，那么编译器可以安全地说这种函数从不修改变量。 - Joe Pineda

问题是f是否修改了变量，而不是它是否能够修改变量。这个回答是正确的。 - Neil G

@JoePineda：假设是开源的，那么我可以毫无障碍地从编译器源代码中复制并粘贴modifies_variable的代码，从而完全推翻了你的论点。 - orlp

Answer 3

不要混淆“在给定这些输入的情况下，将或不将修改变量”和“具有修改变量的执行路径”。前者被称为不透明谓词确定，从简化停机问题的角度来看，它是显然不可能确定的 - 你可以指出输入可能来自未知来源（例如用户）。这对于所有语言都是正确的，而不仅仅是C ++。

然而，后者的陈述可以通过查看解析树来确定，这是所有优化编译器所做的事情。他们这样做的原因是纯函数（和参考透明函数，对于某些参考透明的定义）具有各种好的优化，例如易于内联或在编译时确定它们的值；但要知道一个函数是否是纯函数，我们需要知道它是否可能修改变量。

因此，关于C ++的看似令人惊讶的陈述实际上是关于所有语言的琐碎陈述。

- BlueRaja - Danny Pflughoeft

---

我认为这是最好的答案，重要的是要做出区分。 - UncleZeiv

@Kip “trivially impossible to decide” 可能意味着“不可能决定，证明是平凡的”。 - fredoverflow

Answer 4

我认为在“C++函数是否会改变特定变量的值”中，关键词是“会”。理论上可以构建一个编译器来检查C++函数是否被允许改变特定变量的值，但不能确定这种改变一定会发生：

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

- Sergey Kalinichenko

---

“确实可以构建一个编译器来检查C++函数是否可以更改特定变量的值。”不，不行。请参考Caleb的回答。为了让编译器知道foo()是否可以更改a的值，它必须知道bar()是否可能返回0。然而，没有可计算的函数能够告诉任何可计算函数的所有可能返回值。因此，存在代码路径，编译器无法确定它们是否会被执行。如果一个变量只在无法到达的代码路径中更改，那么它将不会更改，但编译器将无法检测到它。 - Martin Epsz

“可以”指的是“被允许改变”，而不是“可能会改变”。我认为这就是当OP谈论关于const检查时所考虑的内容。 - Sergey Kalinichenko

@dasblinkenlight 我同意，我认为OP可能是指第一个，“is allowed to change”或“may or may not change”，而不是“will definitely not change”。当然，我想不出这会成为问题的情况。你甚至可以修改编译器，使其简单地回答任何包含标识符或调用具有“may change”答案属性的函数的函数“may change”。话虽如此，C和C++是可怕的语言，尝试使用它们进行此操作，因为它们对事物的定义非常松散。我认为这就是为什么const-ness在C++中会成为问题的原因。 - DDS

@MartinEpsz：“没有可计算的函数可以告诉任何可计算函数的所有可能返回值。”我认为检查“所有可能的返回值”是一种不正确的方法。有数学系统（maxima，mathlab）可以解决方程，这意味着将类似的方法应用于函数是有意义的。即将其视为具有多个未知数的方程。问题在于流程控制+副作用=>无法解决的情况。在我看来，如果没有这些（函数语言，无赋值/副作用），就可以预测程序将采取哪条路径。 - SigTerm

Answer 5

我认为没有必要引用停机问题来解释为什么你无法在编译时算法地知道一个给定的函数是否会修改某个变量。

相反，只需指出函数的行为通常取决于运行时条件，这是编译器事先无法知道的。例如：

int y;

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

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

- LarsH

Answer 6

有些函数可以做到这一点，编译器也经常为此进行优化。例如，对于简单的内联访问器或许多纯函数来说，这是一个微不足道的优化。

但在普遍情况下，这是不可能知道的。

每当有来自另一个模块的系统调用或函数调用，或者调用可能被重写的方法时，任何事情都可能发生，包括某个黑客使用堆栈溢出来更改不相关变量的恶意接管。

然而，您应该使用const，避免全局变量，优先使用引用而非指针，避免将变量重新用于不相关的任务等。这将使编译器在执行积极的优化时更加容易。

- kriss

---

如果我记得正确的话，这就是函数式编程的全部意义，对吧？通过仅使用纯确定性、无副作用的函数，编译器可以自由地进行激进的优化，预执行、后执行、记忆化甚至编译时执行。我认为很多回答者忽略了（或者混淆了）的一点是，在所有程序的行为良好的子集中确实可能*。不，这个子集并不是微不足道或无趣的，实际上非常有用。但对于绝对的一般情况来说，它确实是不可能的。 - Joe Pineda

重载（overloading）是一个编译时的概念。你可能指的是“覆盖方法”（overridden method）。 - fredoverflow

@FredOverflow：是的，我确实是指重写。重载确实是一个编译时的概念。感谢你发现了这个问题（当然，如果实现来自另一个编译单元，编译器仍然可能有分析难题，但那不是我的意思）。我会修正这个答案。 - kriss

Answer 7

很惊讶没有人直接使用停机问题来回答！这个问题可以非常直接地约简为停机问题。

假设编译器能够判断函数是否更改变量的值。那么，只要我们能够追踪整个程序中对于 x 变量的调用，在后续所有调用中，它肯定能够判断以下函数是否更改了 y 的值：

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

现在，无论我们喜欢什么程序，让我们将其重写为：

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

请注意，只有当我们的程序更改y的值时，它才会终止-在退出之前，foo()是它执行的最后一件事。这意味着我们解决了停机问题！

上面的简化证明给我们展示，确定变量的值是否更改的问题至少与停机问题一样复杂。停机问题已知是无法计算的，因此这个问题也必须如此。

- John Doucette

---

我不确定我理解你的推理，关于为什么我们的程序在改变y的值时终止。在我看来，foo()很快就返回了，然后main()退出了。（另外，你在没有参数的情况下调用了foo()...这是我的困惑之一。） - LarsH

@LarsH：如果修改后的程序终止，最后调用的函数是f。如果y被修改，那么就调用了f（其他语句不能改变y，因为它只是通过修改引入的）。因此，如果y被修改，程序就会终止。 - MSalters

Answer 8

有多种方法来解释这个问题，其中之一是 停机问题：

在可计算性理论中，停机问题可以被陈述为：“给定任意计算机程序的描述，决定程序是否会完成运行或继续永久运行”。这相当于决定在给定程序和输入的情况下，当使用该输入运行程序时，程序是否最终会停止运行或永远运行。

艾伦·图灵在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部分是否会触发条件 - 或者更基本的是，它是否会停止。这是编译器无法做到的。

- Timothy Shields

Answer 9

当一个函数调用另一个编译器无法“看到”源代码的函数时，它要么假设变量已经被更改，要么可能会导致下面的事情出错。例如，假设我们在“foo.cpp”中有以下内容：

 void foo(int& x)
 {
    ifstream f("f.dat", ifstream::binary);
    f.read((char *)&x, sizeof(x));
 }

我们在 "bar.cpp" 文件中有如下代码：

void bar(int& x)
{
  foo(x);
}

编译器如何“知道”在 bar 中 x 没有变化（或更恰当地说是正在变化）？

如果这还不够复杂，我相信我们可以想出更复杂的东西。

- Mats Petersson

---

编译器可以知道如果将bar x作为传递给常量引用，则x在bar中不会改变，对吗？ - Cricketer

是的，但如果我在foo中添加一个const_cast，它仍然会使x改变 - 我将违反合同，该合同规定您不得更改const变量，但由于您可以将任何东西转换为“更多const”，而且存在const_cast，因此语言设计者肯定有这样一种想法，即有时有充分理由相信const值可能需要更改。 - Mats Petersson

@MatsPetersson：我相信如果你使用const_cast，你可以保留所有因为编译器可能但不一定会对此进行补偿而导致的错误。 - Zan Lynx

@ZanLynx：是的，我确定这是正确的。但同时，强制转换确实存在，这意味着设计语言的人有某种想法，即“我们可能在某个时候需要这个”——这意味着它并不是完全没有任何用处。 - Mats Petersson

Answer 10

通常情况下，编译器无法确定变量是否会被更改，正如已经指出的那样。

在检查const性质时，感兴趣的问题似乎是变量是否可以被函数更改。即使在支持指针的语言中，这也很困难。您无法控制其他代码对指针的操作，甚至可能从外部源读取（尽管不太可能）。在限制访问内存的语言中，这些类型的保证是可能的，并且比C++更具有侵略性的优化。

- Krumelur

---

我希望编程语言中支持临时、可返回和可持久化引用（或指针）之间的区别。临时引用只能复制到其他临时引用，可返回引用可以复制到临时或可返回引用，而可持久化引用可以以任何方式复制。函数的返回值将受限于作为“可返回”参数传递的最严格的参数。我认为，在许多语言中，当一个引用被传递时，没有任何指示它可以被使用多长时间，这是不幸的。 - supercat

那肯定会很有用。当然，对于这个问题已经有了一些模式，但在C++（以及许多其他语言）中，“作弊”总是可能的。 - Krumelur

.NET 相对于 Java 的一个主要优势是它具有短暂引用的概念，但不幸的是，对象无法将属性公开为短暂引用（我真正想看到的是一种方法，使使用属性的代码可以传递短暂引用给代码（以及临时变量），以便用于操作对象）。 - supercat