Warum sind Compiler so zuverlässig?

Wir verwenden Compiler täglich, als ob ihre Korrektheit gegeben wäre, aber Compiler sind auch Programme und können möglicherweise Fehler enthalten. Ich habe mich immer über diese unfehlbare Robustheit gewundert. Haben Sie jemals einen Fehler im Compiler selbst entdeckt? Was war es und wie haben Sie festgestellt, dass das Problem im Compiler selbst liegt?

... und wie machen sie Compiler so zuverlässig?

Sie werden gründlich getestet, indem sie im Laufe der Zeit von Tausenden oder sogar Millionen von Entwicklern verwendet werden.

Auch das zu lösende Problem ist genau definiert (durch eine sehr detaillierte technische Spezifikation). Und die Art der Aufgabe eignet sich leicht für Einheits- / Systemtests. Das heißt, es übersetzt im Grunde Texteingaben in einem sehr spezifischen Format, um sie in einem anderen, genau definierten Format (eine Art Bytecode oder Maschinencode) auszugeben. So ist es einfach, Testfälle zu erstellen und zu verifizieren.

Darüber hinaus sind die Bugs in der Regel auch leicht zu reproduzieren: Abgesehen von den genauen Plattform- und Compilerversionsinformationen ist in der Regel nur ein Stück Eingabecode erforderlich. Ganz zu schweigen davon, dass die Compilerbenutzer (die selbst Entwickler sind) in der Regel weitaus präzisere und detailliertere Fehlerberichte liefern als jeder durchschnittliche Computerbenutzer :-)

Neben all den tollen Antworten bisher:

Sie haben eine "Beobachter-Voreingenommenheit". Sie beobachten keine Bugs und gehen daher davon aus, dass es keine gibt.

Früher habe ich so gedacht wie du. Dann habe ich angefangen, professionell Compiler zu schreiben, und ich sage Ihnen, da sind viele Fehler drin!

Sie sehen die Fehler nicht, weil Sie Code schreiben, der genau wie 99,999% des restlichen Codes ist, den die Leute schreiben. Sie schreiben wahrscheinlich ganz normalen, unkomplizierten, klar korrekten Code, der Methoden aufruft und Schleifen ausführt und nichts Besonderes oder Verrücktes tut, weil Sie ein normaler Entwickler sind, der normale Geschäftsprobleme löst.

Es werden keine Compiler-Fehler angezeigt, da die Compiler-Fehler nicht in den einfach zu analysierenden normalen Codeszenarien enthalten sind. Die Fehler liegen in der Analyse von seltsamem Code, den Sie nicht schreiben.

Ich hingegen habe die gegenteilige Beobachter-Tendenz. Ich sehe jeden Tag den ganzen Tag verrückten Code, und für mich scheinen die Compiler voller Fehler zu sein.

Wenn Sie sich mit der Sprachspezifikation einer beliebigen Sprache abgesetzt und eine Compiler-Implementierung für diese Sprache vorgenommen haben und sich wirklich bemüht haben, festzustellen, ob der Compiler die Spezifikation genau implementiert hat oder nicht, und sich auf dunkle Eckfälle konzentrieren, werden Sie ziemlich bald fündig Compiler-Fehler ziemlich häufig. Lassen Sie mich Ihnen ein Beispiel geben, hier ist ein C # -Compiler-Fehler, den ich vor fünf Minuten buchstäblich gefunden habe.

static void N(ref int x){}
...
N(ref 123);

Der Compiler gibt drei Fehler an.

• Ein ref- oder out-Argument muss eine zuweisbare Variable sein.
• Die beste Übereinstimmung für N (ref int x) hat ungültige Argumente.
• Fehlendes "ref" bei Argument 1.

Offensichtlich ist die erste Fehlermeldung korrekt und die dritte ist ein Fehler. Der Fehlergenerierungsalgorithmus versucht herauszufinden, warum das erste Argument ungültig war, untersucht es, stellt fest, dass es eine Konstante ist, und kehrt nicht zum Quellcode zurück, um zu überprüfen, ob es als "ref" markiert wurde. Vielmehr wird davon ausgegangen, dass niemand so dumm wäre, eine Konstante als ref zu markieren, und es wird entschieden, dass der ref fehlen muss.

