4
$\begingroup$

I am looking for a better explanation (research level, papers) to answer:

Why translating a program from one high-level programming language directly into another is difficult?

Note: When I say difficult I don't mean "hard" - i.e. I am not taking about computational complexity here simply because I am unaware of such results, but you are very much welcome to correct my ignorance.

I understand that at the core of the argument can say something like one-to-one mapping for such translation simply does not exists.

In general, I am not comfortable with terminology used in my own question.

We know from text books: Low-level language - each command or object of the language has one-to-one mapping to CPU commands (e.g. Assembler). All other languages are High-level.

Is there a way to reformulate the question into FSA formalism like with regular languges, or some other formalism. But I don't think Church–Turing thesis can help here - it is not about computability or existence of a proof.

PS

My motivation is very simple - I want to discuss/answer how difficult is such a problem for example in translating PHP to Java. Please note that direct translation is indeed a mapping of language commands or objects (e.g. HipHop does not qualify).

Probably any pragmatic solution would be indirect translation, i.e. in order to (partially) convert a program P written in high-level language A into a high-level language B:

  1. (complexity lowering) convert codebase of program P from A to low or inter-mediate level language C
  2. (shared codebase) resue parts of converted codebase of program P by calling commands in low or inter-mediate level language C from high level language B
Improve this question
$\endgroup$
16
  • $\begingroup$ do you really believe you should ask this (if you should at all, since this is well pretty much more of a rhetoric statement rather than question) at Programmers SE. $\endgroup$
    – shabunc
    Oct 29, 2015 at 15:44
  • 1
    $\begingroup$ Your question works off the assumption that this task is hard. I don't know, is it? I wouldn't think so. (You don't require the result to be idiomatic or anything.) $\endgroup$
    – Raphael
    Oct 29, 2015 at 18:24
  • 1
    $\begingroup$ I don't understand why you ask for a research-level answer when a non-research-level answer would be perfectly satisfactory. I think reading a compiler textbook would be enough to give some sense of why it's hard: after all, it takes an entire textbook to even scratch the surface of the subject! Or, you could read the source code of a commercially deployed compiler (e.g., llvm) -- we're talking about hundreds of thousands of lines of code. If it was easy to get good performance, they wouldn't be anywhere so complex. $\endgroup$
    – D.W. ♦
    Oct 29, 2015 at 21:48
  • 2
    $\begingroup$ What makes this hard is usually the other requirements, like requirements for good performance. If you don't care about performance, it's probably not super hard. Your question doesn't state whether you care about things like performance, ability to link/interface with other Java code, and so on. One way to demonstrate that this is hard is by doing a literature search to find all prior research papers that try to attempt something of this sort, and surveying the prior work. Have you done that? If you're trying to publish a paper on the subject that's something you need to do anyway! $\endgroup$
    – D.W. ♦
    Oct 29, 2015 at 21:50
  • 1
    $\begingroup$ Based on the comments and answers you're getting so far, let me encourage you to edit the question to clarify your requirements: do you require good/near-optimal performance? do you require that the output code be human-readable or human-maintainable? do you require support for all of the libraries and APIs that might be accessible in the source language (PHP) and ability to translate code that uses them? The answers will depend heavily on this information. $\endgroup$
    – D.W. ♦
    Oct 29, 2015 at 21:52

4 Answers 4

Reset to default
3
$\begingroup$

The task is simple. Here are two naive strategies.

Say we want to compile from A to B.

  1. Pick a language C for which you have a compiler A $\to$ C and an interpreter for $C$ in $B$.

    Create a new program in B that includes the compilate (in C) as string and the code of the interpreter.

  2. Compile code in A to machine code or intermediate language. Translate line by line to B.

Both give horrible programs -- but you did not require anything fancy.

The more theoretical answer is: we know that effective (i.e. Turing-computable) compilers exist between any two Turing-complete languages, since such define nothing but an admissible numbering.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This assumes you can implement the semantics of C in B. Also this assumes that C can be interpreted. What if language A is "C++", and B is Java ~ This transformation is not possible without a lot of 'proof by hand waving'. $\endgroup$
    – roscoe_casita
    Oct 29, 2015 at 21:51
  • $\begingroup$ @roscoe_casita These are not assumptions, but certainties (as long as all three languages are Turing-complete, which I guess goes without saying). These language can all do exactly the same, and we even know that we have computable compilers. Oh, I have to add that. $\endgroup$
    – Raphael
    Oct 29, 2015 at 23:41
  • $\begingroup$ strictly speaking, the first one is an assumption because programming languages can do things that turing machines can't. you can't translate java into brainfuck, even though both are turing-complete, because java can make your computer do things like connect to the internet or play a sound. But I agree with the spirit of your answer entirely, and of I can't think of a modern, general-purpose language that can't make a normal computer do everything the hardware is capable of up to the user's ability to tell the difference $\endgroup$
    – Silver
    Oct 3, 2021 at 6:43
2
$\begingroup$

here are two examples of scientific literature on porting projects, the 1st is a large Phd thesis that includes much detail on the intricacies/ difficulties, many of which would apply to different projects, its a C++ to java analysis for a large software system. the difficulties that would be encountered with porting tends to vary by project/ language and is oriented around the rationale for the port. often porting is to achieve better performance, and then the challenge is actually achieving it.

you also mention PHP to Java. a description of a similar project of converting Ruby (also a dynamic scripting language) to Java that happened at Twitter may be useful. there are a huge variety of porting projects that occur and it would be difficult to make generalizations. there is much more literature on eg attempting to compare language performance on standard problems etc.

Improve this answer
$\endgroup$
1
$\begingroup$

I think that when doing the translation, you're going to encounter two main difficulties (read: things that could require lots of work):

  1. High level languages tend to have lots of features. And even if two languages have a similar feature, they tend to work slightly differently. So, for each feature in the source language (and possibly for each edge case of that feature), you will need to find translation to the target language.

    For example, PHP is dynamically typed, Java statically typed. So, to translate from PHP to Java, you would somehow need to simulate PHP's dynamic typing in Java.

  2. Languages often come with large standard libraries/frameworks/runtimes, which often aren't completely written in the language itself (so you can't just use the translator on them).

Improve this answer
$\endgroup$
1
  • $\begingroup$ You can define language features as semantics, thus your comparing the semantics of one language to another, to find similarity. If there is not a direct match, then semantic translation from S1 to S2 need to be done for any kind of conversion. $\endgroup$
    – roscoe_casita
    Oct 29, 2015 at 21:42
0
$\begingroup$

A Simple example of this is trying to show equivalence in C to OCaml.

The features of pointers are not even a language feature in OCaml, and Pattern matching of OCaml is not a feature of C.

This is a simplistic example, but the fundamental semantics of the languages are different.

There are many languages that a 'simple' translation will suffice: Java <=> C#, or Scheme <=> Lisp.

We can show they are all equivalent to a Turing machine, but this does not give you a practical translation.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Are you sure translating between C# generics and Java generics can be considered simple? $\endgroup$
    – svick
    Oct 29, 2015 at 21:46
  • $\begingroup$ This entirely depends on the exact language semantics, they may look and feel very similar, and perhaps even produce the same results, but the semantics would show they are not the same. Thus there is no 'easy' solution in the general case. $\endgroup$
    – roscoe_casita
    Oct 29, 2015 at 21:48

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.