Welche Eigenschaften einer Programmiersprache machen eine Kompilierung unmöglich?

72

Frage:

"Bestimmte Eigenschaften einer Programmiersprache erfordern möglicherweise, dass der darin geschriebene Code nur durch Interpretation ausgeführt wird. Mit anderen Worten, die Kompilierung zu einem systemeigenen Maschinencode einer herkömmlichen CPU ist nicht möglich. Was sind diese Eigenschaften?"

Compiler: Prinzipien und Praxis von Parag H. Dave und Himanshu B. Dave (2. Mai 2012)

Das Buch gibt keinen Hinweis auf die Antwort. Ich habe versucht, die Antwort auf Konzepte von Programmiersprachen (SEBESTA) zu finden, aber ohne Erfolg. Auch die Websuche war wenig hilfreich. Hast du eine Ahnung?

Anderson Nascimento Nunes
quelle
31
Bekanntermaßen kann Perl nicht einmal analysiert werden . Davon abgesehen scheint die Behauptung ohne weitere Annahmen trivial falsch zu sein: Wenn es einen Interpreter gibt, kann ich Interpreter und Code immer in einer ausführbaren Datei bündeln, voila.
Raphael
4
@Raphael: Gute Idee, aber ... 1) Sie gehen davon aus, dass der Code verfügbar ist, bevor er ausgeführt wird. Das gilt nicht für die interaktive Nutzung. Natürlich können Sie die Just-in-Time-Kompilierung verwenden, um systemeigenen Code für Bash-Anweisungen oder PostScript-Stapelinhalte zu erstellen, aber das ist eine ziemlich verrückte Idee. 2) Ihre Idee kompiliert den Code nicht wirklich: Das Bundle ist keine kompilierte Version des Codes, aber dennoch ein Interpreter für den Code.
Reinierpost
7
In der guten alten Zeit hatte ich gwbasic-Programme selbst editiert (gwbasic speichert grundlegende Programme in einer Art Bytecode). Ich kann mir derzeit keine vernünftige Möglichkeit vorstellen, diese zu systemeigenem Maschinencode zu kompilieren, ohne die Möglichkeit zu verlieren, sich selbst zu bearbeiten.
PlasmaHH
15
@PlasmaHH: Selbstmodifizierender Code stammt aus dem Jahr 1948. Der erste Compiler wurde 1952 geschrieben. Das Konzept des selbstmodifizierenden Codes wurde in nativem Maschinencode erfunden .
Mooing Duck
10
@reinierpost Raphael nimmt zu diesem Thema eine theoretische Position ein. Es hat den Vorzug, die konzeptionellen Grenzen der Frage aufzuzeigen. Das Kompilieren ist die Übersetzung von Sprache S in Sprache T. Sprache T könnte eine Erweiterung von S sein, zu der Interpretationscode in einer anderen Sprache hinzugefügt werden kann. Das Bündeln von S und seinem Interpreter ist also ein Programm in der Sprache T. Für einen Ingenieur ist es absurd, aber es zeigt, dass es nicht einfach ist, die Frage sinnvoll zu formulieren. Wie unterscheidet man einen akzeptablen Kompilierungsprozess von einem inakzeptablen (wie Raphaels) aus technischer Sicht?
Babou

Antworten:

61

Die Unterscheidung zwischen interpretiertem und kompiliertem Code ist wahrscheinlich eine Fiktion, wie Raphaels Kommentar unterstreicht :

the claim seems to be trivially wrong without further assumptions: if there is
an interpreter, I can always bundle interpreter and code in one executable ...

Tatsache ist, dass Code immer von der Software, der Hardware oder einer Kombination aus beiden interpretiert wird und der Kompilierungsprozess nicht erkennen kann, um welchen Code es sich handelt.

Was Sie als Zusammenstellung empfinden, ist ein Übersetzungsprozess von einer Sprache (für die Quelle) in eine andere Sprache (für das Ziel). Und der Interpreter für ist in der Regel unterscheidet sich von dem Interpreter für .STST

Das kompilierte Programm wird von einer syntaktischen Form übersetzt auf einem anderen syntaktische Form , so dass die beabsichtigte Semantik der Sprachen gegeben und , und die gleiche Rechenverhalten, bis auf ein paar Dinge , die Sie in der Regel versuchen, Änderungen, möglicherweise zur Optimierung, wie Komplexität oder einfache Effizienz (Zeit, Raum, Oberfläche, Energieverbrauch). Ich versuche, nicht von funktionaler Äquivalenz zu sprechen, da dies genaue Definitionen erfordern würde.PSPTSTPSPT

Einige Compiler wurden lediglich verwendet, um die Größe des Codes zu verringern und nicht, um die Ausführung zu "verbessern". Dies war der Fall für die Sprache, die im Plato-System verwendet wurde (obwohl sie es nicht als Kompilieren bezeichnet haben).

