[peter-fogg]

Ruby and JS are both Turing-complete languages (as with just about any other programming language you'll ever use), which means that one can simulate the other. The simulation might be messy, complicated, or slow, but it will still work. In this case, Ruby and JS are close enough that it can be done without too much trouble (see the compiled JS).

[seanewest]

But does "anything written in language A can be simulated using language B" imply "A can compile down to B"?

[DiggityDug7]

Yes, it does. It may not be easy, efficient, or elegant, but theoretically any problem solvable by a turing complete language can also be solved by any other turing complete language.

[JonnieCache]

https://en.wikipedia.org/wiki/Turing_completeness

https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis

[afarrell]

yes. If you can write a body of code X in language B which performs the same operations as any given body of code Y in language A, then all an A->B compiler needs to do is find X given Y.

[seanewest]

Ok, but is finding X given Y tractable?

To me, it seems like compiling is translation of source (usually higher level source to lower level source), whereas simulation is more like translation of behavior.

Edit: and the ability to translate behavior does not seem to imply the ability to translate source

[Solarsail]

Couldn't you translate source given the ability to translate behaviour? If some behaviour in language X can be simulated by a state machine in Y, then you could just emit said state machine as the translation of the behaviour, give its output to the next state machine, etc. And gradually build up the behaviour of a program in X, but using a bunch of generated code in Y instead of just an interpreter. In other terms, if an interpreter for / simulation of X may be expressed in Y, then for each bytecode / AST node in X you could just inline the bytecode handling you would use in Y into the compiled output.

[seanewest]

I think thats a very clever algorithm.

But I think your first articulation amounts to converting a turing machine to a huge generated state machine, which would be impossible. The behavior of the X program given one input could be modeled as a sequence of states if it terminates. But the process of generation that you described would have to be repeated for all possible inputs into the simulated X program, which would be impossible.

Maybe a single "behavior" could be modeled by a state machine, but it would also seem impossible to me to decompose a program into individual units of behavior.

But as for bytecode -- one could always compile the X code into bytecode, and then decompile that bytecode into Y code. If you can always find a common bytecode language for two languages X and Y, then I think that would be a generic algorithm for X->Y.

Edit: I guess that common bytecode could just be in a language that describes a turing machine.