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 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).
