Issue: ALIST-NIL (Version 3)

[masinter.pa@Xerox.COM]

Ready for release? (Only reply if you have complaints, preferably with a new
version....)

I changed Kent's tentative description of 'remove or justify' in the discussion
into more like an endorsement.

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

Problem Description:

  NIL is permitted to be an element of an a-list but nothing useful
  can be done with such an element. This is confusing to users. 

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:

  No motivation in CLtL is given for NIL being allowed in an a-list.

  The description of a-lists seem needlessly complicated by this feature.

  FIND (with a :KEY of #'CAR) and ASSOC (with no key) are almost identical
  except for their treatment of this issue. If no one makes significant
  use of the feature, it would be better to be able to simplify the
  relationship between these functions.

Current Practice:

  All valid implementations allow NIL.

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 the author is able to guess this
  feature might be used:

  #1: A user might want a leading NIL on an a-list so that if the list
  were empty, there'd 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) ENTRY) ;Something 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.

Cost of Non-Adoption:

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

 Simplified documentation. May allow ASSOC to be faster if it is no 
 longer necessary to check explicitly for NIL.

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. 

 Putting a NIL in an alist as a way of removing the element might
 be simpler than putting some otherwise useless CONS, and allows
 for a quick (remove NIL  alist).

 Some people consider this change gratuitous.

 The cleanup committee discussed some interesting optimizations
 of ASSOC where this feature didn't cost in performance, at least
 in the special case where the predicate was EQ or EQL.