Bootstrapping (Compiler) - Bootstrapping (compilers)

In der Informatik ist Bootstrapping die Technik zum Erstellen eines selbstkompilierenden Compilers , dh eines Compilers (oder Assemblers ), der in der Quellprogrammiersprache geschrieben ist , die er kompilieren möchte. Eine erste Kernversion des Compilers (der Bootstrap-Compiler ) wird in einer anderen Sprache generiert (die eine Assemblersprache sein könnte); sukzessive erweiterte Versionen des Compilers werden unter Verwendung dieser minimalen Teilmenge der Sprache entwickelt. Das Problem des Kompilierens eines selbstkompilierenden Compilers wurde im Compiler-Design das Henne-oder-Ei-Problem genannt , und Bootstrapping ist eine Lösung für dieses Problem.

Viele Compiler für viele Programmiersprachen sind Bootstrapping, einschließlich Compiler für BASIC , ALGOL , C , C# , D , Pascal , PL/I , Factor , Haskell , Modula-2 , Oberon , OCaml , Common Lisp , Scheme , Go , Java , Elixir , Rust , Python , Scala , Nim , Eiffel , Vala und mehr.

Verfahren

Ein typischer Bootstrap-Prozess funktioniert in drei oder vier Stufen:

  • Phase 0: Vorbereiten einer Umgebung, mit der der Bootstrap-Compiler arbeiten kann.
  • Stufe 1: Der Bootstrap-Compiler wird erstellt.
  • Stufe 2: Ein vollständiger Compiler wird vom Bootstrap-Compiler erstellt.
  • Stufe 3: Ein vollständiger Compiler wird durch den vollständigen Compiler der Stufe 2 erzeugt.

Der vollständige Compiler wird zweimal erstellt, um die Ausgaben der beiden Stufen zu vergleichen. Wenn sie unterschiedlich sind, enthält entweder der Bootstrap oder der vollständige Compiler einen Fehler.

Vorteile

Das Bootstrapping eines Compilers hat folgende Vorteile:

  • es ist ein nicht trivialer Test der zu kompilierenden Sprache und als solche eine Form von Dogfooding .
  • Compiler-Entwickler und Bug-Reporter müssen nur die zu kompilierende Sprache kennen.
  • Die Compilerentwicklung kann in der zu kompilierenden höheren Sprache durchgeführt werden.
  • Verbesserungen am Back-End des Compilers verbessern nicht nur allgemeine Programme, sondern auch den Compiler selbst.
  • es ist eine umfassende Konsistenzprüfung, da es in der Lage sein soll, seinen eigenen Objektcode zu reproduzieren.

Beachten Sie, dass einige dieser Punkte davon ausgehen, dass auch die Language Runtime in derselben Sprache geschrieben ist.

Methoden

Wenn man einen Compiler für die Sprache X kompilieren muss, der in der Sprache X geschrieben ist, stellt sich die Frage, wie der erste Compiler kompiliert werden kann. Zu den verschiedenen Methoden, die in der Praxis angewendet werden, gehören:

  • Implementierung eines Interpreters oder Compilers für die Sprache X in die Sprache Y. Niklaus Wirth berichtete, dass er den ersten Pascal- Compiler in Fortran geschrieben hat .
  • Ein anderer Interpreter oder Compiler für X wurde bereits in einer anderen Sprache Y geschrieben; So wird Scheme oft gebootet.
  • Frühere Versionen des Compilers wurden in einer Teilmenge von X geschrieben, für die es einen anderen Compiler gab; Auf diese Weise werden einige Obermengen von Java , Haskell und dem anfänglichen Free Pascal- Compiler gebootet.
  • Ein Compiler, der nicht standardmäßige Spracherweiterungen oder optionale Sprachfeatures unterstützt, kann ohne Verwendung dieser Erweiterungen und Features geschrieben werden, damit er mit einem anderen Compiler kompiliert werden kann, der dieselbe Basissprache, aber einen anderen Satz von Erweiterungen und Features unterstützt. Die Hauptteile des C++- Compiler- Klangs wurden in einer Teilmenge von C++ geschrieben, die sowohl von g++ als auch von Microsoft Visual C++ kompiliert werden kann . Erweiterte Funktionen werden mit einigen GCC-Erweiterungen geschrieben.
  • Der Compiler für X ist Quer zusammengestellt aus einer anderen Architektur , wo es einen Compiler für X vorhanden ist ; so werden Compiler für C normalerweise auf andere Plattformen portiert. Dies ist auch die Methode, die für Free Pascal nach dem ersten Bootstrap verwendet wird.
  • Schreiben des Compilers in X; dann manuell aus dem Quellcode kompilieren (höchstwahrscheinlich auf nicht optimierte Weise) und das auf dem Code ausführen, um einen optimierten Compiler zu erhalten. Donald Knuth nutzte dies für sein WEB Literate Programmiersystem .