Es ist nicht klar, was die richtige dritte Fehlermeldung ist, aber das ist es nicht. Tatsächlich ist auch nicht klar, ob die zweite Fehlermeldung korrekt ist. Sollte die Überladungsauflösung fehlschlagen oder sollte "ref 123" als ref-Argument des richtigen Typs behandelt werden? Ich muss jetzt darüber nachdenken und es mit dem Triage-Team besprechen, damit wir feststellen können, wie es sich richtig verhält.

Sie haben diesen Fehler noch nie gesehen, weil Sie wahrscheinlich niemals etwas so Dummes tun würden, um zu versuchen, 123 per ref zu übergeben. Und wenn ja, würden Sie wahrscheinlich nicht einmal bemerken, dass die dritte Fehlermeldung unsinnig ist, da die erste richtig und ausreichend ist, um das Problem zu diagnostizieren. Aber ich versuche solche Sachen zu machen, weil ich versuche , den Compiler kaputt zu machen. Wenn Sie es versuchen würden, würden Sie auch die Fehler sehen.

Willst du mich veräppeln? Compiler haben auch Bugs, die wirklich geladen werden.

GCC ist wahrscheinlich der berühmteste Open-Source-Compiler der Welt. Schauen Sie sich seine Bug-Datenbank an: http://gcc.gnu.org/bugzilla/buglist.cgi?product=gcc&component=c%2B%2B&resolution=-- -

Sehen Sie sich zwischen GCC 3.2 und GCC 3.2.3 an, wie viele Fehler behoben wurden: http://gcc.gnu.org/gcc-3.2/changes.html

Was andere wie Visual C ++ betrifft, möchte ich gar nicht erst anfangen.

Wie machen Sie Compiler zuverlässig? Zunächst einmal haben sie jede Menge Unit-Tests. Und der ganze Planet nutzt sie also ohne Mangel an Testern.

Im Ernst, Compilerentwickler, von denen ich glaube, dass sie überlegene Programmierer sind, und obwohl sie nicht unfehlbar sind, haben sie einen ziemlichen Durchschlag.

Ich habe zwei oder drei in meinem Tag angetroffen. Die einzige echte Möglichkeit, eine zu erkennen, besteht darin, den Assembler-Code zu betrachten.

Obwohl Compiler aus Gründen, auf die andere Poster hingewiesen haben, äußerst zuverlässig sind, ist die Zuverlässigkeit von Compilern meiner Meinung nach oft eine Selbsteinschätzung. Programmierer neigen dazu, den Compiler als Standard anzusehen. Wenn etwas schief geht, gehen Sie davon aus, dass es Ihre Schuld ist (weil dies zu 99,999% der Fall ist), und ändern Sie Ihren Code, um das Compilerproblem zu umgehen, und nicht umgekehrt. Beispiel: Code, der unter einer hohen Optimierungseinstellung abstürzt, ist definitiv ein Compiler-Fehler, aber die meisten Leute setzen ihn nur etwas niedriger und fahren fort, ohne den Fehler zu melden.

Compiler haben verschiedene Eigenschaften, die zu ihrer Korrektheit führen:

• Die Domain ist sehr bekannt und recherchiert. Das Problem ist klar definiert und die angebotenen Lösungen sind klar definiert.
• Automatisierte Tests sind ausreichend, um zu beweisen, dass Compiler korrekt funktionieren
• Compiler verfügen über sehr umfangreiche, in der Regel öffentliche, automatisierte und Unit-Tests, die sich im Laufe der Zeit angesammelt haben, um einen größeren Teil des Fehlerbereichs als bei den meisten anderen Programmen abzudecken
• Compiler haben eine sehr große Anzahl von Augäpfeln, die ihre Ergebnisse beobachten

