Issue: FUNCTION-TYPE (version 10)

[masinter.pa@Xerox.COM]

Here is my attempt to rewrite FUNCTION-TYPE as per the discussion at the March X3J13 meeting. I added a comment at the end.

!
Issue:        FUNCTION-TYPE
References:   functions (p32), types (p33), FUNCTIONP (p76),
              SYMBOL-FUNCTION (p90), APPLY (p107), COERCE (pp51-52)
Category:     CHANGE
Edit History: 26-Feb-87, Version 1 by Gabriel
              15-Mar-87, Version 2 by Cleanup Committee
              10-May-87, Version 3 by Fahlman
              29-May-87, Version 4 by Masinter (incorporate comments)
              15-Jun-87, Version 5 by Fahlman (include two options)
              23-Oct-87, Version 6 by Masinter (only STRICT-REDEFINITION)
              09-Nov-87, Version 7 by Masinter (minor cleanup)
              14-Nov-87, Version 8 by Pitman (major restructuring)
              13-Feb-88, Version 9 by Masinter, (add back 2nd option)
              19-May-88, Version 10 by Masinter, (modify as per X3J13)


Problem Description:

 The definition of the term ``function'' in CLtL includes all symbols and
 many lists in addition to `true' functions.

 Also, page 47 of CLtL states 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, but since this intent was not explicitly stated, the status
 of FUNCTION as a type is blurred. 

 A consequence of the p47 confusion is that (FUNCTIONP x) cannot portably
 be relied upon to be equivalent to (TYPEP x 'FUNCTION).

Proposal FUNCTION-TYPE:X3J13-MARCH-88

This proposal is basically the STRICT-REDEFINITION proposal of version 9
of this issue, with a few typos corrected and changes to section 2E as
agreed upon at X3J13, March 1988.

 1.  Redefine the type FUNCTION so that it can be used for discrimination
     as well as declaration.

    1a. 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.

    1b. Define that the type COMPILED-FUNCTION is a subtype of FUNCTION.
        Implementations are free to define other subtypes of FUNCTION.

 2. Define that a ``function'' as used throughout the CLtL is restricted
    to be exactly those objects of type FUNCTION.

    2a. This type no longer includes objects of type SYMBOL or lists
        with CAR = LAMBDA.

    2b. The behavior of FUNCTIONP is defined to be exactly equivalent to
        #'(LAMBDA (X) (TYPEP X 'FUNCTION)).  This is an incompatible
        change.

    2c. Clarify that the list form of the FUNCTION type specifier may
        still only be used for declaration.

    2d. Clarify that the symbol form of the FUNCTION type specifier may
        be used for type discrimination.

    2e. Clarify that, under this definition of the FUNCTION type,
        the functions FUNCALL and APPLY, and, by extension, any
	  function that takes a "functional" argument, will accept
        any object that can be coerced to a FUNCTION, including
        objects of type FUNCTION, symbols, and lists that begin
        with lambda. (This is a clarification because it is a 
        restatement of the current meaning of CLtL using the new
        terminology.)

 3. Clarify that the result of a FUNCTION special form must be a function.

    3a. This implies that some (FUNCTION name) may be implicitly interpreted
	  as (THE FUNCTION (FUNCTION name)). 

 4. Clarify that 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.
    
    4a. Some implementations may choose not to signal this error for
        performance reasons, but implementations are forbidden from
        defining the failure to signal an error as a `useful' behavior.

 5. Clarify that it is permissible for FBOUNDP to return true for a macro
    or special form, and that it is permissible to call SYMBOL-FUNCTION
    on any symbol for which FBOUNDP returns true.

    5a. The value returned by SYMBOL-FUNCTION when FBOUNDP returns true
        but the symbol denotes a macro or special form is not well-defined,
        but SYMBOL-FUNCTION will not signal an error. 

    5b. Assuming that symbol is fbound,
	(FUNCTIONP (SYMBOL-FUNCTION symbol))
	implies
	(AND (NOT (MACRO-FUNCTION symbol))
	     (NOT (SPECIAL-FORM-P symbol))).

    5c. The effect of
        (SETF (SYMBOL-FUNCTION symbol) non-procedure)
	is not defined. Implementations are permitted to signal an error.

    5d.  The motivation for this distinction between FUNCTION and 
	SYMBOL-FUNCTION is that FUNCTION is intended for day-to-day
	use within programs while SYMBOL-FUNCTION is a data structure
	accessor used primarily for meta-level applications and not
	recommended for general use. It is provided primarily to
	complete the set of accessors on symbols.


 6. COERCE is extended to allow objects to be coerced to type FUNCTION.

    6a. (COERCE symbol 'FUNCTION) extracts the symbol-function of the
        given symbol, signalling an error if SYMBOL is not fbound or if
	the contents of the symbol-function cell is not a procedure.

    6b. (COERCE lambda-expression 'FUNCTION) is equivalent to
        (EVAL `(FUNCTION ,lambda-expression)).

 7. Clarify that the value of *MACROEXPAND-HOOK* is first coerced to a
    function before being called as the
    expansion interface hook by MACROEXPAND-1.

Rationale:

 The fuzzy definition of ``function'' has descended from older dialects of
 Lisp, such as Maclisp. Many places in existing code make assumptions about
 the current meaning, making any change painful.

 It is very important both for documentation clarity and for program type
 discrimination (such as CLOS) to have a clear term which denotes a 
 ``true function.''

 This proposal is a compromise between a CONSERVATIVE proposal (which left
 FUNCTION alone and introduced a new type), and STRICT-REDEFINITION proposal,
 which incompatibility changed not only the FUNCTION type and SYMBOL-FUNCTION,
 but also the behavior of FUNCALL, APPLY and functions with functional arguments.

Current Practice:

 In some implementations, (TYPEP x 'FUNCTION) signals an error.
 In some implementations, (TYPEP x 'FUNCTION) is true for values
   returned by FUNCTION, symbols that are FBOUNDP, and lambda expressions. 
 In some implementations, (TYPEP x 'FUNCTION) is true only for values
   returned by FUNCTION.

 Implementations vary on what my go into the function cell, depending on
 how much error checking they want to have to do at function call time, and
 depending on whether they store other kinds of information (such as special
 form information) in the function cell.

 Few current Common Lisp implementations have exactly the
 semantics described in this proposal.

Cost to Implementors:

 Bringing type predicates (FUNCTIONP, etc.) and higher order functions
 (APPLY, etc.) into compliance should require little effort in most
 implementations.

 Compiled functions are true functions in almost all current
 implementations, but in many implementations, interpreted functions and
 closures stored in the function cell of a symbol are represented as lists.
 Under this proposal, this representation would have to be different
 (implemented either as 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 reconstructed if necessary).

Cost to Users:

 The changes to FUNCTIONP and the FUNCTION type declaration are relatively easy
 to deal with. 

 Because CLtL's language was somewhat fuzzy about what might go into the
 function cell of a symbol, some code that explicitly deposited symbols
 or lists in a symbol's function cell, or expected lists back, will
 have to change. Such code was already not portable, however, since some
 implementations signal an error  when this is done.

Benefits:

 The term ``function'' would be given a useful and precise meaning.
 The FUNCTION datatype would be useful for type discrimination in CLOS.

 The type hierarchy would be simplified.

This proposal brings Common Lisp slightly closer to Scheme and
the work of the EuLisp committee. Scheme, for example, also has the concept
of a ``procedure'' which is compatible with the FUNCTION type.


Aesthetics:

 This proposal improves the aesthetics of the language.


Discussion:

This issue 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 clarified or revised. The cleanup of the type hierarchy is important
to the CLOS group.

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".  We believe this is a subject for a separate
proposal, as the behavior of COMPILE needs additional clarification.

Many different alternatives have been discussed both in the cleanup committee
and X3J13. Two proposals were circulated at the March 1988 meeting of X3J13;
this version is the result of discussions at that meeting. It is a compromise
between the conflicting goals of backward compatibility, flexibility in the
language, and simple semantics.
 
This proposal does not address the issue of when coercion to functions occur.
For example, it is allowed to write

(MAPCAR 'FROB my-list)

It is not specified when the coercion of FROB to its SYMBOL-FUNCTION 
occurs. For example, 

(DEFUN FROB (X) 
   (WHEN (> X 0) (SETF (SYMBOL-FUNCTION 'FROB) #'(LAMBDA (X) NIL)))
   T)

(MAPCAR 'FROB '(-1 -1 1 1))

may return different results if MAPCAR coerces its functional argument
once rather than for each element. This may require a separate
cleanup issue.