Issue: FUNCTION-TYPE (version 5)

["Scott E. Fahlman" <Fahlman@C.CS.CMU.EDU>]

I have written up a version of this proposal that presents the two
options we have discussed the most as alternatives.  The idea is that we
can perhaps debug this proposal before the Boston meeting, and then have
something concrete and written-down to discuss with the whole X3J13
group.  Perhaps that discussion will lead to some consensus or at least
to a clear view of which way the majority of X3J13 wants to go.  A mail
ballot after the meeting could make things official in that case.  Of
course, it is also possible that people will decide to postpone the
difficult issues and just vote on the type cleanup, without deciding how
the resulting types may be used.

By writing up these two options, I do not mean to preclude others.
However, the only other proposal that has appeared is the one from KMP
that we require a symbol's function cell to accept symbols and lambda
expressions as well as true functions and to return unchanged whatever
was put there.  Kent has indicated some ambivalence about whether he
wants to press forward with this option, which has not received any
support from others on the committee.  If he does want to press this,
he should write up this option himself, since I don't really understand
the fine points of his position.

Since I won't be there, I have included my own vote at the end.  I have
also included what I believe to be RPG's position, since he has made his
views known repeatedly.  I'm not sure exactly where the rest of you
stand at present.

Many small things had to be changed to make this a two-option proposal,
so it is probably best for you to consider this a new proposal and read
it over carefully.  The major substantive change is in point 3 (now in
two distinct versions).  There are also some changes in "cost of
conversion" -- see if you believe my argument that mechanical conversion
of old code to adhere to the strict form of the proposal is possible
and that the result is not significantly less efficient than building
the coercions into FUNCALL and APPLY.  Also, look over the discussion
section and see if I have seriously misrepresented anyone's views.

-- Scott
---------------------------------------------------------------------------

Status:         To be discussed at X3J13 meeting (?).  This is a
                tough but important issue that involves some fundamental
                trade-offs, so discussion by the whole X3J13 committee
                is called for.

Issue:          FUNCTION-TYPE
References:     functions (pg 32), types (pg 33), FUNCTIONP (pg 76),
                SYMBOL-FUNCTION (pg 90), APPLY (pg 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

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.

Two alternative proposals are presented here:

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.

No sub-types of FUNCTION are defined in Common Lisp, but implementations
are free to define subtypes of FUNCTION.  Examples might be
COMPILED-FUNCTION and INTERPRETED-FUNCTION.  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. 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 bogus 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".

Proposal FUNCTION-TYPE:COERCING-REDEFINITION

This is identical to FUNCTION-TYPE:STRICT-REDEFINITION except for
section 3:

3. The text descriptions of FUNCALL, APPLY, MAPCAR and other functions
in Common Lisp which take functional arguments are modified to state
they will accept (true) functions, symbols, or lists that represent
lambda-expressions.  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 current behavior of
Common Lisp; the descriptions must be changed to accommodate the new
definition of the FUNCTION data type.

RATIONALE:

Both proposals provide 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.

The STRICT-REDEFINITION proposal consistently uses the new, strict
definition of FUNCTION in all of the obvious places.

The COERCING-REDEFINITION proposal cleans up the definition of the
FUNCTION data type, but attempts to minimize the impact on existing code
by providing implicit coercions in FUNCALL and APPLY.  

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 either of these
proposals, however.

Adoption Cost:

For either proposal, the type predicates would have to be brought into
compliance, but that 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).

If STRICT-REDEFINE is adopted, 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.  It
also brings Common Lisp into closer alignment with Scheme.

CONVERSION COST:

The COERCING-REDEFINITION 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 would be a change in the operation of certain type
predicates.  Such cases should be relatively easy to find and fix.

The STRICT-REDEFINITION proposal would require some additional changes
to user code.  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.  One strategy for
automatic conversion is to replace every call to FUNCALL, APPLY, etc.
with a call to an equivalent function or macro that tests the functional
argument at runtime and coerces the argument to a true function if
necessary.  If implemented carefully, this should not cost significantly
more than doing a built-in coercion within FUNCALL and APPLY.

Users might also convert their code by running for a time in an
implementation that still does the coercion in FUNCALL and APPLY, but
that issues a warning message whenever the coercion is actually needed.
This will flag all of the non-portable situations in parts of the
program that have actually been executed during the test period.

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 (MACSYMA is one example) depends on this behavior and would
have to be modified if either of these proposals is adopted.  However,
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.

Under either proposal, 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.

The STRICT-REDEFINITION proposal is perceived by most members of the
cleanup committee as the simpler and cleaner of the two proposals.  The
COERCING-REDEFINITION proposal adds some complexity in the name of
compatibility.

DISCUSSION:

This has been discussed at great length within the cleanup committee.
All of us agree that the definition of the FUNCTION data type must be
revised, but there is no clear consensus on what to do about the
coercions.  Since the cleanup of the type hierarchy is important to the
CLOS group, there is some urgency to this part of the proposal, at
least.

Some committee members (Gabriel and Fahlman) have argued that the strict
form of the proposal is preferable because it is simpler: it defines a
FUNCTION data type and then requires every object used as a function to
be a FUNCTION.  The strict proposal requires a somewhat greater
conversion effort for user code, but it seems better to make this effort
once than to live forever with runtime coercion of functional arguments
and the resulting complexity.

Members of the Eulisp group have argued strongly for what amounts to the
STRICT-REDEFINITION proposal.  They feel that this would remove one
important difference between their view of Lisp (similar to Scheme in
this instance) and ours.

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

Several members of the committee argued in favor of presenting both
proposals to X3J13, since the tradeoff between simplicity and conversion
effort must be discussed by the whole community.

White suggested that if the coercing version of the proposal is
adopted, we might need an APPLICABLE-P predicate that is true of any
object that is legal as a functional argument to APPLY and FUNCALL.
FUNCTIONP will not do this job.

Pitman has argued that items 4 and 5 (either proposal) will break a lot
of code that depends on being able to use lambda expressions and symbols
as function definitions, and that it will be hard to fix such problems.
He may produce a third proposal before the X3J13 meeting that deals with
these problems.  He has suggested that we may wish to settle the type
redefinition issues (points 1 and 2 above) now, while deferring a
decision on the more controversial coercion issues.

Fahlman feels that the issues are now clearly drawn and that we should
go ahead and make a decision on the whole package.

Clinger has suggested that the strict form is preferable because 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, but implicit function coercions tends to create loopholes
through which *every* function might be called.

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.

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