Wir verwenden täglich Compiler

... und wie machen sie Compiler so zuverlässig?

Sie tun es nicht. Wir tun Weil jeder sie ständig benutzt, werden Fehler schnell gefunden.

Es ist ein Spiel mit Zahlen. Da Compiler so pervasively gewöhnt, ist es sehr wahrscheinlich , dass jeder Fehler wird von jemandem ausgelöst werden, sondern weil es eine so große Anzahl von Benutzern, ist es höchst unwahrscheinlich , dass jemand , der Sie speziell sein wird.

Das hängt also von Ihrer Sichtweise ab: Compiler sind für alle Benutzer fehlerhaft. Aber es ist sehr wahrscheinlich, dass jemand anderes ein ähnliches Stück Code kompiliert hat, bevor Sie es getan haben. Wenn es sich also um einen Fehler handelte, hätte es sie getroffen, nicht Sie. Aus Ihrer individuellen Sicht sieht es also so aus, als wäre der Fehler aufgetreten niemals dort.

Darüber hinaus können Sie hier natürlich alle anderen Antworten hinzufügen: Compiler sind gut recherchiert und gut verstanden. Es gibt diesen Mythos, dass sie schwer zu schreiben sind, was bedeutet, dass nur sehr kluge, sehr gute Programmierer tatsächlich versuchen, einen zu schreiben, und dabei besonders vorsichtig sind. Sie sind im Allgemeinen leicht zu testen und leicht zu Stresstest oder Fuzz-Test. Compiler-Benutzer sind in der Regel selbst Experten, was zu qualitativ hochwertigen Fehlerberichten führt. Und umgekehrt: Compiler-Schreiber sind in der Regel Benutzer ihres eigenen Compilers.

Zusätzlich zu allen Antworten möchte ich noch hinzufügen:

Ich glaube oft, die Verkäufer essen ihr eigenes Hundefutter. Das heißt, sie schreiben die Compiler selbst.

Ich bin oft auf Compiler-Fehler gestoßen.

Sie finden sie in den dunkleren Ecken, wo es weniger Tester gibt. Um beispielsweise Fehler in GCC zu finden, sollten Sie versuchen:

• Erstellen Sie einen Cross-Compiler. Sie werden buchstäblich Dutzende von Fehlern in den Konfigurations- und Build-Skripten von GCC finden . Einige führen zu Erstellungsfehlern während der GCC-Kompilierung, andere führen dazu, dass der Cross-Compiler keine funktionsfähigen ausführbaren Dateien erstellt.
• Erstellen Sie eine Itanium-Version von GCC mit Profile-Bootstrap. Bei den letzten Versuchen mit GCC 4.4 und 4.5 konnte kein funktionierender C ++ - Ausnahmebehandler erstellt werden. Der nicht optimierte Build hat gut funktioniert. Niemand schien daran interessiert zu sein, den gemeldeten Fehler zu beheben, und ich gab es auf, ihn selbst zu beheben, nachdem ich versucht hatte, herauszufinden, was in den GCC-ASM-Speicherspezifikationen brach.
• Versuchen Sie, Ihren eigenen funktionierenden GCJ aus den neuesten Informationen zu erstellen, ohne ein Skript zum Erstellen einer Distribution zu befolgen. Du traust dich ja nicht.

Mehrere Gründe:

• Compiler-Autoren " essen ihr eigenes Hundefutter ".
• Compiler basieren auf gut verstandenen CS- Prinzipien .
• Compiler sind nach einer sehr klaren Spezifikation aufgebaut .
• Compiler werden getestet .
• Compiler sind nicht immer sehr zuverlässig .

