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?
What properties of a programming language make compilation impossible?
programming languages;compilers;interpreters
The distinction between interpreted and compiled code is probably afiction, as underlined by Raphael's comment:the claim seems to be trivially wrong without further assumptions: if there isan interpreter, I can always bundle interpreter and code in one executable ...The fact is that code is always interpreted, by software, by hardwareor a combination of both, and the compiling process cannot tell whichit will be.What you perceive as compilation is a translation process from onelanguage $S$ (for source) to another language $T$ (for target). And, theinterpreter for $S$ is usually different from the interpreter for $T$.The compiled program is translated from one syntactic form $P_S$ toanother syntactic form $P_T$, such that, given the intended semanticsof the languages $S$ and $T$, $P_S$ and $P_T$ have the samecomputational behavior, up to a few things that you are usually tryingto 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 ofthe 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 compilingprocess, you no longer need the interpreter for $S$. At least, that isthe only way I can read your question, as an engineering rather thantheoretical question (since, theoretically, I can always rebuild theinterpreter).One thing that may raise problem, afaik, is meta-circularity. Thatis when a program will manipulate syntactic structures in its own sourcelanguage $S$, creating program fragment that are then intepreted as ifthey had been part of the original program. Since you can producearbitrary program fragments in the language $S$ as the result of arbitrary computation manipulating meaningless syntactic fragments, I would guess you canmake it nearly impossible (from an engineering point of view) tocompile the program into the language $T$, so that it now generatefragments of $T$. Hence the interpreter for $S$ will be needed, or atleast the compiler from $S$ to $T$ for on-the-fly compiling ofgenerated fragments in $S$ (see also this document).But I am not sure how this can be formalized properly (and do not havetime right now for it). And impossible is a big word for an issue that is not formalized.Futher remarksAdded after 36 hours. You may want to skip this very long sequel. The many comments to this question show two views of the problem: atheoretical view that see it as meaningless, and an engineering viewthat is unfortunately not so easily formalized.There are many ways to look at interpretation and compilation, and Iwill try to sketch a few. I will attempt to be as informal as I can manageThe Tombstone DiagramOne of the early formalization (early 1960s to late 1990) is the T orTombstone diagrams. These diagrams presented in composable graphicalelements the implementation language of the interpreter or compiler,the source language being interpreted or compiled, and the targetlanguage in the case of compilers. More elaborate versions can addattributes. These graphic representations can be seen as axioms,inference rules, usable to mechanically derive processor generationfrom a proof of their existence from the axioms,  la Curry-Howard(though I am not sure that was done in the sixties :).Partial evaluationAnother interesting view is the partial evaluation paradigm. I amtaking a simple view of programs as a kind of function implementationthat 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 resultaccording to the semantics of $S$. Partial evaluation is a techniquefor specializing a program of two arguments $a_1$ and $a_2$, when onlyone argument, say $a_1$, is known. The intent is to have a fasterevaluation when you finally get the second argument $a_2$. It isespecially useful if $a_2$ changes more often than $a_1$ as the costof partial evaluation with $a_1$ can be amortized on all thecomputations where only $a_2$ is changing.This is a frequent situation in algorithm design (often the topic ofthe first comment on SE-CS), when some more static part of the data ispre-processed, so that the cost of the pre-processing can be amortizedon all applications of the algorithm with more variable parts of theinput data.This is also the very situation of interpreters, as the first argumentis the program to be executed, and is usually executed many times withdifferent data (or has subparts executed many times with differentdata). Hence it become a natural idea to specialize an interpreter forfaster evaluation of a given program by partially evaluating it onthis program as first argument.  This may be seen as a way ofcompiling the program, and there has been significantresearch work on compiling by partial evaluation of a interpreter onits first (program) argument.The Smn theoremThe nice point about the partial evaluation approach is that it doestake its roots in theory (though theory can be a liar), notably inKleene's Smn theorem.  I am trying here to give an intuitivepresentation of it, hoping it will not upset pure theoreticians.Given a Gdel numbering $\varphi$ of recursive functions, you canview $\varphi$ as your hardware, so that given the Gdel number $p$(read object code) of a program $\varphi_p$ is the function definedby $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 Gdel numbering $\varphi$ of recursive functions, there is a primitive recursive function $\sigma$ of two arguments with the following property: for every Gdel 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 aprogram $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 programswritten in language $S$.The function $\sigma$ may be seen as a function that specializes theinterpreter $I_S$ for the program $P_S$, as in partial evaluation.Thus the Gdel number $\sigma(I_S,p_S)$ may be seen has object code that isthe compiled version of program $p_S$.So the function $\;C_S = \lambda q_S.\sigma((I_S,q_S)$ may be seen asa function that take as argument the source code of a program $q_S$written in language $S$, and return the object code version for thatprogram. So $C_S$ is what is usually called a compiler.Some conclusionsHowever, as I said: theory can be a liar, or actually seem to be one. The problem is that weknow nothing of the function $\sigma$. There are actually many suchfunctions, and my guess is that the proof of the theorem may use avery simple definition for it, which might be no better, from anengineering point of view, than the solution proposed by Raphael: tosimply bundle the source code $q_S$ with the interpreter $I_S$. Thiscan always be done, so that we can say: compiling is alwayspossible.Formalizing a more restrictive notion of what is a compiler wouldrequire a more subtle theoretical approach. I do not know what mayhave been done in that direction. The very real work done on partialevaluation is more realistic from an engineering point of view. Andthere are of course other techniques for writing compilers, includingextraction of programs from the proof of their specification, asdeveloped in the context of type-theory, based on the Curry-Howardisomorphism (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 evensimple. Saying that something is impossible is a strong statementthat does require precise definitions and a proof, if only to have aprecise understanding of how and why it is impossible. But buildinga proper formalization to express such a proof may be quite difficult.This said, even if a specific feature is not compilable, in the senseunderstood by engineers, standard compiling techniques can always beapplied to parts of the programs that do not use such a feature, as isremarked by Gilles' answer.To follow on Gilles' key remarks that, depending on the language, something may be done at compile-time, while other have to be done atrun-time, thus requiring specific code, we can see that the concept ofcompilation is actually ill-defined, and is probably not definable inany satisfactory way. Compilation is only an optimization process, asI tried to show in the partial evaluation section, when I comparedit with static data preprocessing in some algorithms.As a complex optimization process, the concept of compilation actuallybelongs to a continuum. Depending on the characteristic of thelanguage, or of the program, some information may be availablestatically and allow for better optimization. Others things have to bepostponed to run-time. When things get really bad, everything has tobe done at run-time at least for some parts of the program, andbundling  source-code with the interpreter is all you can do. So thisbundling 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 machinecode is no help. That is precisely what the bundling can do as theinterpreter is machine code (well, thing can get a bit more complexwith cross-compilation).