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

104

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 ...

Cricketer
źródło
24
Pierwszą rzeczą, która przychodzi mi do głowy, są biblioteki dołączane dynamicznie. Jeśli ja kompiluję kod na moim komputerze, a ty kompilujesz kod na twoim komputerze i łączymy je w czasie wykonywania , skąd Twój kompilator może wiedzieć, czy zmodyfikowałem zmienne, czy nie?
Mooing Duck
4
@MooingDuck Dokładnie to. Mówiąc szerzej, kompilator nie kompiluje funkcji indywidualnie, ale kompiluje ją jako część szerszego obrazu, który może nie być w całości objęty zakresem działania kompilatora.
call2voyage
3
„niemożliwe” może być przesadą - „niewykonalne obliczeniowo” (jak w NP-trudne) może być lepszą charakterystyką, ale jest nieco trudniejsze do zrozumienia dla ucznia. Wyobraź sobie połączoną listę lub inną abstrakcyjną strukturę danych. Jeśli wywołam funkcję, która zmienia jeden węzeł na tej liście / drzewie / cokolwiek, jak kompilator mógłby kiedykolwiek mieć nadzieję na udowodnienie, który dokładnie węzeł został zmodyfikowany (a może co ważniejsze, który nie został) bez zasadniczo pełnej symulacji programu za pomocą oczekiwane dane wejściowe, a kompilacja jednego pliku źródłowego nie zajmuje 3 dni ...
twalberg
36
@twalberg Niemożliwe nie jest przesadą, problem zatrzymania dotyczy tutaj, jak wyjaśnia kilka odpowiedzi. Po prostu nie jest możliwa pełna algorytmiczna analiza ogólnego programu.
Fiktik
5
Kompilatory @twalberg, które kompilują tylko podzbiór prawidłowych programów, nie są zbyt przydatne.
Caleb

Odpowiedzi:

139

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ć.

Caleb
źródło
48
@mrsoltys, komputery kwantowe są „tylko” wykładniczo szybsze w przypadku niektórych problemów, nie mogą rozwiązać nierozstrzygalnych problemów.
zch
8
@mrsoltys Te wykładniczo skomplikowane algorytmy (jak faktoring) są idealne dla komputerów kwantowych, ale zatrzymanie problemu jest logicznym dylematem, nie da się go obliczyć bez względu na to, jaki masz komputer.
user1032613
7
@mrsoltys, żeby być sprytnym, tak, to by się zmieniło. Niestety oznaczałoby to, że algorytm został zakończony i nadal działa, niestety nie można powiedzieć, który bez bezpośredniej obserwacji wpływa na stan faktyczny.
Nathan Ernst
9
@ ThorbjørnRavnAndersen: OK, więc przypuśćmy, że wykonuję program. Jak dokładnie mam określić, czy to się zakończy?
ruakh
8
@ ThorbjørnRavnAndersen Ale jeśli faktycznie wykonasz program, który się nie zakończy (np. Nieskończona pętla), nigdy się nie dowiesz, że się nie kończy ... po prostu wykonujesz jeszcze jeden krok, ponieważ może to być ostatni ...
MaxAxeHax
124

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;
}
orlp
źródło
12
Miły! Jestem paradoksem kłamcą jak napisany przez programistę.
Krumelur
28
Właściwie jest to po prostu ładna adaptacja słynnego dowodu na nierozstrzygalność problemu zatrzymania .
Konstantin Weitz
10
W tym konkretnym przypadku "modify_variable" powinno zwrócić prawdę: istnieje przynajmniej jedna ścieżka wykonania, w której zmienna jest rzeczywiście modyfikowana. A ta ścieżka wykonania jest osiągnięta po wywołaniu zewnętrznej, niedeterministycznej funkcji - więc cała funkcja jest niedeterministyczna. Z tych dwóch powodów kompilator powinien przyjąć pogląd pesymistyczny i zdecydować, że modyfikuje zmienną. Jeśli ścieżka do modyfikowania zmiennej zostanie osiągnięta po deterministycznym porównaniu (weryfikowalnym przez kompilator) daje wynik fałsz (tj. „1 == 1”), to kompilator może śmiało powiedzieć, że taka funkcja nigdy nie modyfikuje zmiennej
Joe Pineda
6
@JoePineda: Pytanie brzmi, czy fmodyfikuje zmienną, a nie czy może modyfikować zmienną. Ta odpowiedź jest poprawna.
Neil G,
4
@JoePineda: nic nie stoi na przeszkodzie, aby skopiować / wkleić kod modifies_variableze źródła kompilatora, całkowicie unieważniając Twój argument. (zakładając open-source, ale sprawa powinna być jasna)
orlp,
60

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.

