

22. Evaluation; Stack Frames; Bindings

22.1 Evaluation  
22.2 Dynamic Binding; The specbinding Stack; Unwind-Protects  
22.3 Simple Special Operators  
22.4 Catch and Throw  
22.5 Error Trapping  


22.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 XEmacs, 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.


22.2 Dynamic Binding; The specbinding Stack; Unwind-Protects

struct specbinding
  Lisp_Object symbol;
  Lisp_Object old_value;
  Lisp_Object (*func) (Lisp_Object); /* for unwind-protect */

struct specbinding is used for local-variable bindings and unwind-protects. specpdl holds an array of struct specbinding's, specpdl_ptr points to the beginning of the free bindings in the array, specpdl_size specifies the total number of binding slots in the array, and max_specpdl_size specifies the maximum number of bindings the array can be expanded to hold. grow_specpdl() increases the size of the specpdl array, multiplying its size by 2 but never exceeding max_specpdl_size (except that if this number is less than 400, it is first set to 400).

specbind() binds a symbol to a value and is used for local variables and let forms. The symbol and its old value (which might be Qunbound, indicating no prior value) are recorded in the specpdl array, and specpdl_size is increased by 1.

record_unwind_protect() implements an unwind-protect, which, when placed around a section of code, ensures that some specified cleanup routine will be executed even if the code exits abnormally (e.g. through a throw or quit). record_unwind_protect() simply adds a new specbinding to the specpdl array and stores the appropriate information in it. The cleanup routine can either be a C function, which is stored in the func field, or a progn form, which is stored in the old_value field.

unbind_to() removes specbindings from the specpdl array until the specified position is reached. Each specbinding can be one of three types:

  1. an unwind-protect with a C cleanup function (func is not 0, and old_value holds an argument to be passed to the function);
  2. an unwind-protect with a Lisp form (func is 0, symbol is nil, and old_value holds the form to be executed with Fprogn()); or
  3. a local-variable binding (func is 0, symbol is not nil, and old_value holds the old value, which is stored as the symbol's value).


22.3 Simple Special Operators

or, and, if, cond, progn, prog1, prog2, setq, quote, function, let*, let, while

All of these are very simple and work as expected, calling Feval() or Fprogn() as necessary and (in the case of let and let*) using specbind() to create bindings and unbind_to() to undo the bindings when finished.

Note that, with the exception of Fprogn, these functions are typically called in real life only in interpreted code, since the byte compiler knows how to convert calls to these functions directly into byte code.


22.4 Catch and Throw

struct catchtag
  Lisp_Object tag;
  Lisp_Object val;
  struct catchtag *next;
  struct gcpro *gcpro;
  jmp_buf jmp;
  struct backtrace *backlist;
  int lisp_eval_depth;
  int pdlcount;

catch is a Lisp function that places a catch around a body of code. A catch is a means of non-local exit from the code. When a catch is created, a tag is specified, and executing a throw to this tag will exit from the body of code caught with this tag, and its value will be the value given in the call to throw. If there is no such call, the code will be executed normally.

Information pertaining to a catch is held in a struct catchtag, which is placed at the head of a linked list pointed to by catchlist. internal_catch() is passed a C function to call (Fprogn() when Lisp catch is called) and arguments to give it, and places a catch around the function. Each struct catchtag is held in the stack frame of the internal_catch() instance that created the catch.

internal_catch() is fairly straightforward. It stores into the struct catchtag the tag name and the current values of backtrace_list, lisp_eval_depth, gcprolist, and the offset into the specpdl array, sets a jump point with _setjmp() (storing the jump point into the struct catchtag), and calls the function. Control will return to internal_catch() either when the function exits normally or through a _longjmp() to this jump point. In the latter case, throw will store the value to be returned into the struct catchtag before jumping. When it's done, internal_catch() removes the struct catchtag from the catchlist and returns the proper value.

Fthrow() goes up through the catchlist until it finds one with a matching tag. It then calls unbind_catch() to restore everything to what it was when the appropriate catch was set, stores the return value in the struct catchtag, and jumps (with _longjmp()) to its jump point.

unbind_catch() removes all catches from the catchlist until it finds the correct one. Some of the catches might have been placed for error-trapping, and if so, the appropriate entries on the handlerlist must be removed (see "errors"). unbind_catch() also restores the values of gcprolist, backtrace_list, and lisp_eval, and calls unbind_to() to undo any specbindings created since the catch.


22.5 Error Trapping


This is equivalent to (*fun) (arg), except that various conditions can be trapped or inhibited, according to FLAGS.

If PROBLEM is non-zero, it should be a pointer to a structure into which exact information about any occurring problems (either an error or an attempted throw past this boundary).

If a problem occurred and aborted operation (error, quit, or invalid throw), Qunbound is returned. Otherwise the return value from the call to (*fun) (arg) is returned.

