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 ...
c++
compiler-construction
Cricketer
źródło
źródło
Odpowiedzi:
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:
W jaki sposób kompilator może określić, po prostu patrząc na ten kod, czy
foo
kiedykolwiek się zmienia
? To, czy tak jest, czy nie, zależy od warunków zewnętrznych w stosunku do funkcji, a mianowicie od implementacjibar
. 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ć.źródło
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?
źródło
f
modyfikuje zmienną, a nie czy może modyfikować zmienną. Ta odpowiedź jest poprawna.modifies_variable
ze źródła kompilatora, całkowicie unieważniając Twój argument. (zakładając open-source, ale sprawa powinna być jasna)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.
źródło
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:
źródło
const
kontroli sprawności.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
Jak kompilator mógł przewidzieć z pewnością, czy
y
zostanie zmodyfikowany?źródło
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.
źródło
Istnieje wiele sposobów, aby to wyjaśnić, a jednym z nich jest problem zatrzymania :
Jeśli napiszę program, który wygląda tak:
Czy wartość
x
zmiany? Aby to ustalić, należałoby najpierw ustalić, czy danado tons of complex stuff
część powoduje wystąpienie warunku - lub, co bardziej podstawowe, czy się zatrzymuje. To jest coś, czego kompilator nie może zrobić.źródło
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:
Teraz dla dowolnego programu, który nam się podoba, przepiszmy go jako:
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ć.
źródło
y
. Wydaje mi się, żefoo()
szybko wraca, a potemmain()
wychodzi. (Poza tym dzwoniszfoo()
bez kłótni ... to część mojego zamieszania.)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”:
i mamy to w „bar.cpp”:
Jak kompilator może „wiedzieć”, że
x
się 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.
źródło
const_cast
in foo, to i tak wprowadziłbymx
zmianę - złamałbym umowę, która mówi, że nie możesz zmieniaćconst
zmiennych, ale ponieważ możesz przekonwertować wszystko na „bardziej stałe” iconst_cast
istnieje, projektanci języka z pewnością myśleli o tym, że czasami są dobre powody, by sądzić, żeconst
wartości mogą wymagać zmiany.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 ++.
źródło
Aby uściślić to pytanie, sugeruję następujący zestaw ograniczeń, który mógł mieć na myśli autor książki:
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ć.
źródło
Nawet jeśli zmienna jest zadeklarowana
const
, nie oznacza, że jakiś źle napisany kod może ją nadpisać.wynik:
źródło
a
ib
są zmiennymi stosu ib[1]
po prostu są w tej samej lokalizacji pamięci coa
.const
jeśli wszystko jest oznaczoneconst
. Dzieje się tak, ponieważ niezdefiniowane zachowanie jest częścią C / C ++. Próbowałem znaleźć inny sposób, aby odpowiedzieć na jego pytanie, zamiast wspominać o problemie z zatrzymaniem lub zewnętrznym wkładzie człowieka.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ć:
„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:
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.
źródło