Sie können Ihren Code als vollständig kompiliert betrachten, wenn Sie nach dem Kompilieren den Interpreter für nicht mehr benötigen . Zumindest ist dies die einzige Möglichkeit, Ihre Frage als technische und nicht als theoretische Frage zu lesen (da ich den Interpreter theoretisch immer neu erstellen kann).S

Eine Sache, die ein Problem aufwerfen könnte, ist die Meta-Zirkularität . Dann manipuliert ein Programm syntaktische Strukturen in seiner eigenen Quellsprache und erzeugt Programmfragmente, die dann so interpretiert werden, als wären sie Teil des ursprünglichen Programms gewesen. Da Sie als Ergebnis einer willkürlichen Berechnung, die bedeutungslose syntaktische Fragmente manipuliert , beliebige Programmfragmente in der Sprache erzeugen können , würde ich vermuten, dass Sie es (aus technischer Sicht) nahezu unmöglich machen können, das Programm in die Sprache zu kompilieren , so dass es werden nun Fragmente von . Daher wird der Interpreter für benötigt, oder zumindest der Compiler von bisSSTTSST für das schnelle Kompilieren generierter Fragmente in (siehe auch dieses Dokument ).S

Ich bin mir aber nicht sicher, wie dies richtig formalisiert werden kann (und habe momentan keine Zeit dafür). Und unmöglich ist ein großes Wort für ein Thema, das nicht formalisiert ist.

Weitere Bemerkungen

Nach 36 Stunden hinzugefügt. Möglicherweise möchten Sie diese sehr lange Fortsetzung überspringen.

Die vielen Kommentare zu dieser Frage zeigen zwei Sichtweisen auf das Problem: eine theoretische Sichtweise, die es für bedeutungslos hält, und eine technische Sichtweise, die sich leider nicht so leicht formalisieren lässt.

Es gibt viele Möglichkeiten, Interpretation und Zusammenstellung zu betrachten, und ich werde versuchen, einige davon zu skizzieren. Ich werde versuchen, so ungezwungen wie möglich zu sein

Das Tombstone-Diagramm

Eine der frühen Formalisierungen (Anfang der 1960er bis Ende der 1990er Jahre) sind die T- oder Tombstone-Diagramme . Diese Diagramme zeigen in zusammensetzbaren grafischen Elementen die Implementierungssprache des Interpreters oder Compilers, die zu interpretierende oder zu kompilierende Quellsprache und bei Compilern die Zielsprache. Ausgefeiltere Versionen können Attribute hinzufügen. Diese grafischen Darstellungen können als Axiome, Folgerungsregeln angesehen werden, die zur mechanischen Ableitung der Prozessorgenerierung aus einem Beweis ihrer Existenz aus den Axiomen à la Curry-Howard verwendet werden können (obwohl ich nicht sicher bin, ob dies in den sechziger Jahren geschehen ist :).

Teilbewertung

Eine weitere interessante Sichtweise ist das partielle Evaluierungsparadigma . Ich betrachte Programme einfach als eine Art Funktionsimplementierung, die bei bestimmten Eingabedaten eine Antwort berechnet. Dann ist ein Interpreter für die Sprache ein Programm, das ein in geschriebenes Programm und Daten für dieses Programm nimmt und das Ergebnis gemäß der Semantik von berechnet . Die partielle Auswertung ist eine Technik zum Spezialisieren eines Programms aus zwei Argumenten und , wenn nur ein Argument, beispielsweise , bekannt ist. Die Absicht ist eine schnellere Auswertung, wenn Sie endlich das zweite Argument erhaltenISSpSSdSa1a2a1a2 . Es ist besonders nützlich, wenn sich häufiger ändert als da die Kosten für die Teilbewertung mit bei allen Berechnungen, bei denen sich nur ändert , amortisiert werden können .a2a1a1a2

Dies ist eine häufige Situation beim Algorithmus-Design (häufig das Thema des ersten Kommentars zu SE-CS), wenn ein statischerer Teil der Daten vorverarbeitet wird, sodass die Kosten für die Vorverarbeitung bei allen Anwendungen amortisiert werden können des Algorithmus mit mehr variablen Teilen der Eingabedaten.

Dies ist auch die eigentliche Situation von Interpreten, da das erste Argument das auszuführende Programm ist und normalerweise mehrmals mit unterschiedlichen Daten ausgeführt wird (oder wenn Unterteile mehrmals mit unterschiedlichen Daten ausgeführt werden). Daher ist es naheliegend, einen Interpreter für eine schnellere Bewertung eines bestimmten Programms zu spezialisieren, indem er dieses Programm teilweise als erstes Argument bewertet. Dies kann als ein Weg zur Kompilierung des Programms angesehen werden, und es wurden umfangreiche Forschungsarbeiten zur Kompilierung durch partielle Bewertung eines Interpreters für sein erstes (Programm-) Argument durchgeführt.

Der Satz von Smn

