Common EVAL

[CFry@OZ.AI.MIT.EDU]

Common EVAL

Henry Lieberman and Christopher Fry


Abstract

We propose that the Common Lisp standard be extended by adding to the
language specification a short program, itself written in Common Lisp, to
implement the EVAL function.  The interpreters for every correct
implementation of Common Lisp would be required to match the semantics of
Common EVAL on valid Common Lisp expressions.  
It should treat other expressions as errors or as implementation dependent 
extensions.  There are
three cogent reasons for including a Common EVAL in the standard:
First, since EVAL fixes the meaning of Lisp programs, it would
insure uniformity of program semantics across implementations.
Second, it would aid validation efforts, since the behavior of a
particular implementation could always be compared to the behavior
of Common EVAL.  Third, it would facilitate the creation of debuggers
and other program-manipulating programs that could be ported across
Common Lisp implementations. 

----------------------------------------------------------------------

One of the marvelous things about Lisp is that the language can be written in
itself.  In Lisp, programs can be data and data can be programs.  The
operation of the language itself can be described as a function written in
the very same language: the EVAL function.  Lisp advocates always point
with pride to this fact as a major reason for Lisp's superiority over
conventional languages.  It is why Lisp has traditionally supported the
best debugging environments.  It is why Lisp can be used to write the
program-manipulating programs which are essential in artificial
intelligence work, and in building advanced interactive programming
environments.

Sadly, this important advantage is becoming steadily eroded by some of the
modern production implementations of Lisp.  The quest for efficiency and
experimentation with esoteric programming constructs are leading to
non-standard implementations of Lisp interpreters that foil attempts
to make use of Lisp's self-descriptive capability.

With Common Lisp, we have a unique opportunity to insure that the
program-data equivalence which is one of Lisp's cornerstones remains
available as Lisp implementations proliferate.  But the English
description in the Steele book is not detailed enough to exclude semantic
deviations which frustrate serious developers of program-manipulating
programs.

Specifying the EVAL function as a Common Lisp program can provide a
concise, precise, and easily understood description which could serve as a guide for
implementors and a means by which to evaluate the results.  
Implementors would not be required to run the exact code for Common
EVAL in their implementation. 
They could provide another implementation, which may be more efficient or include
extra features, but they would be required to assure that their version matched the
semantics of Common EVAL.
Differences in behavior between a particular Lisp implementation and Common EVAL
would be evidence for violations of the Common Lisp standard.

Many advanced Lisp applications rely on the precise details of the operation of
EVAL.  Implementing a single-stepping debugger for Lisp code, for example,
requires imitating EVAL on Lisp expressions, while inserting display operations
and requesting input at events during evaluation.

Lisp's extensibility makes it ideal for defining embedded application-dependent
languages, which may even have a different control structure than Lisp's.  Often,
these languages need to "use Lisp" as a subset, call Lisp functions from code in
the other language, or even invoke foreign language code from Lisp code.  For
the interface to be smooth, the language designer must be able to depend on how
Lisp code is evaluated, perhaps including details such as variable environments
and function definitions.

Many programs which need to analyze Lisp programs statically require a "code
walker", a program that determines which subexpressions of a Lisp expression
represent code to be evaluated, and which represent data, like expressions which
appear inside a QUOTEd list.  Such code walkers, which separate the uses of
Lisp expressions as programs from uses as data, appear in virtually every Lisp
compiler.  Smart pretty-printers that print expressions according to their
semantics, indexers, or other "programmer's apprentice" tools need this, too.
Code walkers anticipate the action of EVAL on an expression, so they are
inextricably tied to EVAL's operation.

With Common EVAL, a designer of a program-manipulating program can base their
tools on the definition of Common EVAL rather than the details of a particular
Lisp implementation.
The implementor can then have confidence that the tools will work in all valid
implementations of Common Lisp.
This should significantly enhance Common Lisp's suitability for advanced applications.

The interpreters for MIT-descended Lisp Machines by Symbolics, LMI and TI 
show how production implementations have compromised Lisp semantics.  
Surprisingly, if you look at the system's definition of the EVAL
function, you will find that it only appears to be written in Lisp.  
It calls "subprimitives" which are special-cased by the compiler, compiling
into specialized microcode, motivated by an attempt to make the Lisp interpreter more
efficient.  
The subprimitives do things which, for example, violate the stack discipline of Lisp. 
The system's definition of EVAL cannot even be interpreted by EVAL itself!

Because of the additional complexity that machine-dependent efficiency hacks add to
the evaluator, it is no longer feasible to write an EVAL without subprimitives, and
have any confidence that the results will be equivalent to the system's EVAL.
If the code for the evaluator relies on subprimitives, it won't even be intelligible to
the human reader literate only in Lisp.

This is not to say that we are against subprimitives; obviously, they are necessary
for such functions as CAR and EQ.
The English description of the behavior of lowest level functions in the 
Steele book is adequate, as is the description of middle level functions like APPEND.
It is only when the complexity of something like EVAL is reached that 
divergence among implementations becomes a real problem.

Periodically, internal changes to a system's evaluator require changing any
imitative implementation.
For example, Symbolics recently changed the function cell of an interpreted function
from containing a lambda expression to SI:DIGESTED-LAMBDA, which necessitated
similar changes in any program which expected to interpret functions.
A standard EVAL would clarify what representations a user could rely on, and clarify
what representations an implementor could change without breaking system code
or affecting users. 

