What properties of a programming language make compilation impossible?

Question Detail: 

Question:

"Certain properties of a programming language may require that the only way to get the code written in it be executed is by interpretation. In other words, compilation to a native machine code of a traditional CPU is not possible. What are these properties?"

Compilers: Principles and Practice by Parag H. Dave and Himanshu B. Dave (May 2, 2012)

The book gives no clue about the answer. I tried to find the answer on Concepts of Programming Languages (SEBESTA), but to no avail. Web searches were of little avail too. Do you have any clue?

Asked By : PrinceYann

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29589

Answered By : babou

The distinction between interpreted and compiled code is probably a fiction, as underlined by Raphael's comment:

the claim seems to be trivially wrong without further assumptions: if there is an interpreter, I can always bundle interpreter and code in one executable ... 

The fact is that code is always interpreted, by software, by hardware or a combination of both, and the compiling process cannot tell which it will be.

What you perceive as compilation is a translation process from one language $S$ (for source) to another language $T$ (for target). And, the interpreter for $S$ is usually different from the interpreter for $T$.

The compiled program is translated from one syntactic form $P_S$ to another syntactic form $P_T$, such that, given the intended semantics of the languages $S$ and $T$, $P_S$ and $P_T$ have the same computational behavior, up to a few things that you are usually trying to change, possibly to optimize, such as complexity or simple efficiency (time, space, surface, energy consumption). I am trying not to talk of functional equivalence, as it would require precise definitions.

Some compilers have been actually used simply to reduce the size of the code, not to "improve" execution. This was the case for language used in the Plato system (though they did not call it compiling).

You may consider your code fully compiled if, after the compiling process, you no longer need the interpreter for $S$. At least, that is the only way I can read your question, as an engineering rather than theoretical question (since, theoretically, I can always rebuild the interpreter).

One thing that may raise problem, afaik, is meta-circularity. That is when a program will manipulate syntactic structures in its own source language $S$, creating program fragment that are then intepreted as if they had been part of the original program. Since you can produce arbitrary program fragments in the language $S$ as the result of arbitrary computation manipulating meaningless syntactic fragments, I would guess you can make it nearly impossible (from an engineering point of view) to compile the program into the language $T$, so that it now generate fragments of $T$. Hence the interpreter for $S$ will be needed, or at least the compiler from $S$ to $T$ for on-the-fly compiling of generated fragments in $S$ (see also this document).

But I am not sure how this can be formalized properly (and do not have time right now for it). And impossible is a big word for an issue that is not formalized.

Futher remarks

Added after 36 hours. You may want to skip this very long sequel.

The many comments to this question show two views of the problem: a theoretical view that see it as meaningless, and an engineering view that is unfortunately not so easily formalized.

There are many ways to look at interpretation and compilation, and I will try to sketch a few. I will attempt to be as informal as I can manage

The Tombstone Diagram

One of the early formalization (early 1960s to late 1990) is the T or Tombstone diagrams. These diagrams presented in composable graphical elements the implementation language of the interpreter or compiler, the source language being interpreted or compiled, and the target language in the case of compilers. More elaborate versions can add attributes. These graphic representations can be seen as axioms, inference rules, usable to mechanically derive processor generation from a proof of their existence from the axioms, à la Curry-Howard (though I am not sure that was done in the sixties :).

Partial evaluation

Another interesting view is the partial evaluation paradigm. I am taking a simple view of programs as a kind of function implementation that computes an answer given some input data. Then an interpreter $I_S$ for the language $S$ is a program that take a program $p_S$ written in $S$ and data $d$ for that program, and computes the result according to the semantics of $S$. Partial evaluation is a technique for specializing a program of two arguments $a_1$ and $a_2$, when only one argument, say $a_1$, is known. The intent is to have a faster evaluation when you finally get the second argument $a_2$. It is especially useful if $a_2$ changes more often than $a_1$ as the cost of partial evaluation with $a_1$ can be amortized on all the computations where only $a_2$ is changing.

This is a frequent situation in algorithm design (often the topic of the first comment on SE-CS), when some more static part of the data is pre-processed, so that the cost of the pre-processing can be amortized on all applications of the algorithm with more variable parts of the input data.

This is also the very situation of interpreters, as the first argument is the program to be executed, and is usually executed many times with different data (or has subparts executed many times with different data). Hence it become a natural idea to specialize an interpreter for faster evaluation of a given program by partially evaluating it on this program as first argument. This may be seen as a way of compiling the program, and there has been significant research work on compiling by partial evaluation of a interpreter on its first (program) argument.