Das Schöne am partiellen Bewertungsansatz ist, dass er seine Wurzeln in der Theorie hat (obwohl die Theorie ein Lügner sein kann), insbesondere im Smn-Theorem von Kleene . Ich versuche hier, eine intuitive Darstellung davon zu geben, in der Hoffnung, dass es reine Theoretiker nicht verärgert.

Bei einer Gödel-Nummerierung von rekursiven Funktionen können Sie als Ihre Hardware anzeigen , sodass bei einer Gödel-Nummer (gelesener Objektcode ) eines Programms die durch definierte Funktion ist (dh durch den Objektcode berechnet) Ihre Hardware).φφpφpp

In seiner einfachsten Form ist der Satz in Wikipedia wie folgt angegeben (bis auf eine kleine Änderung in der Notation):

Bei einer Gödel-Nummerierung von rekursiven Funktionen gibt es eine primitive rekursive Funktion von zwei Argumenten mit der folgenden Eigenschaft: Für jede Gödel-Nummer einer partiell berechenbaren Funktion mit zwei Argumenten werden die Ausdrücke und sind für die gleichen Kombinationen von natürlichen Zahlen und , und ihre Werte sind für jede solche Kombination gleich. Mit anderen Worten gilt die folgende erweiterte Gleichheit von Funktionen für jedes : & sgr; q f & phiv; & sgr; ( q , x ) ( y ) f ( x , y ) x y xφσqfφσ(q,x)(y)f(x,y)xyxφσ(q,x)λy.φq(x,y).

Nehmen wir nun als Interpreter , als Quellcode eines Programms und als Daten für dieses Programm, so können wir schreiben: I S x p S yqISxpSydφσ(IS,pS)λd.φIS(pS,d).

φIS kann als die Ausführung des Interpreters auf der Hardware angesehen werden, dh als eine Blackbox, die bereit ist, in der Sprache geschriebene Programme zu interpretieren .ISS

Die Funktion kann als eine Funktion angesehen werden, die den Interpreter für das Programm wie bei der Teilauswertung spezialisiert. Somit kann gesehen werden, dass die Gödel-Nummer einen Objektcode aufweist, der die kompilierte Version des Programms .σISPSσ(IS,pS)pS

