What properties of a programming language make compilation impossible?

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?

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 evalua

StackExchange Computer Science Q#29589, answer score: 63