Beweisen Sie, dass toter Code von Compilern nicht erkannt werden kann

32

Ich plane einen Winterkurs zu verschiedenen Themen, von denen eines Compiler sein wird. Nun, ich bin auf dieses Problem gestoßen, als ich über Aufträge nachgedacht habe, die während des gesamten Quartals zu vergeben waren, aber es hat mich ratlos gemacht, sodass ich es stattdessen als Beispiel verwenden könnte.

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

Im obigen Programm ist es offensichtlich, dass die print-Anweisung wegen der nie ausgeführt wird return. Compiler geben manchmal Warnungen oder Fehler über toten Code aus. Beispielsweise wird der obige Code in Java nicht kompiliert. Der Javac-Compiler erkennt jedoch nicht alle Instanzen von totem Code in jedem Programm. Wie würde ich beweisen, dass kein Compiler dies kann?

Thomas
quelle
29
Was ist Ihr Hintergrund und in welchem ​​Kontext werden Sie unterrichten? Um ehrlich zu sein, mache ich mir ein wenig Sorgen, dass Sie dies fragen müssen, da Sie unterrichten werden. Aber gut anrufen und hier fragen!
Raphael
9
@ MichaelKjörling Dead Code Detection ist auch ohne diese Überlegungen nicht möglich.
David Richerby
2
BigInteger i = 0; while(isCollatzConjectureTrueFor(i)) i++; printf("Hello world\n");
user253751
2
@immibis Die Frage verlangt den Beweis, dass die Erkennung von totem Code unmöglich ist . Sie haben ein Beispiel angegeben, in dem eine korrekte Erkennung von totem Code die Lösung eines offenen Problems in der Mathematik erfordert. Dies beweist nicht , dass eine Erkennung von totem Code unmöglich ist .
David Richerby

Antworten:

57

Es kommt alles von der Unentscheidbarkeit des Halteproblems. Angenommen, wir haben eine "perfekte" Dead-Code-Funktion, eine Turing-Maschine M und eine Eingabezeichenfolge x und eine Prozedur, die ungefähr so ​​aussieht:

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

Wenn M für immer läuft, löschen wir die print-Anweisung, da wir sie nie erreichen werden. Wenn M nicht für immer läuft, müssen wir die print-Anweisung beibehalten. Wenn wir also einen Dead-Code-Entferner haben, können wir damit auch das Halting-Problem lösen, sodass wir wissen, dass es keinen solchen Dead-Code-Entferner geben kann.

Wir umgehen dies durch "konservative Annäherung". In meinem obigen Turing Machine-Beispiel können wir also davon ausgehen, dass M on x möglicherweise beendet wird. Gehen Sie also auf Nummer sicher und entfernen Sie die print-Anweisung nicht. In Ihrem Beispiel wissen wir, dass unabhängig davon, welche Funktionen angehalten werden oder nicht, diese print-Anweisung auf keinen Fall erreicht werden kann.

In der Regel wird dazu ein "Kontrollflussdiagramm" erstellt. Wir machen vereinfachende Annahmen, wie "das Ende einer while-Schleife ist mit dem Anfang und der Anweisung danach verbunden", auch wenn sie für immer oder nur einmal ausgeführt wird und nicht beide besucht. In ähnlicher Weise nehmen wir an, dass eine if-Anweisung alle ihre Zweige erreichen kann, auch wenn in Wirklichkeit einige davon niemals verwendet werden. Diese Art von Vereinfachungen ermöglicht es uns, "offensichtlich toten Code" wie in dem von Ihnen angegebenen Beispiel zu entfernen, ohne dass wir uns dafür entscheiden müssen.

