next up previous contents
Next: Internal Definitions Up: The Metacircular Evaluator Previous: Running the Evaluator as

Data as Programs

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

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

  \begin{figure}\par\figcaption {The factorial program, viewed as an abstract machine.}\end{figure}

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 [*], the evaluator will be able to compute factorials.

  \begin{figure}\par\figcaption {The evaluator emulating a factorial machine.}\end{figure}

From this perspective, our evaluator is seen to be a universal machine. It mimics other machines when these are described as Lisp programs. [*] 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.[*]

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

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.[*] Thus,

(eval '(* 5 5) user-initial-environment)
(eval (cons '* (list 5 5)) user-initial-environment)
will both return 25.[*]

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

(define (run-forever) (run-forever))

(define (try p) (if (halts? p p) (run-forever) 'halted))

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

next up previous contents
Next: Internal Definitions Up: The Metacircular Evaluator Previous: Running the Evaluator as
Ryan Bender