Dowód, że martwy kod nie może zostać wykryty przez kompilatory

Planuję uczyć kurs zimowy na różną liczbę tematów, z których jednym będą kompilatory. Teraz natknąłem się na ten problem, myśląc o zadaniach do wykonania przez cały kwartał, ale to mnie zaskoczyło, więc mogę go użyć jako przykładu.

public class DeadCode {
  public static void main(String[] args) {
     return;
     System.out.println("This line won't print.");
  }
}

W powyższym programie oczywiste jest, że instrukcja print nigdy nie zostanie wykonana z powodu return. Kompilatory czasami dają ostrzeżenia lub błędy dotyczące martwego kodu. Na przykład powyższy kod nie będzie kompilowany w Javie. Kompilator javac nie wykryje jednak wszystkich wystąpień martwego kodu w każdym programie. Jak mam udowodnić, że żaden kompilator nie może tego zrobić?

Wszystko wynika z nierozstrzygalności problemu zatrzymania. Załóżmy, że mamy „idealną” funkcję martwego kodu, trochę maszyny Turinga M i trochę łańcucha wejściowego x oraz procedurę, która wygląda mniej więcej tak:

Run M on input x;
print "Finished running input";

Jeśli M działa wiecznie, usuwamy instrukcję print, ponieważ nigdy jej nie osiągniemy. Jeśli M nie działa wiecznie, musimy zachować instrukcję print. Tak więc, jeśli mamy narzędzie do usuwania martwych kodów, pozwala nam to również rozwiązać problem zatrzymania, więc wiemy, że nie może istnieć takie narzędzie do usuwania martwych kodów.

Poradzimy sobie z tym poprzez „konserwatywne zbliżenie”. Tak więc w powyższym przykładzie maszyny Turinga możemy założyć, że uruchomienie M na x może zakończyć się, więc gramy to bezpiecznie i nie usuwamy instrukcji print. W twoim przykładzie wiemy, że bez względu na to, które funkcje działają, czy nie, nie ma możliwości, abyśmy osiągnęli tę instrukcję print.

Zwykle odbywa się to poprzez zbudowanie „grafu kontrolno-przepływowego”. Przyjmujemy założenia upraszczające, takie jak „koniec pętli while jest połączony z początkiem, a instrukcja po”, nawet jeśli działa wiecznie lub działa tylko raz i nie odwiedza obu. Podobnie zakładamy, że instrukcja if może dotrzeć do wszystkich swoich gałęzi, nawet jeśli w rzeczywistości niektóre z nich nigdy nie są używane. Tego rodzaju uproszczenia pozwalają nam usunąć „oczywiście martwy kod”, taki jak podany przez Ciebie przykład, przy jednoczesnym zachowaniu rozstrzygalności.

Aby wyjaśnić kilka nieporozumień w komentarzach:

1. Nitpick: dla ustalonego M jest to zawsze rozstrzygalne. Wejściem musi być M.

   Jak mówi Raphael, w moim przykładzie rozważamy maszynę Turinga jako dane wejściowe. Chodzi o to, że gdybyśmy mieli doskonały algorytm DCE, moglibyśmy stworzyć fragment kodu, który podam dla dowolnej maszyny Turinga , a posiadanie DCE rozwiązałoby problem zatrzymania.

2. nieprzekonany. return jako tępa instrukcja w bezpośrednim wykonaniu bez rozgałęzienia nie jest trudna do podjęcia. (a mój kompilator mówi mi, że jest w stanie to rozgryźć)

   Jeśli chodzi o problem, który podnosi njzk2: masz absolutną rację, w tym przypadku możesz ustalić, że nie ma możliwości uzyskania instrukcji po uzyskaniu zwrotu. Wynika to z faktu, że jest wystarczająco prosty, abyśmy mogli opisać jego nieosiągalność za pomocą ograniczeń grafu kontrolnego (tzn. Nie ma żadnych krawędzi wychodzących z instrukcji return). Ale nie ma doskonałego eliminatora martwego kodu, który eliminuje cały nieużywany kod.

