6.2.14 Evaluation

SCM uses its type representations to speed evaluation. All of the subr types (see Subr Cells) are tc7 types. Since the tc7 field is in the low order bit position of the CAR it can be retrieved and dispatched on quickly by dereferencing the SCM pointer pointing to it and masking the result.

All the SCM Special Forms get translated to immediate symbols (isym) the first time they are encountered by the interpreter (ceval). The representation of these immediate symbols is engineered to occupy the same bits as tc7. All the isyms occur only in the CAR of lists.

If the CAR of a expression to evaluate is not immediate, then it may be a symbol. If so, the first time it is encountered it will be converted to an immediate type ILOC or GLOC (see Immediates). The codes for ILOC and GLOC lower 7 bits distinguish them from all the other types we have discussed.

Once it has determined that the expression to evaluate is not immediate, ceval need only retrieve and dispatch on the low order 7 bits of the CAR of that cell, regardless of whether that cell is a closure, header, or subr, or a cons containing ILOC or GLOC.

In order to be able to convert a SCM symbol pointer to an immediate ILOC or GLOC, the evaluator must be holding the pointer to the list in which that symbol pointer occurs. Turning this requirement to an advantage, ceval does not recursively call itself to evaluate symbols in lists; It instead calls the macro EVALCAR. EVALCAR does symbol lookup and memoization for symbols, retrieval of values for ILOCs and GLOCs, returns other immediates, and otherwise recursively calls itself with the CAR of the list.

ceval inlines evaluation (using EVALCAR) of almost all procedure call arguments. When ceval needs to evaluate a list of more than length 3, the procedure eval_args is called. So ceval can be said to have one level lookahead. The avoidance of recursive invocations of ceval for the most common cases (special forms and procedure calls) results in faster execution. The speed of the interpreter is currently limited on most machines by interpreter size, probably having to do with its cache footprint. In order to keep the size down, certain EVALCAR calls which don't need to be fast (because they rarely occur or because they are part of expensive operations) are instead calls to the C function evalcar.

ILOCs work up to a maximum depth of 4096 frames or 4096 identifiers in a frame. Radey Shouman added FARLOC to handle cases exceeding these limits. A FARLOC consists of a pair whose CAR is the immediate type IM_FARLOC_CAR or IM_FARLOC_CDR, and whose CDR is a pair of INUMs specifying the frame and distance with a larger range than ILOCs span.

Adding #define TEST_FARLOC to eval.c causes FARLOCs to be generated for all local identifiers; this is useful only for testing memoization.

If the compile FLAG CAUTIOUS is #defined then the number of arguments is always checked for application of closures. If the compile FLAG RECKLESS is #defined then they are not checked. Otherwise, number of argument checks for closures are made only when the function position (whose value is the closure) of a combination is not an ILOC or GLOC. When the function position of a combination is a symbol it will be checked only the first time it is evaluated because it will then be replaced with an ILOC or GLOC.