Die Funktion kann als eine Funktion angesehen werden, die den Quellcode eines in Sprache geschriebenen Programms als Argument nimmt und die Objektcodeversion für dieses Programm . So ist das, was in der Regel einen Compiler genannt wird.CS=λqS.σ((IS,qS)qSSCS

Einige Schlussfolgerungen

Wie gesagt: "Theorie kann ein Lügner sein" oder scheint es tatsächlich zu sein. Das Problem ist, dass wir nichts von der Funktion wissen . Tatsächlich gibt es viele solcher Funktionen, und ich vermute, dass der Beweis des Theorems eine sehr einfache Definition verwendet, die aus technischer Sicht vielleicht nicht besser ist als die von Raphael vorgeschlagene Lösung: einfach die zu bündeln Quellcode mit dem Interpreter . Dies ist immer möglich, so dass wir sagen können: Kompilieren ist immer möglich.q S I SσqSIS

Die Formalisierung einer restriktiveren Vorstellung von dem, was ein Compiler ist, würde einen subtileren theoretischen Ansatz erfordern. Ich weiß nicht, was in dieser Richtung getan worden sein könnte. Die sehr reale Arbeit an der Teilbewertung ist aus technischer Sicht realistischer. Und es gibt natürlich auch andere Techniken zum Schreiben von Compilern, einschließlich der Extraktion von Programmen aus dem Nachweis ihrer Spezifikation, wie sie im Kontext der Typentheorie auf der Grundlage des Curry-Howard-Isomorphismus entwickelt wurden (aber ich komme außerhalb meines Zuständigkeitsbereichs). .

Ich wollte damit zeigen, dass Raffaels Bemerkung nicht "verrückt" ist, sondern eine vernünftige Erinnerung daran, dass die Dinge nicht offensichtlich und nicht einmal einfach sind. Zu sagen, dass etwas unmöglich ist, ist eine starke Aussage, die genaue Definitionen und einen Beweis erfordert, wenn auch nur, um genau zu verstehen, wie und warum es unmöglich ist . Es kann jedoch recht schwierig sein, eine geeignete Formalisierung zu erstellen, um einen solchen Beweis zu erbringen.

Dies bedeutet, dass, selbst wenn ein bestimmtes Feature nicht kompilierbar ist, im Sinne der Ingenieure, Standardkompilierungstechniken immer auf Teile der Programme angewendet werden können, die ein solches Feature nicht verwenden, wie Gilles 'Antwort bemerkte.

Um Gilles 'Schlüsselbemerkungen zu folgen, dass abhängig von der Sprache einige Dinge zur Kompilierungszeit erledigt werden können, während andere zur Laufzeit erledigt werden müssen und daher spezifischen Code erfordern, können wir sehen, dass das Konzept der Kompilierung tatsächlich ist schlecht definiert und wahrscheinlich in keiner zufriedenstellenden Weise definierbar. Die Kompilierung ist nur ein Optimierungsprozess, wie ich im Teilauswertungsabschnitt gezeigt habe, als ich sie mit der statischen Datenvorverarbeitung in einigen Algorithmen verglichen habe.

Als komplexer Optimierungsprozess gehört der Begriff der Kompilierung tatsächlich zu einem Kontinuum. Abhängig von den Merkmalen der Sprache oder des Programms sind einige Informationen möglicherweise statisch verfügbar und ermöglichen eine bessere Optimierung. Andere Dinge müssen auf die Laufzeit verschoben werden. Wenn es wirklich schlimm wird, muss zumindest für einige Teile des Programms zur Laufzeit alles erledigt werden, und Sie können den Quellcode nur mit dem Interpreter bündeln. Diese Bündelung ist also nur das untere Ende dieses Kompilierungskontinuums. Bei der Forschung zu Compilern geht es vor allem darum, Wege zu finden, um statisch zu arbeiten, was früher dynamisch gemacht wurde. Die Garbage Collection zur Kompilierungszeit scheint ein gutes Beispiel zu sein.

Beachten Sie, dass die Aussage, dass der Kompilierungsprozess Maschinencode erzeugen sollte, keine Hilfe ist. Genau das kann die Bündelung bewirken, da es sich bei dem Interpreter um Maschinencode handelt (bei der Cross-Kompilierung kann es etwas komplexer werden).

babou
quelle
3
" unmöglich ist ein großes Wort" Ein sehr sehr großes Wort. =)
Brian S
3
Wenn man "Kompilierung" definiert, bezieht sich dies auf eine Folge von Schritten, die vollständig ablaufen, bevor ein ausführendes Programm seine erste Eingabe erhält, und die Interpretation als der Vorgang, bei dem der Programmfluss über Mittel gesteuert wird, die nicht Teil des abstrakten Maschinenmodells des Programms sind Damit eine Sprache kompiliert werden kann, muss es dem Compiler möglich sein, vor Beginn der Ausführung jede mögliche Bedeutung eines Sprachkonstrukts zu identifizieren. In Sprachen, in denen ein Sprachkonstrukt eine unbegrenzte Anzahl von Bedeutungen haben könnte, funktioniert die Kompilierung nicht.
Supercat
@ BrianS Nein, ist es nicht und es ist unmöglich, etwas anderes zu beweisen;)
Michael Gazonda
@supercat Das ist noch keine Definition. Was bedeutet ein Sprachkonstrukt?
Rhymoid
Ich mag das Konzept, einen Compiler / Interpreter als eine Art Teilausführung anzusehen!
Bergi
17

Die Frage ist eigentlich nicht, ob eine Kompilierung unmöglich ist . Wenn eine Sprache interpretiert werden kann¹, kann sie auf einfache Weise kompiliert werden, indem der Interpreter mit dem Quellcode gebündelt wird. Die Frage ist, welche Sprachmerkmale dies im Wesentlichen zur einzigen Möglichkeit machen.

Ein Interpreter ist ein Programm, das Quellcode als Eingabe verwendet und sich wie in der Semantik dieses Quellcodes angegeben verhält. Wenn ein Interpreter erforderlich ist, bedeutet dies, dass die Sprache eine Möglichkeit zum Interpretieren des Quellcodes enthält. Diese Funktion wird aufgerufen eval. Wenn ein Interpreter als Teil der Laufzeitumgebung der Sprache benötigt wird, bedeutet dies, dass die Sprache Folgendes enthält eval: Entweder evalexistiert sie als Grundelement, oder sie kann auf irgendeine Weise codiert werden. Als Skriptsprachen bekannte Sprachen enthalten normalerweise eine evalFunktion, wie die meisten Lisp- Dialekte.

Nur weil eine Sprache enthält, evalbedeutet dies nicht, dass der Großteil davon nicht zu nativem Code kompiliert werden kann. Zum Beispiel gibt es optimierte Lisp-Compiler, die guten nativen Code generieren und trotzdem unterstützen eval. evalDer Code kann interpretiert oder im laufenden Betrieb kompiliert werden.

evalist die ultimative Funktion, die einen Dolmetscher benötigt, aber es gibt auch andere Funktionen, die einen Dolmetscher erfordern. Betrachten Sie einige typische Phasen eines Compilers:

  1. Parsing
  2. Typüberprüfung
  3. Codegenerierung
  4. Verknüpfen

