Я прочитал эту строку в книге:
Невозможно построить компилятор, который может фактически определить, будет ли функция С++ изменять значение конкретная переменная.
В параграфе говорилось о том, почему компилятор консервативен при проверке на константность.
Почему невозможно построить такой компилятор?
Компилятор всегда может проверить, переназначена ли переменная, на ней вызывается функция не-const, или если она передается как неконстантный параметр...
Почему невозможно построить такой компилятор?
По той же причине, что вы не можете написать программу, которая будет определять, закончится ли какая-либо данная программа. Это называется проблемой остановки, и это одна из тех вещей, которые не могут быть вычислены.
Чтобы быть понятным, вы можете написать компилятор, который может определить, что функция действительно меняет переменную в некоторых случаях, но вы не можете написать ее, которая надежно сообщает вам, что функция будет или не будет изменять переменную (или halt) для каждой возможной функции.
Вот простой пример:
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;
}
Не путайте "будет или не будет изменять переменную, учитывая, что эти входы" для "имеет путь выполнения, который изменяет переменную."
Первый называется непрозрачным определением предикатов, и его невозможно решить - кроме сокращения проблемы с остановкой, вы можете просто указать что входные данные могут поступать из неизвестного источника (например, пользователя). Это относится ко всем языкам, а не только к С++.
Последнее утверждение, однако, может определяться путем просмотра дерева синтаксического разбора, что и делает все оптимизирующие компиляторы. Причина в том, что чистые функции (и ссылочно прозрачный функции для некоторых определений ссылочно прозрачных) имеют всевозможные хорошие оптимизации, которые могут быть применены, например, быть легко проницаемыми или определять их значения во время компиляции; но чтобы знать, является ли функция чистой, нам нужно знать, может ли она когда-либо изменять переменную.
Итак, то, что кажется удивительным утверждением о С++, фактически является тривиальным утверждением обо всех языках.
Я думаю, что ключевое слово в "будет ли функция С++ изменять значение конкретной переменной" - это "будет". Конечно, возможно создать компилятор, который проверяет, разрешено ли функции С++ изменять значение конкретной переменной, вы не можете с уверенностью сказать, что это произойдет:
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 не изменяется (или изменится IS более соответствующим образом) в bar?
Я уверен, что мы можем придумать что-то более сложное, если это недостаточно сложно.
В общем случае невозможно, чтобы компилятор определял, будет ли изменена переменная, как было указано.
При проверке константы возникает вопрос интереса, если переменная может быть изменена функцией. Даже это трудно в языках, поддерживающих указатели. Вы не можете контролировать, что делает другой код с помощью указателя, его можно даже прочитать из внешнего источника (хотя и маловероятно). В языках, которые ограничивают доступ к памяти, эти типы гарантий могут быть возможны и обеспечивают более агрессивную оптимизацию, чем С++.
Даже если объявлена переменная 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
Чтобы сделать вопрос более конкретным, я предлагаю, что следующий набор ограничений мог быть тем, что мог иметь в виду автор книги:
В контексте конструкции компилятора, я думаю, что предположения 1,3,4 имеют смысл с точки зрения автора компилятора в контексте правильности кода и/или оптимизации кода. Предположение 2 имеет смысл в отсутствие ключевого слова volatile. И эти предположения также сфокусируют вопрос достаточно, чтобы судить о предлагаемом ответе гораздо более определенно:-)
Учитывая эти предположения, ключевая причина, почему constness нельзя предположить, связана с переменным псевдонимом. Компилятор не может знать, указывает ли другая переменная на переменную const. Алиасинг может быть вызван другой функцией в одном модуле компиляции, и в этом случае компилятор может просматривать функции и использовать дерево вызовов, чтобы статически определять, что может выполняться сглаживание. Но если сглаживание происходит из-за библиотеки или другого внешнего кода, тогда компилятор не имеет возможности узнать о записи функции, являются ли переменные псевдонимами.
Вы можете утверждать, что если переменная/аргумент помечена как const, она не должна подвергаться изменениям с помощью псевдонимов, но для писателя-компилятора это довольно рискованно. Человеку-программисту может быть даже рискованно объявлять переменную const как часть, скажем, большого проекта, где он не знает поведения всей системы или ОС или библиотеки, чтобы действительно знать переменную won ' t.
Чтобы расширить мои комментарии, этот текст книги неясен, что затуманивает проблему.
Как я уже говорил, эта книга пытается сказать: "Позвольте получить бесконечное количество обезьян, чтобы написать любую мыслимую функцию С++, которая могла когда-либо быть написана. Будут случаи, когда мы выбираем переменную, которая (какая-то конкретная функция обезьяны писали), мы не можем решить, изменит ли эта переменная эту переменную."
Конечно, для некоторых (даже многих) функций в любом конкретном приложении это может быть определено компилятором и очень легко. Но не для всех (или обязательно для большинства).
Эта функция может быть легко проанализирована:
static int global;
void foo()
{
}
"foo" явно не изменяет "глобальный". Он вообще ничего не изменяет, и компилятор может легко справиться с этим.
Эта функция не может быть проанализирована так:
static int global;
int foo()
{
if ((rand() % 100) > 50)
{
global = 1;
}
return 1;
Так как действия "foo" зависят от значения, которое может меняться во время выполнения, он явно не может быть определен во время компиляции, будет ли он изменять "глобальный".
Все это понятие намного проще понять, чем это делают компьютерные ученые. Если функция может делать что-то другое в зависимости от того, что может измениться во время выполнения, то вы не можете решить, что она будет делать, пока она не запустится, и каждый раз, когда она запускается, она может сделать что-то другое. Независимо от того, невозможно ли это или нет, это, очевидно, невозможно.