BlueRaja - Danny Pflughoeft
źródło
5
To najlepsza odpowiedź, imho, ważne jest, aby to rozróżnić.
UncleZeiv
„trywialnie niemożliwe”?
Kip
2
@Kip „trywialnie niemożliwe do rozstrzygnięcia” prawdopodobnie oznacza „niemożliwe do rozstrzygnięcia, a dowód jest trywialny”.
fredoverflow
28

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;
    }
}
dasblinkenlight
źródło
„Z pewnością jest możliwe zbudowanie kompilatora, który sprawdza, czy funkcja C ++ może zmienić wartość określonej zmiennej” Nie, nie jest. Zobacz odpowiedź Caleba. Aby kompilator wiedział, czy foo () może zmienić a, musiałby wiedzieć, czy bar () może zwrócić 0. I nie ma obliczalnej funkcji, która mogłaby podać wszystkie możliwe wartości zwracane przez jakąkolwiek obliczalną funkcję. Istnieją więc takie ścieżki kodu, że kompilator nie będzie w stanie stwierdzić, czy kiedykolwiek zostaną osiągnięte. Jeśli zmienna zostanie zmieniona tylko w ścieżce kodu, do której nie można dotrzeć, to się nie zmieni, ale kompilator jej nie wykryje
Martin Epsz
12
@MartinEpsz Przez „może” mam na myśli „wolno się zmienić”, a nie „może ewentualnie zmienić”. Wierzę, że to właśnie miał na myśli OP, mówiąc o constkontroli sprawności.
dasblinkenlight
@dasblinkenlight Muszę się zgodzić, że moim zdaniem PO mógł oznaczać pierwszy, „można zmienić” lub „może lub nie może się zmienić” a „na pewno się nie zmieni”. Oczywiście nie mogę wymyślić scenariusza, w którym byłby to problem. Możesz nawet zmodyfikować kompilator, aby po prostu odpowiadał „może zmienić” na dowolnej funkcji zawierającej identyfikator lub wywołanie funkcji, która ma atrybut odpowiedzi „może zmienić”. To powiedziawszy, C i C ++ to okropne języki, z którymi warto to wypróbować, ponieważ mają tak luźną definicję rzeczy. Myślę, że właśnie dlatego ciągłość byłaby w ogóle problemem w C ++.
DDS,
@MartinEpsz: "I nie ma obliczalnej funkcji, która może podać wszystkie możliwe wartości zwracane przez jakąkolwiek obliczalną funkcję". Myślę, że sprawdzanie „wszystkich możliwych wartości zwracanych” jest podejściem niepoprawnym. Istnieją systemy matematyczne (maxima, mathlab), które potrafią rozwiązywać równania, co oznacza, że ​​sensowne byłoby zastosowanie podobnego podejścia do funkcji. Traktuję to jako równanie z kilkoma niewiadomymi. Problemami są kontrola przepływu + efekty uboczne => nierozwiązywalne sytuacje. IMO, bez tego (język funkcjonalny, brak przypisania / skutków ubocznych), dałoby się przewidzieć, którą ścieżkę zajmie program
SigTerm
16

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?

LarsH
źródło
7

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.

kriss
źródło
1
Jeśli dobrze to sobie przypominam, o to właśnie chodzi w programowaniu funkcjonalnym, prawda? Korzystając tylko z czysto deterministycznych funkcji bez skutków ubocznych, kompilatory mogą swobodnie przeprowadzać agresywne optymalizacje, przed wykonaniem, po wykonaniu, zapamiętywanie, a nawet wykonywanie w czasie kompilacji. Kwestia, którą myślę, że wielu respondentów ignoruje (lub jest zdezorientowana), jest taka, że jest to rzeczywiście możliwe w przypadku dobrze zachowującego się podzbioru wszystkich programów . I nie, ten podzbiór nie jest trywialny ani nieinteresujący, w rzeczywistości jest bardzo przydatny. Ale jest to rzeczywiście niemożliwe w absolutnie ogólnym przypadku.
Joe Pineda,
Przeciążanie to pojęcie czasu kompilacji. Prawdopodobnie miałeś na myśli „metodę zastępowaną”.
fredoverflow
@FredOverflow: tak, mam na myśli przesłonięcie. Przeciążanie jest rzeczywiście pojęciem czasu kompilacji. Dzięki za wykrycie tego (oczywiście jeśli implementacja pochodzi z innej jednostki kompilującej, kompilator nadal może mieć problemy z jej analizą, ale nie o to mi chodziło). Naprawię odpowiedź.
kriss
6

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ć.

Timothy Shields
źródło
6

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ć.

John Doucette
źródło
Nie jestem pewien, czy rozumiem twoje rozumowanie, dlaczego nasz program kończy działanie, jeśli zmienia wartość y. Wydaje mi się, że foo()szybko wraca, a potem main()wychodzi. (Poza tym dzwonisz foo()bez kłótni ... to część mojego zamieszania.)
LarsH,
1
@LarsH: Jeśli zmodyfikowany program zakończy działanie, ostatnią wywołaną funkcją była f. Jeśli y zostało zmodyfikowane, wywołano f (inne instrukcje nie mogą zmienić y, ponieważ zostało wprowadzone tylko przez modyfikację). Stąd, jeśli y został zmodyfikowany, program kończy działanie.
MSalters
4

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.