evalbedeutet, dass alle diese Phasen zur Laufzeit durchgeführt werden müssen. Es gibt andere Funktionen, die die native Kompilierung erschweren. Einige Sprachen unterstützen die späte Verknüpfung, indem sie angeben, wie Funktionen (Methoden, Prozeduren usw.) und Variablen (Objekte, Verweise usw.) von nicht lokalen Codeänderungen abhängen können. Dies macht es schwierig (aber nicht unmöglich), effizienten nativen Code zu generieren: Es ist einfacher, Objektreferenzen als Aufrufe in einer virtuellen Maschine zu speichern und die VM-Engine die Bindungen im laufenden Betrieb verwalten zu lassen.

Im Allgemeinen erschwert die Reflexion die Kompilierung von Sprachen zu systemeigenem Code. Ein Eval-Primitiv ist ein extremer Reflexionsfall. Viele Sprachen gehen nicht so weit, haben jedoch eine Semantik, die in Bezug auf eine virtuelle Maschine definiert ist. So kann beispielsweise Code eine Klasse nach Namen abrufen, ihre Vererbung überprüfen, ihre Methoden auflisten, eine Methode aufrufen usw. Java mit JVM und C # mit .NET sind zwei berühmte Beispiele. Die einfachste Möglichkeit, diese Sprachen zu implementieren, besteht darin, sie zu Bytecode zu kompilieren. Es gibt jedoch native Compiler (viele Just-in-Time- Compiler ), die mindestens Programmfragmente kompilieren, die keine erweiterten Reflektionsfunktionen verwenden.

Die Typprüfung bestimmt, ob ein Programm gültig ist. Verschiedene Sprachen haben unterschiedliche Standards für die Analyse zur Kompilierungszeit im Verhältnis zur Laufzeit: Eine Sprache wird als "statisch typisiert" bezeichnet, wenn sie vor dem Ausführen des Codes viele Überprüfungen durchführt, und als "dynamisch typisiert", wenn dies nicht der Fall ist. Einige Sprachen enthalten eine dynamische Besetzungsfunktion oder eine Funktion zum Entfernen von Marshall-and-Typechecks. Für diese Funktion muss ein Typechecker in die Laufzeitumgebung eingebettet werden. Dies ist orthogonal zu den Anforderungen, einen Codegenerator oder einen Interpreter in die Laufzeitumgebung aufzunehmen.

¹ Übung: Definieren Sie eine Sprache, die nicht interpretiert werden kann.

Gilles
quelle
(1) Ich bin nicht einverstanden, einen Interpreter mit Quellcode zu bündeln, der als kompiliert gilt, aber der Rest Ihres Beitrags ist ausgezeichnet. (2) Stimme voll und ganz der Bewertung zu. (3) Ich verstehe nicht, warum es durch Reflexion schwierig wäre, Sprachen zu nativem Code zu kompilieren. Objective-C hat Reflexion, und (ich nehme an) es ist in der Regel kompiliert. (4) Vage verwandte Anmerkung: Metamagische C ++ - Vorlagen werden in der Regel eher interpretiert als kompiliert und dann ausgeführt.
Mooing Duck
Gerade ist mir aufgefallen, Lua wird zusammengestellt. Der evalkompiliert einfach den Bytecode und dann führt die Binärdatei als separaten Schritt den Bytecode aus. Und es hat definitiv Reflexion in der kompilierten Binärdatei.
Mooing Duck
Auf einer Harvard Architecture-Maschine sollte die Kompilierung Code ergeben, auf den niemals als "Daten" zugegriffen werden muss. Ich würde davon ausgehen, dass Informationen aus der Quelldatei, die letztendlich als Daten und nicht als Code gespeichert werden müssen, nicht wirklich "kompiliert" werden. Es ist nichts Falsches daran, dass ein Compiler eine Deklaration wie diese erstellt int arr[] = {1,2,5};und einen initialisierten Datenabschnitt mit [1,2,5] generiert, aber ich würde sein Verhalten nicht als Übersetzung von [1,2,5] in Maschinencode beschreiben. Wenn fast das gesamte Programm als Daten gespeichert werden muss, welcher Teil davon würde dann wirklich "kompiliert"?
Supercat
2
@supercat Das verstehen Mathematiker und Informatiker unter Trivialität. Es passt zur mathematischen Definition, aber es passiert nichts Interessantes.
Gilles
@Gilles: Wenn der Begriff "Kompilieren" für die Übersetzung in Maschinenanweisungen reserviert ist (ohne Beibehaltung der zugehörigen "Daten") und akzeptiert, dass in einer Kompilierungssprache das Verhalten der Array-Deklaration nicht das Array "kompilieren" soll, dann Es gibt einige Sprachen, in denen es unmöglich ist, einen sinnvollen Bruchteil des Codes zu kompilieren.
Supercat
13

Ich denke, die Autoren gehen davon aus, dass Kompilierung bedeutet

  • Das Quellprogramm muss zur Laufzeit nicht vorhanden sein
  • Zur Laufzeit muss kein Compiler oder Interpreter vorhanden sein.

