Why is it impossible to build a compiler that can determine if a C++ function will change the value of a particular variable?

Question

I read this line in a book:

It is provably impossible to build a compiler that can actually determine whether or not a C++ function will change the value of a particular variable.

The paragraph was talking about why the compiler is conservative when checking for const-ness.

Why is it impossible to build such a compiler?

The compiler can always check if a variable is reassigned, a non-const function is being invoked on it, or if it is being passed in as a non-const parameter...

Answer 1

Why is it impossible to build such a compiler?

For the same reason that you can't write a program that will determine whether any given program will terminate. This is known as the halting problem, and it's one of those things that's not computable.

To be clear, you can write a compiler that can determine that a function does change the variable in some cases, but you can't write one that reliably tells you that the function will or won't change the variable (or halt) for every possible function.

Here's an easy example:

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

How can a compiler determine, just from looking at that code, whether foo will ever change a? Whether it does or doesn't depends on conditions external to the function, namely the implementation of bar. There's more than that to the proof that the halting problem isn't computable, but it's already nicely explained at the linked Wikipedia article (and in every computation theory textbook), so I'll not attempt to explain it correctly here.

Answer 2

Imagine such compiler exists. Let's also assume that for convenience it provides a library function that returns 1 if the passed function modifies a given variable and 0 when the function doesn't. Then what should this program print?

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