Selbstübersetzung (Compiler)
Sich selbst übersetzen kann ein Compiler, wenn sein Quellcode mit ihm selbst kompiliert werden kann und dabei der gleiche Compiler entsteht. Die Selbstübersetzung ist die nachhaltige Lösung für das Henne-Ei-Problem bei der Entwicklung von Programmiersprachen. Gleichzeitig ist die Selbstübersetzung ein Nachweis für die Erfüllung wichtiger Voraussetzungen an einen Compiler und seiner Programmiersprache.
Entstehung
[Bearbeiten | Quelltext bearbeiten]Bevor ein Compiler sich selbst übersetzen kann, muss er zuerst erzeugt werden. Da die Software zu ihrer eigenen Erzeugung jedoch noch nicht existiert, entsteht ein Henne-Ei-Problem, welches mit Bootstrapping gelöst wird. Dabei wird mindestens die erste Version des Computerprogramms (des Compilers) mittels eines anderen Compilers erzeugt. Erst wenn der Compiler in der Lage ist, sich selbst aus seinem eigenen Quellcode zu erzeugen, gilt er als self-hosted oder selbstübersetzend.[1] Ein Compiler, der ein Programm für ein anderes System erzeugt, wird Cross-Compiler genannt; ein so entstehender Compiler ist dann nicht self-hosted.
Typische Programmiersprachen der ersten Wahl für das Bootstrapping eines Compilers schließen C/C++, Assembler, Python, Lua, Haskell und andere ein.
Ein Nachweis, ob ein Compiler sich selbst übersetzen kann, kann über Idempotenz geführt werden: die Kompilierung des Compiler-Quellcodes, der in der Programmiersprache geschrieben ist, die der Compiler kompiliert, sollte einen Compiler erzeugen, mit dem der Compiler-Quellcode abermals kompiliert werden kann und einen identischen Compiler erzeugt.
Vorteile und Abgrenzung
[Bearbeiten | Quelltext bearbeiten]Durch die Eigenschaft eines Compilers, seinen eigenen Quellcode kompilieren zu können und dabei ein Programm zu erzeugen, das mit diesem Compiler identisch ist, muss in der Entwicklung des Compilers kein separates System mehr eingesetzt werden, da das System für das Kompilieren identisch mit dem System für die Anwendung ist. Daraus ergibt sich, dass auch jede andere Software, die mit diesem Compiler geschrieben werden kann, auf dem gleichen System lauffähig ist und folgerichtig auch dort debuggt werden kann. Die Eigenschaft eines Compilers, sich selbst übersetzen zu können, ist demnach eine sehr wichtige Eigenschaft für die Entwicklung, den Betrieb und die Kompatibilität von Softwaresystemen, die in dieser Sprache geschrieben wurden.
Laufzeitumgebungen
[Bearbeiten | Quelltext bearbeiten]Software, die Dateien erzeugt, welche mit einem Abspielprogramm ausgeführt werden, erzeugt keine Programme, die sich selbst übersetzen können. Hierzu zählen proprietäre Medienformate wie Microsoft PowerPoint oder Shockwave Flash, und streng genommen auch Programmiersprachen, die mit einer Laufzeitumgebung wie der Java-Laufzeitumgebung oder Common Intermediate Language ausgeführt werden müssen. Die Familie der .NET-Programmiersprachen wurde erst mit der Entwicklung der .NET Compiler Platform (unter Nutzung der vorher in C++ geschriebenen Compiler im Bootstrapping) selbstübersetzend und (theoretisch) von dem Modell der mit ihnen verknüpften Laufzeitumgebung unabhängig. Hingegen konnte die durch eine Laufzeitbibliothek interpretierte Programmiersprache QBasic in dem Projekt QB64 von dieser Einschränkung befreit werden; der QB64-Compiler ist selbstübersetzend und erzeugt frei lauffähige Programme.
Skriptsprachen
[Bearbeiten | Quelltext bearbeiten]JavaScript kann seine Ausführungsumgebung, eine virtuelle Maschine, nicht selbst übersetzen. TypeScript, eine echte Obermenge von JavaScript, erzeugt allerdings JavaScript. Die TypeScript-Umgebung ist selbst in TypeScript geschrieben und erzeugt JavaScript-Code. JavaScript kommt hier die Rolle des Betriebssystems für den TypeScript-Compiler und die mit ihm generierte Software zu; TypeScript wiederum ist self-hosted.
Sprachen, die interpretiert werden müssen – zu denen die meisten Skriptsprachen gehören – können sich nicht selbst übersetzen, wenn sie nicht in der Lage sind, auch einen Interpreter für sich selbst zu erzeugen, der in dieser Sprache geschrieben wurde. Je nach ihrem Funktionsumfang und ihren Möglichkeiten kann eine Skriptsprache eine solche Fähigkeit aber erwerben.
Geschichte
[Bearbeiten | Quelltext bearbeiten]Die erste höhere Programmiersprache, deren Compiler sich selbst übersetzen konnte, wurde für Lisp von Hart und Levin am Massachusetts Institute of Technology im Jahr 1962 geschrieben.
„Der Compiler, wie er auf dem Compiler-Standardband existiert, ist ein Programm in Maschinensprache, das gewonnen werden konnte, indem die S-Ausdrucksdefinition des Compilers auf sich selbst durch den Interpreter angewendet wurde.“
Seitdem werden neue Programmiersprachen in der Regel mit dem Ziel geschrieben, dass ihre Compiler einst mit der Sprache geschrieben werden können, von der sie Programme erzeugen, wenn andere technische Gründe, die in ihrem Anwendungsbereich zu finden sind, dem nicht entgegenstehen. Programmiersprachen, deren Compiler sich selbst kompilieren können, sind turingmächtig.
Ken Thompson begann mit der Entwicklung von Unix im Jahr 1968 durch das Schreiben und Kompilieren von Programmen auf dem Großrechner GE-365 von General Electric und übertrug sie zum Testen zum schrankwandgroßen Minirechner PDP-7. Nachdem der erste Unix-Kernel mit einem Kommandozeileninterpreter, einem Texteditor, einem Assembler und einigen Dienstprogrammen vervollständigt wurde, war das Unix-Betriebssystem self-hosted: Programme konnten auf dem PDP-7 selbst geschrieben und getestet werden, ohne den Großrechner und seine damals sehr teure Rechenzeit zu bemühen.[3]
Douglas McIlroy schrieb auf einem Blatt Papier TMG, einen Compiler-Compiler: ein Programm, welches Compiler erzeugt. Er „entschied, seinem Blatt Papier sein Blatt Papier zu geben“, führte die Berechnung selbst durch und „compilierte“ einen TMG-Compiler in Assembler, welches er auf Ken Thompsons PDP-7 eingab.[4]
Liste von Sprachen mit selbst übersetzenden Compilern (Auswahl)
[Bearbeiten | Quelltext bearbeiten]Die folgenden Programmiersprachen verwenden selbst übersetzende Compiler:
- C
- C++ (Visual C++, clang, gcc 4.8)
- C# (Microsoft Roslyn, Mono)
- ClojureScript[5]
- CoffeeScript
- D
- Dart
- Eiffel
- Elixir
- F#
- FASM[6]
- Go
- Haskell[7]
- Kotlin
- Lisp (Common Lisp)
- Oberon
- OCaml
- Python (PyPy)
- QB64
- Rust
- Scala
- Smalltalk
- Standard ML
- Tcl[8]
- TypeScript
- Vala
- Virgil[9]
- Visual Basic .NET (Microsoft Roslyn, Mono)
- Zig
Einzelnachweise
[Bearbeiten | Quelltext bearbeiten]- ↑ Robert Heaton: What is a self-hosting compiler? In: robertheaton.com. 24. Oktober 2017, abgerufen am 5. November 2022 (englisch).
- ↑ Tim Hart, Mike Levin: AI Memo 39 – The new compiler. (PDF) In: publications.ai.mit.edu. 30. November 1995, archiviert vom am 13. Dezember 2020; abgerufen am 23. Mai 2008 (englisch, Benutzername: anonymous, Passwort: anonymous).
- ↑ Dennis M. Ritchie: The Development of the C Language. In: bell-labs.com. 1993, abgerufen am 5. November 2022 (englisch).
- ↑ Ken Thompson: Ken Thompson interviewed by Brian Kernighan at VCF East 2019 (ab 0:38:50) auf YouTube, 6. Mai 2019, abgerufen am 28. Oktober 2019 (englisch).
- ↑ David Nolen: ClojureScript Next. In: swannodette.github.io. 29. Juli 2015, abgerufen am 5. November 2022 (englisch).
- ↑ Tomasz Grysztar: flat assembler. In: flatassembler.net. Abgerufen am 7. Januar 2022 (englisch): „The flat assembler is self-hosting and the complete source code is included.“
- ↑ Ingo Wechsung et al.: Haskell Communities and Activities Report. In: haskell.org. Mai 2016, abgerufen am 5. November 2022 (englisch).
- ↑ Keith Nash: Implement TCL in TCL. In: wiki.tcl-lang.org. 29. Juni 2007, abgerufen am 19. September 2017 (englisch).
- ↑ Ben L. Titzer: virgil – A lightweight multi-paradigm programming language. In: code.google.com. Archiviert vom am 28. Dezember 2014; abgerufen am 27. Mai 2015 (englisch).