22. Evaluation; Stack Frames; Bindings

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

call_trapping_problems():

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

• If FLAGS does not contain NO_INHIBIT_ERRORS, when an error occurs, the error is caught and a warning is issued, specifying the specific error that occurred and a backtrace. In that case, WARNING_STRING should be given, and will be printed at the beginning of the error to indicate where the error occurred.
• If FLAGS does not contain NO_INHIBIT_THROWS, all attempts to throw out of the function being called are trapped, and a warning issued. (Again, WARNING_STRING should be given.)
• If FLAGS contains INHIBIT_WARNING_ISSUE, no warnings are issued; this applies to recursive invocations of call_trapping_problems, too.
• If FLAGS contains POSTPONE_WARNING_ISSUE, no warnings are issued; but values useful for generating a warning are still computed (in particular, the backtrace), so that the calling function can issue a warning.
• If FLAGS contains ISSUE_WARNINGS_AT_DEBUG_LEVEL, warnings will be issued, but at level debug, which normally is below the minimum specified by log-warning-minimum-level, meaning such warnings will be ignored entirely. The user can change this variable, however, to see the warnings.)

  Note: If neither of NO_INHIBIT_THROWS or NO_INHIBIT_ERRORS is given, you are guaranteed that there will be no non-local exits out of this function.

• If FLAGS contains INHIBIT_QUIT, QUIT using C-g is inhibited. (This is rarely a good idea. Unless you use NO_INHIBIT_ERRORS, QUIT is automatically caught as well, and treated as an error; you can check for this using EQ (problems->error_conditions, Qquit).
• If FLAGS contains UNINHIBIT_QUIT, QUIT checking will be explicitly turned on. (It will abort the code being called, but will still be trapped and reported as an error, unless NO_INHIBIT_ERRORS is given.) This is useful when QUIT checking has been turned off by a higher-level caller.
• If FLAGS contains INHIBIT_GC, garbage collection is inhibited. This is useful for Lisp called within redisplay, for example.
• If FLAGS contains INHIBIT_EXISTING_PERMANENT_DISPLAY_OBJECT_DELETION, Lisp code is not allowed to delete any window, buffers, frames, devices, or consoles that were already in existence at the time this function was called. (However, it’s perfectly legal for code to create a new buffer and then delete it.)

  #### It might be useful to have a flag that inhibits deletion of a specific permanent display object and everything it’s attached to (e.g. a window, and the buffer, frame, device, and console it’s attached to.

• If FLAGS contains INHIBIT_EXISTING_BUFFER_TEXT_MODIFICATION, Lisp code is not allowed to modify the text of any buffers that were already in existence at the time this function was called. (However, it’s perfectly legal for code to create a new buffer and then modify its text.)

  [These last two flags are implemented using global variables Vdeletable_permanent_display_objects and Vmodifiable_buffers, which keep track of a list of all buffers or permanent display objects created since the last time one of these flags was set. The code that deletes buffers, etc. and modifies buffers checks

  1. if the corresponding flag is set (through the global variable inhibit_flags or its accessor function get_inhibit_flags()), and
  2. if the object to be modified or deleted is not in the appropriate list.

  If so, it signals an error.

  Recursive calls to call_trapping_problems() are allowed. In the case of the two flags mentioned above, the current values of the global variables are stored in an unwind-protect, and they’re reset to nil.]

• If FLAGS contains INHIBIT_ENTERING_DEBUGGER, the debugger will not be entered if an error occurs inside the Lisp code being called, even when the user has requested an error. In such case, a warning is issued stating that access to the debugger is denied, unless INHIBIT_WARNING_ISSUE has also been supplied. This is useful when calling Lisp code inside redisplay, in menu callbacks, etc. because in such cases either the display is in an inconsistent state or doing window operations is explicitly forbidden by the OS, and the debugger would causes visual changes on the screen and might create another frame.
• If FLAGS contains INHIBIT_ANY_CHANGE_AFFECTING_REDISPLAY, no changes of any sort to extents, faces, glyphs, buffer text, specifiers relating to display, other variables relating to display, splitting, deleting, or resizing windows or frames, deleting buffers, windows, frames, devices, or consoles, etc. is allowed. This is for things called absolutely in the middle of redisplay, which expects things to be exactly the same after the call as before. This isn’t completely implemented and needs to be thought out some more to determine exactly what its semantics are. For the moment, turning on this flag also turns on
  • - INHIBIT_EXISTING_PERMANENT_DISPLAY_OBJECT_DELETION
  • - INHIBIT_EXISTING_BUFFER_TEXT_MODIFICATION
  • - INHIBIT_ENTERING_DEBUGGER
  • - INHIBIT_WARNING_ISSUE
  • - INHIBIT_GC
• #### The following five flags are defined, but unimplemented:

  #define INHIBIT_EXISTING_CODING_SYSTEM_DELETION (1<<6) #define INHIBIT_EXISTING_CHARSET_DELETION (1<<7) #define INHIBIT_PERMANENT_DISPLAY_OBJECT_CREATION (1<<8) #define INHIBIT_CODING_SYSTEM_CREATION (1<<9) #define INHIBIT_CHARSET_CREATION (1<<10)

• FLAGS containing CALL_WITH_SUSPENDED_ERRORS is a sign that call_with_suspended_errors() was invoked. This exists only for debugging purposes – often we want to break when a signal happens, but ignore signals from call_with_suspended_errors(), because they occur often and for legitimate reasons.

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.

This document was generated by Aidan Kehoe on December 27, 2016 using texi2html 1.82.