105

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

事实证明，构建一个能够实际确定 C++ 函数是否会更改特定变量的值的编译器是不可能的。

该段讨论了为什么编译器在检查 const-ness 时是保守的。

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

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

4

13 回答 13

140

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

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

需要明确的是，您可以编写一个编译器来确定某个函数在某些情况下确实会更改变量，但您不能编写一个能够可靠地告诉您该函数将或不会更改变量（或暂停）的编译器每个可能的功能。

这是一个简单的例子：

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

编译器如何仅通过查看该代码来确定是否foo会更改a？是否执行取决于函数外部的条件，即bar. 停止问题不可计算的证明不仅如此，但在链接的 Wikipedia 文章（以及每本计算理论教科书）中已经很好地解释了它，所以我不会尝试在这里正确解释它。

于 2013-07-01T17:23:21.143 回答
125

想象一下这样的编译器存在。我们还假设为方便起见，它提供了一个库函数，如果传递的函数修改了给定的变量，则返回 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;
}
于 2013-07-01T19:13:22.830 回答
60

不要将“将或不会修改给定这些输入的变量”与“具有修改变量的执行路径”混淆。

前者称为不透明谓词确定，并且几乎不可能决定 - 除了减少停止问题之外，您只需指出输入可能来自未知来源（例如用户）。这适用于所有语言，而不仅仅是 C++。

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

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

于 2013-07-02T06:10:26.137 回答
28

我认为“C++ 函数是否会改变特定变量的值”中的关键词是“将”。当然可以构建一个编译器来检查是否允许C++ 函数更改特定变量的值，您不能肯定地说更改将会发生：

void maybe(int& val) {
    cout << "Should I change value? [Y/N] >";
    string reply;
    cin >> reply;
    if (reply == "Y") {
        val = 42;
    }
}
于 2013-07-01T17:23:23.067 回答
16

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

相反，指出函数的行为通常取决于运行时条件就足够了，编译器无法提前知道这些条件。例如

int y;

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

编译器如何确定是否y会被修改？

于 2013-07-01T21:49:42.163 回答
8

它可以做到，编译器一直在为某些函数做这件事，例如，这是对简单内联访问器或许多纯函数的微不足道的优化。

不可能的是在一般情况下知道它。

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

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

于 2013-07-02T11:41:33.853 回答
6

真的很惊讶没有直接使用停止问题的答案！从这个问题到停机问题有一个非常简单的简化。

想象一下，编译器可以判断一个函数是否改变了变量的值。然后它肯定能够判断以下函数是否更改了 y 的值，假设可以在整个程序的其余部分的所有调用中跟踪 x 的值：

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

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

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

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

上述简化告诉我们的是，确定变量值是否变化的问题至少与停止问题一样困难。众所周知，停机问题是无法计算的，所以这个问题也必须是。

于 2013-07-02T00:20:28.993 回答
6

有多种方法可以解释这一点，其中之一是停机问题：

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

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部件是否会导致条件触发 - 或者更基本的是，它是否会停止。这是编译器无法做到的。

于 2013-07-01T17:25:19.200 回答
4

一旦一个函数调用编译器没有“看到”其源代码的另一个函数，它要么必须假设变量已更改，要么下面的事情很可能会出错。例如，假设我们在“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);
}

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

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

于 2013-07-01T17:25:33.497 回答
1

为了使问题更具体，我建议以下一组约束可能是本书作者可能想到的：

  1. 假设编译器正在检查特定函数相对于变量的 const-ness 的行为。为了正确起见，如果函数调用另一个函数，则编译器必须假设（因为下面解释的别名）变量已更改，因此假设 #1 仅适用于不进行函数调用的代码片段。
  2. 假设变量没有被异步或并发活动修改。
  3. 假设编译器只确定变量是否可以修改，而不是是否会被修改。换句话说，编译器只执行静态分析。
  4. 假设编译器只考虑正确运行的代码（不考虑数组溢出/欠载、错误指针等）

在编译器设计的上下文中，我认为假设 1、3、4 在编译器编写者的观点中在代码生成正确性和/或代码优化的上下文中非常有意义。假设 2 在没有 volatile 关键字的情况下是有意义的。而且这些假设也足够集中问题，以使判断提出的答案更加明确:-)

鉴于这些假设，不能假设 const-ness 的一个关键原因是变量混叠。编译器无法知道另一个变量是否指向 const 变量。别名可能是由同一编译单元中的另一个函数引起的，在这种情况下，编译器可以查看函数并使用调用树来静态确定可能发生别名。但是，如果别名是由于库或其他外部代码引起的，那么编译器无法在函数输入时知道变量是否有别名。

您可能会争辩说，如果变量/参数被标记为 const 那么它不应该通过别名进行更改，但是对于编译器编写器来说这是非常冒险的。对于人类程序员来说，将变量 const 声明为其中的一部分，比如说一个他不知道整个系统、操作系统或库的行为的大型项目，要真正知道一个变量是有风险的。 t 改变。

于 2013-07-02T03:55:50.277 回答
1

正如已经指出的那样，编译器通常不可能确定变量是否会改变。

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

于 2013-07-01T17:34:50.650 回答
0

为了扩展我的评论，那本书的文字不清楚是哪个混淆了这个问题。

正如我评论的那样，那本书试图说，“让我们让无限数量的猴子来编写每个可以编写的 C++ 函数。在某些情况下，如果我们选择一个变量（猴子编写的某些特定函数）使用，我们无法确定该函数是否会更改该变量。”

当然，对于任何给定应用程序中的某些（甚至许多）函数，这可以由编译器确定，而且非常容易。但并非所有人（或一定是大多数人）。

这个函数可以很容易地这样分析：

static int global;

void foo()
{
}

“foo”显然不会修改“global”。它根本不修改任何东西，编译器可以很容易地解决这个问题。

这个函数不能这么分析：

static int global;

int foo()
{
    if ((rand() % 100) > 50)
    {
        global = 1;
    }
    return 1;

由于“foo”的动作依赖于一个可以在运行时改变的值，显然无法在编译时确定它是否会修改“global”。

整个概念比计算机科学家想象的要简单得多。如果函数可以根据运行时可能发生的变化来做不同的事情，那么在它运行之前你无法确定它会做什么，并且每次运行时它可能会做一些不同的事情。不管它是否可以证明是不可能的，这显然是不可能的。

于 2013-07-02T22:47:36.190 回答
0

即使声明了一个变量const，也不意味着一些写得不好的代码可以覆盖它。

//   g++ -o foo foo.cc

#include <iostream>
void const_func(const int&a, int* b)
{
   b[0] = 2;
   b[1] = 2;
}

int main() {
   int a = 1;
   int b = 3;

   std::cout << a << std::endl;
   const_func(a,&b);
   std::cout << a << std::endl;
}

输出：

1
2
于 2013-07-01T23:57:06.963 回答