Wie sind die ersten Compiler entstanden?

70

Ich frage mich immer, und vielleicht brauche ich eine gute Geschichtsstunde in Programmiersprachen. Aber da die meisten Compiler heutzutage in C erstellt wurden, wie wurden die allerersten Compiler erstellt (AKA vor C) oder wurden alle Sprachen nur interpretiert?

Trotzdem verstehe ich immer noch nicht, wie die erste Assembler-Sprache erstellt wurde, ich verstehe, was Assembler-Sprache ist, aber ich sehe nicht, wie sie die SEHR erste Assembler-Sprache zum Laufen gebracht haben (wie haben sie die erste gemacht?) Befehle (wie mov R21) oder wir setzen auf das binäre Äquivalent?

Mücke
quelle
9
Es gab einmal einen komisch unfähigen Programmierer in meinem Team, bei dem er sich nur über C # beschwerte. Wir scherzten über eine erfundene fiktive Sprache namens Crunk. Eine wenig bekannte Tatsache über Crunk, es ist die erste Sprache, in der der Compiler AUCH in Crunk geschrieben wurde. :)
maple_shaft
2
Warum sollte sich jemand über C # beschweren? Hat er nie Smalltalk oder Lisp benutzt? lol
2
mögliches Duplikat von C-Compiler und Dennis Ritchie
vartec
4
@maple_shaft: Um fair zu sein, ist der GCC-Compiler in C geschrieben . Das ist eigentlich kein Problem, wenn Sie einen guten Cross-Compiler haben, um die erste Version zu kompilieren. Der erste C-Compiler musste natürlich in einer anderen Sprache geschrieben sein.
Scott Whitlock
5
mögliches Duplikat von Wie wurde der erste Compiler geschrieben?
Greg Hewgill

Antworten:

89

Ha, ich habe das getan. Viele CPUs verfügen über einfache Anweisungen mit fester Größe, die nur wenige Bytes lang sind. Für eine einfache CPU wie beispielsweise ein Motorola 6800 könnten Sie alle Anweisungen auf ein einzelnes Blatt Papier schreiben . Jeder Anweisung würde ein Zwei-Byte-Opcode und Argumente zugeordnet sein. Sie können ein Programm von Hand zusammenstellen, indem Sie den Opcode jeder Anweisung nachschlagen. Sie würden dann Ihr Programm auf Papier schreiben und jede Anweisung mit dem entsprechenden Opcode versehen. Nachdem Sie Ihr Programm geschrieben haben, können Sie jeden Opcode nacheinander in ein EPROM brennendas würde dann dein programm speichern. Verbinden Sie das EPROM mit den richtigen Anweisungen an den richtigen Adressen mit der CPU, und Sie haben ein einfaches Arbeitsprogramm. Und um Ihre nächste Frage zu beantworten, ja. Es war schmerzhaft (wir haben das in der High School gemacht). Aber ich muss sagen, dass ich durch das Verdrahten jedes Chips in einem 8-Bit-Computer und das manuelle Schreiben eines Programms ein tiefes Verständnis der Computerarchitektur hatte, das ich wahrscheinlich auf keine andere Weise hätte erreichen können.

Weiterentwickelte Chips (wie x86) sind weitaus schwieriger per Hand zu codieren, da sie häufig Befehle mit variabler Länge enthalten. VLIW / EPIC-Prozessoren wie der Itanium lassen sich praktisch nicht effizient handhaben, da sie mit Anweisungspaketen arbeiten, die von fortschrittlichen Compilern optimiert und zusammengestellt wurden. Bei neuen Architekturen werden Programme fast immer zuerst auf einem anderen Computer geschrieben und zusammengestellt und dann in die neue Architektur geladen. Für Unternehmen wie Intel, die tatsächlich CPUs bauen, können sie tatsächliche Programme auf Architekturen ausführen, die es noch nicht gibt, indem sie sie auf Simulatoren ausführen. Aber ich schweife ab...

Compiler können im einfachsten Fall nicht mehr als "Ausschneiden und Einfügen" -Programme sein. Sie könnten eine sehr einfache, nicht optimierende "Hochsprache" schreiben, die einfache Assemblersprachenanweisungen ohne großen Aufwand zusammenfügt.

Wenn Sie eine Geschichte von Compilern und Programmiersprachen wollen, empfehle ich Ihnen eine Geschichte von FORTRAN .