Verfahren zum Verteilen von Compilern im Quellcode umfassen das Bereitstellen einer tragbaren Bytecode- Version des Compilers, um den Prozess des Kompilierens des Compilers mit sich selbst zu booten . Das T-Diagramm ist eine Notation, die verwendet wird, um diese Compiler-Bootstrap-Techniken zu erklären. In einigen Fällen erfordert der bequemste Weg, einen komplizierten Compiler auf einem System mit wenig oder gar keiner Software zum Laufen zu bringen, eine Reihe immer ausgefeilterer Assembler und Compiler.

Geschichte

Assembler waren die ersten Sprachwerkzeuge, um sich selbst zu booten.

Die erste Hochsprache, die einen solchen Bootstrap bereitstellte, war 1958 NELIAC . Die ersten weit verbreiteten Sprachen, die dies taten , waren 1961 Burroughs B5000 Algol und 1962 LISP .

Hart und Levin schrieben 1962 am MIT einen LISP-Compiler in LISP und testeten ihn in einem bestehenden LISP-Interpreter. Nachdem sie den Compiler so weit verbessert hatten, dass er seinen eigenen Quellcode kompilieren konnte, war er selbst-hosting.

Der Compiler, wie er auf dem Standard-Compilerband existiert, ist ein Maschinensprachenprogramm, das erhalten wurde, indem die S-Ausdrucksdefinition des Compilers durch den Interpreter an sich selbst arbeiten ließ.

—  AI-Memo 39

Diese Technik ist nur möglich, wenn bereits ein Interpreter für dieselbe zu kompilierende Sprache existiert. Es nimmt direkt Anleihen bei der Vorstellung, ein Programm auf sich selbst als Eingabe laufen zu lassen, die auch in verschiedenen Beweisen in der theoretischen Informatik verwendet wird , wie zum Beispiel dem Beweis, dass das Halteproblem unentscheidbar ist.

Aktuelle Bemühungen

Aufgrund von Sicherheitsbedenken in Bezug auf den Trusting Trust Attack und verschiedene Angriffe auf die Vertrauenswürdigkeit von Binärdateien arbeiten mehrere Projekte daran, den Aufwand nicht nur für das Bootstrapping von der Quelle zu reduzieren, sondern es auch jedem zu ermöglichen, die Übereinstimmung von Quelle und ausführbarer Datei zu überprüfen. Dazu gehören das Bootstrapable Builds-Projekt und das Reproducible Builds-Projekt.

Siehe auch

Verweise

  1. ^ Reynolds, John H. (Dezember 2003). "Bootstrapping eines selbstkompilierenden Compilers von Maschine X zu Maschine Y" . CCSC: Ostkonferenz. Journal of Computing Sciences in Colleges . 19 (2): 175–181. Die Idee eines Compilers, der in der Sprache geschrieben ist, die er kompiliert, wirft das alte "Huhn-oder-das-Ei"-Rätsel auf: Woher kommt der erste?
  2. ^ Glück, Robert (2012). „Bootstrapping Compiler-Generatoren von partiellen Evaluatoren“. In Clarke, Edmund; Virbitskaite, Irina; Woronkow, Andrei (Hrsg.). Perspektiven der Systeminformatik: 8. Internationale Andrei-Ershov-Gedächtniskonferenz, PSI 2011, Novosibirsk, Russland, 27. Juni - 1. Juli 2011, Revised Selected Papers . Skript zur Vorlesung Informatik. 7162 . Springer. S. 125–141. doi : 10.1007/978-3-642-29709-0_13 . Der Einstieg stellt das Henne-und-Ei-Problem dar, das aus der Compiler-Konstruktion bekannt ist: Man braucht einen Compiler, um einen Compiler zu booten, und das Bootstrapping von Compiler-Generatoren ist keine Ausnahme.
  3. ^ a b "Installieren von GCC: Gebäude" . GNU-Projekt - Free Software Foundation (FSF) .
  4. ^ "rost-lang/rust: bootstrap" . GitHub .
  5. ^ „Erweiterte Build-Konfigurationen – LLVM 10-Dokumentation“ . llvm.org .
  6. ^ Compiler und Compilergeneratoren: Eine Einführung in C++. Patrick D. Terry 1997. Internationale Thomson-Computerpresse. ISBN  1-85032-298-8
  7. ^ a b "Compiler-Konstruktion und Bootstrapping" von PDTerry 2000. HTML Archiviert 2009-11-23 an der Wayback Machine . PDF Archiviert am 14. Dezember 2010 an der Wayback Machine .
  8. ^ Niklaus Wirth. 2021. 50 Jahre Pascal. Komm. ACM 64, 3 (März 2021), 39–41. DOI: https://doi.org/10.1145/3447525
  9. ^ "Bootstrapping eines einfachen Compilers aus dem Nichts" Archiviert am 3. März 2010, an der Wayback Machine von Edmund GRIMLEY EVANS 2001
  10. ^ a b Tim Hart und Mike Levin. "AI Memo 39-Der neue Compiler" (PDF) . Archiviert vom Original (PDF) am 13.12.2020 . Abgerufen 2008-05-23 .
  11. ^ http://bootstrappable.org/
  12. ^ https://reproduzierbare-builds.org/