Sie sind normalerweise bei -O0 sehr gut. Wenn wir einen Compiler-Fehler vermuten, vergleichen wir -O0 mit der Ebene, die wir verwenden möchten. Höhere Optimierungsstufen gehen mit einem höheren Risiko einher. Einige sind sogar absichtlich so und in der Dokumentation als solche gekennzeichnet. Ich habe sehr viele (mindestens hundert während meiner Zeit) getroffen, aber sie werden in letzter Zeit viel seltener. Trotzdem ist die Versuchung groß, bei der Verfolgung guter Spezifikationsnummern (oder anderer für das Marketing wichtiger Benchmarks) die Grenzen zu überschreiten. Wir hatten vor ein paar Jahren Probleme, als ein Anbieter (der nicht namentlich genannt wurde) beschloss, einen Verstoß gegen die Standardeinstellung in Klammern zu machen, anstatt eine spezielle, eindeutig gekennzeichnete Kompilierungsoption.

Es kann schwierig sein, einen Compilerfehler zu diagnostizieren, wenn man von einer Streuspeicherreferenz spricht. Eine Neukompilierung mit verschiedenen Optionen kann einfach die relative Position von Datenobjekten im Speicher verschlüsseln, sodass Sie nicht wissen, ob es sich um den Heisenbug oder einen Buggy Ihres Quellcodes handelt Compiler. Viele Optimierungen bewirken auch legitime Änderungen in der Reihenfolge der Operationen oder sogar algebraische Vereinfachungen in Ihrer Algebra. Diese haben unterschiedliche Eigenschaften in Bezug auf Gleitkommarundung und Unter- / Überlauf. Es ist schwer, diese Effekte von WIRKLICHEN Fehlern zu entwirren. Hardcore-Fließkomma-Computing ist aus diesem Grund schwierig, da Fehler und numerische Sensitivität oft nicht einfach zu entwirren sind.

Compiler-Fehler sind gar nicht so selten. Der häufigste Fall ist, dass ein Compiler einen Fehler in einem Code meldet, der akzeptiert werden soll, oder dass ein Compiler Code akzeptiert, der abgelehnt werden sollte.

Ja, ich bin erst gestern auf einen Fehler im ASP.NET-Compiler gestoßen:

Wenn Sie stark typisierte Modelle in Ansichten verwenden, ist die Anzahl der Parametervorlagen begrenzt. Offensichtlich können nicht mehr als 4 Template-Parameter verwendet werden, sodass der Compiler mit den beiden folgenden Beispielen zu viel zu tun hat:

ViewUserControl<System.Tuple<type1, type2, type3, type4, type5>>

Kompiliert nicht wie es ist, sondern wird entfernt, wenn type5es entfernt wird.

ViewUserControl<System.Tuple<MyModel, System.Func<type1, type2, type3, type4>>>

Kompilieren würde, wenn type4entfernt wird.

Beachten Sie, dass System.Tuplees viele Überladungen gibt und bis zu 16 Parameter aufnehmen kann (ich weiß, es ist verrückt).

Haben Sie jemals einen Fehler im Compiler selbst entdeckt? Was war es und wie haben Sie festgestellt, dass das Problem im Compiler selbst liegt?

Jep!

Die beiden denkwürdigsten waren die ersten beiden, denen ich jemals begegnet bin. Sie waren beide 1985-7 im Lightspeed C-Compiler für 680x0-Macs.

Das erste war, wo der Ganzzahl-Post-Inkrement-Operator unter bestimmten Umständen nichts tat - mit anderen Worten, in einem bestimmten Codeteil hat "i ++" einfach nichts mit "i" gemacht. Ich zog meine Haare aus, bis ich eine Demontage ansah. Dann habe ich das Inkrementieren einfach anders durchgeführt und einen Fehlerbericht eingereicht.

Das zweite war etwas komplizierter und ein wirklich schlecht überlegtes "Feature", das schief gelaufen ist. Die frühen Macs hatten ein kompliziertes System für die Ausführung von Festplattenoperationen auf niedriger Ebene. Aus irgendeinem Grund habe ich nie verstanden - wahrscheinlich weil ich kleinere ausführbare Dateien erstellt habe -, dass der Compiler nicht nur die Anweisungen für die Plattenoperation im Objektcode generiert hat, sondern dass der Lightspeed-Compiler eine interne Funktion aufruft, die zur Laufzeit die Plattenoperation generiert Anweisungen auf dem Stapel und sprang dorthin.

