In thinking about a JavaScript program that evaluates JavaScript expressions, an analogy might be helpful. One operational view of the meaning of a program is that a program is a description of an abstract (perhaps infinitely large) machine. For example, consider the familiar program to compute factorials:

function factorial(n) { return n === 1 ? 1 : factorial(n - 1) * n; }

We may regard this program as the description of a machine containing parts that decrement, multiply, and test for equality, together with a two-position switch and another factorial machine. (The factorial machine is infinite because it contains another factorial machine within it.) Figure 4.2 is a flow diagram for the factorial machine, showing how the parts are wired together.

In a similar way, we can regard the evaluator as a very special
machine that takes as input a description of a machine. Given this
input, the evaluator configures itself to emulate the machine
described. For example, if we feed our evaluator the definition of
`factorial`, as shown in Figure 4.3, the
evaluator will be able to compute factorials.

From this perspective, our evaluator is seen to be a *universal machine*.
It mimics other machines when these are described as
JavaScript
programs.[1]

This is striking. Try to imagine an analogous evaluator for electrical circuits. This would be a circuit that takes as input a signal encoding the plans for some other circuit, such as a filter. Given this input, the circuit evaluator would then behave like a filter with the same description. Such a universal electrical circuit is almost unimaginably complex. It is remarkable that the program evaluator is a rather simple program.[2]

Another striking aspect of the evaluator is that it acts as a bridge
between the data objects that are manipulated by our programming
language and the programming language itself. Imagine that the
evaluator program (implemented in
JavaScript)
is running, and that a user is
typing expressions to the evaluator and observing the results.
From
the perspective of the user, an input expression such as
`x * x`
is an expression in the programming language, which the evaluator
should execute.
From the perspective of the evaluator, however, the
expression is simply a string or—after parsing—a
tagged-object representation
that is to be manipulated according to
a well-defined set of rules.

That the user's programs are the evaluator's data need not be a source
of confusion. In fact, it is sometimes convenient to ignore this
distinction, and to give the user the ability to explicitly evaluate a
string as a JavaScript expression, using JavaScript's primitive function
`eval`
that takes as argument a string. It parses the string and—provided
that it syntactically correct—evaluates the resulting representation
in the environment in which `eval` is
applied.[3]

halton

function run_forever() { return run_forever(); } function try(p) { return halts(p, p) ? run_forever(); : "halted"; }

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

[1]
The fact that the machines are described in
JavaScript
is inessential. If we give our evaluator a
JavaScript
program that behaves as an evaluator for
some other language, say C, the
JavaScript
evaluator will emulate the C
evaluator, which in turn can emulate any machine described as a C
program. Similarly, writing a
JavaScript
evaluator in C produces a C
program that can execute any
JavaScript
program. The deep idea here is that
any evaluator can emulate any other. Thus, the notion of *computability*. This
was first demonstrated in a clear way by
Alan M. Turing (1912–1954),
whose 1936 paper laid the foundations for theoretical
computer science. In the paper, Turing presented a simple computational
model—now known as a
*Turing machine*—and argued that any
*Church-Turing thesis*.)
Turing then implemented a universal machine, i.e., a Turing machine
that behaves as an evaluator for Turing-machine programs. He used
this framework to demonstrate that there are well-posed problems that
cannot be computed by Turing machines (see
exercise 4.7), and so by implication cannot be
formulated as Hodges 1983 for a biography of
Turing.

what can in principle be computed(ignoring practicalities of time and memory required) is independent of the language or the computer, and instead reflects an underlying notion of

effective processcan be formulated as a program for such a machine. (This argument is known as the

effective processes.Turing went on to make fundamental contributions to practical computer science as well. For example, he invented the idea of structuring programs using general-purpose subroutines. See

[2]
Some people find it
counterintuitive that an evaluator, which is implemented by a
relatively simple
function,
can emulate programs that are more
complex than the evaluator itself. The existence of a universal
evaluator machine is a deep and wonderful property of computation.
*Recursion theory*, a branch of mathematical logic, is concerned
with logical limits of computation.
Douglas Hofstadter's beautiful
book *Gödel, Escher, Bach* (1979)
explores some of these ideas.

[3]
Warning:
This `eval` primitive is not
identical to the `evaluate`
function we implemented in
section 4.1.1, because it
uses *actual* JavaScript environments rather than the sample environment
structures we
built in section 4.1.3. These actual
environments cannot be manipulated by the user as ordinary lists; they
must be accessed via `eval` or other special
operations.
Similarly, the `apply` primitive we saw
in section 2.4.3 is not identical
to the metacircular `apply`, because it uses
actual JavaScript functions
rather than the function
objects we constructed in
sections 4.1.3
and 4.1.4.

[4]
Although we stipulated that
`halts`
is given a
function
object,
notice that this reasoning still applies even if
`halts`
can gain access to the
function's
text and its environment.
This is Turing's celebrated *Halting Theorem*, which gave
the first clear example of a *non-computable* problem, i.e., a
well-posed task that cannot be carried out as a computational
function.

4.1.5 Data as Programs