Issue CONSTANTP-DEFINITION Writeup

Issue:            CONSTANTP-DEFINITION

References:       CONSTANTP (p324)

Related issues:   CONSTANTP-ENVIRONMENT

                  SYMBOL-MACROS-AND-PROCLAIMED-SPECIALS

Category:         CLARIFICATION/CHANGE

Edit history:     v1, 07 Mar 1991, Sandra Loosemore

		  v2, 12 Mar 1991, Kent Pitman

                  v3, 14 Mar 1991, Sandra Loosemore


Problem description:


  The specification of CONSTANTP in CLtL says:


    CONSTANTP object       [Function]


    If the predicate CONSTANTP is true of an object, then that object,

    when considered as a form to be evaluated, always evaluates to the

    same thing; it is a constant.  This includes self-evaluating objects

    such as numbers, characters, strings, bit-vectors and keywords,

    as well as constant symbols declared by DEFCONSTANT, such as

    NIL, T, and PI.  In addition, a list whose car is QUOTE, such as

    (QUOTE FOO), is considered to be constant.


    If CONSTANTP is false of an object, then that object, considered

    as a form, might or might not always evaluate to the same thing.


  Some have interpreted this definition to mean what the first sentence

  says, with the rest of the definition being merely an elaboration.


  Others have interpreted that the definition seeks to identify a 

  specific set of things which are considered to be constants for the

  purpose of this function, namely

   * a self-evaluating object

   * a symbol naming a defined constant (built-in or declared by DEFCONSTANT)

   * a list whose car is the symbol QUOTE


  Most implementors have implemented tests only for these specific items

  although there is little first-hand evidence about whether this was

  because they felt restricted from implementing other cases or whether

  they just didn't have the ambition to think up or implement additional

  cases.  At least one implementor has implemented a small number of 

  additional cases.


  Some users have assumed that this was an exhaustive list of the

  situations for which CONSTANTP must return true, and have written code

  which purports to depend on that fact.


  Some users have assumed that this was not an exhaustive list of the

  situations for which CONSTANTP must return true, and have written code

  which would perform better if other kinds of constant forms were 

  detectable as well.


  Of the two authors of this proposal, neither Pitman nor Loosemore

  believes there is an ambiguity, but their opinions diverge.  And since

  users and implementors have in good faith interpreted this wording

  differently, then by definition there must be an ambiguity.


Terminology:


  For the purposes of this discussion, a `simple constant form' will

  be defined as the union of these three items:

   * a self-evaluating object

   * a symbol naming a defined constant (built-in or declared by DEFCONSTANT)

   * a list whose car is the symbol QUOTE


Background:

  

  The description of CONSTANTP in the draft standard (version 8.81) 

  contained a bug because it did not acknowledge that (QUOTE xxx) would

  reliably be detected as a constant by CONSTANTP.  The amended text of

  the definition, which is the current definition in the draft 

  specification at the time this proposal is written, says:


    CONSTANTP object			[Function]


    Returns <true> if its argument can be determined by the

    <implementation> to be a <constant form>; otherwise, 

    it returns <false>.


    The following items are considered constant forms:


    * <constant objects> (such as <numbers>, <characters>, and

      the various kinds of <arrays>) are always considered

      <constant forms>.


    * <constant variables>, such as <keywords>, symbols defined

      by Common Lisp as constant (such as NIL, T, and PI),

      and symbols defined by the user as constant using DEFCONSTANT

      are always considered <constant forms>.


    * QUOTE <forms> are considered <constant forms>.


    * an <implementation> is permitted to, but not required to,

      detect additional <constant forms>.  Examples of such forms

      that might be detected are: (SQRT PI), (+ 3 2),

      (LENGTH '(A B C)), and (LET ((X 7)) (ZEROP X)).


  The glossary definition of <constant form> says:


    constant form  n.  any <form> for which <evaluation> 

      always <yields> the same <value> and which neither

      affects nor is affected by the <environment> in which 

      it is <evaluated>.


  [Loosemore has criticized this definition as being overly vague on the

   issue of whether a <constant form> may affect or be affected by

   the objects accessible in that environment.  Pitman says this is

   just an oversight.]


  At issue is both whether these descriptions accurately capture the

  intent of CLtL, and whether even if they do, the definition should

  be amended.



Proposal (CONSTANTP-DEFINITION:EXACT):


  Clarify that CONSTANTP returns true if and only if its argument is

  a `simple constant form' (see definition above).


  Rationale:


    CONSTANTP is typically used to implement some simple kinds of

    code motion optimizations and side-effects analysis, for example

    in computing the expansion of a macro or compiler-macro.  Permitting

    CONSTANTP to return false for the three situations listed would

    inhibit these kinds of optimizations in the obvious situations

    where they were intended to be applied.  Permitting CONSTANTP to 

    return true in other situations could cause these applications to

    perform semantically invalid "optimizations".  


    There is also a compatibility problem if CONSTANTP is permitted to

    be sensitive to the lexical environment in which the form appears 

    (see the cost to users section below).