Das hat auf 68000-CPUs sehr gut funktioniert, aber wenn Sie denselben Code auf einer 68020-CPU ausführen, führt dies häufig zu seltsamen Ergebnissen. Es stellte sich heraus, dass ein neues Merkmal des 68020 ein 256-Byte-Befehls-Cache mit primitiven Befehlen war. In den Anfängen mit CPU-Caches war der Cache nicht "schmutzig" und musste nachgefüllt werden. Ich denke, die CPU-Designer von Motorola haben nicht an selbstmodifizierenden Code gedacht. Wenn Sie also in Ihrer Ausführungssequenz zwei Festplattenoperationen durchgeführt haben, die nahe genug beieinander liegen, und die Lightspeed-Laufzeit die tatsächlichen Anweisungen an derselben Stelle auf dem Stapel erstellt hat, würde die CPU fälschlicherweise annehmen, dass ein Anweisungscachetreffer aufgetreten ist, und die erste Festplattenoperation zweimal ausführen.

Um das herauszufinden, musste man wieder mit einem Disassembler herumgraben und in einem Low-Level-Debugger viele Schritte ausführen. Meine Problemumgehung bestand darin, jeder Plattenoperation einen Aufruf einer Funktion voranzustellen, die 256 "NOP" -Anweisungen ausführte, die den Anweisungscache überfluteten (und damit löschten).

In den 25 Jahren seitdem habe ich im Laufe der Zeit immer weniger Compiler-Bugs gesehen. Ich denke, dafür gibt es ein paar Gründe:

• Es gibt immer mehr Validierungstests für Compiler.
• Moderne Compiler sind in der Regel in zwei oder mehr Teile unterteilt, von denen einer plattformunabhängigen Code generiert (z. B. LLVMs, die auf eine möglicherweise imaginäre CPU abzielen), und ein anderer, der dies in Anweisungen für Ihre eigentliche Zielhardware umsetzt. In Multi-Plattform-Compilern wird der erste Teil überall verwendet, so dass unzählige Tests in der Praxis durchgeführt werden.

Vor 5.5 Jahren wurde in Turbo Pascal ein eklatanter Fehler gefunden. Ein Fehler, der weder in der vorherigen (5.0) noch in der nächsten (6.0) Version des Compilers vorhanden ist. Und eine, die leicht zu testen gewesen sein sollte, da es sich überhaupt nicht um einen Eckfall handelte (nur um einen Anruf, der nicht so häufig verwendet wird).

Im Allgemeinen verfügen die kommerziellen Compiler-Hersteller (und nicht die Hobby-Projekte) mit Sicherheit über sehr umfangreiche QS- und Testverfahren. Sie wissen, dass ihre Compiler ihre Flaggschiffprojekte sind und dass Fehler für sie sehr schlimm sein werden, schlimmer als für andere Unternehmen, die die meisten anderen Produkte herstellen. Softwareentwickler sind eine unerbittliche Bande, unsere Werkzeuglieferanten lassen uns im Stich, wir werden wahrscheinlich nach Alternativen suchen, anstatt auf eine Lösung des Lieferanten zu warten, und wir werden diese Tatsache sehr wahrscheinlich unseren Kollegen mitteilen, die unseren folgen könnten Beispiel. In vielen anderen Branchen ist dies nicht der Fall. Daher ist der potenzielle Verlust für einen Compilerhersteller aufgrund eines schwerwiegenden Fehlers weitaus größer als der eines Herstellers von Videobearbeitungssoftware.

Wenn sich das Verhalten Ihrer Software beim Kompilieren mit -O0 und mit -O2 unterscheidet, haben Sie einen Compiler-Fehler gefunden.

Wenn sich das Verhalten Ihrer Software nur von dem unterscheidet, was Sie erwarten, liegt der Fehler wahrscheinlich in Ihrem Code.

Compiler Fehler passieren, aber Sie neigen dazu, sie in merkwürdigen Ecken zu finden ...

