Issue: ALIST-NIL (Version 3)

[Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>]

The discussion following this proposal showed that NIL did have more
purpose in an a-list than my "problem description" had suggested, yet
my biased writeup had persisted through three revisions. In spite of
the "good uses" people have suggested, I still support my proposal,
but I felt enough guilty that I rewrote the proposal to try to at
least remove my original bias and present the issue fairly.

-----
Issue:        ALIST-NIL
References:   Definition of "a-list" (p279), ASSOC (p280)
Category:     CHANGE
Edit history: 20-Jun-88, Version 1 by Pitman
              04-Sep-88, Version 2 by Masinter (reflect discussion)
              21-Sep-88, Version 3 by Masinter (minor edits)
	      01-Oct-88, Version 4 by Pitman (remove some bias)

Problem Description:

  NIL is permitted to be an element of an a-list but very little of
  use can be done with such an element, and the idea can be confusing.

  In most situations where an a-list entry is to be removed, it is
  done by straightfoward uses like
     (SETQ THE-ALIST (REMOVE THE-ENTRY THE-ALIST))
  or (SETQ THE-ALIST (DELETE THE-ENTRY THE-ALIST)).

  Relatively few situations require the more advanced technique of
     (SETF (CAR THE-ALIST-TAIL) NIL)
  in order to remove an entry from a list. Usually these situations
  involve multiple pointers into different parts of the same a-list,
  or very long a-lists where DELETE or REMOVE would take a long time.

Proposal ALIST-NIL:DISALLOW:

  Change the definition of an a-list to require all elements to be
  real conses. Uses of ASSOC with non-standard a-list would be an error.

Test Case:

  (ASSOC 'X '(NIL (X . 3)))
  is currently defined to return (X . 3).
  Under this proposal, this would be an error.

Rationale:

  An a-list is a commonly used data structure that should be easy to
  explain. Permitting NIL in an a-list complicates the description
  considerably.

  This change would make the relationship between FIND (with key of 
  #'CAR) and ASSOC simpler and easier to explain.

Current Practice:

  All valid implementations permit NIL in an a-list.

Cost to Implementors:

  Since the proposal is to make this an "is an error" situation, no
  implementation would be forced to change.

Cost to Users:

  There are two basic ways in which we expect this feature is used
  currently.

  #1: A user wants a leading NIL on an a-list so that if the list
      is empty, there's still be a tail to which cells could be
      attached in the future. That is,
       (DEFVAR *MY-ALIST* (CONS NIL '()))
      so that 
       ...(NCONC *MY-ALIST* (LIST new-cell))...
      would always be possible as a side-effect and
       ...(ASSOC element *MY-ALIST*)...
      would always be possible for lookup. It might be argued that
      this is more clearly written:
       (DEFVAR *MY-TABLE* (CONS NIL '()))
       (DEFUN ADD-ENTRY (ENTRY TABLE) (NCONC TABLE (LIST ENTRY)))
       (DEFMACRO MY-TABLE-CONTENTS (X) `(CDR ,X))
       ...(ADD-ENTRY new-cell *MY-TABLE*)...
       ...(ASSOC element (MY-TABLE-CONTENTS *MY-TABLE*))...

  #2: A user might want to splice out an element from an a-list, preserving
      the place that the element occupied in the list. In the very rare cases
      where this was necessary, one could rewrite:
       (DEFUN VOID-FIRST-ENTRY (ALIST) (SETF (CAR ALIST) NIL))
      as:
       (DEFUN VOID-FIRST-ENTRY (ALIST)
         (LET ((ENTRY (CONS NIL NIL)))
           (SETF (CAR ENTRY) (GENSYM)) ;or ENTRY or something otherwise unique
           (SETF (CAR ALIST) ENTRY)))
      This might change the behavior of ASSOC-IF, ASSOC-IF-NOT, RASSOC-IF
      and RASSOC-IF-NOT depending on the predicate used.
      Also, in this case, the user must also consider that whatever is used
      as the unique key must be acceptable to ASSOC.

  In rare cases where neither of these rewrites were acceptable, the user could
  still write his own variant of ASSOC to handle NIL even if the system version
  did not.

Cost of Non-Adoption:

  The only consequence of non-adoption is the burden of carrying around
  the additional complexity in each implementation, in the documentation,
  and in teaching. The cost of this burden is likely to be a subjective
  matter.

Benefits:

  FIND (with a :KEY of #'CAR) and ASSOC (with no key) would be identical.

Aesthetics:

  This change would simplify the language.

Discussion:

  The description of association lists is currently cluttered by this 
  unmotivated feature; no strong motivation or widespread use
  of the feature has been found. 

  Some people consider this change gratuitous.

  The cleanup committee discussed some interesting optimizations
  of ASSOC where the existing situation (special-casing NIL) didn't
  actually cost in performance (at least in the special case where
  the predicate was EQ or EQL), so performance issues were dismissed
  as a rationale for this change.