Proposal (CONSTANTP-DEFINITION:INTENTIONAL):


  1. Clarify that if the predicate CONSTANTP is true of an object, 

     then that object, when considered as a form to be evaluated, 

     is a <constant form>.


  2. Clarify that if CONSTANTP is false of an object, then that

     object, considered as a form, might or might not be a

     <constant form>.


  3. a. Clarify that the other text in CLtL's definition of CONSTANTP 

	is intended only as examples and to outline a minimal level

	of expectation for users.  Explicitly permit implementations 

	of CONSTANTP to return true for additional situations not listed

	among those examples, but which satisfy (1).


     b. Clarify that among the actions which an implementation is 

        permitted to take is to macro expand and to do function 

        inlining, but not to do expansion of compiler macros.


  4. a. Clarify that execution of a <constant form> neither affects nor 

        is affected by the run-time environment, except that it is 

        sensitive to the presence of DEFCONSTANT.


     b. Clarify that execution of a <constant form> neither affects nor 

        is affected by either the state of any object except those objects 

        which are otherwise inaccessible parts of objects created by the 

        form itself.


     That is, a form for which CONSTANTP previously returned NIL 

     might at some point return T, but not vice versa.


  Rationale:


    Paragraphs (1) and (2) of this proposal are taken word-for-word

    from CLtL (with the appropriate substitution to the new glossary

    term) and Pitman thinks they speak for themselves.



Proposal (CONSTANTP-DEFINITION:ADD-ARGUMENT):


  Add an optional SIMPLE-P argument to CONSTANTP, which defaults to T.

  [Any effect of issue CONSTANT-ENVIRONMENT is assumed to precede the

   effect of this issue, so unless the ENVIRONMENT argument proposed 

   by that issue would precede the SIMPLE-P argument proposed here.]


  Define that if the SIMPLE-P argument is true, CONSTANTP 

  behaves according to proposal EXACT, and that otherwise 

  it behaves according to proposal INTENTIONAL.


  Rationale:


    This permits CONSTANTP to satisfy both needs, and allows programmers

    to make their intent clear.



Proposal (CONSTANTP-DEFINITION:RENAME):


  Rename CONSTANTP to SIMPLE-CONSTANT-FORM-P.


  Clarify that SIMPLE-CONSTANT-FORM-P returns true if and only if its argument

  is one of the three kinds of things listed in the problem description.


  Rationale:


    This doesn't preclude an extension named CONSTANTP which does

    more work to recognize other kinds of constant forms.



Proposal (CONSTANTP-DEFINITION:EXTEND-SLIGHTLY):


  Extend the definition of `simple constant form' to include a fourth case:

    (VALUES x1 x2 ... xN)

  where every xI is a `simple constant form.'


