tutorial - learn c++




為什麼不可能建立一個可以確定C++函數是否會改變特定變量值的編譯器? (9)

為什麼不可能建立這樣一個編譯器?

出於同樣的原因,您不能編寫程序來確定是否有任何給定的程序將終止。 這被稱為暫停問題 ,而這是不可計算的。

清楚的是,你可以編寫一個編譯器來確定函數在某些情況下確實會改變變量,但是你不能編寫一個能夠可靠地告訴你函數將會或者不會改變變量(或者停止)每個可能的功能。

這是一個簡單的例子:

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

編譯器如何通過查看代碼來確定foo是否會更改? 不管它是否依賴於函數外部的條件,即執行bar 。 除了證明暫停問題不可計算的證據外,還有很多,但已在鏈接的維基百科文章(以及每個計算理論教科書中)中很好地解釋了這一點,所以我不會在此嘗試正確解釋它。

我在一本書中讀到這一行:

建立一個能真正確定C ++函數是否會改變特定變量值的編譯器是不可能的。

該段討論為什麼編譯器在檢查常量時保守。

為什麼不可能建立這樣一個編譯器?

編譯器總是可以檢查變量是否被重新分配,非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

只要一個函數調用另一個編譯器沒有“看到”源的函數,它就不得不假定該變量已被改變,否則事情可能會在下面進一步出錯。 例如,假設我們在“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);
}

編譯器如何“知道” xbar沒有改變(或IS正在改變,更恰當)?

如果這不夠複雜,我相信我們可以想出更複雜的東西。


我不認為有必要調用暫停問題來解釋,在編譯時你無法通過算法知道給定的函數是否會修改某個變量。

相反,指出函數的行為常常取決於運行時條件,這是編譯器事先不知道的。 例如

int y;

int main(int argc, char *argv[]) {
   if (argc > 2) y++;
}

編譯器如何可以肯定地預測y是否會被修改?


我認為“C ++函數是否會改變特定變量的值”的關鍵詞是“will”。 當然可以構建一個編譯器來檢查是否允許 C ++函數更改特定變量的值,但不能肯定地說將會發生變化:

void maybe(int& val) {
    cout << "Should I change value? [Y/N] >";
    string reply;
    cin >> reply;
    if (reply == "Y") {
        val = 42;
    }
}

正如已經指出的那樣,編譯器通常不可能確定變量是否會改變。

檢查常量時,感興趣的問題似乎是變量是否可以通過函數進行更改。 即使這在支持指針的語言中也很難。 你不能控制其他代碼如何使用指針,它甚至可以從外部源讀取(儘管不太可能)。 在限制訪問內存的語言中,這些類型的保證是可能的,並且允許比C ++更積極的優化。


為了使這個問題更加具體,我建議下面這組約束可能是本書作者可能想到的:

  1. 假設編譯器正在檢查特定函數相對於變量的常量的行為。 為了正確性,編譯器必須假設(因為如下所述的別名),如果函數調用另一個函數變量被改變,所以假設#1僅適用於不進行函數調用的代碼片段。
  2. 假設變量未被異步或併發活動修改。
  3. 假設編譯器只確定變量是否可以被修改,而不是它是否被修改。 換句話說,編譯器只執行靜態分析。
  4. 假設編譯器只考慮正確運行的代碼(不考慮數組超出/欠載,壞指針等)

在編譯器設計的上下文中,我認為假設1,3,4在編譯器編寫者的觀點中對於代碼gen正確性和/或代碼優化是非常有意義的。 假設2在沒有volatile關鍵字的情況下有意義。 這些假設也將問題集中在足以使判斷提出的答案更加明確的問題上:-)

鑑於這些假設,無法假定恆定性的一個關鍵原因是由於可變混疊。 編譯器無法知道另一個變量是否指向const變量。 別名可能是由於同一個編譯單元中的另一個函數造成的,在這種情況下,編譯器可以查看函數並使用調用樹來靜態確定可能發生別名。 但是,如果別名是由於庫或其他外部代碼引起的,那麼編譯器無法在函數輸入中知道變量是否是別名。

你可以爭辯說,如果一個變量/參數被標記為const,那麼它不應該通過別名來改變,但是對於一個編譯器作者來說,這是非常危險的。 對於一個人類程序員來說,將一個變量const聲明為一個大項目的一部分甚至是有風險的,他不知道整個系統,操作系統或者圖書館的行為,以便真正了解一個變量,改變。


真的很驚訝,沒有直接使用暫停問題的答案! 從這個問題到停止問題有一個非常直接的減少。

想像一下,編譯器可以判斷一個函數是否改變了變量的值。 那麼它肯定能夠判斷下面的函數是否改變了y的值,假設x的值可以在整個程序的其餘部分的所有調用中被跟踪:

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

現在,對於我們喜歡的任何程序,我們將其重寫為:

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

請注意,如果且僅當我們的程序更改y的值時,才會終止 - foo()是退出前最後一件事情。 這意味著我們已經解決了暫停問題!

上述減少表明,確定變量值是否發生變化的問題至少與停滯問題一樣困難。 停止問題已知是不可信的,所以這個問題也是必須的。





compiler-construction