Dlaczego nie można zbudować kompilatora, który może określić, czy funkcja C ++ zmieni wartość określonej zmiennej?

Przeczytałem ten wiersz w książce:

Nie można udowodnić, że zbudowanie kompilatora, który może faktycznie określić, czy funkcja C ++ zmieni wartość określonej zmiennej, czy nie.

W akapicie mówiono o tym, dlaczego kompilator jest konserwatywny podczas sprawdzania ciągłości.

Dlaczego nie można zbudować takiego kompilatora?

Kompilator zawsze może sprawdzić, czy zmienna jest przypisana ponownie, wywoływana jest funkcja inna niż stała lub czy jest przekazywana jako parametr inny niż stała ...

Dlaczego nie można zbudować takiego kompilatora?

Z tego samego powodu, że nie możesz napisać programu, który określi, czy dany program się zakończy. Jest to znane jako problem zatrzymania i jest to jedna z tych rzeczy, których nie można obliczyć.

Aby było jasne, możesz napisać kompilator, który może określić, że funkcja zmienia zmienną w niektórych przypadkach , ale nie możesz napisać takiego, który niezawodnie powie ci, że funkcja zmieni lub nie zmieni zmiennej (lub zatrzyma się) dla każdą możliwą funkcję.

Oto prosty przykład:

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

W jaki sposób kompilator może określić, po prostu patrząc na ten kod, czy fookiedykolwiek się zmieni a? To, czy tak jest, czy nie, zależy od warunków zewnętrznych w stosunku do funkcji, a mianowicie od implementacji bar. Dowód na to, że problemu zatrzymania nie można obliczyć, jest więcej niż to, ale jest już dobrze wyjaśniony w powiązanym artykule w Wikipedii (i w każdym podręczniku teorii obliczeń), więc nie będę próbował go tutaj poprawnie wyjaśniać.

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ą i 0, gdy funkcja tego nie robi. Co zatem 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 należy mylić „będzie lub nie będzie modyfikować zmiennej, biorąc pod uwagę, że te dane wejściowe” dla „ma ścieżkę wykonywania, która modyfikuje zmienną”.

To pierwsze nazywa się wyznaczaniem nieprzezroczystych predykatów i jest trywialnie niemożliwe do podjęcia decyzji - poza redukcją 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 można jednak określić, patrząc na drzewo parsowania, co jest czymś, co robią wszystkie kompilatory optymalizujące. Powodem jest to, że czyste funkcje (i referencyjnie przezroczyste funkcje, dla pewnej definicji referencyjnie przezroczystych ) mają wszelkiego rodzaju przyjemne optymalizacje, które można zastosować, takie jak łatwe do wstawiania lub określanie ich wartości w czasie kompilacji; ale wiedzieć, czy funkcja jest czysta, musimy wiedzieć, czy to może kiedykolwiek zmodyfikować zmienną.

To, co wydaje się być zaskakującym stwierdzeniem dotyczącym C ++, jest w rzeczywistości trywialnym stwierdzeniem dotyczącym wszystkich języków.

Myślę, że kluczowym słowem w „czy funkcja C ++ zmieni wartość określonej zmiennej” jest „wola”. Z pewnością jest możliwe zbudowanie kompilatora, który sprawdza, czy funkcja C ++ może zmieniać wartość określonej zmiennej, nie można powiedzieć z 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;
    }
}

Nie sądzę, aby konieczne było wywoływanie problemu zatrzymania, aby wyjaśnić, że nie można algorytmicznie wiedzieć w czasie kompilacji, czy dana funkcja zmodyfikuje określoną zmienną, czy nie.

Zamiast tego wystarczy wskazać, że zachowanie funkcji często zależy od warunków w czasie wykonywania, o których kompilator nie może wiedzieć z góry. Na przykład

int y;

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

Jak kompilator mógł przewidzieć z pewnością, czy yzostanie zmodyfikowany?

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

Niemożliwe jest poznanie tego w ogólnym przypadku.

Ilekroć pojawia się wywołanie systemowe lub wywołanie funkcji pochodzące z innego modułu lub wywołanie potencjalnie nadpisanej metody, może się zdarzyć wszystko, w tym wrogie przejęcie przez jakiegoś hakera przepełnienia stosu w celu zmiany niepowiązanej zmiennej.

Powinieneś jednak używać const, unikać globałów, preferować odniesienia do wskaźników, unikać ponownego wykorzystywania zmiennych do niepowiązanych zadań itp., Co ułatwi życie kompilatora podczas wykonywania agresywnych optymalizacji.

Istnieje wiele sposobów, aby to wyjaśnić, a jednym z nich jest problem zatrzymania :

W teorii obliczalności problem zatrzymania można sformułować następująco: „Mając opis dowolnego programu komputerowego, zdecyduj, czy program zakończy się, czy będzie działał bez końca”. Jest to równoważne z problemem związanym z podjęciem decyzji, biorąc pod uwagę program i dane wejściowe, czy program ostatecznie zatrzyma się po uruchomieniu z tym wejściem, czy też będzie działał w nieskończoność.

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

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ść xzmiany? Aby to ustalić, należałoby najpierw ustalić, czy dana do tons of complex stuffczęść powoduje wystąpienie warunku - lub, co bardziej podstawowe, czy się zatrzymuje. To jest coś, czego kompilator nie może zrobić.

Naprawdę zaskoczony, że nie ma odpowiedzi, że używając problemu zatrzymania bezpośrednio! Istnieje bardzo prosta redukcja od tego problemu do problemu zatrzymania.