The Smn theorem

The nice point about the partial evaluation approach is that it does take its roots in theory (though theory can be a liar), notably in Kleene's Smn theorem. I am trying here to give an intuitive presentation of it, hoping it will not upset pure theoreticians.

Given a Gödel numbering $\varphi$ of recursive functions, you can view $\varphi$ as your hardware, so that given the Gödel number $p$ (read object code) of a program $\varphi_p$ is the function defined by $p$ (i.e. computed by the object code on your hardware).

In its simplest form, the theorem is stated in wikipedia as follows (up to a small change in notation):

Given a Gödel numbering $\varphi$ of recursive functions, there is a primitive recursive function $\sigma$ of two arguments with the following property: for every Gödel number $q$ of a partial computable function $f$ with two arguments, the expressions $\varphi_{\sigma(q,x)}(y)$ and $f(x,y)$ are defined for the same combinations of natural numbers $x$ and $y$, and their values are equal for any such combination. In other words, the following extensional equality of functions holds for every $x$: $\;\;\varphi_{\sigma(q,x)} \simeq \lambda y.\varphi_q(x,y).\,$

Now, taking $q$ as the interpreter $I_S$, $x$ as the source code of a program $p_S$, and $y$ as the data $d$ for that program, we can write: $\;\;\varphi_{\sigma(I_S,p_S)} \simeq \lambda d.\varphi_{I_S}(p_S,d).\,$

$\varphi_{I_S}$ may be seen as the execution of the interpreter $I_S$ on the hardware, i.e., as a black-box ready to interpret programs written in language $S$.

The function $\sigma$ may be seen as a function that specializes the interpreter $I_S$ for the program $P_S$, as in partial evaluation. Thus the Gödel number $\sigma(I_S,p_S)$ may be seen has object code that is the compiled version of program $p_S$.

So the function $\;C_S = \lambda q_S.\sigma((I_S,q_S)$ may be seen as a function that take as argument the source code of a program $q_S$ written in language $S$, and return the object code version for that program. So $C_S$ is what is usually called a compiler.

Some conclusions

However, as I said: "theory can be a liar", or actually seem to be one. The problem is that we know nothing of the function $\sigma$. There are actually many such functions, and my guess is that the proof of the theorem may use a very simple definition for it, which might be no better, from an engineering point of view, than the solution proposed by Raphael: to simply bundle the source code $q_S$ with the interpreter $I_S$. This can always be done, so that we can say: compiling is always possible.

Formalizing a more restrictive notion of what is a compiler would require a more subtle theoretical approach. I do not know what may have been done in that direction. The very real work done on partial evaluation is more realistic from an engineering point of view. And there are of course other techniques for writing compilers, including extraction of programs from the proof of their specification, as developed in the context of type-theory, based on the Curry-Howard isomorphism (but I am getting outside my domain of competence).

My purpose here has been to show that Raphael's remark is not "crazy", but a sane reminder that things are not obvious, and not even simple. Saying that something is impossible is a strong statement that does require precise definitions and a proof, if only to have a precise understanding of how and why it is impossible. But building a proper formalization to express such a proof may be quite difficult.

This said, even if a specific feature is not compilable, in the sense understood by engineers, standard compiling techniques can always be applied to parts of the programs that do not use such a feature, as is remarked by Gilles' answer.

To follow on Gilles' key remarks that, depending on the language, some thing may be done at compile-time, while other have to be done at run-time, thus requiring specific code, we can see that the concept of compilation is actually ill-defined, and is probably not definable in any satisfactory way. Compilation is only an optimization process, as I tried to show in the partial evaluation section, when I compared it with static data preprocessing in some algorithms.

As a complex optimization process, the concept of compilation actually belongs to a continuum. Depending on the characteristic of the language, or of the program, some information may be available statically and allow for better optimization. Others things have to be postponed to run-time. When things get really bad, everything has to be done at run-time at least for some parts of the program, and bundling source-code with the interpreter is all you can do. So this bundling is just the low end of this compiling continuum. Much of the research on compilers is about finding ways to do statically what used to be done dynamically. Compile-time garbage collection seems a good example.

Note that saying that the compilation process should produce machine code is no help. That is precisely what the bundling can do as the interpreter is machine code (well, thing can get a bit more complex with cross-compilation).