Почему невозможно создать компилятор, который может определить, изменит ли функция C ++ значение определенной переменной?

Я прочитал эту строчку в книге:

Доказано, что невозможно создать компилятор, который действительно может определить, изменит ли функция C ++ значение определенной переменной.

В абзаце говорилось о том, почему компилятор консервативен при проверке константности.

Почему невозможно построить такой компилятор?

Компилятор всегда может проверить, переназначена ли переменная, для нее вызывается неконстантная функция или передается ли она как неконстантный параметр ...

Почему невозможно построить такой компилятор?

По той же причине, что вы не можете написать программу, которая будет определять, завершится ли какая-либо данная программа. Это известно как проблема остановки , и это одна из тех вещей, которые невозможно вычислить.

Чтобы было ясно, вы можете написать компилятор, который может определять, что функция действительно изменяет переменную в некоторых случаях , но вы не можете написать такой, который надежно сообщает вам, что функция изменит или не изменит переменную (или остановится) для всевозможные функции.

Вот простой пример:

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

Как компилятор может определить, просто взглянув на этот код, fooизменится ли когда-нибудь a? Будет ли это или нет, зависит от внешних по отношению к функции условий, а именно от реализации bar. Есть нечто большее, чем доказательство того, что проблема остановки не вычислима, но она уже хорошо объяснена в связанной статье Википедии (и в каждом учебнике теории вычислений), поэтому я не буду пытаться объяснять ее здесь правильно.

Представьте, что такой компилятор существует. Также предположим, что для удобства он предоставляет библиотечную функцию, которая возвращает 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 ++.

Однако последнее утверждение можно определить, посмотрев на дерево синтаксического анализа, что и делают все оптимизирующие компиляторы. Причина, по которой они это делают, заключается в том, что чистые функции (и ссылочно прозрачные функции для некоторого определения ссылочно прозрачных ) имеют всевозможные хорошие оптимизации, которые можно применять, например, их легко встраивать или определять их значения во время компиляции; но чтобы знать, является ли функция чистой, нам нужно знать, может ли она когда-либо изменять переменную.

Итак, то, что кажется неожиданным заявлением о C ++, на самом деле является тривиальным заявлением обо всех языках.

Я думаю, что ключевым словом в выражении «будет ли функция C ++ изменять значение конкретной переменной» является «будет». Конечно, можно создать компилятор, который проверяет, разрешено ли функции 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, избегать глобальных переменных, предпочитать ссылки на указатели, избегать повторного использования переменных для несвязанных задач и т. Д., Что облегчит жизнь компилятору при выполнении агрессивных оптимизаций.

Есть несколько способов объяснить это, одна из которых - проблема остановки :

В теории вычислимости проблема остановки может быть сформулирована следующим образом: «Учитывая описание произвольной компьютерной программы, решите, завершит ли программа выполнение или продолжит выполнение бесконечно». Это эквивалентно проблеме принятия решения при наличии программы и ввода, остановится ли программа в конечном итоге при запуске с этим вводом или будет работать вечно.

Алан Тьюринг доказал в 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вызывает ли деталь условие срабатывания или, что более важно, останавливается ли оно. Этого компилятор сделать не может.

Действительно удивлен, что нет ответа, который бы использовал проблему остановки напрямую! Существует очень прямое сокращение от этой проблемы до проблемы остановки.

Представьте, что компилятор может определить, изменила ли функция значение переменной. Тогда он определенно сможет определить, изменяет ли следующая функция значение y или нет, предполагая, что значение x можно отслеживать во всех вызовах остальной части программы:

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

Теперь для любой понравившейся программы давайте перепишем ее так:

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

Обратите внимание, что если и только если наша программа изменяет значение y, она затем завершается - foo () - это последнее, что она делает перед завершением. Это означает, что мы решили проблему остановки!

Приведенное выше сокращение показывает нам, что проблема определения того, изменяется ли значение переменной: не менее сложна, чем проблема остановки. Известно, что проблема остановки не поддается расчету, поэтому и эта проблема тоже должна быть.

Как только функция вызывает другую функцию, источник которой компилятор не «видит», она либо должна предположить, что переменная изменена, либо что-то может пойти не так, как описано ниже. Например, скажем, у нас есть это в "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?

