Die Compiler, die ich in C oder Java verwendet habe, verhindern toten Code (Warnung, wenn eine Zeile niemals ausgeführt wird). Mein Professor sagt, dass dieses Problem von Compilern niemals vollständig gelöst werden kann. Ich habe mich gefragt, warum das so ist. Ich bin mit der tatsächlichen Codierung von Compilern nicht allzu vertraut, da dies eine theoretische Klasse ist. Aber ich habe mich gefragt, was sie überprüfen (wie mögliche Eingabezeichenfolgen gegenüber akzeptablen Eingaben usw.) und warum dies nicht ausreicht.
compiler-theory
Lerner
quelle
quelle
if (isPrime(1234234234332232323423)){callSomething();}
Wird dieser Code jemals etwas aufrufen oder nicht? Es gibt viele andere Beispiele, bei denen die Entscheidung, ob eine Funktion jemals aufgerufen wird, weitaus teurer ist, als sie nur in das Programm aufzunehmen.public static void main(String[] args) {int counterexample = findCollatzConjectureCounterexample(); System.out.println(counterexample);}
<- Ist der Println Call Dead Code? Nicht einmal Menschen können dieses Problem lösen!Antworten:
Das Problem mit dem toten Code hängt mit dem Problem des Anhaltens zusammen .
Alan Turing hat bewiesen, dass es unmöglich ist, einen allgemeinen Algorithmus zu schreiben, der ein Programm erhält, und zu entscheiden, ob dieses Programm für alle Eingaben angehalten wird. Möglicherweise können Sie einen solchen Algorithmus für bestimmte Programmtypen schreiben, jedoch nicht für alle Programme.
Wie hängt das mit totem Code zusammen?
Das Problem des Anhaltens lässt sich auf das Problem reduzieren , toten Code zu finden. Wenn Sie also einen Algorithmus finden, der toten Code in einem Programm erkennen kann, können Sie diesen Algorithmus verwenden, um zu testen, ob ein Programm angehalten wird. Da sich dies als unmöglich erwiesen hat, ist das Schreiben eines Algorithmus für toten Code ebenfalls unmöglich.
Wie überträgt man einen Algorithmus für toten Code in einen Algorithmus für das Halting-Problem?
Einfach: Sie fügen nach dem Ende des Programms, das Sie auf Halt prüfen möchten, eine Codezeile hinzu. Wenn Ihr Dead-Code-Detektor feststellt, dass diese Zeile tot ist, wissen Sie, dass das Programm nicht angehalten wird. Wenn dies nicht der Fall ist, wissen Sie, dass Ihr Programm angehalten wird (bis zur letzten Zeile und dann bis zur hinzugefügten Codezeile).
Compiler prüfen normalerweise, ob Dinge, die zum Zeitpunkt der Kompilierung nachgewiesen werden können, tot sind. Zum Beispiel Blöcke, die von Bedingungen abhängig sind, die zum Zeitpunkt der Kompilierung als falsch bestimmt werden können. Oder eine Aussage nach a
return
(im gleichen Rahmen).Dies sind spezielle Fälle, und daher ist es möglich, einen Algorithmus für sie zu schreiben. Es ist möglicherweise möglich, Algorithmen für kompliziertere Fälle zu schreiben (z. B. einen Algorithmus, der prüft, ob eine Bedingung syntaktisch ein Widerspruch ist und daher immer false zurückgibt), der jedoch nicht alle möglichen Fälle abdeckt.
quelle
256^(2^64)
Zuständen istO(1)
so, dass die Erkennung von totem Code in Polynomzeit erfolgen kann.Nehmen wir den klassischen Beweis für die Unentscheidbarkeit des Stoppproblems und ändern den Stoppdetektor in einen Totcodedetektor!
C # -Programm
Wenn
YourVendor.Compiler.HasDeadCode(quine_text)
Rückkehrfalse
, dann ist die LinieSystem.Console.WriteLn("Dead code!");
nicht immer ausgeführt werden, so dass dieses Programm tatsächlich nicht tot - Code, und der Detektor war falsch.Wenn es jedoch zurückkehrt
true
, wird die ZeileSystem.Console.WriteLn("Dead code!");
ausgeführt, und da das Programm keinen Code mehr enthält, gibt es überhaupt keinen toten Code. Auch hier war der Detektor falsch.Da haben Sie es also, ein Totcodedetektor, der nur "Es gibt toten Code" oder "Es gibt keinen toten Code" zurückgibt, muss manchmal falsche Antworten liefern.
quelle
Wenn das Problem des Anhaltens zu dunkel ist, stellen Sie es sich so vor.
Nehmen Sie ein mathematisches Problem, von dem angenommen wird, dass es für alle positiven Ganzzahlen n gilt , das jedoch nicht für jedes n gilt . Ein gutes Beispiel wäre Goldbachs Vermutung , dass jede positive gerade ganze Zahl größer als zwei durch die Summe zweier Primzahlen dargestellt werden kann. Führen Sie dann (mit einer geeigneten Bigint-Bibliothek) dieses Programm aus (Pseudocode folgt):
Die Implementierung von
isGoldbachsConjectureTrueFor()
bleibt als Übung für den Leser, könnte aber zu diesem Zweck eine einfache Iteration über alle Primzahlen sein, die kleiner als sindn
Logischerweise muss das Obige entweder das Äquivalent von sein:
(dh eine Endlosschleife) oder
wie Goldbachs Vermutung muss entweder wahr oder nicht wahr sein. Wenn ein Compiler immer toten Code eliminieren könnte, gäbe es in beiden Fällen definitiv toten Code, der hier eliminiert werden könnte. Dabei müsste Ihr Compiler jedoch zumindest beliebig schwierige Probleme lösen. Wir könnten Probleme bereitstellen, die nachweislich schwer zu lösen wären (z. B. NP-vollständige Probleme), um zu bestimmen, welches Codebit beseitigt werden soll. Zum Beispiel, wenn wir dieses Programm nehmen:
Wir wissen, dass das Programm entweder "Gefundener SHA-Wert" oder "Nicht gefundener SHA-Wert" ausgibt (Bonuspunkte, wenn Sie mir sagen können, welcher wahr ist). Damit ein Compiler dies jedoch vernünftigerweise optimieren kann, würde dies in der Größenordnung von 2 ^ 2048 Iterationen liegen. Es wäre in der Tat eine großartige Optimierung, da ich voraussage, dass das obige Programm bis zum Hitzetod des Universums laufen würde (oder könnte), anstatt etwas ohne Optimierung zu drucken.
quelle
sha256
ein Byte-Array zurückgegeben, und Byte-Arrays werden nicht mit Zeichenfolgen in Ihrer Sprache verglichen.Implementation of isGoldbachsConjectureTrueFor() is left as an exercise for the reader
Das brachte mich zum Lachen.Ich weiß nicht, ob C ++ oder Java eine Typfunktion haben
Eval
, aber in vielen Sprachen können Sie Methoden nach Namen aufrufen . Betrachten Sie das folgende (erfundene) VBA-Beispiel.Der Name der aufzurufenden Methode ist bis zur Laufzeit nicht bekannt. Daher kann der Compiler per Definition nicht mit absoluter Sicherheit wissen, dass eine bestimmte Methode niemals aufgerufen wird.
In Anbetracht des Beispiels, eine Methode beim Namen aufzurufen, ist die Verzweigungslogik nicht einmal erforderlich. Einfach sagen
Ist mehr als der Compiler bestimmen kann. Wenn der Code kompiliert wird, weiß der Compiler nur, dass ein bestimmter Zeichenfolgenwert an diese Methode übergeben wird. Es wird erst zur Laufzeit überprüft, ob diese Methode vorhanden ist. Wenn die Methode nicht durch normalere Methoden an anderer Stelle aufgerufen wird, kann ein Versuch, tote Methoden zu finden, falsch positive Ergebnisse zurückgeben. Das gleiche Problem tritt in jeder Sprache auf, in der Code über Reflection aufgerufen werden kann.
quelle
Unbedingter toter Code kann von fortgeschrittenen Compilern erkannt und entfernt werden.
Es gibt aber auch bedingten toten Code. Dies ist Code, der zum Zeitpunkt der Kompilierung nicht bekannt ist und nur zur Laufzeit erkannt werden kann. Beispielsweise kann eine Software so konfiguriert werden, dass bestimmte Funktionen je nach Benutzerpräferenz ein- oder ausgeschlossen werden, wodurch bestimmte Codeabschnitte in bestimmten Szenarien scheinbar tot erscheinen. Das ist kein wirklich toter Code.
Es gibt spezielle Tools, mit denen Sie Tests durchführen, Abhängigkeiten auflösen, bedingten toten Code entfernen und den nützlichen Code zur Laufzeit aus Effizienzgründen neu kombinieren können. Dies wird als dynamische Eliminierung von totem Code bezeichnet. Aber wie Sie sehen, geht es über den Rahmen von Compilern hinaus.
quelle
Ein einfaches Beispiel:
Nehmen wir nun an, dass der Port 0x100 nur 0 oder 1 zurückgibt. In diesem Fall kann der Compiler nicht herausfinden, dass der
else
Block niemals ausgeführt wird.In diesem grundlegenden Beispiel jedoch:
Hier kann der Compiler die berechnen
else
Block ein toter Code ist. Der Compiler kann also nur dann vor dem toten Code warnen, wenn er über genügend Daten verfügt, um den toten Code herauszufinden, und er sollte auch wissen, wie diese Daten angewendet werden, um herauszufinden, ob der angegebene Block ein toter Code ist.BEARBEITEN
Manchmal sind die Daten zum Zeitpunkt der Kompilierung einfach nicht verfügbar:
Beim Kompilieren von a.cpp kann der Compiler nicht wissen, dass
boolMethod
immer zurückgegeben wirdtrue
.quelle
Dem Compiler fehlen immer einige Kontextinformationen. Sie wissen vielleicht, dass ein Doppelwert niemals 2 überschreitet, da dies ein Merkmal der mathematischen Funktion ist, die Sie aus einer Bibliothek verwenden. Der Compiler sieht nicht einmal den Code in der Bibliothek, und er kann niemals alle Merkmale aller mathematischen Funktionen kennen und alle unerwünschten und komplizierten Möglichkeiten erkennen, sie zu implementieren.
quelle
Der Compiler sieht nicht unbedingt das gesamte Programm. Ich könnte ein Programm haben, das eine gemeinsam genutzte Bibliothek aufruft, die eine Funktion in meinem Programm aufruft, die nicht direkt aufgerufen wird.
Eine Funktion, die in Bezug auf die Bibliothek, für die sie kompiliert wurde, tot ist, könnte also lebendig werden, wenn diese Bibliothek zur Laufzeit geändert wird.
quelle
Wenn ein Compiler den gesamten toten Code genau eliminieren könnte, würde er als Interpreter bezeichnet .
Stellen Sie sich dieses einfache Szenario vor:
my_func()
kann beliebigen Code enthalten, und damit der Compiler feststellen kann, ob er true oder false zurückgibt, muss er entweder den Code ausführen oder etwas tun, das funktional dem Ausführen des Codes entspricht.Die Idee eines Compilers ist, dass er nur eine teilweise Analyse des Codes durchführt, wodurch die Arbeit einer separaten laufenden Umgebung vereinfacht wird. Wenn Sie eine vollständige Analyse durchführen, ist dies kein Compiler mehr.
Wenn Sie den Compiler als eine Funktion betrachten
c()
, woc(source)=compiled code
und die laufende Umgebung alsr()
, wor(compiled code)=program output
, müssen Sie den Wert von berechnen, um die Ausgabe für einen beliebigen Quellcode zu bestimmenr(c(source code))
. Wenn Rechenc()
das Wissen des Wertes erfordertr(c())
für jede Eingabe, gibt es keine Notwendigkeit für einen separatenr()
undc()
: Sie nur eine Funktion ableiteni()
aus ,c()
so dassi(source)=program output
.quelle
Andere haben das Problem des Anhaltens usw. kommentiert. Diese gelten im Allgemeinen für Teile von Funktionen. Es kann jedoch schwierig / unmöglich sein zu wissen, ob auch nur ein ganzer Typ (Klasse / usw.) verwendet wird oder nicht.
In .NET / Java / JavaScript und anderen zur Laufzeit gesteuerten Umgebungen hindert nichts das Laden von Typen über Reflection. Dies ist bei Abhängigkeitsinjektions-Frameworks beliebt und angesichts der Deserialisierung oder des Ladens dynamischer Module noch schwieriger zu begründen.
Der Compiler kann nicht wissen, ob solche Typen geladen werden würden. Ihre Namen könnten zur Laufzeit aus externen Konfigurationsdateien stammen.
Möglicherweise möchten Sie nach Baumschütteln suchen, was ein häufiger Begriff für Tools ist, die versuchen, nicht verwendete Untergraphen von Code sicher zu entfernen.
quelle
Nehmen Sie eine Funktion
Können Sie beweisen, dass
actnumber
das niemals2
so sein wird, dassAction2()
es niemals heißt ...?quelle
Action2()
nie genannt werden‘ ist es unmöglich , den Anspruch in der Praxis zu beweisen - nicht vollständig durch einen Compiler gelöst werden . Der Unterschied ist wie 'es gibt eine Zahl X' vs. 'wir können die Zahl X dezimal schreiben'. Für einige X wird das letztere niemals passieren, obwohl das erstere wahr ist.actnumber==2
. Diese Antwort behauptet lediglich, es sei schwierig, ohne auch nur eine Komplexität anzugeben.Ich bin nicht einverstanden mit dem Problem des Anhaltens. Ich würde einen solchen Code nicht als tot bezeichnen, obwohl er in Wirklichkeit niemals erreicht werden kann.
Betrachten wir stattdessen:
(Typ- und Überlauffehler ignorieren) Toter Code?
quelle
Schauen Sie sich dieses Beispiel an:
Der Compiler kann nicht wissen, dass ein int nur gerade oder ungerade sein kann. Daher muss der Compiler in der Lage sein, die Semantik Ihres Codes zu verstehen. Wie soll dies umgesetzt werden? Der Compiler kann nicht sicherstellen, dass die niedrigste Rückgabe niemals ausgeführt wird. Daher kann der Compiler den toten Code nicht erkennen.
quelle
return i%2==0;
.i % 2 == 0
undi % 2 != 0
erfordert nicht einmal eine Überlegung über den Wert eines ganzzahligen Modulo einer Konstanten (was immer noch einfach zu tun ist), sondern nur die Eliminierung von Unterausdrücken und das allgemeine Prinzip (sogar Kanonisierung),if (cond) foo; if (!cond) bar;
das vereinfacht werden kannif (cond) foo; else bar;
. Natürlich ist "Semantik verstehen" ein sehr schwieriges Problem, aber dieser Beitrag zeigt weder, dass dies der Fall ist, noch, dass die Lösung dieses schwierigen Problems für die Erkennung von totem Code erforderlich ist.i % 2
und zieht ihn in eine temporäre Variable. Es wird dann erkannt, dass sich die beidenif
Anweisungen gegenseitig ausschließen und als geschrieben werden könnenif(a==0)...else...
, und dann festgestellt, dass alle möglichen Ausführungspfade die ersten beidenreturn
Anweisungen durchlaufen und daher die drittereturn
Anweisung toter Code ist. (Ein guter Optimierungs-Compiler ist noch aggressiver: GCC hat meinen Testcode in zwei Bitmanipulationsoperationen umgewandelt.)if (availableMemory()<0) then {dead code}
.{dead code}
Teil. GCC entdeckt dies, indem es nachweist, dass ein unvermeidbarer Überlauf mit vorzeichenbehafteten Ganzzahlen vorliegt. Der gesamte Code in diesem Bogen im Ausführungsdiagramm ist daher toter Code. GCC kann sogar den bedingten Zweig entfernen, der zu diesem Bogen führt.