Test Cases:


  These cases are not evaluable forms, but rather objects that are

  offered as arguments to the indicated functionality:


  #1:  37


       True under all proposals.  This is self-evaluating and hence

       a `simple constant form'.


  #2:  PI


       True under all proposals.  This is the name of a defined constant

       and hence a `simple constant form'.


  #3:  'FOO


       True under all proposals.  This is a QUOTE form and hence a 

       `simple constant form.'


  #4:  (VALUES 37 PI 'FOO)


       True under proposals EXACT, INTENTIONAL, ADD-ARGUMENT, and RENAME

       iff proposal EXTEND-SLIGHTLY is also adopted.  Otherwise, false.


  #5:  (PROGN NIL)


       Might be either true or false under proposal INTENTIONAL, or under

       proposal ADD-ARGUMENT when the SIMPLE-P argument is true.  Otherwise,

       must return false.


  #6:  ;after a non-macro/non-inline DEFUN of START-WW-III

       (PROGN (START-WW-III) NIL) 


       False under all proposals.


  #7:  (SQRT PI)


       Might be either true or false under proposal INTENTIONAL, or under

       proposal ADD-ARGUMENT when the SIMPLE-P argument is true.  Otherwise,

       must return false.


  #7:  (LET ((X 7)) (ZEROP X))


       Might be either true or false under proposal INTENTIONAL, or under

       proposal ADD-ARGUMENT when the SIMPLE-P argument is true.  Otherwise,

       must return false.


  #8:  ;after (DEFMACRO FOO () 37)

       (FOO) 


       Might be either true or false under proposal INTENTIONAL, or under

       proposal ADD-ARGUMENT when the SIMPLE-P argument is true.  Otherwise,

       must return false.


  #9:  ;in (SYMBOL-MACROLET ((FOO MOST-POSITIVE-FIXNUM)) ...)

       FOO


       Might be either true or false under proposal INTENTIONAL, or under

       proposal ADD-ARGUMENT when the SIMPLE-P argument is true.  Otherwise,

       must return false.


 #10:  (LET ((X (CONS 'X 'Y))) (CDR (RPLACA X 'Z)))


       Might be either true or false under proposal INTENTIONAL, or under

       proposal ADD-ARGUMENT when the SIMPLE-P argument is true.  Otherwise,

       must return false.



Current Practice:


  Utah Common Lisp, KCL, CMU Common Lisp, Chestnut's Lisp-to-C

  translator, and IIM all implement proposal EXACT (and proposal

  INTENTIONAL, since it is compatible).


  Symbolics Genera implements proposal EXACT+EXTEND-SLIGHTLY

  (and proposal INTENTIONAL, since it is compatible), except

  that (CONSTANTP ''(#,X)) returns NIL.  The implementors indicate

  that the intent was to implemention INTENTIONAL and that so far

  they've just been busy with other things.


  From empirical observation, it appears that Lucid and Allegro also

  implement proposal EXACT (and proposal INTENTIONAL, since it is

  compatible).



Cost to Implementors:


  Very small.  Here's a portable definition of CONSTANTP that

  conforms with proposal RENAME:


  (defun simple-constant-form-p (x &optional env)

    (cond ((symbolp x) (eq (variable-information x env) :constant))

          ((consp x) (eq (car x) 'quote))

          (t t)))


  Proposal EXTEND-SLIGHTLY modifies that definition in this way:


  (defun simple-constant-form-p (x &optional env)

    (cond ((symbolp x) (eq (variable-information x env) :constant))

          ((consp x) (or (eq (car x) 'quote)

			 (and (eq (car x) 'values)

			      (every #'simple-constant-form-p (cdr x)))))

          (t t)))



Cost to Users:


  If there are user programs that depend on CONSTANTP recognizing 

  either more than just `simple constant forms' OR only

  `simple constant forms' they're already nonportable.

  

  The portable uses of CONSTANTP currently include those which depend

  on it returning true for `simple constant forms' but which are not

  hurt by it returning true for other kinds of constant forms.


  Many applications that now use CONSTANTP assume that the value it returns

  is not sensitive to the lexical environment in which the form appears.

  (Since CONSTANTP has not previously been specified to accept an 

  environment argument, it is hard to see how any other interpretation

  could be made.)  Proposals INTENTIONAL and ADD-ARGUMENT represent an 

  incompatible change in this respect.  All calls to CONSTANTP within 

  user programs would have to be examined to see whether an environment 

  argument must be passed.  This also requires that something other than 

  EVAL (like FUNCALL of ENCLOSE) be used to compute the value of something 

  that is CONSTANTP.