3. Nie biorę dowodu zależnego od danych wejściowych. Jeśli istnieje taki rodzaj danych wejściowych użytkownika, który może pozwolić na skończenie kodu, kompilator może założyć, że kolejna gałąź nie jest martwa. Nie widzę, po co są te wszystkie głosy poparcia, jest to zarówno oczywiste (np. Niekończące się standardowe wejście), jak i złe.

   Dla TomášZato: tak naprawdę nie jest to dowód zależny od danych wejściowych. Zinterpretuj to raczej jako „forall”. Działa w następujący sposób: załóżmy, że mamy doskonały algorytm DCE. Jeśli podasz mi dowolną maszynę Turinga M i wprowadzisz x, mogę użyć mojego algorytmu DCE do ustalenia, czy M się zatrzymuje, konstruując powyższy fragment kodu i sprawdzając, czy instrukcja print została usunięta. Ta technika polegająca na pozostawieniu parametru arbitralnego w celu udowodnienia zdania forall jest powszechna w matematyce i logice.

   Nie do końca rozumiem punkt widzenia TomášZato o skończeniu kodu. Z pewnością kod jest skończony, ale doskonały algorytm DCE musi mieć zastosowanie do całego kodu, który jest zestawem infinte. Podobnie, mimo że sam kod jest skończony, potencjalne zestawy danych wejściowych są nieskończone, podobnie jak potencjalny czas działania kodu.

   Jeśli chodzi o rozważenie, że końcowa gałąź nie jest martwa: jest bezpieczna w kategoriach „konserwatywnego przybliżenia”, o którym mówię, ale nie wystarczy wykrycie wszystkich przypadków martwego kodu, o które prosi OP.

Rozważ taki kod:

while (true)
  print "Hello"
print "goodbye"

Oczywiście możemy usunąć print "goodbye"bez zmiany zachowania programu. Jest to więc martwy kod. Ale jeśli (true)w whilewarunku występuje inne wywołanie funkcji , nie wiemy, czy możemy je usunąć, czy nie, co prowadzi do nierozstrzygalności.

