15.1 Evaluation

Feval() evaluates the form (a Lisp object) that is passed to it. Note that evaluation is only non-trivial for two types of objects: symbols and conses. A symbol is evaluated simply by calling symbol-value on it and returning the value.

Evaluating a cons means calling a function. First, eval checks to see if garbage-collection is necessary, and calls garbage_collect_1() if so. It then increases the evaluation depth by 1 (lisp_eval_depth, which is always less than max_lisp_eval_depth) and adds an element to the linked list of struct backtrace’s (backtrace_list). Each such structure contains a pointer to the function being called plus a list of the function’s arguments. Originally these values are stored unevalled, and as they are evaluated, the backtrace structure is updated. Garbage collection pays attention to the objects pointed to in the backtrace structures (garbage collection might happen while a function is being called or while an argument is being evaluated, and there could easily be no other references to the arguments in the argument list; once an argument is evaluated, however, the unevalled version is not needed by eval, and so the backtrace structure is changed).

At this point, the function to be called is determined by looking at the car of the cons (if this is a symbol, its function definition is retrieved and the process repeated). The function should then consist of either a Lisp_Subr (built-in function written in C), a Lisp_Compiled_Function object, or a cons whose car is one of the symbols autoload, macro or lambda.

If the function is a Lisp_Subr, the lisp object points to a struct Lisp_Subr (created by DEFUN()), which contains a pointer to the C function, a minimum and maximum number of arguments (or possibly the special constants MANY or UNEVALLED), a pointer to the symbol referring to that subr, and a couple of other things. If the subr wants its arguments UNEVALLED, they are passed raw as a list. Otherwise, an array of evaluated arguments is created and put into the backtrace structure, and either passed whole (MANY) or each argument is passed as a C argument.

If the function is a Lisp_Compiled_Function, funcall_compiled_function() is called. If the function is a lambda list, funcall_lambda() is called. If the function is a macro, [..... fill in] is done. If the function is an autoload, do_autoload() is called to load the definition and then eval starts over [explain this more].

When Feval() exits, the evaluation depth is reduced by one, the debugger is called if appropriate, and the current backtrace structure is removed from the list.

Both funcall_compiled_function() and funcall_lambda() need to go through the list of formal parameters to the function and bind them to the actual arguments, checking for &rest and &optional symbols in the formal parameters and making sure the number of actual arguments is correct. funcall_compiled_function() can do this a little more efficiently, since the formal parameter list can be checked for sanity when the compiled function object is created.

funcall_lambda() simply calls Fprogn to execute the code in the lambda list.

funcall_compiled_function() calls the real byte-code interpreter execute_optimized_program() on the byte-code instructions, which are converted into an internal form for faster execution.

When a compiled function is executed for the first time by funcall_compiled_function(), or during the dump phase of building SXEmacs, the byte-code instructions are converted from a Lisp_String (which is inefficient to access, especially in the presence of MULE) into a Lisp_Opaque object containing an array of unsigned char, which can be directly executed by the byte-code interpreter. At this time the byte code is also analyzed for validity and transformed into a more optimized form, so that execute_optimized_program() can really fly.

Here are some of the optimizations performed by the internal byte-code transformer:

1. References to the constants array are checked for out-of-range indices, so that the byte interpreter doesn’t have to.
2. References to the constants array that will be used as a Lisp variable are checked for being correct non-constant (i.e. not t, nil, or keywordp) symbols, so that the byte interpreter doesn’t have to.
3. The maximum number of variable bindings in the byte-code is pre-computed, so that space on the specpdl stack can be pre-reserved once for the whole function execution.
4. All byte-code jumps are relative to the current program counter instead of the start of the program, thereby saving a register.
5. One-byte relative jumps are converted from the byte-code form of unsigned chars offset by 127 to machine-friendly signed chars.

Of course, this transformation of the instructions should not be visible to the user, so Fcompiled_function_instructions() needs to know how to convert the optimized opaque object back into a Lisp string that is identical to the original string from the .elc file. (Actually, the resulting string may (rarely) contain slightly different, yet equivalent, byte code.)

Ffuncall() implements Lisp funcall. (funcall fun x1 x2 x3 ...) is equivalent to (eval (list fun (quote x1) (quote x2) (quote x3) ...)). Ffuncall() contains its own code to do the evaluation, however, and is very similar to Feval().

From the performance point of view, it is worth knowing that most of the time in Lisp evaluation is spent executing Lisp_Subr and Lisp_Compiled_Function objects via Ffuncall() (not Feval()).

Fapply() implements Lisp apply, which is very similar to funcall except that if the last argument is a list, the result is the same as if each of the arguments in the list had been passed separately. Fapply() does some business to expand the last argument if it’s a list, then calls Ffuncall() to do the work.

apply1(), call0(), call1(), call2(), and call3() call a function, passing it the argument(s) given (the arguments are given as separate C arguments rather than being passed as an array). apply1() uses Fapply() while the others use Ffuncall() to do the real work.