Hochsprache zu Maschinen-Code und zurück

[starcow]

Kürzlich wurde eine Frage an mich herangetragen, die mich ins Grübeln brachte und bei der ich mir auch jetzt nicht sicher bin, ob ich die richtige Antwort darauf kenne.

Etwas gekürzt lautet sie in etwa so:

Ist es (prinzipiell) möglich einen Compiler zu schreiben, der Code von einer Hochsprache (z.B. C) in eine andere transkribiert?
Dabei ist jedoch gefordert, dass beide Sources-Codes kompiliert (immer) zum exakt selben Maschinencode führen (Python jetzt in diesem Fall wie C zu Maschinencode - nicht zu Bytecode).

Meine Einschätzung wäre:
Nein, das ist prinzipiell unmöglich.
Begründen müsste es sich damit lassen, dass es keine Möglichkeit gibt, in jedem Fall und ohne Ausnahme Maschinencode zu re-compilen, dessen Quellcode dann erneut compiliert wieder zum exakt gleichen Maschinencode führt (vermute ich).

Die reine "Funktionalität" müsste sich ja eigentlich immer in jede Sprache übersetzen lassen, die Turing complete ist. Doch das beinhaltet ja dadurch nicht auch zwangsläufig, dass die Sources-Codes compiliert zum selben Maschinen-Code führen.

Mit anderen Worten (konkret): Man kann keinen Compiler schrieben, der aus C-Code Python-Code erzeugt (oder umgekehrt), so dass beide dann compiliert zum im selben Maschinencode führen (mit Gewissheit und immer).

[Alexander Kornrumpf]

Ich denke die allgemeine Version dieser Frage ist ob es drei Sprachen geben kann die paarweise zueinander deterministisch transpilierbar sind aber nicht dieselbe Grammatik haben. Die Nebenbedingung dass einer der drei Sprachen x86 sein muss (oder was ist "Maschinencode"?) macht es schon schwerer, die Idee, dass alle drei existierende Sprachen sein sollen macht es viel schwieriger. C, ASM und x86 sind vielleicht jeweils nahe genug aneinander dass man was tricksen kann, aber man müsste den Compiler dann explizit mit diesem Ziel schreiben. Mit einem "normalen" C Compiler wird es natürlich nicht gehen.

Aber die generischen Frage ohne Bindung an existierende Sprachen ist ein interessantes Projekt für einen Informatikstudenten. Ich bin sicher da kommt man mit Mitteln der theoretischen Informatik sehr weit. Am Ende wird es aber auf die Frage hinauslaufen, wann du zwei Grammatiken als "verschieden" genug akzeptierst, dass es nicht trivial ist.

[starcow]

Vielen Dank Kornrumpf, das hat geholfen!

[Lord Delvin]