Mats Petersson
źródło
Kompilator może wiedzieć, że x nie zmienia się w bar, jeśli bar x jest przekazywany jako pass-by-reference-to-const, prawda?
Cricketer
Tak, ale jeśli dodam a const_castin foo, to i tak wprowadziłbym xzmianę - złamałbym umowę, która mówi, że nie możesz zmieniać constzmiennych, ale ponieważ możesz przekonwertować wszystko na „bardziej stałe” i const_castistnieje, projektanci języka z pewnością myśleli o tym, że czasami są dobre powody, by sądzić, że constwartości mogą wymagać zmiany.
Mats Petersson
@MatsPetersson: Uważam, że jeśli wykonasz const_cast, możesz zachować wszystkie elementy, które się psują, ponieważ kompilator może, ale nie musi tego kompensować.
Zan Lynx
@ZanLynx: Tak, jestem pewien, że to prawda. Ale jednocześnie obsada istnieje, co oznacza, że ​​ktoś, kto zaprojektował język, miał pewien pomysł, że „może nam się to kiedyś przydać” - co oznacza, że ​​w ogóle nie ma to nic pożytecznego.
Mats Petersson
1

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 ++.

Krumelur
źródło
2
Jedną rzeczą, którą chciałbym uzyskać w językach, jest rozróżnienie między ulotnymi, zwrotnymi i trwałymi odniesieniami (lub wskaźnikami). Odwołania efemeryczne można kopiować tylko do innych odniesień ulotnych, zwrotne można skopiować do odniesień ulotnych lub zwrotnych, a trwałe można skopiować w dowolny sposób. Zwracana wartość funkcji będzie ograniczona przez najbardziej restrykcyjne argumenty przekazywane jako parametry „zwrotne”. Uważam za niefortunne, że w wielu językach, gdy podaje się odniesienie, nie ma nic wskazującego, jak długo można go używać.
supercat
To z pewnością byłoby przydatne. Oczywiście są do tego schematy, ale w C ++ (i wielu innych językach) zawsze można „oszukiwać”.
Krumelur
Głównym sposobem, w jaki .NET jest lepszy od Javy, jest to, że ma koncepcję efemerycznego odniesienia, ale niestety nie ma sposobu, aby obiekty ujawniały właściwości jako efemeryczne odwołania (naprawdę chciałbym zobaczyć sposób który kod wykorzystujący właściwość przekazałby efemeryczne odniesienie do kodu (wraz ze zmiennymi tymczasowymi), którego należy użyć do manipulowania obiektem.
supercat
1

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ć.

Χpẘ
źródło
0

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
Mark Lakata
źródło
Dzieje się tak, ponieważ zmienne stosu ai bsą zmiennymi stosu i b[1]po prostu są w tej samej lokalizacji pamięci co a.
Mark Lakata,
1
-1. Undefined Behavior usuwa wszystkie ograniczenia dotyczące zachowania kompilatora.
MSalters
Nie jestem pewien co do głosu przeciwnego. To tylko przykład odnoszący się do pierwotnego pytania OP, dlaczego kompilator nie może dowiedzieć się, czy coś jest naprawdę, constjeśli wszystko jest oznaczone const. 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.
Mark Lakata,
0

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.

El Zorko
źródło
to, co mówisz, jest prawdą, ale nawet dla bardzo prostych programów, dla których wszystko jest znane w czasie kompilacji, nie będziesz w stanie niczego udowodnić, nawet tego, że program się zatrzyma. To jest problem z zatrzymaniem. Na przykład możesz napisać program oparty na Hailstone Sequences en.wikipedia.org/wiki/Collatz_conjecture i sprawić, że zwróci on prawdę, jeśli zbiegnie się do jednego. Kompilatory nie będą w stanie tego zrobić (ponieważ w wielu przypadkach byłoby to przepełnione), a nawet matematycy nie wiedzą, czy to prawda, czy nie.
kriss
Jeśli masz na myśli „istnieją pewne bardzo proste wyglądających programów, dla których nie można niczego udowodnić” Ja całkowicie zgadzam. Ale klasyczny dowód zatrzymania problemu Turinga polega zasadniczo na tym, że sam program jest w stanie stwierdzić, czy zatrzymuje się, aby ustawić sprzeczność. Ponieważ jest to matematyka, a nie implementacja. Z pewnością istnieją programy, w których jest całkowicie możliwe statyczne określenie w czasie kompilacji, czy dana zmienna zostanie zmodyfikowana i czy program się zatrzyma. Może nie da się tego matematycznie udowodnić, ale w niektórych przypadkach jest to praktycznie osiągalne.
El Zorko,