| Sussman and Steele | December 22, 1975 | 28 | Implementation of the Interpreter |
Section 5: The Implementation of the Interpreter
Here we present a real live SCHEME interpreter. This particular version was written primarily for expository purposes; it works, but not as efficiently as possible. The "production version" of SCHEME is coded somewhat more intricately, and runs about twice as fast as the interpreter presented below.
The basic idea behind the implementation is think machine language. In particular, we must not use recursion in the implementation language to implement recursion in the language being interpreted. This is a crucial mistake which has screwed many language implementations (e.g. Micro-PLANNER [Sussman]). The reason for this is that if the implementation language does not support certain kinds of control structures, then we will not be able to effectively interpret them. Thus, for example, if the control frame structure in the implementation language is constrained to be stack-like, then modelling more general control structures in the interpreted language will be very difficult unless we divorce ourselves from the constrained structures at the outset.
It will be convenient to think of an implementation machine which has certain operations, which are "micro-coded" in LISP; these are used to operate on various "registers", which are represented as free LISP variables. These registers are:
**EXP**- The expression currently being evaluated.
**ENV**-
A pointer to the environment in which to evaluate
EXP. **CLINK**- A pointer to the frame for the computation of which the current one is a subcomputation.
**PC**-
The "program counter". As each "instruction" is executed, it updates
**PC**to point to the next instruction to be executed. **VAL**-
The returned value of a subcomputation. This register is not saved and restored in
**CLINK**frames; in fact, its sole purpose is to pass values back safely across the restoration of a frame. **UNEVLIS**,**EVLIS**-
These are utility registers which are part of the state of the interpreter (they are saved in
**CLINK**frames). They are used primarily for evaluation of components of combinations, but may be used for other purposes also.
