[Theorie] Abbildung eines Systems auf auf eines anderer Klassen

[Stefan H. (Firma: dm2sh) (stefan_helmert)]

Hallo,

ich habe diesmal eine eher theoretische Frage. Gibt es 
Software/Forschungsansätze/Theorien, welche sich mit folgendem Problem 
beschäftigen?

Es existiert ein System A, welches aus bestimmten Verhalten/Klassen a 
besteht. Bsp. Das System ist ein Programm für einen 6502-Prozessor. Die 
Verhalten sind die Befehle mit allen Einschränkungen (Registersatz, 
Bitbreite, Veränderung des Statusworts, Stack).

Man möchte nun ein System A' synthetisieren, welches mit den 
Verhalten/Klassen b das gleiche tut wie System A. Bsp. man möchte ein 
Programm für den 8051-Prozessor erzeugen, welches das gleiche äußere 
Verhalten zeigt, wie das Programm auf dem 6502-Prozessor.

Also: f(A)=f'(A')
wovon f, A und f' gegeben sind und A' gesucht.
Natürlich könnte auch einmal f', A und A' gegeben sein und f gesucht.
Die System f und f' werden mit (formalen) Elementar-Anweisungen 
beschrieben.
Es gibt in der Regel sehr viele Lösungen, wobei es Ziel ist, eine zu 
finden.

Gibt es schon etwas (außer der Mensch), was Probleme dieser Art lösen 
kann?

[Karl H. (kbuchegg)]

Wenn mich nicht alles täuscht, dann ist deine Fragestellung homolog zu 
dem Problem eine Übersetzung anzufertigen, wobei der Sinn eines Textes 
erhalten bleibt. Wie gut das im Allgemeinen funktioniert kann man sich 
ja an diversen Englisch/Deutsch Übersetzern ansehen.

Du hast natürlich einen Sonderfall, da die Assemblersprachen von 
Prozessoren bei weitem nicht so mehrdeutig sind, wie es natürliche 
Sprache ist :-)

Möglich ist es. Im schlimmsten Fall bildet man CPU A mit den Mitteln von 
CPU B nach und kann so Programme von A auf B laufen lassen. Das kann 
auch soweit gehen, dass man die Möglichkeiten von A auf B konzeptmässig 
nachbildet und so den Transfer schafft. Konvertierprogramme von zb 
Pascal nach Fortran arbeiten so. Die Frage ist halt immer: wie sinnvoll 
ist das? Unterschiedliche CPU haben unterschiedliche Möglichkeiten 
bedingt durch unterschiedlichen Hardwareaufbau. Eine mehr oder weniger 
1:1 Übersetzung wird dieses mehr aber nicht ausnutzen können.
Sinnvoll wäre es daher erst einmal den Sinn hinter einer Codepassage zu 
erkennen und dann im Zielsystem eine Sequenz zu schaffen, die diesen 
Sinn übernimmt ohne sich auf den Originalcode zu stützen.

Und da hakt es dann: Sinnerkennung ist extrem schwer und m.W. nicht 100% 
gelöst.

[Stefan H. (Firma: dm2sh) (stefan_helmert)]

>dass MAN die Möglichkeiten von A auf B konzeptmässig nachbildet

genau das meine ich eben nicht. Du meinst das so:
A'=F'(f(A))
Das heißt ein Ingenieur denkt sich aus, wie die Befehle von CPU A auf 
CPU B übersetzte werden müssen.

Ich meine das so: Es existiert das Modell von CPU A und das Model von 
CPU B und die Software, die ich meine nimmt die Umkehrung vor.
Anders ausgedrückt: Man kann das Modell einer CPU habe und das Programm, 
das auf ihr läuft. Das nennt man dann Interpreter. Programm und CPU 
bilden dann ein System mit einem bestimmten Systemverhalten. Das ist 
alles ganz einfach.

Schwieriger wird es, wenn ich eine Modell einer CPU habe (der 
Interpreter) und will ein Programm wissen, welches ich dem Interpreter 
geben muss, damit er mein gewünschtes Verhalten zeigt. Das ist das was 
ich meine!

Bei CPUs mag das alles noch relativ einfach gehen, weil ein Befehl in 
der Regel nur geringe Nebenwirkungen zeigt (Resourcen-Verbrauch, z. B. 
Register). Ein anderes Beispiel, wo es einleuchtender wird. Ich habe ein 
Cad-Modell eines Autos und ich habe Modelle von den Teilen und 
Halbzeugen und suche jetzt ein Fertigungsverfahren, welches aus den 
Teilen und Halbzeugen ein Auto macht. Das ist nicht ganz einfach, da ein 
bereits montiertes Teil ein erhitzen verbieten kann oder den Zugang zu 
Montagepunkten verhindert.
Der Vorteil einer solchen Software läge vor allem in der 
adaptierbarkeit. Wenn man eine "Kleinigkeit" am Modell des Fahrzeugs 
ändert, könnte das ein komplette Redesign der Fertigung verlangen. Das 
würde die Software innerhalb von Minuten (oder Stunden) fehlerfrei 
hinbekommen. Das gleiche Problem besteht bei einer Änderung der 
zugekauften Teile. Man könnte dann Restposten gut verwerten. Die 
Software würde sich anhand des Modells der Restposten "überlegen", wie 
diese im Fertigungsprozess mit verwertet werden können.

Ein Vorteil wäre auch im Compilerbau vorhanden. Man benötigt eine CPU 
und hat der (Befehlssatz-)Modell. Dann braucht man noch einen 
Übersetzer, der den Zwischencode des Compilers in Maschinenbefehle 
wandelt. Das ist doppelte Arbeit. Wenn man das Befehlssatz-Modell 
bereits hat, dann könnte man es ja "Umkehren" und daraus automatisch den 
Übersetzer erzeugen, welcher Zwischencode in Maschinenbefehle Wandelt.

[Arc N. (arc)]

Nur ein paar Anregungen:
Die Analyse und Erklärung von Systemen und deren Verhalten, wäre 
allgemein die Kybernetik bzw. Systemtheorie

> Schwieriger wird es, wenn ich eine Modell einer CPU habe (der
> Interpreter) und will ein Programm wissen, welches ich dem Interpreter
> geben muss, damit er mein gewünschtes Verhalten zeigt. Das ist das was
> ich meine!

Curry–Howard correspondence, program extraction / contructive proofs, 
theorem proving, type theory, ILP, SMT solver...
(letztlich umfassen die geschilderten Problemen fast alles, was 
Gegenstand aktueller Forschung in diesen Bereichen ist)

Nur ein paar Beispiele:
"We describe new methods to induce functional programs
from small sets of non-recursive equations representing a subset of the
input-output behaviour of some function to be implemented."
http://www.cogsys.wiai.uni-bamberg.de/publications/lopstr08pre.pdf

http://nautilus.cs.miyazaki-u.ac.jp/~skata/index.html
http://nautilus.cs.miyazaki-u.ac.jp/~skata/MagicHaskeller.html
http://www.inf.ed.ac.uk/publications/thesis/online/IM080649.pdf

http://www.nuprl.org/Algorithms/03cucs-intsqrt.pdf