Hier sind einige Beispielfunktionen, die es für ein solches Schema problematisch, wenn nicht "unmöglich" machen würden:

  1. Wenn Sie den Wert einer Variablen zur Laufzeit abfragen können, indem Sie auf die Variable anhand ihres Namens (einer Zeichenfolge) verweisen, müssen die Variablennamen zur Laufzeit vorhanden sein.

  2. Wenn Sie eine Funktion / Prozedur zur Laufzeit aufrufen können, indem Sie sie mit ihrem Namen (der eine Zeichenfolge ist) referenzieren, benötigen Sie die Funktions- / Prozedurnamen zur Laufzeit.

  3. Wenn Sie ein Programm zur Laufzeit erstellen können (als Zeichenfolge), indem Sie beispielsweise ein anderes Programm ausführen oder es von einer Netzwerkverbindung usw. lesen, benötigen Sie zur Laufzeit entweder einen Interpreter oder einen Compiler Führen Sie dieses Programm aus.

Lisp hat alle drei Funktionen. Auf Lisp-Systemen ist daher zur Laufzeit immer ein Interpreter geladen. Die Sprachen Java und C # verfügen zur Laufzeit über Funktionsnamen und Tabellen, in denen nachgeschlagen wird, was sie bedeuten. Wahrscheinlich haben Sprachen wie Basic und Python zur Laufzeit auch Variablennamen. (Da bin ich mir nicht 100% sicher).

Uday Reddy
quelle
Was ist, wenn der "Interpreter" in den Code kompiliert ist? Wenn Sie zum Beispiel Dispatch-Tabellen zum Aufrufen virtueller Methoden verwenden, sind dies ein Beispiel für Interpretation oder Kompilierung?
Erwin Bolwidt
2
msgstr "zur Laufzeit muss kein Compiler oder Interpreter vorhanden sein", oder? Nun, wenn das stimmt, dann kann C auf den meisten Plattformen auch nicht "kompiliert" werden. Die C-Laufzeit hat nicht viel zu tun: Starten, Einrichten von Stacks usw. und Herunterfahren für die atexitVerarbeitung. Aber es muss noch da sein.
Pseudonym
1
"Auf Lisp-Systemen ist zur Laufzeit immer ein Interpreter geladen." - Nicht unbedingt. Viele Lisp-Systeme haben zur Laufzeit einen Compiler. Einige haben nicht einmal einen Dolmetscher.
Jörg W Mittag
2
Netter Versuch, aber de.wikipedia.org/wiki/Lisp_machine#Technical_overview . Sie kompilieren Lisp und sind darauf ausgelegt, das Ergebnis effizient auszuführen.
Peter - Reinstate Monica
@Pseudonym: Die C-Laufzeit ist eine Bibliothek, kein Compiler oder Interpreter.
Mooing Duck
8

Es ist möglich, dass die aktuellen Antworten die Aussagen / Antworten "überdenken". Möglicherweise beziehen sich die Autoren auf das folgende Phänomen. Viele Sprachen haben einen "eval" -ähnlichen Befehl. zB siehe Javascript eval und sein Verhalten wird allgemein als spezieller Teil der CS-Theorie untersucht (zB Lisp). Die Funktion dieses Befehls besteht darin, den String im Kontext der Sprachdefinition auszuwerten. Daher hat es tatsächlich eine Ähnlichkeit mit einem "eingebauten Compiler". Der Compiler kann den Inhalt des Strings erst zur Laufzeit kennen. Daher ist das Kompilieren des Evaluierungsergebnisses in Maschinencode zur Kompilierungszeit nicht möglich.

Andere Antworten weisen darauf hin, dass die Unterscheidung zwischen interpretierten und kompilierten Sprachen in vielen Fällen erheblich verschwimmen kann, insbesondere bei moderneren Sprachen wie Java mit einem "Just-in-Time-Compiler", auch "Hotspot" genannt (Javascript-Engines, z. B. V8, verwenden zunehmend dieselbe Technik). "eval-like" Funktionalität ist sicherlich einer von ihnen.

vzn
quelle
2
V8 ist ein gutes Beispiel. Es ist ein reiner Compiler, es wird nie interpretiert. Es unterstützt jedoch weiterhin die vollständige Semantik von ECMAScript, einschließlich der uneingeschränkten eval.
Jörg W Mittag
1
Lua macht dasselbe.
Mooing Duck
3

LISP ist ein schreckliches Beispiel, da es als eine Art übergeordnete "Maschinensprache" als Grundlage für eine "echte" Sprache konzipiert wurde. Diese "echte" Sprache hat sich nie verwirklicht. LISP-Maschinen basieren auf der Idee, (einen Großteil) von LISP in Hardware auszuführen. Da ein LISP-Interpreter nur ein Programm ist, ist es im Prinzip möglich, es in Schaltungen zu implementieren. Vielleicht nicht praktisch; aber bei weitem nicht unmöglich.