Dave Markle
quelle
27
. . . und sollte das nicht sein "... Ich schlage vor, Sie JMP zu einer Geschichte ..."
Binary Worrier
2
Es tut mir so sehr sehr leid. Aber ich musste. Ich hatte gerade. zu ...
Dave Markle
9
@ Dave: Weißt du, dass du dich selbst durch Velociraptor zum Tode verurteilt hast ?
Binary Worrier
7
Sie "wussten", weil sie buchstäblich fest verdrahtet waren, um diese Operation auszuführen, als sie ein 101010100-Signal für eine gegebene Anweisung sahen. Sie haben tatsächlich eine On-Chip-Einheit, die für die Instruktionsdecodierungsinstruktionen verantwortlich ist: en.wikipedia.org/wiki/Decoder
Dave Markle
7
Es lohnt sich hinzuzufügen: Der Compiler für eine neue Sprache wird, wenn er in derselben neuen Sprache geschrieben ist, manchmal mit einem "Protocompiler" kompiliert, der in einer anderen Sprache geschrieben ist und nachweislich korrekten, aber fürchterlich ineffizienten Code erzeugt. Sobald dies kompiliert ist, wird es selbst ausgeführt, um einen relativ schnellen Compiler zu erstellen. Vergleichen Sie Von Neumann Machine. : D
BMDan
54

Darum geht es beim Compiler-Bootstrapping (da niemand erwähnte, wie es heißt =).

das Schreiben eines Compilers (oder Assemblers) in der Zielprogrammiersprache, die kompiliert werden soll. Das Anwenden dieser Technik führt zu einem selbsthostenden Compiler.

Viele Compiler für viele Programmiersprachen werden gebootet, einschließlich Compiler für BASIC, ALGOL, C, Pascal, PL / I, Faktor, Haskell, Modula-2, Oberon, OCaml, Common Lisp, Schema, Java, Python, Scala und mehr. .

Das Henne-Ei-Problem

Wenn man einen Compiler für Sprache X benötigt, um einen Compiler für Sprache X (der in Sprache X geschrieben ist) zu erhalten, wie wurde der erste Compiler geschrieben? Mögliche Methoden zur Lösung dieses Hühner- oder Eiproblems sind:

  • Implementierung eines Interpreters oder Compilers für Sprache X in Sprache Y. Niklaus Wirth berichtete, dass er den ersten Pascal-Compiler in Fortran geschrieben habe.
  • 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 eine Teilmenge von X geschrieben, für die es einen anderen Compiler gab. Auf diese Weise werden einige Supersets von Java, Haskell und dem anfänglichen Free Pascal-Compiler gebootet.
  • Der Compiler für X wird aus einer anderen Architektur cross-kompiliert, in der ein Compiler für X vorhanden ist. Auf diese Weise 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; Kompilieren Sie es dann von Hand aus dem Quellcode (höchstwahrscheinlich auf nicht optimierte Weise) und führen Sie es im Code aus, um einen optimierten Compiler zu erhalten. Donald Knuth verwendete dies für sein WEB-Programmiersystem ...
Reben
quelle
Guter Link, der Sie auch zu en.wikipedia.org/wiki/History_of_compiler_writing führt . Im Allgemeinen denke ich, dass die ursprünglichen Compiler in Assemblersprache geschrieben wurden ( en.wikipedia.org/wiki/Assembly_language ). Erst später kam die Idee auf, Bootstrapping oder Selfhosting zu betreiben.
Michael Levy
1
+1 ENDLICH! Seltsam, dass dies nur die dritthäufigste Antwort ist. Ja, Bootstrapping. Das ist die Antwort
Adam Rackis
15

Letztendlich arbeiten alle Computer mit Binärcodes, die in die CPU eingespeist werden. Diese Binärcodes sind für eine CPU völlig natürlich, aber auch für den Menschen vollkommen unbrauchbar. Eine der ersten Möglichkeiten, ein Programm zu schreiben, bestand darin, Löcher in Karten zu stanzen. Die Position der Löcher stellte eine bestimmte Bitposition innerhalb eines Wortes dar, und das Vorhandensein oder Nichtvorhandensein des Lochs wurde als Null oder Eins interpretiert. Diese Karten wurden in einer Schachtel in die richtige Reihenfolge gebracht und dann einem Kartenleser zugeführt, der sie effektiv in Binärcode für die CPU umwandelte (und Ihr Leben war effektiv verloren, wenn Sie die Schachtel fallen ließen).

Offensichtlich arbeiteten die allerersten Programmierer die Binärcodes nacheinander aus und hatten eine Maschine, um die Karten zu lochen. Dies ist im Wesentlichen Assembler-Programmierung auf Händen und Knien. Sobald Sie das haben, können Sie alle anderen Dinge daraus erstellen: einen einfachen Texteditor, einen Assembler-Compiler (um die Text-Assembler-Anweisungen in Binärcodes umzuwandeln), einen Linker und einen Loader. Und der Rest ist, wie sie sagen, Geschichte.

