libera/#commonlisp - IRC Chatlog
Search
8:25:10
beach
This page says ALIST is an association list. And the glossary says that an association list is a list of conses.
8:27:01
beach
It gives two almost equivalent expressions, but they are equivalent only if NIL is a member of the association list. But then, it is not an association list, now is it?
8:28:32
beach
If I were to implement ASSOC, I would take the wording in the "Exceptional situations:" section to mean that if I detect that I don't have a proper list, or if I detect that an element is not a CONS cell, then I would signal an error.
8:29:08
beach
And that I don't have to search beyond a matching element to find out whether it is really an association list.
8:31:51
beach
And the error message hints that SBCL considers an association list to be a list of elements of type LIST, rather than (as the glossary says) a list of elements of type CONS.
8:40:36
Equill
I don't like it either, but this appears to be a case of duck-typing: both `(listp nil)` and `(atom nil)` return `t`, so the crucial test in this case is whether an element is considered a list, rather than whether it's (possibly _also_) some other type.
8:43:10
beach
I take the situation to be a "don't fail unless you have to" one. But this attitude is out of fashion, and nowadays we prefer "help the programmer as much as possible".
8:45:10
Equill
It's the part where it's a list but not a cons, that conflicts with my assumption that lists are by definition made of conses. That means there's something I didn't properly understand.
8:45:54
beach
Well, the empty list is a list, and the empty list is the same as NIL, so NIL must be a list.
8:46:26
beach
You are right that lists are "made of conses", but there could be zero conses in a list.
8:46:48
mariari
Equill: in ML, lists are defined as CONS or NIL, thus if you had a CONSP function, it should answer false for NIL. The same view can be said for CL, modulo improper lists
8:48:13
mariari
beach: fair, I was implicitly typing the cdr to be a LIST, which improper lists lets us say end it with 5
8:48:49
Equill
Defining a list as *zero or more* conses resolves that issue. Thanks for that insight.
12:59:21
_death
beach: another alternative is to change the definition of alist.. presumably the notes section mentions nil entries as a reflection of historical use, where one would set some entries to nil as a way to delete entries from an alist without consing
13:03:47
_death
again I'm missing my lisp manuals, it'd be interesting to see whether such use is mentioned in one of them
13:08:37
beach
Page 431 in CLtL2: It is permissible to let NIL be an element of an a-list in place of a pair. Such an element is not considered to be a pair but is simply passed over when the a-list is searched by ASSOC.
13:09:16
beach
So my guess is that the standard did not allow this exception, and that SBCL did not change its implementation according to the standard.
13:19:42
_death
there's a related discussion in cl-su-ai http://cl-su-ai.lisp.se/msg04192.html (there's a reply by KMP)
13:23:13
pfdietz
It's not much of an efficiency hit to handle these nils. Just specialize the implementation of ASSOC to special case a nil key; in that case, there's an additional check you actually found a cons.
13:27:01
_death
pfdietz: there's a mirror argument to KMP's "so asking ASSOC to ignore atoms would mean putting an explicit atom check in the ASSOC inner loop, which might be very slow in some implementations." .. you could say the same for an implementation that explicitly checks for conses
13:28:50
pfdietz
I meant a nil key. If the key is not nil, you never have to check for nil alist elements, since (car nil) != the key.
13:30:23
pfdietz
Yes, it should. The nil key case would require checking if the alist element is not itself nil.
13:33:42
pfdietz
The error checking that the alist element must be of type LIST is handled automatically by CAR on modern implementations.
13:37:25
pfdietz
I wonder how trapping bad accesses can be made to work with very low overhead in the non-trapping case. You don't want to do something heavyweight to set up a handler for conditions.
13:39:04
_death
since car and cdr must have type-error signaling code, maybe implementation don't always choose to inline them