Dlaczego niemożliwe jest zbudowanie kompilatora, który potrafi określić, czy funkcja C++ zmieni wartość danej zmiennej?

Wyobraź sobie, że taki kompilator istnieje. Załóżmy również, że dla wygody udostępnia funkcję biblioteczną, która zwraca 1, jeśli przekazana funkcja modyfikuje daną zmienną, a 0, gdy funkcja nie. więc co powinien wydrukować ten program?

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;
}

Nie myl "spowoduje lub nie zmodyfikuje zmiennej biorąc pod uwagę te wejścia" dla "ma ścieżkę wykonania, która modyfikuje zmienną."

Pierwszy z nich nazywa się nieprzezroczystym określeniem predykatu i jest trywialnie niemożliwy do rozstrzygnięcia - poza redukcją z problemu zatrzymania, można po prostu wskazać, że dane wejściowe mogą pochodzić z nieznanego źródła (np. użytkownika). Dotyczy to WSZYSTKICH języków, nie tylko C++.

To ostatnie stwierdzenie, jednak, Może być określona przez patrzenie na drzewo parse, które jest czymś, co robią wszystkie Kompilatory optymalizujące. Powodem jest to, że czyste funkcje (i referencjalnie przejrzyste funkcje, dla pewnej definicji referencjalnie przejrzyste) mieć różnego rodzaju ładne optymalizacje, które mogą być stosowane, jak być łatwo inlinable lub mają ich wartości określone w czasie kompilacji; ale aby wiedzieć, czy funkcja jest czysta, musimy wiedzieć, czy może kiedykolwiek zmodyfikować zmienną.

Więc to, co wydaje się być zaskakującym stwierdzeniem o C++, jest tak naprawdę trywialnym stwierdzeniem o wszystkich językach.

Myślę, że słowem kluczowym w "whether a C++ function will change the value of a particular variable "jest " will". Z pewnością jest możliwe zbudowanie kompilatora, który sprawdza, czy funkcja C++ Może zmienić wartość danej zmiennej, nie można powiedzieć z całą pewnością, że zmiana nastąpi:

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

Myślę, że nie jest konieczne wywoływanie problemu zatrzymania, aby wyjaśnić, że nie można algorytmicznie wiedzieć w czasie kompilacji, czy dana funkcja zmodyfikuje pewną zmienną, czy nie.

Zamiast tego wystarczy zaznaczyć, że zachowanie funkcji często zależy od warunków wykonywania, o których kompilator nie może wiedzieć z góry. Np.

int y;

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

Jak kompilator mógłby przewidzieć z całą pewnością, czy y zostanie zmodyfikowany?

Można to zrobić i kompilatory robią to cały czas dla niektórych funkcji, jest to na przykład trywialna Optymalizacja dla prostych accesorów wbudowanych lub wielu czystych funkcji.

To, co jest niemożliwe, to znać go w ogólnym przypadku.

Ilekroć jest wywołanie systemowe lub wywołanie funkcji pochodzące z innego modułu lub wywołanie potencjalnie nadpisanej metody, wszystko może się zdarzyć, włączając wrogie przejęcie od jakiegoś hakera użycie przepełnienia stosu do Zmień niespokrewnioną zmienną.

Należy jednak używać const, unikać globali, preferować odniesienia do wskaźników, unikać ponownego wykorzystywania zmiennych dla niepowiązanych zadań itp. ułatwi to życie kompilatora podczas wykonywania agresywnych optymalizacji.

Istnieje wiele sposobów na wyjaśnienie tego, jednym z nich jest problem zatrzymania :

W teorii obliczeń, problem zatrzymania może być stwierdzony w następujący sposób: "biorąc pod uwagę opis dowolnego programu komputerowego, zdecyduj, czy program zakończy działanie, czy nadal będzie działać w nieskończoność". Jest to równoznaczne z problemem decydowania, biorąc pod uwagę program i dane wejściowe, czy program ostatecznie zatrzyma się po uruchomieniu z tym wejściem, czy będzie działał w nieskończoność.

Alan Turing udowodnił w 1936 roku, że ogólny algorytm rozwiązywania problemu zatrzymania dla wszystkich możliwych par program-wejście nie może istnieć.

Jeśli napiszę program, który wygląda tak:

do tons of complex stuff
if (condition on result of complex stuff)
{
    change value of x
}
else
{
    do not change value of x
}

Czy wartość x zmienia się? Aby to ustalić, najpierw musisz określić, czy część do tons of complex stuff powoduje odpalenie warunku - lub nawet bardziej podstawowe, czy się zatrzymuje. To jest coś, czego kompilator nie może zrobić.

Naprawdę zaskoczony, że nie ma odpowiedzi, że za pomocą problemu zatrzymania bezpośrednio! Istnieje bardzo prosta redukcja z tego problemu do problemu zatrzymania.

Wyobraź sobie, że kompilator może stwierdzić, czy funkcja zmieniła wartość zmiennej. Wtedy z pewnością będzie w stanie stwierdzić, czy poniższa funkcja zmienia wartość y, czy nie, zakładając, że wartość x może być śledzona we wszystkich wywołaniach przez resztę program:

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

Teraz, dla dowolnego programu, który nam się podoba, przepisz go jako:

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

Zauważ, że jeśli i tylko wtedy, nasz program zmieni wartość y, to zakończy-foo() jest ostatnią rzeczą, którą zrobi przed zakończeniem. Oznacza to, że rozwiązaliśmy problem zatrzymania!

