Почему невозможно создать компилятор, который может определить, изменит ли функция C++ значение конкретной переменной?
Я прочитал эту строку в книге:
Вероятно, невозможно создать компилятор, который фактически может определить, изменит ли функция C++ значение конкретной переменной.
В этом параграфе говорилось о том, почему компилятор консервативен при проверке на константность.
Почему невозможно построить такой компилятор?
Компилятор всегда может проверить, переназначена ли переменная, вызывается ли неконстантная функция или передается ли она как неконстантный параметр...
13 ответов
Почему невозможно построить такой компилятор?
По той же причине, по которой вы не можете написать программу, которая будет определять, прекратится ли какая-либо из этих программ. Это известно как проблема остановки, и это одна из тех вещей, которые нельзя вычислить.
Чтобы было ясно, вы можете написать компилятор, который может определить, что функция в некоторых случаях изменяет переменную, но вы не можете написать тот, который надежно говорит вам, что функция будет или не будет изменять переменную (или останавливать) для каждая возможная функция.
Вот простой пример:
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?
Я уверен, что мы можем придумать что-то более сложное, если это не достаточно сложно.
Чтобы сделать этот вопрос более конкретным, я предлагаю следующий набор ограничений, которые, возможно, имел в виду автор книги:
- Предположим, что компилятор проверяет поведение конкретной функции относительно постоянства переменной. Для корректности компилятор должен был бы предположить (из-за псевдонимов, как объяснено ниже), если функция, вызвавшая другую функцию, изменилась переменная, поэтому предположение № 1 применяется только к фрагментам кода, которые не вызывают функции.
- Предположим, что переменная не изменена асинхронным или одновременным действием.
- Предположим, что компилятор определяет только, может ли переменная быть изменена, а не будет ли она изменена. Другими словами, компилятор выполняет только статический анализ.
- Предположим, что компилятор рассматривает только правильно функционирующий код (не учитывая переполнение / переполнение массива, неправильные указатели и т. Д.)
В контексте дизайна компилятора, я думаю, предположения 1,3,4 имеют смысл с точки зрения автора компилятора в контексте корректности кода и / или оптимизации кода. Предположение 2 имеет смысл в отсутствие ключевого слова volatile. И эти предположения также достаточно сфокусированы на вопросе, чтобы сделать предложенный ответ более определенным:-)
Учитывая эти допущения, основная причина, по которой константность не может быть принята, связана с переменным псевдонимом. Компилятор не может знать, указывает ли другая переменная на переменную const. Псевдоним может быть вызван другой функцией в том же модуле компиляции, и в этом случае компилятор может просматривать функции и использовать дерево вызовов для статического определения возможности появления псевдонимов. Но если создание псевдонимов происходит из-за библиотеки или другого стороннего кода, то компилятор не может узнать при вводе функции, являются ли переменные псевдонимами.
Вы можете утверждать, что если переменная / аргумент помечена как const, то она не должна подвергаться изменению с помощью псевдонимов, но для автора компилятора это довольно рискованно. Даже программисту может быть рискованно объявить переменную const как часть, скажем, большого проекта, в котором он не знает поведения всей системы, или ОС, или библиотеки, чтобы действительно знать, что выигранная переменная ' т изменить.
В общем случае для компилятора невозможно определить, будет ли переменная изменена, как уже указывалось.
При проверке константности возникает интересный вопрос, может ли переменная быть изменена функцией. Даже это трудно для языков, которые поддерживают указатели. Вы не можете контролировать то, что другой код делает с указателем, он может быть даже прочитан из внешнего источника (хотя вряд ли). В языках, которые ограничивают доступ к памяти, эти типы гарантий могут быть возможны и допускают более агрессивную оптимизацию, чем в C++.
Даже если переменная объявлена 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" зависят от значения, которое может изменяться во время выполнения, во время компиляции явно не может быть определено, будет ли оно изменять "глобальное".
Эту концепцию гораздо проще понять, чем ее представляют компьютерные ученые. Если функция может делать что-то другое в зависимости от того, что может измениться во время выполнения, вы не сможете понять, что она будет делать, пока не запустится, и каждый раз, когда она запускается, она может делать что-то другое. Будет ли это доказуемо невозможно или нет, это, очевидно, невозможно.