Darüber hinaus gibt es viele in Silizium programmierte Interpreter, die normalerweise als "CPU" bezeichnet werden. Und es ist oft nützlich, Maschinencodes zu interpretieren (noch nicht vorhanden, nicht zur Hand, ...). ZB Linux 'x86_64 wurde zuerst auf Emulatoren geschrieben und getestet. Als die Chips auf den Markt kamen, gab es volle Distributionen, auch nur für Early Adopters / Tester. Java wird häufig in JVM-Code kompiliert, der ein Interpreter ist, der in Silicon nicht allzu schwer zu schreiben wäre.

Die meisten "interpretierten" Sprachen werden zu einer internen Form kompiliert, die optimiert und dann interpretiert wird. Dies ist zB das, was Perl und Python tun. Es gibt auch Compiler für zu interpretierende Sprachen, wie die Unix-Shell. Andererseits ist es möglich, traditionell kompilierte Sprachen zu interpretieren. Ein etwas extremes Beispiel, das ich sah, war ein Editor, der interpretiertes C als Erweiterungssprache verwendete. Es ist C könnte normale, aber einfache Programme ohne Probleme ausführen.

Auf der anderen Seite nehmen moderne CPUs sogar die Eingabe "Maschinensprache" und übersetzen sie in Anweisungen auf niedrigerer Ebene, die dann neu angeordnet und optimiert (dh "kompiliert") werden, bevor sie zur Ausführung übergeben werden.

Diese ganze Unterscheidung zwischen "Compiler" und "Interpreter" ist wirklich umstritten. Irgendwo im Stack gibt es einen ultimativen Interpreter, der "Code" nimmt und "direkt" ausführt. Die Eingabe vom Programmierer durchläuft Transformationen entlang der Linie, die als "Kompilieren" bezeichnet wird und nur eine willkürliche Linie in den Sand zeichnet.

vonbrand
quelle
1

Die Realität ist, dass es einen großen Unterschied zwischen der Interpretation eines Basic-Programms und der Ausführung von Assembler gibt. Und dazwischen gibt es Bereiche mit P-Code / Byte-Code mit oder ohne (Just-in-Time-) Compiler. Deshalb werde ich versuchen, einige Punkte im Kontext dieser Realität zusammenzufassen.

  • Wenn das Parsen des Quellcodes von den Laufzeitbedingungen abhängt, kann das Schreiben eines Compilers unmöglich oder so schwierig werden, dass sich niemand darum kümmert.

  • Code, der sich selbst ändert, kann im Allgemeinen nicht kompiliert werden.

  • Ein Programm, das eine eval-ähnliche Funktion verwendet, kann normalerweise nicht im Voraus vollständig kompiliert werden (wenn Sie die ihm zugeführte Zeichenfolge als Teil des Programms ansehen), auch wenn Sie den evaluierten Code wiederholt ausführen, kann dies immer noch der Fall sein nützlich, damit Ihre eval-ähnliche Funktion den Compiler aufruft. Einige Sprachen bieten eine API für den Compiler, um dies zu vereinfachen.

  • Die Möglichkeit, nach Namen zu suchen, schließt die Kompilierung nicht aus, Sie benötigen jedoch Tabellen (wie erwähnt). Das Aufrufen von Funktionen nach Namen (wie IDispatch) erfordert eine Menge Installationsaufwand, bis zu dem Punkt, an dem ich denke, dass die meisten Leute zustimmen würden, dass es sich effektiv um einen Funktionsaufruf-Interpreter handelt.

  • Eine schwache Eingabe (unabhängig von Ihrer Definition) erschwert die Kompilierung und macht das Ergebnis möglicherweise weniger effizient, ist jedoch häufig nicht unmöglich, es sei denn, unterschiedliche Werte lösen unterschiedliche Parser aus. Hier gibt es eine gleitende Skala: Wenn der Compiler den tatsächlichen Typ nicht ableiten kann, muss er Verzweigungen, Funktionsaufrufe und solche ausgeben, die sonst nicht vorhanden wären, und so effektiv Interpreter-Bits in die ausführbare Datei einbetten.

Anonymer Feigling
quelle
1

Ich würde davon ausgehen, dass das Hauptmerkmal einer Programmiersprache, die einen Compiler für die Sprache unmöglich macht (im engeren Sinne, siehe auch Selbst-Hosting ), das Selbstmodifikationsmerkmal ist . Das heißt, die Sprache erlaubt es, den Quellcode während der Laufzeit zu ändern (was ein Compiler, der festen und statischen Objektcode erzeugt, nicht kann). Ein klassisches Beispiel ist Lisp (siehe auch Homoikonizität ). Ähnliche Funktionen werden mit einem Sprachkonstrukt wie eval bereitgestellt , das in vielen Sprachen enthalten ist (z. B. JavaScript). Eval ruft den Interpreter (als Funktion) zur Laufzeit auf .

Mit anderen Worten, die Sprache kann ein eigenes Metasystem darstellen (siehe auch Metaprogrammierung ).

