私は本でこの行を読みました：
C++ 関数が特定の変数の値を変更するかどうかを実際に判断できるコンパイラを構築することは、おそらく不可能です。
パラグラフは、const-ness をチェックするときにコンパイラが保守的である理由について話していました。
そのようなコンパイラを構築できないのはなぜですか?
コンパイラは、変数が再割り当てされているかどうか、非 const 関数が呼び出されているかどうか、または変数が非 const パラメーターとして渡されているかどうかを常に確認できます...
7371 次
13 に答える
140
そのようなコンパイラを構築できないのはなぜですか?
特定のプログラムが終了するかどうかを判断するプログラムを作成できないのと同じ理由で。これは停止問題として知られており、計算できない問題の 1 つです。
明確にするために、場合によっては関数が変数を変更することを判断できるコンパイラを作成できますが、関数が変数を変更するか変更しない (または停止する) かを確実に伝えるコンパイラを作成することはできません。可能なすべての機能。
簡単な例を次に示します。
void foo() {
if (bar() == 0) this->a = 1;
}
コンパイラは、そのコードを見るだけで、foo変更されるかどうかをどのように判断できaますか? 実行するかしないかは、関数の外部条件、つまり の実装に依存しますbar。停止問題が計算可能でないことの証明にはそれ以上のものがありますが、リンクされたウィキペディアの記事 (およびすべての計算理論の教科書) で既にうまく説明されているため、ここでは正しく説明しようとはしません。
于 2013-07-01T17:23:21.143 に答える
125
そのようなコンパイラが存在すると想像してください。また、便宜上、渡された関数が特定の変数を変更する場合は 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;
}
于 2013-07-01T19:13:22.830 に答える
60
「これらの入力が与えられた変数を変更する、または変更しない」を「変数を変更する実行パスを持つ」と混同しないでください。
前者はopaque predicate decision と呼ばれ、決定するのは自明のことです。停止問題からの削減は別として、入力が未知のソース (ユーザーなど) から来ている可能性があることを指摘することもできます。これは、C++ だけでなく、すべての言語に当てはまります。
ただし、後者のステートメントは、すべての最適化コンパイラが行う解析ツリーを調べることで判断できます。それらがそうする理由は、純粋な関数 （および参照透過関数のいくつかの定義では、参照透過関数）には、簡単にインライン化できる、コンパイル時に値が決定されるなど、適用できるあらゆる種類の優れた最適化があるためです。しかし、関数が純粋かどうかを知るには、変数を変更できるかどうかを知る必要があります。
したがって、C++ に関する驚くべき記述のように見えることは、実際にはすべての言語に関する些細な記述です。
于 2013-07-02T06:10:26.137 に答える
28
「C++関数が特定の変数の値を変更するかどうか」のキーワードは「意志」だと思います。C++ 関数が特定の変数の値を変更できるかどうかを確認するコンパイラを構築することは確かに可能ですが、変更が行われるとは断言できません。
void maybe(int& val) {
cout << "Should I change value? [Y/N] >";
string reply;
cin >> reply;
if (reply == "Y") {
val = 42;
}
}
于 2013-07-01T17:23:23.067 に答える
16
特定の関数が特定の変数を変更するかどうかをコンパイル時にアルゴリズム的に知ることができないことを説明するために停止問題を呼び出す必要はないと思います。
代わりに、関数の動作は多くの場合、コンパイラが事前に知ることができない実行時の条件に依存することを指摘するだけで十分です。例えば
int y;
int main(int argc, char *argv[]) {
if (argc > 2) y++;
}
コンパイラは、 が変更されるかどうかを確実に予測するにはどうyすればよいでしょうか?
于 2013-07-01T21:49:42.163 に答える
8
それは可能であり、コンパイラーは一部の関数に対して常にそれを実行しています。これは、たとえば、単純なインラインアクセサーまたは多くの純粋な関数の簡単な最適化です。
不可能なことは、一般的なケースでそれを知ることです。
システム コールや別のモジュールからの関数呼び出し、または潜在的にオーバーライドされたメソッドへの呼び出しがある場合は常に、関係のない変数を変更するためにスタック オーバーフローを使用するハッカーによる敵対的な乗っ取りなど、あらゆることが発生する可能性があります。
ただし、const を使用する、グローバルを避ける、ポインターへの参照を優先する、無関係なタスクに変数を再利用するなどを避ける必要があります。これにより、積極的な最適化を実行するときにコンパイラーの作業が楽になります。
于 2013-07-02T11:41:33.853 に答える
6
これを説明するには複数の方法があり、そのうちの 1 つが停止問題です。
計算可能性理論では、停止問題は次のように述べることができます。これは、プログラムと入力が与えられた場合、プログラムがその入力で実行されると最終的に停止するか、永久に実行されるかを決定する問題と同じです。
アラン・チューリングは 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パーツが条件を発火させるかどうか、またはさらに基本的な状態を停止するかどうかを判断する必要があります。それはコンパイラができないことです。
于 2013-07-01T17:25:19.200 に答える
6
停止問題を直接使用する答えがないことに本当に驚きました! この問題から停止問題への非常に単純な縮小があります。
関数が変数の値を変更したかどうかをコンパイラが判断できると想像してください。次に、プログラムの残りの部分のすべての呼び出しで x の値を追跡できると仮定すると、次の関数が y の値を変更するかどうかを確実に判断できます。
foo(int x){
if(x)
y=1;
}
さて、好きなプログラムを次のように書き直しましょう。
int y;
main(){
int x;
...
run the program normally
...
foo(x);
}
プログラムが y の値を変更した場合にのみ終了することに注意してください。終了する前に foo() が最後に実行されます。これは、停止の問題を解決したことを意味します。
上記の還元が示しているのは、変数の値が変化するかどうかを判断する問題は、少なくとも停止問題と同じくらい難しいということです。停止問題は計算不能であることが知られているため、これも計算不能に違いありません。
于 2013-07-02T00:20:28.993 に答える
4
コンパイラがソースを「認識」していない別の関数を関数が呼び出すとすぐに、変数が変更されたと想定する必要があります。そうしないと、さらに下で問題が発生する可能性があります。たとえば、「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ますか?
これが十分に複雑でなければ、もっと複雑なものを思い付くことができると確信しています。
于 2013-07-01T17:25:33.497 に答える
1
質問をより具体的にするために、次の一連の制約が本の著者が念頭に置いていた可能性があることを示唆しています。
- コンパイラーが、変数の const-ness に関して特定の関数の動作を調べているとします。正確を期すために、関数が別の関数を呼び出して変数が変更された場合、コンパイラは (以下で説明するエイリアシングのために) 仮定する必要があるため、仮定 #1 は関数呼び出しを行わないコード フラグメントにのみ適用されます。
- 非同期アクティビティまたは同時アクティビティによって変数が変更されていないと仮定します。
- コンパイラは、変数が変更されるかどうかではなく、変更できるかどうかのみを判断していると仮定します。つまり、コンパイラは静的解析のみを実行しています。
- コンパイラが正しく機能するコードのみを考慮していると仮定します (配列のオーバーラン/アンダーラン、不正なポインターなどは考慮していません)。
コンパイラ設計の文脈では、仮定 1、3、4 は、コード生成の正確性および/またはコード最適化の文脈でコンパイラ作成者の観点から完全に理にかなっていると思います。仮定 2 は、volatile キーワードがない場合に意味があります。そして、これらの仮定はまた、提案された回答をより決定的に判断するのに十分なほど質問に焦点を当てています:-)
これらの仮定を考えると、const-ness を仮定できない主な理由は、変数のエイリアシングによるものです。コンパイラは、別の変数が const 変数を指しているかどうかを知ることができません。エイリアシングは同じコンパイル ユニット内の別の関数が原因である可能性があります。しかし、エイリアシングがライブラリまたは他の外部コードによるものである場合、コンパイラは関数のエントリ時に変数がエイリアシングされているかどうかを知る方法がありません。
変数/引数が const とマークされている場合、エイリアシングによって変更されるべきではないと主張できますが、コンパイラの作成者にとってはかなり危険です。人間のプログラマーが、システム全体、OS、またはライブラリの動作を知らない大規模なプロジェクトの一部として、変数 const を宣言することは危険ですらあります。変わりません。
于 2013-07-02T03:55:50.277 に答える
0
変数が宣言され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
于 2013-07-01T23:57:06.963 に答える
0
私のコメントを拡張すると、その本のテキストは不明確であり、それが問題を難読化しています。
私がコメントしたように、その本は次のように言おうとしています。関数がその変数を変更するかどうかはわかりません。」
もちろん、特定のアプリケーションのいくつかの (場合によっては多くの) 関数については、これはコンパイラによって非常に簡単に決定できます。しかし、すべて（または必ずしもほとんど）ではありません。
この関数は、次のように簡単に分析できます。
static int global;
void foo()
{
}
「foo」は明らかに「global」を変更しません。何も変更しません。コンパイラはこれを非常に簡単に解決できます。
この関数はそのように分析できません:
static int global;
int foo()
{
if ((rand() % 100) > 50)
{
global = 1;
}
return 1;
「foo」のアクションは実行時に変化する可能性のある値に依存するため、「グローバル」を変更するかどうかをコンパイル時に決定することは明らかにできません。
この概念全体は、コンピューター科学者が理解するよりもはるかに簡単に理解できます。関数が実行時に変化する可能性があることに基づいて別のことを実行できる場合、実行するまでその関数が何をするかを判断できず、実行するたびに別のことを実行する可能性があります。証明不可能か否かにかかわらず、明らかに不可能です。
于 2013-07-02T22:47:36.190 に答える