Um einige Verwirrungen aus den Kommentaren zu klären:

  1. Nitpick: Für festes M ist dies immer entscheidbar. M muss der Eingang sein

    Wie Raphael in meinem Beispiel sagt, betrachten wir die Turing-Maschine als Eingabe. Die Idee ist, dass wir, wenn wir einen perfekten DCE-Algorithmus hätten, das Codefragment konstruieren könnten, das ich für jede Turing-Maschine gebe , und dass ein DCE das Stopp-Problem lösen würde.

  2. nicht überzeugt. return als unverblümte Anweisung in einer einfachen Ausführung ohne Verzweigung ist nicht schwer zu entscheiden. (und mein Compiler sagt mir, dass es in der Lage ist, dies herauszufinden)

    Für das Problem, das njzk2 aufwirft: Sie haben absolut Recht, in diesem Fall können Sie feststellen, dass es keine Möglichkeit gibt, eine Aussage zu treffen, nachdem die Rückgabe erreicht wurde. Dies liegt daran, dass es so einfach ist, dass wir seine Nichterreichbarkeit mit Hilfe von Kontrollflussgraphenbeschränkungen beschreiben können (dh es gibt keine ausgehenden Kanten aus einer return-Anweisung). Es gibt jedoch keinen perfekten Dead Code-Eliminator, der den gesamten nicht verwendeten Code eliminiert.

  3. Ich nehme keinen eingabeabhängigen Beweis für einen Beweis. Wenn solche Benutzereingaben vorhanden sind, die es ermöglichen, dass der Code endlich ist, ist es richtig, dass der Compiler annimmt, dass der folgende Zweig nicht tot ist. Ich kann nicht sehen, wofür all diese Upvotes sind, es ist sowohl offensichtlich (z. B. endloses stdin) als auch falsch.

    Für TomášZato: Es ist nicht wirklich ein eingabeabhängiger Beweis. Vielmehr interpretieren Sie es als "Forall". Es funktioniert wie folgt: Nehmen wir an, wir haben einen perfekten DCE-Algorithmus. Wenn Sie mir eine beliebige Turing-Maschine M geben und x eingeben, kann ich meinen DCE-Algorithmus verwenden, um zu bestimmen, ob M anhält, indem ich den obigen Codeausschnitt konstruiere und sehe, ob die print-Anweisung entfernt ist. Diese Technik, einen Parameter willkürlich zu lassen, um eine forall-Anweisung zu beweisen, ist in Mathematik und Logik üblich.

    Ich verstehe TomášZato nicht ganz, dass Code endlich ist. Sicher ist der Code endlich, aber ein perfekter DCE-Algorithmus muss für jeden Code gelten, der eine unendliche Menge ist. Während der Code selbst endlich ist, sind die möglichen Mengen von Eingaben ebenso unendlich, wie die mögliche Laufzeit des Codes.

    Wenn man bedenkt, dass der letzte Zweig nicht tot ist: Es ist in Bezug auf die "konservative Annäherung", von der ich spreche, sicher, aber es reicht nicht aus, alle Instanzen von totem Code zu erkennen, wenn das OP danach fragt.

Betrachten Sie Code wie folgt:

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

Natürlich können wir entfernen, print "goodbye"ohne das Verhalten des Programms zu ändern. Es ist also toter Code. Wenn es jedoch einen anderen Funktionsaufruf als (true)in der whileBedingung gibt, wissen wir nicht, ob wir ihn entfernen können oder nicht, was zur Unentscheidbarkeit führt.