Beachten Sie, dass die Sprachreflexion im Sinne des Abfragens von Metadaten eines bestimmten Quellcodes und möglicherweise des Änderns nur der Metadaten (wie der Reflexionsmechanismus von Java oder PHP) für einen Compiler kein Problem darstellt , da dieser bereits über diese verfügt Metadaten zur Kompilierungszeit und können bei Bedarf dem kompilierten Programm zur Verfügung gestellt werden.

Ein weiteres Merkmal, das das Kompilieren erschwert oder nicht zur besten Option macht (aber nicht unmöglich macht), ist das in der Sprache verwendete Schreibschema (dh dynamisches Schreiben im Vergleich zum statischen Schreiben und starkes Schreiben im Vergleich zum losen Schreiben). Dies erschwert es dem Compiler, zur Kompilierungszeit die gesamte Semantik zu haben, sodass ein Teil des Compilers (mit anderen Worten ein Interpreter) effektiv Teil des generierten Codes wird, der die Semantik zur Laufzeit verarbeitet . Dies ist also keine Zusammenstellung, sondern eine Interpretation .

Nikos M.
quelle
LISP ist ein schreckliches Beispiel, wie es begreifen als sprt war
vonbrand
@vonbrand, vielleicht aber zeigt sowohl das Homoikonizitätskonzept als auch die einheitliche Datencode-Dualität
Nikos M.
-1

Ich bin der Meinung, dass die ursprüngliche Frage nicht gut formuliert ist. Die Autoren der Frage wollten möglicherweise eine etwas andere Frage stellen: Welche Eigenschaften einer Programmiersprache erleichtern das Schreiben eines Compilers dafür?

Zum Beispiel ist es einfacher, einen Compiler für eine kontextfreie Sprache zu schreiben als eine kontextsensitive Sprache. Die Grammatik, die eine Sprache definiert, kann auch Probleme enthalten, die das Kompilieren erschweren, z. B. Mehrdeutigkeiten. Solche Probleme können gelöst werden, erfordern jedoch zusätzlichen Aufwand. In ähnlicher Weise sind Sprachen, die durch uneingeschränkte Grammatik definiert sind, schwerer zu analysieren als kontextsensitive Sprachen (siehe Chomsky-Hierarchie ). Meines Wissens sind die am weitesten verbreiteten prozeduralen Programmiersprachen nahezu kontextfrei, enthalten jedoch einige kontextsensitive Elemente, sodass sie relativ einfach zu kompilieren sind.

Georgie
quelle
2
Die Frage hat eindeutig die Absicht, Compiler und Interpreten abzulehnen / zu vergleichen. Obwohl sie möglicherweise anders funktionieren und dies normalerweise mit Ausnahme des obigen @ Raphael-Grenzfalls tun, haben sie hinsichtlich Syntaxanalyse und Mehrdeutigkeit genau dieselben Probleme. Syntax kann also nicht das Problem sein. Ich glaube auch, dass syntaktische Probleme heutzutage nicht das Hauptanliegen beim Schreiben von Compilern sind, obwohl dies in der Vergangenheit der Fall war. Ich bin nicht der Abwähler: Ich ziehe es vor zu kommentieren.
Babou
-1

Die Frage hat eine richtige Antwort, die so offensichtlich ist, dass sie normalerweise als trivial übersehen wird. Aber es spielt in vielen Zusammenhängen eine Rolle und ist der Hauptgrund, warum es interpretierte Sprachen gibt:

Das Kompilieren von Quellcode in Maschinencode ist unmöglich, wenn Sie den Quellcode noch nicht haben.

Dolmetscher erhöhen die Flexibilität und insbesondere die Flexibilität, Code auszuführen, der beim Kompilieren des zugrunde liegenden Projekts nicht verfügbar war.

tylerl
quelle
2
"Ich habe den Quellcode verloren" ist keine Eigenschaft einer Programmiersprache, sondern eines bestimmten Programms, sodass die Frage nicht beantwortet wird. Und Sie brauchen definitiv ein Zitat für die Behauptung, dass die Vermeidung des Verlusts des Quellcodes "der Hauptgrund dafür ist, dass interpretierte Sprachen existieren" oder sogar ein Grund, warum sie existieren.
David Richerby
1
@DavidRicherby Ich denke, der Anwendungsfall, den tyleri im Sinn hat, ist die interaktive Interpretation, dh der zur Laufzeit eingegebene Code. Ich stimme jedoch zu, dass dies nicht in Frage kommt, da es kein Merkmal der Sprache ist.
Raphael
@DavidRicherby und Raphael, ich sage, dass der Autor dieses Beitrags (was ich in meiner Antwort beschreibe) als Selbstmodifikationsmerkmal impliziert, das natürlich ein Sprachkonstrukt von Natur aus und kein Artefakt eines bestimmten Programms ist
Nikos M.