In thinking about a JavaScript program that evaluates JavaScript statements and 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;
}
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.6,
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 programs to the evaluator and observing the results. From the perspective of the user, an input program such as x * x; is a program in the programming language, which the evaluator should execute. From the perspective of the evaluator, however, the program is simply a string or—after parsing—a tagged-list 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 statement, using JavaScript's primitive function eval that takes as argument a string. It parses the string and—provided that it is syntactically correct—evaluates the resulting representation in the environment in which eval is applied. Thus,
eval("5 * 5;");
evaluate(parse("5 * 5;"), the_global_environment);
halton a if evaluating the expression f(a) returns a value (as opposed to terminating with an error message or running forever). Show that it is impossible to write a function halts that correctly determines whether f halts on a for any function f and object a. Use the following reasoning: If you had such a function halts, you could implement the following program:
function run_forever() { return run_forever(); }
function strange(f) {
return halts(f, f)
? run_forever()
: "halted";
}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 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
effective processcan be formulated as a program for such a machine. (This argument is known as the 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.15), and so by implication cannot be formulated as
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