Earlier message on function objects

[BENSON at SPA-Nimbus]

Here is the message I sent about a month ago.  The last paragraphs
suggests some system-building tools.  Purists may object to these as
violating referential transparency.  They are not essential for most
users, but every system will need something like them, so they might as
well be portable.

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

-*-Mode:Text-*-
To: Common-Lisp%su-ai@usc-ecl
Subject: Function objects

The Laser Edition of the Common Lisp Reference Manual is inconsistent in
its treatment of functions.  This inconsistency is due to confusion
between the name of a function and the actual function object.  This
confusion has been around for a long time, and is manifested in many
Lisp implementations where the name of a function object and the object
itself are the same.  To quote from the Standard Lisp Report: "FUNCTION
is like QUOTE but its argument may be affected by compilation."

First, we need to state what we mean by a function object.  The
definition of the FUNCTIONP data type predicate says that it

"is true if its argument is suitable for applying to arguments, using
for example the FUNCALL or APPLY function."

The definition of APPLY states that its argument

"may be a compiled-code object, or a lambda expression, or a symbol; in
the latter case the global functional value of that symbol is used."

(Let's ignore compiled-code objects for the time being; we'll get back
to them later.)  This is the definition which confuses the name (symbol
or lambda expression) and the function object.  Conflicting with this
definition is the Functions section of the Progam Structure chapter
(Section 5.2, p. 42).  It states that

"Lambda-expressions and symbols as names of functions can appear only as
the first element of a function-call form, or as the second element of
the FUNCTION special form."

The definition of the FUNCTION special form, where FN is the second
element of the form, states that

"if FN is a symbol, the functional value of the variable whose name is
that symbol is returned.  If FN is a lambda expression, then a lexical
closure is returned."

Notice that the definition of APPLY doesn't even mention lexical
closures, yet these are the things which are produced by the FUNCTION
special form, which is presumably the preferred means of obtaining a
suitable object to use as an argument to APPLY!

The key to understanding all of this is to realize that the CAR of a
Lisp form (ignoring macros and special forms) is not "not evaluated," in
fact it is a function name which is evaluated to produce a function
object.  In Scheme this evaluation is the same as that used to produce
function arguments, i.e. the function EVAL.  Common Lisp must use a
different algorithm, because it permits symbols to have distinct
variable and function values.  The function which implements this
algorithm is not mentioned in the Common Lisp manual.  In fact I don't
know of any Lisp implementations which provide it; it is usually
open-coded (sometimes a no-op!) within EVAL.  For the sake of
discussion, let's call it FEVAL.  In fact the one we are most interested
in is *FEVAL, analogous to *EVAL, since this function must use the
current lexical environment in its evaluation process.

Evaluation of a form which represents an ordinary function call is thus:
FEVAL the CAR of the form, EVAL all the other elements of the list, call
the result of FEVAL with the EVALed arguments.  FEVAL is useful to
produce a function object which will not be called immediately.  The
FUNCTION special form says in effect: use FEVAL instead of EVAL to
produce this argument.  Conversely, EVAL is also useful in producing
function objects.  FUNCALL allows normal argument evaluation to return
a function object to be called.  Note that neither FUNCTION nor
FUNCALL is needed in Scheme precisely because EVAL and FEVAL are the
same.

FEVAL is a very simple function.  If its argument is a lambda
expression, it returns a closure of the expression over the lexical
environment.  If it is a symbol, the "functional variable" value of the
symbol in the lexical (or global) environment is returned.  Anything
else is an error.  As an upward-compatible extension, function specs as
provided in Zetalisp, such as (:PROPERTY FOO BAR), are treated
essentially the same as symbols.  They simply specify a place from which
to fetch a function object.

The semantics of compiled-code objects have not been described
extensively in the Common Lisp manual.  They are mentioned in the
spurious definition of APPLY above, which might lead one to think of
them as being "like lambda expressions, only faster."  In fact the only
sensible interpretation of a compiled-code object is "like FEVAL of a
lambda expression, only faster."  In other words, anything a lexical
closure can do, a compiled-code object can do, except that the structure
selector functions defined below would only be for lexical closures.
This should be stated explicitly in the manual in the data type section.

The argument to APPLY (and FUNCALL) can be a compiled-code object or a
lexical closure; anything else is an error.  A language standard which
considers symbols or lambda expressions to be functions is perpetuating
the confusion described above.

To acheive the effect of using a symbol as a function as described above
(and currently implemented in Zetalisp, for example), that is, using the
global functional value at the time it is called, one must use a closure
which calls the function, e.g. to give BAR as a functional argument to
FOO, where BAR's definition may change between the call to FOO and the
FUNCALL of its functional argument, use: 
 
(FOO #'(LAMBDA (X) (BAR X)))	;BAR is a function of one argument

instead of

(FOO 'BAR)

In general, if the number of arguments is unknown:

(FOO #'(LAMBDA (&REST X) (APPLY #'BAR X)))

Or, if you really mean the global function value, not the lexical:

(FOO #'(LAMBDA (&REST X) (APPLY (SYMBOL-FUNCTION 'BAR) X)))

The current language definition does not provide either a function which
takes a lambda expression and a lexical environment and returns a
lexical closure (*FEVAL) or functions to extract these components from
an existing lexical closure.  These aren't strictly necessary, but
without them many useful parts of a programming environment must be
written non-portably.  For example, GRINDEF is impossible in portable
Common Lisp, since SYMBOL-FUNCTION must return either a lexical closure
or a compiled-code object.  A structure editor which can redefine a
function requires both selector functions and the constructor function,
since it must create a new closure with the modified function body.

I recommend that lexical environments be included in the language as
first-class objects.  *EVAL and EVALHOOK would then be defined to take
exactly two arguments.  ENCLOSE (*FEVAL restricted to lambda
expressions) takes a lambda expression and a lexical environment and
returns a lexical closure.  CLOSURE-EXPRESSION and CLOSURE-ENVIRONMENT
take a lexical closure and return its components.  The constant
NULL-ENVIRONMENT, the empty lexical environment, should be defined.  The
structure of a lexical environment need not (indeed, should not) be
specified. These additions are not major and would aid immensely in
supporting a truly lexical Lisp.