Issue: FUNCTION-TYPE (Version 6)

[Masinter.pa@Xerox.COM]

(I fixed a couple of minor typo's, and cc'd Clinger in this message.)


As I promised back in July, here is a revised version of the
STRICT-REDEFINITION option of FUNCTION-TYPE. In this version, I also
added to the Problem Description some of the issues in
EVAL-DEFEATS-LINKER. I left COMPILED-FUNCTION and COMPILED-FUNCTION-P as
subtypes of FUNCTION. I attempted to move "discussion" items into the
body where appropriate, and eliminated them where they duplicated
arguments already in the body of the proposal. I added a proposal to
extend COERCE to allow (COERCE x 'FUNCTION).

As this is a controversial proposal, avoiding controversy is impossible,
and so I have not attempted it. I am vaguely uneasy that some of the
alternatives and considerations discussed at X3J13 were not mentioned
here -- it *was* a lengthy session. Anyone remember better than I any
other points brought up at the time?

!
Issue:          FUNCTION-TYPE
References:     functions (p. 32), types (p. 33), FUNCTIONP (p. 76),
                SYMBOL-FUNCTION (p. 90), APPLY (p. 107).
Category:     	CHANGE/CLARIFICATION
Edit History:   Version 1 by Gabriel 02/26/87
                Version 2 by cleanup committee 15-Mar-87
                Version 3 by Fahlman 10-May-87
                Version 4 by Masinter 29-May-87 incorporate comments
                Version 5 by Fahlman 15-June-87 include two options
                Version 6 by Masinter 23-Oct-87, only
STRICT-REDEFINITION

Problem Description:

The definition of the term `function' in CLtL includes all symbols and
many lists in addition to true functions.  The type named `function' is
therefore not a useful type, and its presence complicates the type
hierarchy. The language would be improved if functions were treated as a
type in a consistent and useful manner.  This would also make it easier
to integrate the function data type into the CLOS class hierarchy.

At present, it is not the case that (FUNCTIONP x) is equivalent to
(TYPEP x 'FUNCTION), because the latter form is illegal under a strict
reading of the manual.  On page 47 it is stated that the FUNCTION type
specifier can only be used for declaration and not for discrimination.
Some of the original Common Lisp designers maintain that this
restriction on the use of the FUNCTION specifier was meant to apply only
to long-form FUNCTION specifiers.  In any event, this issue blurs the
status of the FUNCTION data-type.

The current confused situation came about mostly because of a desire in
the original Common Lisp definition to retain compatibility with older
Lisp dialects, but in the context of Common Lisp some of these ancient
design decisions are inappropriate.

In addition, the practice that APPLY, FUNCALL and the numerous functions
that take functional arguments (such as MAPC, MAPCAR, FIND-IF) can
potentially do the equivalent of  SYMBOL-FUNCTION to go from a symbol to
its functional-value is a serious impediment to program analysis which
require the ability to determine by examining a program which functional
definitions might be accessed from it. For example, "selective linking"
(which would allow a delivery system to include only those parts of the
Common Lisp library actually accessed) is seriously hampered by the
numerous implicit coercions of symbols to functions.

Proposal FUNCTION-TYPE:STRICT-REDEFINITION

1. Under this proposal FUNCTION is a full-fledged data type that can be
used both for declaration and discrimination.  The list form of the
FUNCTION type specifier may still be used only for declaration.

Symbols (whether or not the symbol is FBOUNDP) and lambda expressions
are not of type FUNCTION under this proposal.

The types CONS, SYMBOL, ARRAY, NUMBER, CHARACTER, and FUNCTION are
pairwise disjoint.  In particular, a list may not be used to implement
any FUNCTION subtype.

The COMPILED-FUNCTION subtype of FUNCTION is defined; implementations
are free to define subtypes of FUNCTION, e.g., INTERPRETED-FUNCTION.  

2. The behavior of FUNCTIONP is defined to be exactly equivalent to
#'(LAMBDA (X) (TYPEP X 'FUNCTION)).  In particular, FUNCTIONP is no
longer true of symbols and lambda lists.

3. FUNCALL and APPLY will now accept only a true function as the
functional argument.  This restriction is inherited by MAPCAR and other
functions in Common Lisp that take a functional argument suitable for
FUNCALL or APPLY.  It is no longer legal to pass a symbol or lambda
expression as the functional argument to any of these functions; to do
so "is an error".

4. In all non-error situations, the result of evaluating a FUNCTION
special form is required to be of type FUNCTION.  It is an error to use
the special form FUNCTION on a symbol that does not denote a function in
the lexical environment in which the special form appears. Specifically,
it is an error to use the FUNCTION special form on a symbol that denotes
a macro or special form.  (Some implementations may choose not to signal
this error for performance reasons.)

5. If SYMBOL-FUNCTION is called on a symbol that names a function in the
null lexical context, it returns that function (which, of course, is of
type FUNCTION).  It is an error to call SYMBOL-FUNCTION on anything
else.  In particular, it is an error to call SYMBOL-FUNCTION on a symbol
that names a macro or special form in the null lexical context; it is
unpredictable what will be returned in this case.

It is an error to pass anything other than a (true) function as the
value to (SETF (SYMBOL-FUNCTION symbol) value).  Some implementations
will signal an error in this case; others may accept the object and fail
only when the supposed function is called.

6. The description of COMPILE must be changed, since it is no longer
meaningful to speak of a symbol with a definition that "is a
lambda-expression".  Where CLtL says "a definition that is a
lambda-expression", substitute "a definition from which the
implementation is able to reconstruct a lambda-expression".

7. Extend the definition of COERCE to allow coercion of objects to type
FUNCTION. That is, "Some symbols and lists may be converted to
functions." (COERCE SYMBOL 'FUNCTION) performs SYMBOL-FUNCTION (getting
the top level function definition, the current lexical context is not
relevant), while (COERCE LIST 'FUNCTION) is equivalent to (EVAL
`(FUNCTION ,LIST)), i.e., it creates a function from a LAMBDA expression
by interpreting it as a list in the top level lexical environment.

8.  Modify the description of the macro expansion process to say that
the value of *MACROEXPAND-HOOK* is coerced to a function before being
called as the expansion interface hook by MACROEXPAND-1. 
Rationale:

This proposal provides a clean, useful definition for the FUNCTION
data-type in Common Lisp.  Under the current definition, FUNCTIONP is
nearly useless, since it is defined to be true of all symbols, including
those that do not have functional definitions.

It also enhances the semantics of Common Lisp functional arguments to be
more consistent with other programming languages, and allows better
program analysis tools.

Current Practice:

Current Common Lisp implementations vary in the way they handle
FUNCTIONP and TYPEP of FUNCTION.  They also vary in what they will allow
to be put into a SYMBOL-FUNCTION cell.  No current Common Lisp
implementation has exactly the semantics described in this proposal,
however, although it corresponds more closely to Scheme and to the work
of the EuLisp community.

Adoption Cost:

Bringing type predicates (FUNCTIONP, etc.)  into compliance should
require little effort.

Compiled functions are true functions in almost all current
implementations, but in some implementations interpreted functions and
closures are represented as lists.  Such lists would have to be changed
to structures or to some special internal data type.  The behavior of
COMPILE, STEP, TRACE, and possibly ED would have to be modified to deal
with functions that are not lists (but from which the list form can be
easily reconstructed if necessary).

Implementations may choose to convert FUNCALL and APPLY to the new
stricter form, but they are not required to do so.  Since the use of a
symbol or lambda expression in place of a
function "is an error", an implementation may handle these cases as a
local extension.  Most implementations that continue to provide the
coercion will at least want to install an optional warning in FUNCALL
and APPLY to flag the use of this non-portable feature in user code.

Benefits:

By resurrecting FUNCTION as a useful concept, this proposal (either
version) will eliminate a lot of confusion and will make it easier to
talk about situations in which (true) functions are passed around as
Lisp objects.

By eliminating some tangles in the type hierarchy, this proposal
simplifies the task of mapping Common Lisp types into CLOS classes.

This proposal brings Common Lisp into closer alignment with Scheme and
the work of the EuLisp committee.

This proposal allows for better program analysis tools, enhances the
ability to do "selective linking" correctly. It makes it possible to
reduce the total size of a delivered application program. Only those
Common Lisp functions that are actually called need to be
included; implicit coercions tend to create loopholes through which
*every* function might be called.

Conversion cost:

This proposal may have a high conversion cost for some existing Common
Lisp programs. The changes to FUNCTIONP and the FUNCTION type
declaration is relatively easy to deal with. However, the strict
redefinition of FUNCALL, APPLY and functional arguments will require the
addition of an explicit coercion would have to be added whenever a
symbol or lambda expression is used as a functional argument. Many such
cases can be identified at compile time, but not all. 

Some implementations might provide tools to assist in detecting implicit
coercion of symbols to functions. For example, an implementation might
add run-time test in which the implementation still does the coercion
but that issues a warning message whenever the coercion is actually
needed. Alternatively, a "smart" code-walker or editor macro might find
all of the calls to FUNCALL, APPLY, and the 61 Common Lisp functions
that take :TEST or :KEY arguments and, if the argument is not already an
explicitly quoted FUNCTION form, wrap a COERCE around the body.  

In some current Common Lisp implementations, SETF of SYMBOL-FUNCTION
will accept a symbol or lambda expression and SYMBOL-FUNCTION will
return this item unchanged.  If a symbol FOO is used as the functional
definition of BAR, then any change to FOO will affect BAR as well.  Some
old code depends on this behavior and would have to be modified if this
proposal is adopted; doing so will be difficult as these uses cannot
easily be detected from simple examination of the program. (Such code is
not currently portable because many existing Common Lisp implementations
already violate these assumptions.  CLtL does not clearly state what
values SETF of SYMBOL-FUNCTION will accept and how that object may be
modified.)


Aesthetics:

Making the concept of a function well-defined is a simplification of the
language. This proposal is the cleanest of the alternatives; it defines
a FUNCTION data type and then requires every object used as a function
to be a FUNCTION. While many argue that removing automatic coercion
results in a simpler, cleaner, and more aesthetic language definition,
others have argued otherwise ("its all a matter of taste.")

Discussion:

This proposal has been discussed at great length; this section attempts
only to summarize the important points.

There is general agreement that the definition of the FUNCTION data type
must be revised. (There was one suggestion to create a new type name and
to leave FUNCTION alone, but it was not generally perceived as
acceptable.) The cleanup of the type hierarchy is important to the CLOS
group. 

There is much more disagreement about disallowing implicit coercions;
cleanup of implicit coercions are important for compatibility with other
Lisp standards work.

Some argue that it seems better to make this effort once than to live
forever with runtime coercion of functional arguments and the resulting
complexity.

Some have argued that the coercing form of the proposal is no more
complex than the strict form; it is all a matter of taste.

If coercing was continued to be allowed, Common Lisp might need an
APPLICABLE-P predicate that is true of any object that is legal as a
functional argument to APPLY and FUNCALL, since FUNCTIONP would no
longer do this job.

The cleanup committee believes that the definition of COMPILE needs
clarification, but that it should be done in a separate proposal. The
change to COMPILE in this proposal is the minimum necessary.

This proposal interacts with the proposal on compiler semantics: some
claim that strict-redefinition would allow further compiler
optimizations, since compiled FUNCALL is not required to go through
extensive inline checks. 

Fahlman, Gabriel and Masinter support FUNCTION-TYPE:STRICT-REDEFINITION.

Pitman and Moon have expressed support for an alternative proposal which
would continue to allow coercion.