9.1 Evaluator Functions Eval and Apply

The evaluator is responsible for the execution of PSL programs. The evaluator is available to the user through the function eval. This function gives the operational semantics, or meaning, to the programming constructs found in PSL. With eval we have the ability to evaluate constructed expressions. The ability to evaluate lists which have the appearance of expressions highlights the program data duality of LISP.

Apply represents the piece of the evaluator which is responsible for invoking functions. Any list which is not quoted is taken to be a function application by the evaluator. Apply provides the user with a tool to explicity invoke functions.

In eval, apply and the support functions which follow, errors are continuable. When an error occurs the user is permitted to correct the offending expression or perhaps define a missing function (see Chapter 16 for more information). If the number of arguments to a function is not equal to the number of parameters specified by the definition then the error

occurs. If there is an id in the function position of a form, and there is no function definition associated with it, an error occurs and the message

is printed. If the function position is not occupied by an id, lambda expression or code-pointer then it is an error and one of the following is printed.

The first message is displayed when the error is detected within eval.

As a basis for discussion, an approximation to the actual definition of eval is given.

Eval first determines if its argument is a constant. Examples of constants are numbers, strings, vectors and quoted expressions. For the most part, the function denote will simply return its argument. However, if the constant is a quoted expression then the expression is returned as value.

An identifier is considered a variable. In such a case, eval returns the contents of the value cell of the identifier. Of course things are not quite all that simple. This raises a conceptual issue about when to find the values. The issue is one of scoping rules. Scoping rules come into play when functions are defined. In particular, this involves free variables (those variables which are not parameters of the definition). One approach is static scoping. This strategy locates the values of free variables at the time the function is defined. PSL uses a second approach called dynamic scoping. Using this approach, the values of free variables are not determined until the function is applied.

The PSL environment (the values associated with variables) will typically change during evaluation. When a function is applied, the variables specified by its definition are associated with the arguments of the application. As a result, the value of each variable has changed. As noted above, the value of a variable is found in its value cell. However, the definition and access of values depends upon the binding strategy being used by the implementation. Two common techniques are shallow binding (used in the current implementation of PSL), and deep binding. In a deep bound system the environment is defined by a table of names and values. Each time a variable is set to a value, an entry is added to the table. To locate the value of a variable this table must be searched. When there are multiple definitions for a given variable within this table, the convention is adopted that it is always the latest value which is retrieved. With this strategy we can easily restore an old value, by simply removing the current value from the table. With shallow binding, the value of a variable is positioned with the id which represents the variable. In this case there is no need to search for a value. It is known to always be in a fixed location, the value cell of the id. This second technique makes finding values much more efficient, but it is much more difficult now to keep track of previous values.

If the expression being evaluated is neither a constant or a variable it is assumed to be a function application form. When we apply the function definition to the arguments we associate the parameters of the definition with the arguments. This process of association is called binding and simulates substitution. Within the new environment the body of the function is evaluated. Notice we do not explicitly substitute the values for the variables in an expression.

Eval first looks at the function position, making sure a function definition is available. The manner in which the function is applied depends upon the type of the function. For both exprs and nexprs the arguments are evaluated in a left to right order by the function evlis. Since nexprs expect a single argument, the arguments are gathered into a list. The arguments to an fexpr are not evaluated but they are gathered into a list. The remaining function type to consider is macro. The entire function application form is passed to macros. The result of applying the macro is then evaluated.

Apply uses the additional functions codeapply and lambdaapply to actually evaluate the body of the function. The arguments in ARGS are not evaluated (for example, by a call on evlis). This may seem odd since the type of the function may be expr or nexpr. Apply assumes that the arguments are in the form required for binding to the formal parameters of FUN. Getcodepointer returns the code-pointer associated with an id. The body of a function which is not compiled is found on the property list of its name, under the *lambdalink indicator.