4.1.5 Data as Programs - SICP Comparison Edition

Permalink copied!

In thinking about a Lisp JavaScript program that evaluates Lisp 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:

Original	JavaScript
`(define (factorial n) (if (= n 1) 1 (* (factorial (- n 1)) n)))`	`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.4 is a flow diagram for the factorial machine, showing how the parts are wired together.

Figure 4.4 The factorial program, viewed as an abstract machine.

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.5, figure 4.6, the evaluator will be able to compute factorials.

Original		JavaScript
Figure 4.5 The evaluator emulating a factorial machine.		Figure 4.6 The evaluator emulating a factorial machine.

From this perspective, our evaluator is seen to be a universal machine. It mimics other machines when these are described as Lisp 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 Lisp) (implemented in JavaScript) is running, and that a user is typing expressions programs to the evaluator and observing the results. From the perspective of the user, an input expression program such as (* x x) x * x; is an expression a program in the programming language, which the evaluator should execute. From the perspective of the evaluator, however, the expression is simply a list (in this case, a list of three symbols: *, x, and x) that is to be manipulated according to a well-defined set of rules. 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.

Original		JavaScript
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 data object as a Lisp expression, by making `eval` available for use in programs. Many Lisp dialects provide a primitive `eval` procedure that takes as arguments an expression and an environment and evaluates the expression relative to the environment.[3] Thus, `(eval '(* 5 5) user-initial-environment)` and `(eval (cons '* (list 5 5)) user-initial-environment)` will both return 25.[4]		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;");` and `evaluate(parse("5 * 5;"), the_global_environment);` will both return 25.[5]

Exercise 4.20 Given a one-argument procedure function p f and an object a, p f is said to halt on a if evaluating the expression (p a) f(a) returns a value (as opposed to terminating with an error message or running forever). Show that it is impossible to write a procedure function halts? halts that correctly determines whether p f halts on a for any procedure function p f and object a. Use the following reasoning: If you had such a procedure function halts?, halts, you could implement the following program:

Original	JavaScript
`(define (run-forever) (run-forever)) (define (try p) (if (halts? p p) (run-forever) 'halted))`	`function run_forever() { return run_forever(); } function strange(f) { return halts(f, f) ? run_forever() : "halted"; }`

Now consider evaluating the expression (try try) strange(strange) and show that any possible outcome (either halting or running forever) violates the intended behavior of halts?halts.[6]

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 Lisp JavaScript is inessential. If we give our evaluator a Lisp JavaScript program that behaves as an evaluator for some other language, say C, the Lisp JavaScript evaluator will emulate the C evaluator, which in turn can emulate any machine described as a C program. Similarly, writing a Lisp JavaScript evaluator in C produces a C program that can execute any Lisp JavaScript program. The deep idea here is that any evaluator can emulate any other. Thus, the notion of 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 process can 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.20), 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 Hodges 1983 for a biography of Turing.

[2] Some people find it counterintuitive that an evaluator, which is implemented by a relatively simple procedure, 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 eval procedure we implemented in section 4.1.1, because it uses actual Scheme 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 earlier is not identical to the metacircular apply, because it uses actual Scheme procedures rather than the procedure objects we constructed in sections 4.1.3 and 4.1.4.

[4] The MIT implementation of Scheme includes eval, as well as a symbol user-initial-environment that is bound to the initial environment in which the user's input expressions are evaluated.

[5] Note that eval may not be available in the JavaScript environment that you are using, or its use may be restricted for security reasons.

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

< Previous

Next >

4.1.5 Data as Programs