Cost of non-adoption:


  Users will be confused about what to expect.

  Implementors will be confused about what to implement.

  The editor will be frustrated by the mess that must be documented.


  

Performance impact:


  For the typical program, the performance impact is not major.


  However, it is conceivable that there are cases where recognizing only

  `simple constant forms' could have a substantial performance penalty

  on certain otherwise-portable uses of DEFINE-COMPILER-MACRO which tried

  to base decisions about whether code-motion was appropriate on the return

  value of this function, and which found that such code motion was 

  inhibited by this function being required to return NIL for constant

  forms that were not simple constant forms but that the implementation 

  would have been capable of recognizing as constant. e.g., consider

  the following hypothetical example (which doesn't use &environment

  only because the status of an environment argument to CONSTANTP is still

  a pending issue).


  (defun foo (&key x y) (foo-positional x y))


  (define-compiler-macro foo (&whole form &rest key-value-pairs)

    (cond ((= (length key-value-pairs) 4)

	   (cond ((and (eq (nth 0 key-value-pairs) :x)

		       (eq (nth 2 key-value-pairs) :y))

                  `(foo-positional ,(nth 1 key-value-pairs)

				   ,(nth 3 key-value-pairs)))

		 ((and (eq (nth 0 key-value-pairs) :y)

		       (eq (nth 2 key-value-pairs) :x)

		       (or (constantp (nth 1 key-value-pairs))

			   (constantp (nth 3 key-value-pairs))))

		  `(foo-positional ,(nth 3 key-value-pairs)

				   ,(nth 1 key-value-pairs)))

		 (t form)))

	  ...))



Benefits:


  The cost of non-adoption is avoided: everyone can finally know

  what this function can be depended upon to do.



Esthetics:


  Having a well-defined CONSTANTP function is better than having

  a vague CONSTANTP function.



Discussion:


  Loosemore wrote and supports option EXACT.


  Pitman believes that the consensus among the Symbolics developers

  is for proposal INTENTIONAL.  Regardless of the outcome of the four

  `main' proposals, Symbolics would prefer to see option EXTEND-SLIGHTLY

  passed.


  Loosemore notes:


    There is a danger with this issue in trying to make CONSTANTP into

    something over-complicated and over-featurized.  I don't think that

    the original purpose of this function was to do anything more than

    perform some quick tests to detect the "obvious" situations, and

    trying to extend it into some kind of more sophisticated code-walking

    program analysis tool is likely to break more applications than it

    would help.


  In response to Pitman's urging for more leeway for CONSTANTP to

  return true, JonL notes:


    Years ago, I suggested a function CONSTANT-EXPRESSION-P which would be

    modeled after the similar term in Interlisp; it would try to do the

    more complicated-albeit-heuristic processing to notice forms like

    (+ 3 (- 9 <symbolic-constant>)).  Didn't get a lot of interest then.

    Although I think your last example [test case item #10] strains

    even our best SSC's, I would still say "Keep it up!"


  Barrett raised the issue about expansion of compiler-macros under

  proposal INTENTIONAL.  Pitman replied:


    Sandra talked about the issue of needless extra hair, and I guess this

    is where I draw the line.  The semantics of the form are fully

    specified without compiler macros, and I'd like to keep compiler

    macros packaged away in a corner without having them clutter every

    single operator.  So it seemed simplest to just say they don't get

    used by CONSTANTP.