Zauważ, że sam tego nie wymyślę. Jest to dobrze znany wynik w teorii kompilatorów. Jest to omówione w The Tiger Book . (Być może możesz zobaczyć, o czym mówią w książkach Google .

Jest to zwrot w odpowiedzi Jmite, który omija potencjalne zamieszanie związane z brakiem rozwiązania. Dam program, który zawsze się zatrzymuje, może mieć martwy kod, ale nie możemy (zawsze) algorytmicznie decydować, czy ma.

Rozważ następującą klasę danych wejściowych dla identyfikatora martwego kodu:

simulateMx(n) {
  simulate TM M on input x for n steps
  if M did halt
    return 0
  else
    return 1
}

Ponieważ Mi xsą poprawione, simulateMsma martwy kod z return 0i tylko wtedy, Mgdy się nie zatrzymuje x.

To natychmiast daje nam redukcję problemu zatrzymania do sprawdzania martwego kodu: biorąc pod uwagę TM jako przykład problemu zatrzymania, stwórz powyższy program z kodem - ma martwy kod wtedy i tylko wtedy, gdy nie zatrzymuje się sam kod.$M$x$M$$M$

Dlatego sprawdzanie martwego kodu nie jest obliczalne.

Jeśli nie jesteś zaznajomiony z redukcją jako techniką dowodową w tym kontekście, polecam nasz materiał referencyjny .

Prostym sposobem wykazania tego rodzaju własności bez zagłębiania się w szczegóły jest użycie następującego lematu:

Lemma: Dla każdego kompilatora C dla języka pełnego Turinga istnieje funkcja, undecidable_but_true()która nie przyjmuje argumentów i zwraca wartość logiczną true, tak że C nie może przewidzieć, czy undecidable_but_true()zwróci true lub false.

Zauważ, że funkcja zależy od kompilatora. Biorąc pod uwagę funkcję undecidable_but_true1(), kompilator można zawsze rozszerzyć o wiedzę, czy ta funkcja zwraca wartość prawda czy fałsz; ale zawsze jest jakaś inna funkcja undecidable_but_true2(), która nie będzie objęta.

Dowód: według twierdzenia Rice'a właściwość „ta funkcja zwraca wartość true” jest nierozstrzygalna. Dlatego żaden algorytm analizy statycznej nie jest w stanie zdecydować o tej właściwości dla wszystkich możliwych funkcji.

Następstwo: biorąc pod uwagę kompilator C, następujący program zawiera martwy kod, którego nie można wykryć:

if (!undecidable_but_true()) {
    do_stuff();
}

Uwaga na temat Java: język Java nakazuje, aby kompilatory odrzucały niektóre programy zawierające nieosiągalny kod, jednocześnie rozsądnie nakazując, aby kod był dostarczany we wszystkich osiągalnych punktach (np. Przepływ sterujący w funkcji nie-void musi kończyć się returninstrukcją). Język określa dokładnie, w jaki sposób przeprowadzana jest nieosiągalna analiza kodu; jeśli nie, pisanie programów przenośnych byłoby niemożliwe. Biorąc pod uwagę program formularza

some_method () {
    <code whose continuation is unreachable>
    // is throw InternalError() needed here?
}

konieczne jest określenie, w których przypadkach po nieosiągalnym kodzie musi znajdować się jakiś inny kod, a w których przypadkach nie może występować żaden kod. Przykład programu Java, który zawiera kod, który jest nieosiągalny, ale nie w sposób, który mogą zauważyć kompilatory Java, pojawia się w Javie 101:

String day_of_week(int n) {
    switch (n % 7) {
    case 0: return "Sunday";
    case 1: case -6: return "Monday";
    …
    case 6: case -1: return "Saturday";
    }
    // return or throw is required here, even though this point is unreachable
}

Odpowiedź jmite dotyczy tego, czy program kiedykolwiek zakończy obliczenia - tylko dlatego, że jest nieskończony, nie wywołałbym kodu po jego śmierci.

Istnieje jednak inne podejście: problem, na który istnieje odpowiedź, ale nie jest znana:

public void Demo()
{
  if (Chess.Evaluate(new Chessboard(), int.MaxValue) != 0)
    MessageBox.Show("Chess is unfair!");
  else
    MessageBox.Show("Chess is fair!");
}

public class chess
{
  public Int64 Evaluate(Chessboard Board, int SearchDepth)
  {
  ...
  }
}

Procedura ta niewątpliwie ma zawierać martwego kodu - funkcja zwróci odpowiedź, która wykonuje jedną ścieżkę, ale nie innych. Powodzenia w znalezieniu go! Moja pamięć nie jest żadnym teoretycznym komputerem, który mógłby rozwiązać ten problem w ciągu życia wszechświata.

Bardziej szczegółowo:

W Evaluate()Oblicza funkcja, która strona wygrywa Chess Games jeśli obie strony doskonale grać (z maksymalną głębokością wyszukiwania).

Oceniający szachy zwykle patrzą przed siebie przy każdym możliwym ruchu na pewną określoną głębokość, a następnie próbują punktować planszę w tym punkcie (czasami rozszerzanie niektórych gałęzi dalej, ponieważ spojrzenie w połowie wymiany lub temu podobne może powodować bardzo wypaczoną percepcję). Ponieważ rzeczywista maksymalna głębokość wynosi 17695 ruchów na pół, wyszukiwanie jest wyczerpujące, przemierzy każdą możliwą grę w szachy. Ponieważ wszystkie gry się kończą, nie ma problemu z podjęciem decyzji o tym, jak dobra jest pozycja każdej planszy (a zatem nie ma powodu, aby patrzeć na logikę oceny planszy - nigdy nie zostanie wywołana), wynikiem jest wygrana, przegrana lub rysunek. Jeśli wynikiem jest remis, gra jest sprawiedliwa, jeśli wynikiem nie jest remis, jest to gra niesprawiedliwa. Aby ją nieco rozszerzyć, otrzymujemy:

public Int64 Evaluate(Chessboard Board, int SearchDepth)
{
  foreach (ChessMove Move in Board.GetPossibleMoves())
    {
      Chessboard NewBoard = Board.MakeMove(Move);
      if (NewBoard.Checkmate()) return int.MaxValue;
      if (NewBoard.Draw()) return 0;
      if (SearchDepth == 0) return NewBoard.Score();
      return -Evaluate(NewBoard, SearchDepth - 1);
    }
}

Zauważ też, że kompilator praktycznie nie będzie mógł zrozumieć, że Chessboard.Score () jest martwym kodem. Znajomość zasad gry w szachy pozwala nam to zrozumieć, ale aby to zrozumieć, musisz wiedzieć, że MakeMove nigdy nie może zwiększyć liczby sztuk i że Chessboard.Draw () zwróci wartość true, jeśli liczba sztuk pozostanie statyczna przez zbyt długi czas .

Zauważ, że głębokość wyszukiwania jest w pół-ruchach, a nie w całości. Jest to normalne dla tego rodzaju procedury AI, ponieważ jest to procedura O (x ^ n) - dodanie jeszcze jednej warstwy wyszukiwania ma znaczący wpływ na czas działania.

Myślę, że w kursie komputerowym pojęcie martwego kodu jest interesujące w kontekście zrozumienia różnicy między czasem kompilacji a czasem wykonywania!

Kompilator może ustalić, kiedy masz kod, którego w żadnym scenariuszu kompilacji nie można kiedykolwiek przejść, ale nie może tego zrobić w przypadku środowiska wykonawczego. pokazuje to prosta pętla while z danymi wejściowymi użytkownika do testu przerwania pętli.

Jeśli kompilator rzeczywiście może ustalić martwy kod środowiska wykonawczego (tzn. Rozpoznaje ukończenie Turinga), istnieje argument, że kod nigdy nie musi być uruchamiany, ponieważ zadanie zostało już wykonane!

Co więcej, istnienie kodu, który przechodzi sprawdzanie martwego kodu w czasie kompilacji, ilustruje potrzebę pragmatycznego sprawdzania ograniczeń danych wejściowych i ogólnej higieny kodowania (w prawdziwym świecie prawdziwych projektów).