Another central problem is that "extensions" to the Lisp language may be 
implemented in the interpreter by low-level constructs that cannot
be directly implemented by a Lisp program.  While Common Lisp is
designed to permit extensions to the language, it should not allow
extensions which rely on microcode and other non-Lisp implementation techniques to 
change the basic semantics of the language.
Such extensions effectively prevent any program-manipulating
program written in Common Lisp from operating on code containing
the extensions. 

Spaghetti stacks in Interlisp are an example where an attempt to
implement non-standard programming constructs wreaks havoc with the
interpreter's semantics.  It is impossible for an Interlisp
user to write a stepping debugger capable of working on interpreted code
that uses spaghetti stacks.  
Common EVAL should provide well-defined points in the evaluation process at which
particular implementations could provide extensions, such as defining a new variety of
functional object.

How detailed should the Common EVAL implementation be?  Everyone knows
that it is possible to implement a wide range of meta-circular
interpreters ranging from a one-page interpreter in the vein of the
original Lisp 1.5 book, to one that is so detailed it specifies every bit
and would probably run to hundreds of pages.  Clearly, a middle course is
called for.  The interpreter should be the minimal size necessary
to specify the interpreter in terms of calls to Common Lisp functions.
It should probably take no more than ten pages to do this.  It should
be detailed enough to do things like specify the behavior of all
the special forms, but does not have to be so detailed as to
specify all the internal representations used by the evaluator.  

The interpreter may need a variety of helping functions to access
representations of data structures, for example lexical variable binding
environments.  To avoid constraining the freedom of implementors to choose
efficient representations for such data structures, Common EVAL could call
abstract functions whose implementation would not be prescribed by the
standard.  Every implementation could provide its own EXTEND-ENVIRONMENT
function, whose behavior would be specified by a description, in the
manner of the Steele book.  A simple Common Lisp implementation, for
example implementing environments as ALISTs, could be shown for
illustrative purposes without fixing the ALIST representation in every
Common Lisp implementation.

Finally, to illustrate the intent of our proposal more concretely, we present a
short segment of Lisp code for a skeleton Common EVAL.  Don't take this code
too literally -- we mean it only to illustrate the style and the level of detail
we would expect of the real Common EVAL, and as a springboard for
discussion.  

#| 

Some notes about the code:
- The LE package contains the lexical environment manipulator
   fns, many of which are yet to be written. If the CL community
   decides to provide advertised support for lexical environment functions,
   some of the functions here could be moved into to LISP package.

- The NOT-CL package contains miscellaneous support functions for Common EVAL.
 
- An implementation of eval is permitted to differ semantically
  from Common EVAL only by redefining NOT-CL:EVAL.
  This provides a well defined place for modifications to take place.
  Our default definition here simply errors, as would a pure CL
  implementation.

Functions here which are called, not in CL, and intended to be
  defined by Common EVAL include:
  - APPLY
  - The lexical environment accessors.
  - The functions for handling individual special forms.
  - Closures and lexical functions are not dealt with yet.
  
|#

(defun eval (exp &optional lex-env)
  "currently doesn't check for lex-env fns.
   Right now, CL doesn't permit EVAL to take a 2nd arg.
   LEX-ENV defaults to the null lexical environment."
   (cond ((not-cl:self-evaluating-p exp) exp)
         ((symbolp exp) (not-cl:symbol-eval exp lex-env))                 
         ((consp exp) 
          (cond ((symbolp (car exp))                          
                 (cond ((macro-function (car exp))
                        (eval (macroexpand exp) lex-env))
                       ((special-form-p (car exp)) 
                        (not-cl:eval-special-function-call exp lex-env))
                       ((fboundp (car exp))                         
                        (apply (car exp) 
                               (not-cl:list-of-values (cdr exp) lex-env)))
                       (t (not-cl:eval exp lex-env))))
                 ((and (consp (car exp)) 
                       (eq (car (car exp)) 'lambda))
                  (apply (car exp) (cdr exp)))
                 (t (not-cl:eval exp lex-env))))
         (t (not-cl:eval exp lex-env))))

(defun not-cl:self-evaluating-p (form)
   (or (numberp form) (stringp form) (characterp form) (keywordp form)
       (null form) (eq form t)))

(defun not-cl:symbol-eval (symbol lex-env)
  "If SYMBOL is a variable in LEX-ENV, return its value.
   Else If SYMBOL is bound, return its value, 
   else error."
  (if (le:boundp symbol)
      (le:symbol-value symbol lex-env)
      (if (boundp symbol)
          (symbol-value symbol)
          (error "Attempt to evaluate an unbound symbol ~S" symbol))))

(defun not-cl:list-of-values (list lex-env)
   (if list
       (cons (eval (car list) lex-env)
             (not-cl:list-of-values (cdr list) lex-env))))

(defun not-cl:eval-special-function-call (exp lex-env)
  (case (car exp)
   (block (not-cl:eval-block exp lex-env))
   (catch (not-cl:eval-catch exp lex-env))
   ;...
   (otherwise (error "not-cl:eval-special-function-call passed
                      non-implemented special form ~S" exp))))

(defun not-cl:eval (exp &optional lex-env)
      (error "Eval passed non-CL form ~S" exp))