Я прочитал эту строчку в книге:
> это доказуемо невозможно построить компилятор, который на самом деле может
определить, является ли или не C++ функция изменит значение По конкретной переменной.
Этот пункт говорил о том, почему компилятор является консервативным при проверке на константность.
Почему невозможно построить такой компилятор?
Компилятор всегда можете проверить, если переменная переназначены не-константная функция вызывается, или если он передается как параметр const...
почему невозможно создать такой компилятор?
По той же причине, что вы можете'т написать программу, которая будет определять, является ли данная программа будет закрыта. Это известно как проблема остановки, и это's один из тех вещей, что's не вычислимым.
Чтобы было понятно, можно написать компилятор, который может определить, что функция не изменяет переменной в некоторых случаях, но вы можете'т писать одно, что достоверно указывает на то, что функция или выиграл'т изменение переменной (или прекратить) для каждой возможной функции.
Здесь'ы простой пример:
void foo() {
if (bar() == 0) this->a = 1;
}
Как может компилятор определить, просто глядя на этот код, будь то фу
не изменится а
? Является ли оно или не'т зависит от условий внешней функции, а именно осуществление бар
. Там's больше, чем это доказательство того, что проблема остановки это'т вычислимой, но это's уже хорошо объяснено в связанной статье Википедии (а в каждом вычислений, теории учебника), поэтому я'мр не пытайтесь объяснить это правильно здесь.
Представьте себе такого компилятора не существует. Позвольте's также предположить, что для удобства он предоставляет библиотечной функции, которая возвращает 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;
}
Дон'т путать то"будет или не будет изменять переменной при заданных входных данных" и для "есть путь исполнения, который изменяет переменную.&ьquot;
Бывший называется непрозрачное определение сказуемого, а это заведомо невозможно решить - помимо сокращения от проблемы остановки, можно просто указать исходные данные могут прийти из неизвестного источника (например. пользователь). Это касается всех языков, не только c++.
Последнее утверждение, правда, может быть определено, смотря на дерево разбора, который является то, что все оптимизирующие компиляторы делать. Причина они делают это чистые функции (а совершенно прозрачна функций на какое-то определение совершенно прозрачна) есть всякие приятные оптимизаций, которые могут быть применены, как легко поддерживать подстановку или имеющие свои значения, определенные во время компиляции; но, чтобы знать, если функция является чистой, мы должны знать, если он может не изменять переменные.
Так, что, кажется, удивляет заявление о C++ - это на самом деле тривиальное утверждение о всех языках.
Я думаю, что ключевое слово в "является ли функция C++ будет изменить значение определенной переменной" и есть "будет" по. Можно конечно построить компилятор, который проверяет, является ли функция c++ разрешено изменить значение определенной переменной, вы не можете с уверенностью сказать, что изменения будут происходить:
void maybe(int& val) {
cout << "Should I change value? [Y/N] >";
string reply;
cin >> reply;
if (reply == "Y") {
val = 42;
}
}
Я не'т думаю, что это's необходимый, чтобы вызвать прекращение проблему объяснить, что вы можете'т алгоритмически знать во время компиляции, является ли данная функция позволит изменять определенные переменные или нет.
Вместо этого, он'ы достаточно отметить, что функция'поведение часто зависит от выполнения условия, которое компилятор может'т знать заранее. Е. Г.
int y;
int main(int argc, char *argv[]) {
if (argc > 2) y++;
}
Как может компилятор предсказать с уверенностью, был ли г
будет изменен?
Это может быть сделано и компиляторы делают это все время для некоторых функций, это например банальная оптимизация для простых встроенные средства доступа или много чистых функций.
То, что невозможно знать это в общем случае.
Всякий раз, когда системный вызов или вызов функции из другого модуля или звонка на потенциально является overriden метод, всякое может случиться, включены враждебного поглощения какой-нибудь хакер'ы использование переполнения стека для изменения независимой переменной.
Однако, вы должны использовать 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? Чтобы определить это, вы должны сначала определить, является ли
делать множество сложных вещей часть вызывает состояние пожарной или даже более основным, будь то останавливает. Что's что-то компилятор может'т сделать.
Очень удивлена, что нет'т ответ, который, используя проблемы остановки напрямую! Там's очень прост снижение от этой проблемы к проблеме остановки.
Представьте, что компилятор может сказать, является ли функция изменить значение переменной. Тогда он наверняка смог бы сказать, являются ли приведенные ниже изменения функции значение Y или нет, предполагая, что значение X можно отследить все звонки по всей остальной части программы:
foo(int x){
if(x)
y=1;
}
Теперь, по любой программе у нас как, позвольте'ы переписать это как:
int y;
main(){
int x;
...
run the program normally
...
foo(x);
}
Обратите внимание, что, если, и только если программа изменяет значение Y, то ли его завершить - фу () - это последняя вещь, которую он делает перед выходом. Это означает, что мы'вэ решена проблема с запинками!
Чем выше сокращение показывает нам, что проблема определения того, является ли переменная's изменяет значение at least так сложно, как проблема останова. Проблема с запинками известно incomputable, так что на этот раз должно быть также.
Как только функция вызывает другую функцию, что компилятор не'т "не видеть" и источник, то или нужно предположить, что эта переменная не будет изменена, или вещи, которые могут пойти не так далее. Например, сказать, что у нас это в "фу.УОЗ" по:
void foo(int& x)
{
ifstream f("f.dat", ifstream::binary);
f.read((char *)&x, sizeof(x));
}
а у нас это в "Бар.УОЗ" по:
void bar(int& x)
{
foo(x);
}
Как может компилятор "не знаю", что X
не меняется (или меняется, более правильно) в бар
?
Я'м уверена, что мы сможем придумать что-то более сложное, если это'т достаточно сложная.
Вообще невозможно для компилятора, чтобы определить, если переменная ** быть изменено, как было указано.
При проверке Конст-ности, вопрос, интерес, кажется, если переменная может быть изменено функцией. Даже это трудно на языках, которые поддерживают указатели. Вы можете'т контролировать то, что другой код не указатель, это может быть даже чтение из внешнего источника (хотя вряд ли). В языках, которые ограничивают доступ к памяти, такие гарантии могут быть возможными и позволяет более агрессивные оптимизации, чем с++.
Чтобы сделать вопрос более конкретным, я предлагаю следующий набор ограничений может быть то, что автор книги имел в виду:
В контексте проектирования компилятор, я думаю, что предположения 1,3,4 делает совершенное чувство, по мнению писателя компилятора в контексте код Gen правильности и/или оптимизации кода. Предположение 2 имеет смысл при отсутствии volatile ключевое слово. И эти предположения также уделять достаточно вопроса, чтобы судить предложено ответить на гораздо более определенное :-)
Учитывая эти предположения, основная причина, почему константность может'т быть приняты из-за переменной сглаживания. Компилятор может'т знаю, есть ли другой переменной указывает на переменную const. Сглаживание может быть из-за другой функции в той же самой единице компиляции, в этом случае компилятор мог бы взглянуть на функции и использовать дерево называют статически определить, что сглаживание может произойти. Но если псевдоним-это из-за библиотеки или другой иностранный код, то компилятор не имеет возможности узнать, на входе функции, какие переменные являются псевдонимами.
Вы можете возразить, что если переменная/аргумент помечен как const тогда он должен'т быть изменены через псевдонимов, но для писателя-компилятора, что'ы довольно рискованно. Это может быть даже рискованным для человека-программиста, чтобы объявить переменную const а часть, скажем, крупный проект, где он не'т знаем, поведение всей системы, или ОС, или библиотеку, чтобы действительно знать, переменная выиграл't изменить.
Даже если переменная объявлена как 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
Чтобы развернуть на мой комментарий, что книга'ы текста неясно, что запутывает вопрос.
Как я прокомментировал, что книга хочет сказать, "Давайте's получают бесконечное количество обезьян писать каждую функцию мыслимые C++, который может быть написано. Есть случаи, когда если мы выберем переменную, которая (какой-то функции обезьян писал) использует, мы можем't работа, есть ли функция изменения этой переменной.&и"
Конечно, для некоторых (даже многих) функций в любой программе, Это можно определить на этапе компиляции, и очень легко. Но не для всех (или обязательно большинство).
Эта функция может быть легко проанализированы:
static int global;
void foo()
{
}
на "фу" и явно не изменить и"глобальных" по. Это не'т изменить все, что угодно, и компилятор может очень легко разобраться.
Эта функция не может быть проанализирована:
static int global;
int foo()
{
if ((rand() % 100) > 50)
{
global = 1;
}
return 1;
Так что "фу" и'ы действия зависит от того значения, которое может меняться во время выполнения, это явно не может быть определен во время компиляции* будет ли он изменять мне;глобальные " и;.
Вся эта концепция гораздо проще понять, чем компьютер ученые делают это, чтобы быть. Если функция может сделать что-то другое, основанные на вещи могут меняться во время выполнения, то вы можете'т работу, что это'будете делать, пока он работает, и при каждом запуске может сделать что-то другое. Будет ли это'ы доказуемо невозможно или нет, это'ы, очевидно, невозможно.