Issue: ALIST-NIL (Version 1)

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

Issue:        ALIST-NIL
References:   Definition of "a-list" (p279), ASSOC (p280)
Category:     CHANGE
Edit history: 20-Jun-88, Version 1 by Pitman
Status:	      For Internal Discussion

Problem Description:

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

Proposal (ε1issue-nameε0:ε1proposal-nameε0):

  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)))

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.

Aesthetics:

  This change would simplify the language.

Discussion:

  Pitman submitted this proposal after looking at the write-up of
  a-lists in the new standard. The description seems needlessly
  cluttered by this unmotivated and he felt that either a motivation
  for this feature should be cited and defended or the feature should
  go away. The degree to which he believes in this feature will be
  determined by any claims made by others in ensuing discussion.

  Some people might consider this change gratuitous.