Beachten Sie, dass ich mir das nicht selbst einfallen lasse. Es ist ein bekanntes Ergebnis in der Compilertheorie. Es wird in The Tiger Book besprochen . (Möglicherweise können Sie in Google-Büchern sehen, worüber sie sprechen .

jmite
quelle
1
@ njzk2: Wir versuchen , es ist unmöglich , zu zeigen , einen toten Code - Eliminator , dass eliminiert zu bauen alle toten Code nicht, dass es einen toten Code zu bauen Eliminator , dass eliminiert unmöglich ist , einige von totem Code. Das Print-After-Return-Beispiel kann mithilfe von Kontrollflussgraphentechniken leicht beseitigt werden, aber nicht der gesamte tote Code kann auf diese Weise beseitigt werden.
user2357112 unterstützt Monica
4
Diese Antwort verweist auf Kommentare. Während ich die Antwort lese, muss ich in die Kommentare springen und dann zur Antwort zurückkehren. Dies ist verwirrend (wenn Sie bedenken, dass Kommentare zerbrechlich sind und verloren gehen können). Eine in sich geschlossene Antwort wäre viel einfacher zu lesen.
TRiG
1
@ TomášZato - Betrachte das Programm, das eine Variable inkrementiert und prüft, ob eine ungerade perfekte Zahl ist oder nicht. Es endet nur, wenn es eine solche Zahl findet. Es ist klar, dass dieses Programm nicht von externen Eingaben abhängig ist. Behaupten Sie, dass leicht festgestellt werden kann, ob dieses Programm beendet wird oder nicht? nnn
Gregory J. Puleo
3
@ TomášZato Sie haben ein falsches Verständnis für das Stopp-Problem. Wenn eine endliche Turing-Maschine und eine endliche Eingabe , ist es unmöglich zu bestimmen, ob während des Laufens auf Endlosschleife bildet . Ich habe dies nicht konsequent bewiesen, weil es immer wieder bewiesen wurde und ein grundlegendes Prinzip der Informatik ist. Es gibt eine schöne Skizze des Beweises auf Wikipediax M xMxMx
jmite
1
jmite, bitte füge gültige Kommentare in die Antwort ein, damit die Antwort für sich steht. Kennzeichnen Sie dann alle Kommentare, die als solche veraltet sind, damit wir aufräumen können. Vielen Dank!
Raphael
14

Dies ist eine Wendung in Bezug auf die Antwort von jmite, die die mögliche Verwirrung über die Nichtbeendigung umgeht. Ich gebe ein Programm, das sich immer selbst anhält, möglicherweise toten Code hat, aber wir können nicht (immer) algorithmisch entscheiden, ob dies der Fall ist.

Berücksichtigen Sie die folgende Klasse von Eingaben für die Dead-Code-ID:

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

Da Mund xbehoben sind, simulateMshat Dead Code mit return 0genau dann, wenn Mnicht halt auf x.

Dies führt uns sofort zu einer Reduzierung des Halteproblems auf die Überprüfung auf toten Code: Wenn TM als Instanz für das Halteproblem angegeben ist, erstellen Sie das obige Programm mit dem Code - es hat toten Code, wenn nicht von selbst anhält Code.M MMxMM

Daher ist die Dead-Code-Überprüfung nicht berechenbar.

Für den Fall, dass Sie mit der Reduktion als Proof-Technik in diesem Zusammenhang nicht vertraut sind, empfehle ich unser Referenzmaterial .

Raphael
quelle
5

Eine einfache Möglichkeit, diese Art von Eigenschaft zu demonstrieren, ohne sich in Details zu verstricken, ist die Verwendung des folgenden Lemmas:

Lemma: Für jeden Compiler C für eine Turing-complete-Sprache gibt es eine Funktion, undecidable_but_true()die keine Argumente akzeptiert und den booleschen Wert true zurückgibt, sodass C nicht vorhersagen kann, ob undecidable_but_true()true oder false zurückgegeben wird.

Beachten Sie, dass die Funktion vom Compiler abhängt. Bei einer gegebenen Funktion undecidable_but_true1()kann ein Compiler immer mit dem Wissen erweitert werden, ob diese Funktion true oder false zurückgibt. Es gibt jedoch immer eine andere Funktion undecidable_but_true2(), die nicht behandelt wird.

Beweis: Nach dem Satz von Rice ist die Eigenschaft „Diese Funktion gibt wahr zurück“ unentscheidbar. Daher kann ein statischer Analysealgorithmus diese Eigenschaft nicht für alle möglichen Funktionen bestimmen.

Fazit: Bei einem Compiler C enthält das folgende Programm toten Code, der nicht erkannt werden kann:

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

Ein Hinweis zu Java: Die Java-Sprachanweisung, dass Compiler bestimmte Programme ablehnen, die nicht erreichbaren Code enthalten, und sinnvollerweise, dass dieser Code an allen erreichbaren Punkten bereitgestellt wird (z. B. muss der Kontrollfluss in einer nicht ungültigen Funktion mit einer returnAnweisung enden ). Die Sprache gibt genau an, wie die Analyse des nicht erreichbaren Codes durchgeführt wird. Wenn dies nicht der Fall wäre, wäre es unmöglich, tragbare Programme zu schreiben. Gegeben ein Programm der Form

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

Es muss angegeben werden, in welchen Fällen auf den nicht erreichbaren Code ein anderer Code folgen muss und in welchen Fällen auf keinen Code. Ein Beispiel für ein Java-Programm, das Code enthält, der nicht erreichbar ist, aber den Java-Compilern nicht auffällt, ist Java 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
}
Gilles 'SO - hör auf böse zu sein'
quelle
Beachten Sie, dass einige Compiler für einige Sprachen möglicherweise erkennen können, dass das Ende von day_of_weeknicht erreichbar ist.
user253751
@immibis Ja, zum Beispiel können CS101-Schüler es meiner Erfahrung nach tun (obwohl CS101-Schüler zugegebenermaßen keine soliden statischen Analysegeräte sind, vergessen sie normalerweise die negativen Fälle). Das ist ein Teil meines Standpunkts: Es ist ein Beispiel für ein Programm mit nicht erreichbarem Code, das ein Java-Compiler nicht erkennt (zumindest kann er warnen, aber möglicherweise nicht ablehnen).
Gilles 'SO- hör auf böse zu sein'
1
Ich fürchte, die Formulierung des Lemma ist bestenfalls irreführend, mit einem Hauch von Falschheit. Unentscheidbarkeit ist nur dann sinnvoll, wenn Sie sie mit (unendlichen) Mengen von Instanzen ausdrücken. (Der Compiler gibt für jede Funktion eine Antwort, und wir wissen, dass dies nicht immer korrekt sein kann, aber wenn wir sagen, dass es eine einzige unentscheidbare Instanz gibt, ist sie deaktiviert.) Ihr Absatz zwischen dem Lemma und dem Proof (der nicht ganz mit dem Lemma übereinstimmt) wie gesagt) versucht dies zu beheben, aber ich denke, es wäre besser, ein klar korrektes Lemma zu formulieren.
Raphael
@Raphael Uh? Nein, der Compiler muss keine Antwort auf die Frage "Ist diese Funktion konstant?" Es muss nicht zwischen "Ich weiß nicht" und "Nein" unterschieden werden, um Arbeitscode zu erstellen. Dies ist hier jedoch nicht relevant, da wir uns nur für den statischen Analyseteil des Compilers interessieren, nicht für den Code-Übersetzungsteil. Ich verstehe nicht, was Sie an der Aussage des Lemmas irreführend oder falsch finden - es sei denn, Sie meinen, ich sollte "static analyzer" anstelle von "compiler" schreiben?
Gilles 'SO- hör auf böse zu sein'
Die Aussage klingt wie "Unentscheidbarkeit bedeutet, dass es eine Instanz gibt, die nicht gelöst werden kann", was falsch ist. (Ich weiß, dass du das nicht sagen willst, aber so kann es den Unachtsamen / Neulingen vorlesen, imho.)
Raphael
3

