Imagine two machines of different architecture which produce output of a standard format.

If you have a program for one machine and can observe it's operation and output, what techniques exist to automatically produce an equivalent program for the alternate architecture?

By equivalent I mean produces equal output (by some equality relation) for equivalent input.

  • $\begingroup$ When translating from one program to another, do I have access to the code of the first program, or can I only see the output it produces? $\endgroup$ Commented Oct 24, 2012 at 11:50
  • $\begingroup$ You have access to the program and the complete state of the first machine as it runs the program. Thanks, for thinking about it :) $\endgroup$
    – Marcus
    Commented Oct 24, 2012 at 12:05
  • 2
    $\begingroup$ Use/write a compiler. Is that too obvious? Why do you think you need something else? $\endgroup$
    – Raphael
    Commented Oct 25, 2012 at 10:51

1 Answer 1


A "simple" way of solving this problem is to write an emulator for the first machine's instruction set on the second machine. Then set the first program as input to this emulator. One could also apply partial evaluation techniques to optimise things a little, which would result in an emulator that runs only the first program (and nothing else).

  • $\begingroup$ Thanks for your answer... But how would one generate an emulator for the first machine? As a human I could take a look and understand the equivalence of instructions or sequences of instructions between the two machines and construct an emulator. But how would you automate this? I was hoping for answers in the general, something like noticing subgraph isomorphisms between some graph representation of the first machine state as it processes and graph a representation of the second machine as it processes, finding equivalent operations in that way, or some other similar method. $\endgroup$
    – Marcus
    Commented Oct 24, 2012 at 12:21
  • $\begingroup$ Ah. I missed the word "automatically". You would need a description of the architecture of the first machine as a basis. $\endgroup$ Commented Oct 24, 2012 at 12:28
  • $\begingroup$ @Marcus. The emulator cannot be produced automatically. But, once you have an emulator and a partial evaluator, every program for the first machine can be translated automatically. Sorry if that was already quite obvious to you. $\endgroup$
    – Uday Reddy
    Commented Oct 28, 2012 at 16:40
  • $\begingroup$ I have marked a solution. It isn't really the answer to the question I was asking, but perhaps that is the fault of the question. I now have a more specific question, I will ask that... $\endgroup$
    – Marcus
    Commented Nov 2, 2012 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.