Kommt auf die Randbedingungen an, aber i.A. nicht. Du kannst dir überlegen ob die Quellen immer in den Metadaten zu halten zählen würde; so ne Art schräger Quine (https://de.wikipedia.org/wiki/Quine_(Computerprogramm). Wenn das nicht zählt ist die Antwort nein auch dann, wenn es x86, C und C ist. Man trollt sich da mit einfachen Beispielen, aber bei größen Programmen ist der Informationsverlust einfach zu hoch.

[Jonathan]

Man kann die Frage auf viele Arten betrachten, aber die meisten davon finde ich glaube ich nicht wirklich interessant.

Es ist ja zunächst einmal nichtmal einfach ein und den selben Quellcode auf verschiedenen Computern in exakt den selben Maschinencode zu übersetzen. Compilerversionen, Versionen verschiedener Abhängigkeiten, und so weiter. Stichwort "reproducible builds". Alleine die Tatsache, dass Leute darüber nachdenken und das Fordern, zeigt schon, dass es eher die Ausnahme als die Norm ist und man Arbeit investieren muss, um das hinzubekommen.

Dann ist der Vergleich zwischen C und Python sehr komisch, weil Python ja in einem Interpreter läuft. Wie soll da Maschinencode identisch sein?

Und selbst wenn man 2 verschiedene Code-Versionen hat, die zum gleichen Maschinencode kompilieren (etwa in C), könnte der eine ja sinnvolle Variablennamen haben und der andere Quatschnamen. Guter Code macht ja die Logik verstehbar, wenn ich all meine Bezeichner durch zufällige Worte ersetze ist mein Code in etwa genau so viel Wert wie Maschinencode. Kein Mensch kann damit mehr etwas anfangen, obwohl er theoretisch genau das selbe macht.

Du redest auch nirgendwo von Komplexität. Programme sind ja bloß endlich lang, ich könnte jetzt jahrhundertelang zufälligen Quellcode raten und gucken ob der zum richtigen Maschinencode kompiliert. In der theoretischen Informatik könnte das also Lösung zählen, auch wenns natürlich Quatsch ist und in echt niemals zu einem Ergebnis kommt.

Noch ein Hack: Man muss ja nicht direkt nach Maschinencode kompilieren. Die meisten Sprache sollte man z.B. auf C mappen können. Das kann man dann wiederrum nach Maschinencode kompilieren und hat dann trivial ein C-Programm, dass den selben Maschinencode erzeugt. Ähnliches funktioniert vermutlich für die meisten Kombinationen von Sprachen, sinnvoll ist das natürlich aber nicht.

Und wieso diese komische Idee, dass der Maschinencode identisch sein soll? Das schaffst du ja nichtmal mit zwei unterschiedlichen C++ Compilern, trotzdem macht das Programm ja in beiden Fällen auf unter einer gewissen sinnvollen Betrachtungsweise das selbe, ist also identisch. (Wenn man während der Ausführung den RAM extern modifiziert gehen sie wohl auf verschiedene Arten kaputt und sind dann nicht mehr gleich, deshalb also die "sinnvolle Betrachtungsweise").

Insgesamt also eine ziemlich philosophische Fragestellung. In der Praxis bleibt es aber wohl dabei, unterschiedliche Sprachen sind für unterschiedliche Dinge gut, aber das wusste man ja eigentlich auch schon vorher.

[Alexander Kornrumpf]

auch dann, wenn es x86, C und C ist. Man trollt sich da mit einfachen Beispielen, aber bei größen Programmen ist der Informationsverlust einfach zu hoch.

Die Frage die er im Titel gestellt hat ist nicht die Frage die er im Beitrag gestellt hat. Hin und zurück geht nicht wenn man ganz C zulässt.

Er wollte aber wissen ob man zwei Sprachen X und Y deterministisch ineinander übersetzen kann sodas der jeweilige Text nach Z übersetzt gleich ist. Und das geht natürlich immer weil man X -> Z als X -> Y -> Z implementieren kann und dann trivial zu X ein Y bekommt was dasselbe Z erzeugt.

Das ist aber nicht der interessante Fall, ist klar.

[Alexander Kornrumpf]

Ich denke die allgemeine Version dieser Frage ist ob es drei Sprachen geben kann die paarweise zueinander deterministisch transpilierbar sind aber nicht dieselbe Grammatik haben. [...]

Aber die generischen Frage ohne Bindung an existierende Sprachen ist ein interessantes Projekt für einen Informatikstudenten. Ich bin sicher da kommt man mit Mitteln der theoretischen Informatik sehr weit.

Insgesamt also eine ziemlich philosophische Fragestellung.

So philosophisch finde ich das gar nicht, wir haben eine "harte" Wissenschaft, die sich mit solchen Fragen beschäftigt. Es gklingt eher wie etwas wo ich die Antwort schon kennen müsste, aber naja ich will jetzt nicht das ganze Wochenende investieren.

Ich gebe dir aber wohl recht, dass es keinen Sinn macht das im Konkreten mit Compilern zu betrachten, die nicht für diesen Zweck gemacht sind.

[Lord Delvin]

auch dann, wenn es x86, C und C ist. Man trollt sich da mit einfachen Beispielen, aber bei größen Programmen ist der Informationsverlust einfach zu hoch.

Die Frage die er im Titel gestellt hat ist nicht die Frage die er im Beitrag gestellt hat. Hin und zurück geht nicht wenn man ganz C zulässt.

Er wollte aber wissen ob man zwei Sprachen X und Y deterministisch ineinander übersetzen kann sodas der jeweilige Text nach Z übersetzt gleich ist. Und das geht natürlich immer weil man X -> Z als X -> Y -> Z implementieren kann und dann trivial zu X ein Y bekommt was dasselbe Z erzeugt.

Das ist aber nicht der interessante Fall, ist klar.

Falls das wirklich die Intention ist, dann kann man für X = C, Y = x86 und Z = Python für X -> Y einen deterministischen C Compiler nehmen und Z -> Y eine x86 VM als Präfix und Y als Postfix, alles deterministisch in Python codiert.

Aber ich kämpfe erkennbar mit der Interpretation der Frage ;)

[Alexander Kornrumpf]

Aber ich kämpfe erkennbar mit der Interpretation der Frage ;)

Nichts für Ungut, aber ich glaube das tut der original poster auch. Sieht mir wie eine von diesen Fragen aus, wo die Frage korrekt zu stellen schon 80% der Antwort ist.

[TomasRiker]

Für bestimmte Paare von Sprachen geht das bestimmt (wobei man sich fragen muss, wie man "Sprache" definiert: sind C89 und C90 verschiedene Sprachen?). Für beliebige Sprachen nicht. Compiler, die kein SSE beherrschen, wird man beispielsweise nicht dazu bringen können, SSE-Instruktionen auszugeben.

[NytroX]

Also generell geht das.
Ein konkretes Beispiel ist D. (https://dlang.org/spec/importc.html)
Damit kann man C einlesen, was dann im gleichen AST (Abstract Syntax Tree) abgelegt wird.
Und danach wird der Maschinencode anhand des ASTs generiert - ist also prinzipiell für C und D gleich.

Das Problem ist aber aus meiner Sicht eher, dass die beiden Sprachen ja semantisch auch weitgehend identisch sein müssen, damit das überhaupt Sinn macht.
Und das haben die meisten Sprachen halt nicht, per Design (sonst würde es ja keinen Sinn machen eine neue Sprache zu erfinden).

Aber technisch spricht erstmal nichts dagegen, aus den beiden Sprachen identischen Code in der IR (Intermediate Representation) zu generieren und daraus dann den Maschinencode zu erzeugen - der dann ja auch gleich wäre, wenn man den Compiler dementsprechend implementiert.