Die Antwort von jmite bezieht sich darauf, ob das Programm jemals eine Berechnung beenden wird - nur weil es unendlich ist, würde ich den Code nicht aufrufen, wenn er tot ist.

Es gibt jedoch einen anderen Ansatz: Ein Problem, für das es eine Antwort gibt, das jedoch nicht bekannt ist:

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)
  {
  ...
  }
}

Diese Routine ohne Zweifel nicht enthält toten Code - die Funktion wird eine Antwort zurück , das einen Weg führt aber nicht die andere. Viel Glück beim Finden! Mein Gedächtnis ist kein theoretischer Computer, der dies innerhalb der Lebensdauer des Universums lösen kann.

Ausführlicher:

Die Evaluate()Funktion berechnet, welche Seite eine Schachpartie gewinnt, wenn beide Seiten perfekt spielen (mit maximaler Suchtiefe).

Normalerweise schauen die Schachbewerter bei jeder möglichen Bewegung in einer bestimmten Tiefe nach vorn und versuchen dann, das Spielfeld an dieser Stelle zu bewerten (manchmal kann das Erweitern bestimmter Zweige, wenn sie auf halbem Wege durch einen Austausch oder dergleichen schauen, eine sehr verzerrte Wahrnehmung hervorrufen.) Da die tatsächliche maximale Tiefe Ist 17695 Halbzüge die Suche erschöpfend, durchläuft sie jede mögliche Schachpartie. Da alle Spiele zu Ende sind, gibt es kein Problem zu entscheiden, wie gut ein Brett ist (und daher keinen Grund, die Bewertungslogik des Brettes zu überprüfen - sie wird niemals aufgerufen), das Ergebnis ist entweder ein Gewinn, ein Verlust oder ein Verlust Gleichstand. Wenn das Ergebnis ein Unentschieden ist, ist das Spiel fair, wenn das Ergebnis kein Unentschieden ist, ist es ein unfaires Spiel. Um es ein bisschen zu erweitern, bekommen wir:

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

Beachten Sie auch, dass der Compiler praktisch nicht erkennen kann, dass Chessboard.Score () toter Code ist. Die Kenntnis der Schachregeln ermöglicht es uns Menschen, dies herauszufinden, aber um dies herauszufinden, muss man wissen, dass MakeMove die Stückzahl niemals erhöhen kann und dass Chessboard.Draw () true zurückgibt, wenn die Stückzahl zu lange statisch bleibt .

Beachten Sie, dass die Suchtiefe in Halbzügen und nicht in ganzen Zügen angegeben ist. Dies ist normal für diese Art von KI-Routine, da es sich um eine O (x ^ n) -Routine handelt. Das Hinzufügen einer weiteren Suchschicht hat einen großen Einfluss darauf, wie lange die Ausführung dauert.

