Selbstübersetzung (Compiler)

Sich selbst übersetzen kann ein Compiler, wenn sein Quellcode mit ihm selbst kompiliert werden kann und dabei der gleiche Compiler entsteht. Das Konzept des Self-Hostings, wie es auf englisch heißt, findet sich auch in anderen Systemen: Versionsverwaltungen können ihren eigenen Quellcode verwalten und ein Betriebssystem kann mithilfe seiner selbst entwickelt werden.

QS-Informatik
Beteilige dich an der Diskussion!
 Dieser Artikel wurde wegen inhaltlicher Mängel auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen, und beteilige dich an der Diskussion! (+)


Begründung: Zur Diskussion steht noch die Themenüberschneidung, die sich aus der Übersetzung ergeben: self-hosted steht für Softwaresysteme an sich, Selbstübersetzung ist eine spezifische Fähigkeit des Compilers --Herzmut (Diskussion)

Entstehung

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.[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

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.

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 als Zwischenschicht ausgeführt werden müssen, wenn diese Laufzeitumgebungen nicht auch selbst in dieser Programmiersprache geschrieben wurden und durch die Kompilierung des Compilers erzeugt werden. Die Familie der .NET-Programmiersprachen wurde erst mit der Entwicklung der .NET Compiler Platform (unter Nutzung der vorher in C++ geschriebenen Compiler im Bootstrapping) selbsttragend 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.

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

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.“

– AI Memo 39[2]

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, aus denen ihr Compiler sich selbst bauen kann, 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]

Die Entwicklung des GNU-Systems verlässt sich hauptsächlich auf den GNU C-Compiler und den Texteditor Emacs. Das GNU-System ermöglicht so die selbst erhaltende und selbst pflegende Entwicklung von freier Software aus dem GNU-Projekt für das GNU-Projekt.

Liste von Sprachen mit selbst übersetzenden Compilern (Auswahl)

Die folgenden Programmiersprachen verwenden selbst übersetzende Compiler:

Einzelnachweise
  1. Robert Heaton: What is a self-hosting compiler? In: robertheaton.com. 24. Oktober 2017, abgerufen am 5. November 2022 (englisch).
  2. Tim Hart, Mike Levin: AI Memo 39 – The new compiler. (PDF) In: publications.ai.mit.edu. 30. November 1995, archiviert vom Original am 13. Dezember 2020; abgerufen am 23. Mai 2008 (englisch, Benutzername: anonymous, Passwort: anonymous).
  3. Dennis M. Ritchie: The Development of the C Language. In: bell-labs.com. 1993, abgerufen am 5. November 2022 (englisch).
  4. 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).
  5. David Nolen: ClojureScript Next. In: swannodette.github.io. 29. Juli 2015, abgerufen am 5. November 2022 (englisch).
  6. 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.“
  7. Ingo Wechsung et al.: Haskell Communities and Activities Report. In: haskell.org. Mai 2016, abgerufen am 5. November 2022 (englisch).
  8. Keith Nash: Implement TCL in TCL. In: wiki.tcl-lang.org. 29. Juni 2007, abgerufen am 19. September 2017 (englisch).
  9. Ben L. Titzer: virgil – A lightweight multi-paradigm programming language. In: code.google.com. Archiviert vom Original am 28. Dezember 2014; abgerufen am 27. Mai 2015 (englisch).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.