Powyższa redukcja pokazuje nam, że problem ustalenia, czy zmienna zmienia wartość jest co najmniej tak trudny jak problem zatrzymania. Problem zatrzymania jest znany jako niezrozumiały, więc ten też musi być.

Jak tylko funkcja wywoła inną funkcję, której kompilator nie "widzi" źródła, musi albo założyć, że zmienna została zmieniona, albo coś może pójść nie tak dalej. Na przykład, powiedzmy, że mamy to w " foo.cpp": {]}

 void foo(int& x)
 {
    ifstream f("f.dat", ifstream::binary);
    f.read((char *)&x, sizeof(x));
 }

I mamy to w " barze.cpp": {]}

void bar(int& x)
{
  foo(x);
}

Skąd kompilator może "wiedzieć", że x nie zmienia się (lub zmienia się, bardziej odpowiednio) w bar?

Jestem pewien, że możemy wymyślić coś bardziej złożonego, jeśli to nie jest skomplikowane wystarczy.

Ogólnie rzecz biorąc, kompilator nie jest w stanie określić, czy zmienna będzie zmieniana, jak już wspomniano.

Podczas sprawdzania const-ness pojawia się pytanie, czy zmienna może zostać zmieniona przez funkcję. Nawet to jest trudne w językach, które obsługują wskaźniki. Nie możesz kontrolować tego, co robi inny kod za pomocą wskaźnika, może być nawet odczytany z zewnętrznego źródła (choć mało prawdopodobne). W językach, które ograniczają dostęp do pamięci, tego typu gwarancji może być możliwe i pozwala na bardziej agresywną optymalizację niż c++.

Aby pytanie było bardziej szczegółowe, sugeruję następujący zestaw ograniczeń, który mógł mieć na myśli autor książki:

1. Załóżmy, że kompilator bada zachowanie określonej funkcji w odniesieniu do const-ness zmiennej. Dla poprawności kompilator musiałby założyć (z powodu aliasingu, jak wyjaśniono poniżej), że jeśli funkcja wywołująca inną funkcję zmienna zostanie zmieniona, więc założenie #1 dotyczy tylko fragmentów kodu, które nie powodują wywołania funkcji.
2. Załóżmy, że zmienna nie jest modyfikowana przez działanie asynchroniczne lub współbieżne.
3. Załóżmy, że kompilator określa tylko, czy zmienna może zostać zmodyfikowana, a nie czy zostanie zmodyfikowana. Innymi słowy kompilator wykonuje tylko analizę statyczną.
4. Załóżmy, że kompilator rozważa tylko poprawne działanie kodu (nie bierze pod uwagę przekroczeń/niedociągnięć tablicy, złych wskaźników itp.)

W kontekście projektowania kompilatora myślę, że założenia 1,3,4 mają sens w ujęciu kompilatora w kontekście poprawności genu kodu i / lub optymalizacji kodu. Założenie 2 ma sens w przypadku braku zmiennego słowa kluczowego. I te założenia również skupiają pytanie na tyle, aby ocenić proponowaną odpowiedź znacznie bardziej definitywne: -)

Biorąc pod uwagę te założenia, kluczowym powodem, dla którego nie można przyjąć const-ness, jest zmienna aliasing. Kompilator nie może wiedzieć, czy inna zmienna wskazuje na zmienną const. Aliasing może to być spowodowane inną funkcją w tej samej jednostce kompilacji, w takim przypadku kompilator może przeglądać funkcje i używać drzewa wywołań do statycznego określenia, że może wystąpić aliasing. Ale jeśli aliasing jest spowodowany biblioteką lub innym obcym kodem, to kompilator nie ma możliwości dowiedzieć się po wprowadzeniu funkcji, czy zmienne są aliasowane.

Można argumentować, że jeśli zmienna / argument jest oznaczona const, to nie powinna być zmieniana przez aliasing, ale dla kompilatora, który jest dość ryzykowne. Może nawet być ryzykowne dla ludzkiego programisty deklarowanie zmiennej const jako części, powiedzmy dużego projektu, w którym nie zna zachowania całego systemu, systemu operacyjnego lub biblioteki, aby naprawdę wiedzieć, że zmienna się nie zmieni.

Nawet jeśli zmienna jest zadeklarowana const, nie oznacza to, że jakiś źle napisany kod może ją nadpisać.

//   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;
}

Wyjście:

1
2

Aby rozwinąć moje komentarze, tekst tej książki jest niejasny, co zaciemnia problem.

Jak skomentowałem, ta książka stara się powiedzieć: "niech nieskończona liczba małp napisze każdą możliwą funkcję C++, która kiedykolwiek mogłaby zostać napisana. Będą przypadki, w których jeśli wybierzemy zmienną, której (jakaś konkretna funkcja, którą napisali małpy) używa, nie będziemy mogli ustalić, czy funkcja zmieni tę zmienną."

Oczywiście dla niektórych (nawet wielu) funkcji w danym aplikacji, może to być określone przez kompilator i bardzo łatwo. Ale nie dla wszystkich (lub koniecznie dla większości).

Tę funkcję można łatwo przeanalizować:

static int global;

void foo()
{
}

"foo" wyraźnie nie modyfikuje "globalnego". W ogóle niczego nie modyfikuje, a kompilator może to bardzo łatwo rozwiązać.

Tej funkcji nie można tak analizować:

static int global;

int foo()
{
    if ((rand() % 100) > 50)
    {
        global = 1;
    }
    return 1;

Ponieważ działania "foo" zależą od wartości, która może się zmienić w czasie wykonywania , nie można jednoznacznie określić podczas kompilacji CZAS czy zmieni "globalny".