Я уверен, что мы можем придумать что-то более сложное, если это будет недостаточно сложно.

Как уже указывалось, компилятор не может определить, будет ли изменена переменная .

При проверке константный-ности, вопрос о том, интерес , как представляется, если переменная может быть изменена с помощью функции. Даже это сложно для языков, поддерживающих указатели. Вы не можете контролировать, что делает другой код с помощью указателя, его можно даже прочитать из внешнего источника (хотя маловероятно). В языках, ограничивающих доступ к памяти, эти типы гарантий возможны и допускают более агрессивную оптимизацию, чем это делает C ++.

Чтобы сделать вопрос более конкретным, я предполагаю, что автор книги мог иметь в виду следующий набор ограничений:

1. Предположим, что компилятор изучает поведение конкретной функции в отношении константы переменной. Для корректности компилятор должен предположить (из-за псевдонима, как объяснено ниже), если функция вызвала другую функцию, переменная будет изменена, поэтому предположение № 1 применимо только к фрагментам кода, которые не вызывают вызовов функций.
2. Предположим, что переменная не изменяется в результате асинхронного или одновременного действия.
3. Предположим, что компилятор только определяет, можно ли изменить переменную, но не будет ли она изменена. Другими словами, компилятор выполняет только статический анализ.
4. Предположим, что компилятор учитывает только правильно работающий код (не учитывая переполнения / недоработки массива, неверные указатели и т. Д.)

В контексте разработки компилятора, я думаю, что предположения 1,3,4 имеют смысл с точки зрения автора компилятора в контексте правильности генерации кода и / или оптимизации кода. Предположение 2 имеет смысл при отсутствии ключевого слова volatile. И эти предположения также фокусируют вопрос достаточно, чтобы сделать оценку предлагаемого ответа гораздо более окончательной :-)

Учитывая эти предположения, основная причина, по которой нельзя предполагать постоянство, связана с сглаживанием переменных. Компилятор не может знать, указывает ли другая переменная на переменную const. Псевдонимы могут быть связаны с другой функцией в том же модуле компиляции, и в этом случае компилятор может просматривать функции и использовать дерево вызовов, чтобы статически определить, что наложение может возникнуть. Но если псевдоним связан с библиотекой или другим сторонним кодом, то компилятор не имеет возможности узнать при входе в функцию, имеют ли переменные псевдонимы.

Вы можете возразить, что если переменная / аргумент помечена как const, она не должна изменяться с помощью псевдонима, но для автора компилятора это довольно рискованно. Для программиста-человека может быть даже рискованно объявлять переменную const как часть, скажем, большого проекта, где он не знает поведения всей системы, ОС или библиотеки, чтобы действительно знать, что переменная выиграла. т изменить.

Даже если переменная объявлена 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

Чтобы расширить мои комментарии, текст этой книги неясен, что запутывает проблему.

Как я уже сказал, эта книга пытается сказать: «Давайте заставим бесконечное количество обезьян написать все мыслимые функции C ++, которые когда-либо могли быть написаны. Будут случаи, когда мы выберем переменную, которая (какую-то конкретную функцию, которую написали обезьяны) использует, мы не можем понять, изменит ли функция эту переменную ".

Конечно, для некоторых (даже многих) функций в любом приложении это может быть определено компилятором, и это очень легко. Но не для всех (или обязательно для большинства).

Эту функцию легко проанализировать так:

static int global;

void foo()
{
}

"foo" явно не изменяет "global". Он вообще ничего не меняет, и компилятор может с этим легко справиться.

Эту функцию нельзя так анализировать:

static int global;

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

Поскольку действия "foo" зависят от значения, которое может изменяться во время выполнения , во время компиляции явно невозможно определить , изменит ли он "global".

Всю эту концепцию понять намного проще, чем предполагают компьютерные ученые. Если функция может делать что-то другое в зависимости от того, что может измениться во время выполнения, то вы не можете понять, что она будет делать, пока не запустится, и каждый раз, когда она запускается, она может делать что-то другое. Доказуемо это невозможно или нет, но очевидно невозможно.