wolfgangsz
quelle
4
Vor Karten hatten Sie eine Reihe von Schaltern für die Adresse, eine Reihe für das Datenwort und einen Schalter zum Laden der Daten. Sie haben jede Speicheradresse einzeln programmiert, indem Sie die Adress- und Datenschalter mit der Binärdarstellung eingestellt und den Ladeschalter ein- und ausgeschaltet haben. Es dauerte eine Ewigkeit, aber das Programm war nur ein paar Worte lang - Bytes waren damals noch nicht erfunden worden.
uɐɪ
4
... und davor musste man es neu verkabeln . Spaß Spaß Spaß!
Michael K
Ja, aber als Sie das tun mussten, war es nicht wirklich das, was wir als modernen Computer betrachten würden, da die Von Neumann-Architektur noch nicht erfunden worden war.
Dave Markle
7

Ein bisschen googeln taucht bei EDSAC Initial Orders aus den späten 40ern auf. Da es der erste Assembler war, wurde es wahrscheinlich in Maschinensprache codiert.

Später kamen Assembler für andere Maschinen, wie SOAP I und II für die IBM 650. SOAP I wurde wahrscheinlich auch in Maschinensprache codiert, obwohl ich die endgültige Aussage nicht gefunden habe.

Ein wenig später kam Fortran (Formelübersetzer) für die IBM 704. Vermutlich wurde es in Assembler für die 704 geschrieben. Ein früher Assembler für die 701 wird Nathan Rochester gutgeschrieben .

Wenn Sie eine Vorstellung davon haben möchten, wie ein Computer in Maschinensprache programmiert wird, besuchen Sie eine meiner Lieblingsseiten, Harry Porters Relais-Computer .

Mike Dunlavey
quelle
Heiliger Mist, der von Harry Porter (beinahe gesagt, Harry Potter lol) selbstgebaute Computer ist FANTASTISCH. Ich wünschte, ich hätte verstanden, wie so etwas gebaut wurde :(.
1
@ Sauron: Harry Porter hätte nichts lieber, als es dir zu sagen. Von dieser Seite aus hat er einen wunderbaren Powerpoint, der alles erklärt. Grundlegende Kenntnisse der Schaltungstechnik werden vorausgesetzt, sind aber nicht allzu schwer zu bekommen.
Mike Dunlavey
Ich weiß, ich messe nur ^ _ ^, unabhängig davon, ob es sich um eine sehr beeindruckende Maschine handelt, und ich bin mir sicher, dass viele Zaubererstunden darauf verwendet wurden :).
6

Es ist möglich (wenn mühsam), direkten Maschinencode zu schreiben. Vielleicht schreiben Sie das Programm in Assembler auf ein Blatt Papier und übersetzen es dann von Hand in die numerischen Maschinencode-Anweisungen, die Sie in den Maschinenspeicher eingeben. Sie können den Assembler-on-Paper-Schritt sogar überspringen, wenn Sie die numerischen Werte aller Maschinencodeanweisungen gespeichert haben - heutzutage keine Seltenheit, ob Sie es glauben oder nicht!

Die ersten Computer wurden direkt in Binärform programmiert, indem die physischen Schalter umgeschaltet wurden. Es war eine große Produktivitätsverbesserung, als die Hardware so weiterentwickelt wurde, dass der Programmierer (oder der Dateneingabeassistent) den Code in hexadezimalen Zahlen über eine Tastatur eingeben konnte!

Ein Software-Assembler wurde erst relevant, als mehr Speicher verfügbar wurde (da der Assembler-Code mehr Platz beansprucht als der unformatierte Maschinencode) und die Hardware so entwickelt wurde, dass alphanumerische Eingaben möglich sind. Die ersten Assembler wurden also direkt von Leuten geschrieben, die fließend mit Maschinencode umgehen können.

Wenn Sie einen Assembler haben, können Sie einen Compiler für eine höhere Sprache in Assembler schreiben.

Die Geschichte für C hat mehrere Schritte. Der erste C-Compiler wurde in B (ein Vorgänger von C) geschrieben, der wiederum in BCPL geschrieben wurde. BCPL ist eine ziemlich einfache Sprache (zum Beispiel hat sie überhaupt keine Typen), ist aber immer noch ein Schritt weiter als Raw Assembler. Sie sehen also, wie allmählich komplexere Sprachen in einfacheren Sprachen erstellt werden, bis hin zu Assembler. Und selbst C ist für heutige Verhältnisse eine ziemlich kleine und einfache Sprache.

