Issue: FUNCTION-TYPE (version 4)

[Masinter.pa@Xerox.COM]

Status:        Ready to release? [Use ballot]

Issue:          FUNCTION-TYPE
References:     functions (pg 32), types (pg 33), FUNCTIONP (pg 76),
                APPLY (pg 107).
Category:     	CHANGE/CLARIFICATION
Edit History:   Version 1 by RPG 02/26/87
                Version 2 by cleanup committee 15-Mar-87
                Version 3 by SEF 10-May-87
                Version 4 by Masinter 29-May-87 incorporate comments

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.

Even though there is a predicate FUNCTIONP, it is not synonomous to the
use
of the type FUNCTION; the FUNCTION type cannot be used for
discrimination.

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.


Proposal FUNCTION-TYPE:REDEFINE

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.

No sub-types of FUNCTION are defined in Common Lisp, but implementations
are free to define subtypes of FUNCTION.  Examples might be
COMPILED-FUNCTION, INTERPRETED-FUNCTION, and so on. Note that this
is a change from the current Common Lisp definition which explicitly
defines a COMPILED-FUNCTION type. This proposal removes the predicate
COMPILED-FUNCTION-P from the standard language.

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. The text descriptions of FUNCALL, APPLY, MAPCAR and other functions
in Common Lisp which take functional arguments should be to clarify that
they will take either functions, symbols, or lists that represent
lambda-expressions, where a symbol or lambda expression is coerced to a
function using the null lexical environment, and the resulting function
is used.  Note that this is not a change to the the behavior of Common 
Lisp; the descriptions must be changed to accommodate the new definition
of the FUNCTION type.

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 bogus object
and fail only when the supposed function is called.

6. The description of COMPILE is 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" the behavior of COMPILE should be described as "a
definition from which the implementation is able to reconstruct a
lambda-expression". 

Rationale:

This change gives a clean, useful definition to the FUNCTION data type
in
Common Lisp and the related type predicates.  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.

Current Practice:

The definition of FUNCTIONP varies widely between Common Lisp
implementations. No current Common Lisp implementation has exactly the
semantics described here, however.

Adoption Cost:

The type predicates would of course have to be brought into compliance
with this proposal, but that should require little effort.

Compiled functions are true functions in almost all implementations,
but, in some implementations, interpreted functions and closures are
represented as lists.  Some implementations already always store special
types in function cells, but others, which currently store and return 
LAMBDA expressions in SYMBOL-FUNCTION, would be required to change the
behavior of (interpreted FUNCTION).

Some implementations will have to modify the behavior of COMPILE, STEP,
TRACE and (possibly) ED to deal with non-list values in symbol-function
cells.

Benefits:

By resurrecting FUNCTION as a useful concept, this proposed change 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.  It
also brings Common Lisp into closer alignment with Scheme.

Conversion Cost:

This proposal attempts to minimize the impact on user code by allowing
APPLY, FUNCALL, and related functions to accept symbols and lambda
lists, as they currently do.  One impact on user-level code should
be a change in the operation of certain type predicates, and such cases
should be relatively easy to find and fix.

User code which relies on the fact that in some environments,
SYMBOL-FUNCTION returns a list in a well-known format for functions
defined in the lexical global environment will have to change. 

Similarly, some implementations currently allow users to say (SETF #'FOO
'BAR) and then subsequently have a redefinition of BAR affect the
behavior of FOO. This would no longer be allowed, and users of those
implementations would have to change their code.  Others with home-grown
steppers, trace and advise facilities which manipulated the contents of
function cells might have additional work to do.

User code which uses COMPILED-FUNCTION-P would no longer be valid or
portable.

Aesthetics:

Making the concept of a function well-defined will probably be perceived
as a simplification.

It would be cleaner to require all functional arguments to be true
functions, eliminating the use of symbols and lambda-lists in this
context.  However, in this case we felt that the simplification was not
worth a major incompatible change.

Discussion:

The original form of this proposal suggested that APPLY and friends
should take only true functions as the functional argument.  The
current proposal was written after a discussion of the conversion
problems that such an incompatible change might entail. Some cleanup
committee members would prefer the stronger proposal.  

Some committee members have argued for an APPLICABLE-P predicate that
would be true of all objects that can be passed as the functional
argument to APPLY and friends: true functions, lambda lists, and symbols
that are FBOUNDP.  Fahlman believes that this is not terribly useful and
can easily be defined by any user who wants it (or something similar).
In any event, this can be handled in a separate proposal.

Pitman believes that items 4 and 5 are major incopatibilities, and would
prefer if FUNCTION and SYMBOL-FUNCTION be allowed to return things which
are non-functions if those objects can be coerced to functions, and SETF
of SYMBOL-FUNCTION can accept such a coercible object,    and the value
later retrieved will be the given object (not a coerced form of it),
though obviously internally some encapsulation may want to go on for
stock hardware to make function calling fast.

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.