In den 1990er Jahren gab es einen seltsamen Fehler im VAX VMS C-Compiler der Digital Equipment Corporation

(Ich trug eine Zwiebel am Gürtel, wie es damals Mode war)

Ein überflüssiges Semikolon vor einer for-Schleife wird als Hauptteil der for-Schleife kompiliert.

f(){...}
;
g(){...}

void test(){
  int i;
  for ( i=0; i < 10; i++){
     puts("hello");
  }
}

Auf dem fraglichen Compiler wird die Schleife nur einmal ausgeführt.

es sieht

f(){...}
g(){...}

void test(){
  int i;
  for ( i=0; i < 10; i++) ;  /* empty statement for fun */

  {
     puts("hello");
  }
}

Das hat mich viel Zeit gekostet.

Die ältere Version des PIC C-Compilers, die wir (früher) für Schüler mit Berufserfahrung verwendet haben, konnte keinen Code generieren, der den Interrupt mit hoher Priorität korrekt verwendete. Man musste 2-3 Jahre warten und upgraden.

Der MSVC 6-Compiler hatte einen raffinierten Fehler im Linker, der Segmentierungsfehler verursachte und von Zeit zu Zeit ohne Grund ausfiel. Ein sauberer Build reparierte es im Allgemeinen (aber seufzte nicht immer).

In einigen Bereichen, wie z. B. Avionik-Software, bestehen extrem hohe Zertifizierungsanforderungen an Code und Hardware sowie an den Compiler. Zu diesem letzten Teil gibt es ein Projekt, das auf die Erstellung eines formal verifizierten C-Compilers namens Compcert abzielt . Theoretisch ist diese Art von Compiler so zuverlässig wie sie kommen.

Ich habe mehrere Compiler-Fehler gesehen und einige selbst gemeldet (speziell in F #).

Trotzdem denke ich, dass Compiler-Bugs selten sind, weil Leute, die Compiler schreiben, sich im Allgemeinen sehr gut mit den strengen Konzepten der Informatik auskennen, die sie über die mathematischen Implikationen von Code wirklich bewusst machen.

Die meisten von ihnen sind vermutlich sehr vertraut mit Dingen wie Lambda-Kalkül, formaler Verifikation, Denotationssemantik usw. - Dinge, die ein durchschnittlicher Programmierer wie ich nur schwer nachvollziehen kann.

Außerdem ist die Zuordnung von Eingabe zu Ausgabe in Compilern in der Regel recht unkompliziert, sodass das Debuggen einer Programmiersprache wahrscheinlich viel einfacher ist als das Debuggen von beispielsweise einer Blog-Engine.

Ich habe vor nicht allzu langer Zeit einen Fehler im C # -Compiler gefunden. Sie können sehen, wie Eric Lippert (der Mitglied des C # -Designteams ist) herausgefunden hat, was der Fehler hier war .

Zusätzlich zu den bereits gegebenen Antworten möchte ich noch ein paar Dinge hinzufügen. Compiler-Designer sind oft sehr gute Programmierer. Compiler sind sehr wichtig: Die meisten Programmierungen werden mit Compilern durchgeführt, daher ist es unerlässlich, dass der Compiler von hoher Qualität ist. Es ist daher im besten Interesse von Unternehmen, Compiler dazu zu bringen, ihre besten Leute darauf zu setzen (oder zumindest sehr gute: Die Besten mögen vielleicht kein Compiler-Design). Microsoft wünscht sich sehr, dass die C- und C ++ - Compiler ordnungsgemäß funktionieren, oder der Rest des Unternehmens kann seine Aufgaben nicht ausführen.

Wenn Sie einen wirklich komplexen Compiler erstellen, können Sie ihn auch nicht einfach zusammen hacken. Die Logik hinter den Compilern ist sehr komplex und leicht zu formalisieren. Daher werden diese Programme oft sehr 'robust' und allgemein aufgebaut, was dazu führt, dass weniger Fehler auftreten.