[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Issue: FUNCTION-TYPE (version 9)



I've left the CONSERVATIVE proposal pretty much intact, and attempted to add back in the STRICT-REDEFINITION proposal as an alternative proposal with a shared cost/benefit analysis. 

We really owe X3J13 a version they can vote on, and I think that this is one issue that is big enough and thorny enough that we can ask for votes on more than one alternative. 


!

Issue:        FUNCTION-TYPE
References:   functions (p32), types (p33), FUNCTIONP (p76),
              SYMBOL-FUNCTION (p90), APPLY (p107), COERCE (pp51-52)
Category:     COMPATIBLE 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)

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:CONSERVATIVE

 1. Introduce a new type PROCEDURE that can be used both for declaration
    and discrimination.

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

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

    1c. Introduce a new function, PROCEDUREP, such that
	(PROCEDUREP x) == (TYPEP x 'PROCEDURE).

 2. Define that a ``function'' may be a procedure, a list whose car is
    the symbol LAMBDA, or any symbol (whether fbound or not).

    2a. Clarify that the FUNCTION type behaves as if it had been
        defined by:

         (DEFUN LAMBDA-P (X) (AND (NOT (ATOM X)) (EQ (CAR X) 'LAMBDA)))

         (DEFTYPE FUNCTION ()
	   `(OR SYMBOL (SATISFIES LAMBDA-P) PROCEDURE))

    2b. Clarify that (FUNCTIONP x) == (TYPEP x 'FUNCTION).
        This change is compatible.

    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 FUNCALL and APPLY continue to accept functions
        as arguments. However, some implementations may produce better
	code for expressions such as (FUNCALL (THE PROCEDURE ...) ...)
	or (APPLY (THE PROCEDURE ...) ...).

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

    3a. This implies that some (FUNCTION name) may be implicitly interpreted
	as (THE PROCEDURE (FUNCTION name)). As such, the potential
	optimizations mentioned in 2e are also possible for
	(FUNCALL (FUNCTION ...) ...) and (APPLY (FUNCTION ...) ...).

 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. Clarifythat 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,
	(PROCEDUREP (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,
	but they are also permitted to define useful (non-portable)
	interpretations.

    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.

	Implementations are permitted, but not required, to store
	information about a global macro-function or special form
	in the function cell. This definition of SYMBOL-FUNCTION
	is intended to leave enough freedom for such implementations
	to conveniently implement FUNCTION, SPECIAL-FORM-P, and
	MACRO-FUNCTION using SYMBOL-FUNCTION as the underlying
	subprimitive.

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

    6a. (COERCE symbol 'PROCEDURE) 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 'PROCEDURE) is equivalent to
        (EVAL `(FUNCTION ,lambda-expression)).

 7. Clarify *MACROEXPAND-HOOK* is permitted to contain any kind of function.
    The function is coerced to a procedure before being called as the
    expansion interface hook by MACROEXPAND-1.

!
Proposal FUNCTION-TYPE:STRICT-REDEFINITION

STRICT-REDEFINITION is similar to CONSERVATIVE, except that it redefines
the type FUNCTION instead of adding a new type PROCEDURE, and it restricts
coercion by functions that take functions as arguments. The numbering of
CONSERVATIVE is preserved for comparison.

 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 PROCEDURE 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. Change FUNCALL and APPLY such that they accept only a function
        as the functional argument.  This restriction is inherited by
        all functions in Common Lispthat take a functional argument. 
        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".

 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 procedure.

    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:

Since the two proposals are similar, they are discussed together. Where
motiviation and justification differ, the proposals are referred to by
name (STRICT-REDEFINITION, CONSERVATIVE.)

 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.''

 CONSERVATIVE manages a compatible definition with most existing uses of
 the term ``function'' while providing a graceful upgrade path to the term
 ``procedure'' for use in situations that call for a higher degree of clarity.

 STRICT-REDEFINITION avoids introducing a new term at the cost of
 incompatible change.

Current Practice:

 In some implementations, (TYPEP x 'FUNCTION) signals an error.
 In some implementations, (TYPEP x 'FUNCTION) is the same as (FUNCTIONP x).
 In some implementations, (TYPEP x 'FUNCTION) is the same as what this
  new proposal calls (TYPEP x 'PROCEDURE).

 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 are likely to have exactly the
 semantics described in either. CONSERVATIVE is more compatible with
 current practice than STRICT-REDEFINITION, however.

Cost to Implementors:

 Bringing type predicates (FUNCTIONP, etc.) and higher order functions
 (APPLY, etc.) into compliance should require little effort in most
 implementations. While STRICT-REDEFINITION makes it an error to pass
 non-function arguments to APPLY, FUNCALL etc, there is no requirement
 to check for that error.

 Compiled functions are true functions in almost all current
 implementations, but in some implementations interpreted functions and
 closures stored in the function cell of a symbol are represented as lists.
 Under this proposal, such lists would have to be changed to be procedures
 (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 conversion cost associated with CONSERVATIVE is very low because the
 model of FUNCTIONP which it takes is largely consistent with existing 
 practice.

 The new features introduced by CONSERVATIVE, particularly the PROCEDURE
 data type, can be converted to fairly lazily.

 The conversion cost for the STRICT-REDEFINITION proposal is higher. 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.  

 For either proposal:
 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 might have to change. Such code was 
 already not portable, however, since some implementations signal an error
 when this is done.


Benefits:

 For CONSERVATIVE:

   The term ``function'' would be given a useful meaning that was relatively
   compatible with existing usage.
   A new term ``procedure'' would be available for descriptional clarity.
   The new PROCEDURE datatype would be useful for type discrimination in CLOS.

 For STRICT-REDEFINITION:

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

 STRICT-REDEFINITION provides useful constraints which will be of aid to systems
 doing automatic program analysis for the purpose of ``selective linking.''
 Such tools may in turn make it possible to reduce the total size of a
 delivered application program because only those Common Lisp functions
 that are actually called need to be included.

 For either proposal:

   The type hierarchy would be simplified.

   Either proposal brings Common Lisp into closer alignment with Scheme and
   the work of the EuLisp committee. Scheme, for example, also has the concept
   of a ``procedure'' which is compatible with this proposal.

Aesthetics:

 Both proposals improve the aesthetics of the language.

Discussion:

 These proposals have 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. These two proposals are the distillation of the alternatives.
 
 The CONSERVATIVE proposal offers the advantage of backward compatibility,
 and considerably more flexibility in the language.

 The STRICT-REDEFINITION proposal offers the advantage of a slightly cleaner
 resulting language. 

 Some concerns were raised about STRICT-REDEFINITION in a previous discussion
 about "late binding" of function definitions. Neither proposal disallows
 late binding of symbols to functions. For example, in the call

  (MAPCAR #'FROB my-list)

  the effect of the FUNCTION special form (as generated by the #' read macro)
 is to obtain the function definition of FROB at the time the #'FROB is
 evaluated. Neither proposal changes this.

  Currently, it is allowed to write

  (MAPCAR 'FROB my-list)

 while this form would no longer be allowed under the STRICT-REDEFINITION
 clause. Currently, neither CLtL nor the CONSERVATIVE proposal addresses
 the question of the time at which FROB's function definition is obtained;
 if, during the processing of my-list, FROB is redefined, it is not clear
 whether the processing of subsequent elements would be changed.