Loren Pechtel
quelle
8
Sie gehen davon aus, dass ein Prüfalgorithmus die Berechnung durchführen müsste. Ein häufiger Irrtum! Nein, Sie können nicht davon ausgehen , wie ein Checker funktionieren würde, sonst können Sie seine Existenz nicht widerlegen.
Raphael
6
Die Frage verlangt einen Beweis, dass es unmöglich ist , toten Code zu erkennen. Ihr Beitrag enthält ein Beispiel für einen Fall, bei dem Sie den Verdacht haben, dass es schwierig ist , toten Code zu erkennen. Das ist keine Antwort auf die vorliegende Frage.
David Richerby
2
@LorenPechtel Ich weiß es nicht, aber das ist kein Beweis. Siehe auch hier ; ein klareres Beispiel für Ihr Missverständnis.
Raphael
3
Wenn es hilft, denken Sie daran, dass es theoretisch nichts gibt, das jemanden davon abhält, seinen Compiler für mehr als die Lebensdauer des Universums auszuführen. Die einzige Einschränkung ist die Praktikabilität. Ein entscheidbares Problem ist ein entscheidbares Problem, auch wenn es in der Komplexitätsklasse NONELEMENTARY liegt.
Pseudonym
4
Mit anderen Worten, diese Antwort ist bestenfalls eine Heuristik, die zeigen soll, warum es wahrscheinlich nicht einfach ist, einen Compiler zu erstellen, der sämtlichen toten Code erkennt - aber es ist kein Beweis für die Unmöglichkeit. Diese Art von Beispiel könnte als eine Möglichkeit , nützlich sein Gespür für Studenten zu bauen, aber es ist kein Beweis. Indem es sich als Beweis präsentiert, leidet es darunter. Die Antwort sollte dahingehend bearbeitet werden, dass sie ein Beispiel für die Schaffung von Intuition darstellt, jedoch keinen Beweis für die Unmöglichkeit darstellt.
DW
-3

Ich denke, in einem Computerkurs ist der Begriff des toten Codes im Kontext des Verständnisses des Unterschieds zwischen Kompilierungszeit und Laufzeit interessant!

Ein Compiler kann feststellen, wann Code vorhanden ist, der in keinem Kompilierungsszenario jemals verarbeitet werden kann, dies jedoch nicht zur Laufzeit. Eine einfache while-Schleife mit Benutzereingabe für den Loop-Break-Test zeigt dies.

Wenn ein Compiler tatsächlich feststellen könnte, dass der Code zur Laufzeit tot ist (dh Turing vollständig erkennt), dann gibt es ein Argument, dass der Code niemals ausgeführt werden muss, da der Job bereits erledigt ist!

Das Vorhandensein von Code, der die Dead-Code-Prüfungen zur Kompilierungszeit besteht, verdeutlicht die Notwendigkeit einer pragmatischen Überprüfung der Eingaben und der allgemeinen Codierungshygiene (in der realen Welt realer Projekte).

Dwoz
quelle
1
Die Frage verlangt einen Beweis, dass es unmöglich ist, toten Code zu erkennen. Sie haben diese Frage nicht beantwortet.
David Richerby
Außerdem ist Ihre Behauptung, dass ein Compiler feststellen kann, wann Sie Code haben, der in keinem Kompilierungsszenario jemals durchlaufen werden kann, falsch und widerspricht direkt dem, was Sie in der Frage zu beweisen haben.
David Richerby
@ David Richerby, ich denke, Sie können mich falsch lesen. Ich schlage nicht vor, dass die Überprüfung zur Kompilierungszeit ALLEN toten Code finden kann, ganz bestimmt nicht. Ich schlage vor, dass es eine Teilmenge der Menge aller toten Codes gibt, die zur Kompilierungszeit erkennbar ist. Wenn ich schreibe: if (true == false) {print ("something");}, ist diese print-Anweisung zur Kompilierungszeit als toter Code erkennbar. Stimmen Sie nicht zu, dass dies ein Gegenbeispiel zu Ihrer Behauptung ist?
Dwoz
Sicher, Sie können einen toten Code feststellen . Aber wenn Sie sagen "Bestimmen, wann [Sie einen toten Code haben]", ohne Qualifikationen, dann bedeutet das für mich, den gesamten toten Code zu finden, nicht nur einen Teil davon.
David Richerby