Wyobraź sobie, że kompilator może stwierdzić, czy funkcja zmieniła wartość zmiennej. Wtedy z pewnością byłby w stanie stwierdzić, czy następująca funkcja zmienia wartość y, czy nie, zakładając, że wartość x można śledzić we wszystkich wywołaniach w pozostałej części programu:

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

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

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

Zauważ, że jeśli i tylko wtedy, gdy nasz program zmieni wartość y, to wtedy kończy się - foo () jest ostatnią rzeczą, jaką robi przed zakończeniem. Oznacza to, że rozwiązaliśmy problem zatrzymania!

Powyższa redukcja pokazuje nam, że problem ustalenia, czy zmienia się wartość zmiennej, jest co najmniej tak trudny, jak problem zatrzymania. Wiadomo, że problem zatrzymania jest nieobliczalny, więc i ten musi być.

Gdy tylko funkcja wywołuje inną funkcję, której kompilator nie „widzi” źródła, musi albo założyć, że zmienna została zmieniona, albo dalej może coś pójść nie tak. Na przykład załóżmy, ż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 „bar.cpp”:

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

Jak kompilator może „wiedzieć”, że xsię nie zmienia (lub zmienia, bardziej odpowiednio) bar?

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

Ogólnie rzecz biorąc, kompilator nie może określić, czy zmienna zostanie zmieniona, jak już wskazano.

Podczas sprawdzania stałej nasuwa się pytanie, czy zmienną można zmienić za pomocą funkcji. Nawet to jest trudne w językach, które obsługują wskaźniki. Nie możesz kontrolować tego, co robi inny kod ze wskaźnikiem, może nawet zostać odczytany z zewnętrznego źródła (choć jest to mało prawdopodobne). W językach, które ograniczają dostęp do pamięci, tego typu gwarancje mogą być możliwe i pozwalają na bardziej agresywną optymalizację niż robi to C ++.

Aby uściślić to pytanie, 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 stałej zmiennej. Dla poprawności kompilator musiałby założyć (z powodu aliasingu, jak wyjaśniono poniżej), jeśli funkcja nazywana inną funkcją zostanie zmieniona, zmienna zostanie zmieniona, więc założenie # 1 dotyczy tylko fragmentów kodu, które nie wywołują 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 zmienną można zmodyfikować, a nie, czy zostanie zmodyfikowana. Innymi słowy, kompilator wykonuje tylko analizę statyczną.
4. Załóżmy, że kompilator bierze pod uwagę tylko poprawnie działający kod (nie biorąc pod uwagę przepełnień / niedomiarów tablicy, złych wskaźników itp.)

W kontekście projektowania kompilatora, myślę, że założenia 1,3,4 mają sens z punktu widzenia autora kompilatora w kontekście poprawności generowania kodu i / lub optymalizacji kodu. Założenie 2 ma sens w przypadku braku zmiennego słowa kluczowego. Te założenia również skupiają się na pytaniu na tyle, aby ocena proponowanej odpowiedzi była znacznie bardziej ostateczna :-)

Biorąc pod uwagę te założenia, głównym powodem, dla którego nie można założyć stałej, jest aliasowanie zmiennych. Kompilator nie może wiedzieć, czy inna zmienna wskazuje na zmienną const. Aliasowanie może być spowodowane inną funkcją w tej samej jednostce kompilacji, w którym to przypadku kompilator może przejrzeć funkcje i użyć drzewa wywołań, aby statycznie określić, czy może wystąpić aliasowanie. Ale jeśli aliasowanie wynika z biblioteki lub innego obcego kodu, to kompilator nie ma możliwości dowiedzenia się po wprowadzeniu funkcji, czy zmienne są aliasowane.

Można argumentować, że jeśli zmienna / argument jest oznaczona jako stała, to nie powinna podlegać zmianie przez aliasowanie, ale dla autora kompilatora jest to dość ryzykowne. Zadeklarowanie zmiennej const jako części, powiedzmy, dużego projektu, w którym nie zna zachowania całego systemu, systemu operacyjnego lub biblioteki, może być nawet ryzykowne, aby programista naprawdę wiedział, że zmienna wygrała. t zmienić.

Nawet jeśli zmienna jest zadeklarowana const, nie oznacza, ż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;
}

wynik:

1
2

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

Jak już wspomniałem, w tej książce próbuje się powiedzieć: „zdobądźmy nieskończoną liczbę małp, aby napisać każdą możliwą funkcję C ++, jaka kiedykolwiek mogłaby zostać zapisana. Będą przypadki, w których jeśli wybierzemy zmienną, która (jakaś konkretna funkcja, którą napisały małpy) używa, nie możemy ustalić, czy funkcja zmieni tę zmienną. "

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

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

static int global;

void foo()
{
}

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

Ta funkcja nie może być tak analizowana:

static int global;

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

Ponieważ akcje "foo" zależą od wartości, która może zmieniać się w czasie wykonywania , nie można oczywiście określić w czasie kompilacji, czy zmieni ona wartość "globalną".

Cała ta koncepcja jest o wiele prostsza do zrozumienia, niż uważają ją informatycy. Jeśli funkcja może zrobić coś innego w zależności od tego, co może się zmienić w czasie wykonywania, nie możesz określić, co będzie robić, dopóki nie zostanie uruchomiona, a za każdym razem, gdy zostanie uruchomiona, może zrobić coś innego. Niezależnie od tego, czy jest to niemożliwe, czy nie, jest to oczywiście niemożliwe.