Heutzutage wird der erste Compiler für eine neue Sprache oft in C geschrieben, aber wenn die Sprache eine bestimmte Reife erreicht, wird sie oft "in sich selbst" umgeschrieben. Der erste Java-Compiler wurde in C geschrieben, später jedoch in Java umgeschrieben. Der erste C # -Compiler wurde in C ++ geschrieben, aber vor kurzem wurde er in C # umgeschrieben. Der Python-Compiler / -Interpreter ist in C geschrieben, aber das PyPy-Projekt ist ein Versuch, es in Python umzuschreiben.

Es ist jedoch nicht immer möglich, einen Compiler / Interpreter für eine Sprache in der Sprache selbst zu schreiben. Ein in JavaScript geschriebener JavaScript-Interpreter ist vorhanden, aber die Compiler / Interpreter in aktuellen Browsern sind aus Leistungsgründen immer noch in C oder C ++ geschrieben. In JavaScript geschriebenes JavaScript ist einfach zu langsam.

Sie müssen C jedoch nicht als "Startsprache" für einen Compiler verwenden. Der erste F # -Compiler wurde in OCaml geschrieben, der anderen Sprache, die mit F # am engsten verwandt ist. Wenn der Compiler fertig war, wurde er in F # umgeschrieben. Der erste Compiler für Perl 6 wurde in Haskell geschrieben (eine reine funktionale Sprache, die sich von Perl stark unterscheidet), verfügt jedoch jetzt über einen Compiler in C.

Ein interessanter Fall ist Rust, wo der erste Compiler in OCaml geschrieben wurde (jetzt ist er in Rust umgeschrieben). Dies ist insofern bemerkenswert, als OCaml im Allgemeinen als höher eingestuft wird als Rust, eine Sprache, die den Metallsystemen näher kommt. Es handelt sich also nicht immer um Sprachen höherer Ebenen, die in Sprachen niedrigerer Ebenen implementiert sind, sondern möglicherweise auch umgekehrt.

JacquesB
quelle
3

Angenommen, Sie beginnen mit einem bloßen Befehlssatz und nichts anderem, dann erstellen Sie zunächst einen minimalen Assembler oder Compiler mit nur wenigen Funktionen, mit dem eine Datei geladen, eine minimale Teilmenge der Zielsprache analysiert und eine ausführbare Datei generiert werden kann Datei als Ausgabe, indem der rohe Maschinencode mit einem Hex-Editor oder ähnlichem geschrieben wird.

Sie würden dann diesen kaum funktionierenden Compiler oder Assembler verwenden, um einen etwas leistungsfähigeren Compiler oder Assembler zu implementieren, der eine größere Teilmenge der Zielsprache erkennen kann. Aufschäumen, ausspülen, wiederholen, bis Sie das Endprodukt haben.

John Bode
quelle
2

Es ist nicht so schwer, wie es scheint. In der Kindheit;) habe ich einige x86-Demontagen vorgenommen.

Sie müssen es nicht einmal speziell lernen. Es passiert einfach, wenn Sie in der Lage sind, in ASM zu programmieren und dann versuchen, eine Drittanbieter-Binärdatei mithilfe interaktiver Disassembler zu reparieren. Oder wenn Sie Ihren eigenen Schutz mit Codeverschlüsselung schreiben.

Dh manchmal migrieren Sie sogar ohne Wunder von Sprache zu Codes.

Pavel Koryagin
quelle
1

Die ersten Compiler wurden in Assemblersprache implementiert. Und die ersten Assembler wurden implementiert, indem Programme in Binärform codiert wurden ...


Es ist noch nicht so lange her, dass das Programmieren in Binärform eine Fähigkeit war, die die Leute verwendeten.

Als ich ein Student war, erinnere ich mich an eine Programmierübung, bei der ein winziges Programm in PDP-8 (glaube ich) Maschinencode geschrieben, über die Schalter an der Vorderseite eingegeben und ausgeführt wurde. Einige Jahre später kaufte ich mir ein 6502-Systementwicklungskit mit einer Hex-Tastatur für die Programmeingabe und 4 KB RAM.

Stephen C
quelle
-3

EINE SEHR EINFACHE ANTWORT Angenommen, wir schreiben ein festverdrahtetes Programm und speichern es im ROM. Es kann als Compiler betrachtet werden. Ich möchte nur sagen, dass der allererste Compiler fest verdrahtet war. Im Zuge der Verbesserung der Technologie wurden diese einfachen Compiler dann verwendet, um Compiler auf hoher Ebene zu schreiben.

DINOTOPO
quelle