[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Issue: ALIST-NIL (Version 3)
- To: CL-Cleanup@SAIL.Stanford.EDU
- Subject: Issue: ALIST-NIL (Version 3)
- From: Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>
- Date: Sat, 1 Oct 88 20:07 EDT
- In-reply-to: <880921-013345-5657@Xerox>
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.
References: Definition of "a-list" (p279), ASSOC (p280)
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)
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.
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.
(ASSOC 'X '(NIL (X . 3)))
is currently defined to return (X . 3).
Under this proposal, this would be an error.
An a-list is a commonly used data structure that should be easy to
explain. Permitting NIL in an a-list complicates the description
This change would make the relationship between FIND (with key of
#'CAR) and ASSOC simpler and easier to explain.
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
#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 '()))
...(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))
(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
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
FIND (with a :KEY of #'CAR) and ASSOC (with no key) would be identical.
This change would simplify the language.
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.