Administered by:
#programming #lowLevel #lisp #commonLisp #article #medium
I wrote a short description of how lisp is coded by writing lisp sequences (lists), and the low level dotted cons view of the lists.
I wrote a funny piece of lisp that outputs a lower triangular emacs orgmode matrix depiction of a lisp form.
https://medium.com/@screwlisp/lisp-code-in-dotted-conses-7b8e53486742
Which leaves me wondering, does anyone "use" or otherwise think about (a . (b . NIL)) the dotted cons way of writing lists while programming?
@screwtape I only know of one: the dotted conses make for a natural representation of a pair on an association list.
But even so, it doesn't have to be a dotted cons. It can be a two-element list.
IIRC, somebody who invented Lisp has been heard saying that if he had known, he would have required all lists to be proper lists, ending in NIL, and neither dotted nor circular.
@riley @dougmerritt
Yeah,
(let ((alist '((:foo . bar) (:baz buz))))
(cdr (assoc :foo alist)) ; -> bar
(cadr (assoc :baz alist))) ; -> buz
There isn't a lot of cost (well, one cons to nil) of using cadr or second instead of cdr. And then you could store other stuff in later positions of the list as well. When I only knew the definitions of assoc and pairlis, I mostly used cdr, but then in lisp code I've read, like you said, the cadr one seems more common in lots of places.
= 
log
) @screwtape @riley
As a historical note:
> There isn't a lot of cost (well, one cons to nil)
Back in the days when RAM was measured in kilobytes / kilowords, some implementations did in fact have space-optimized representations for short lists represented as small arrays.
See cdr-coding
https://en.wikipedia.org/wiki/CDR_coding
That might still be in some implementations today, since its savings might be significant in large structures or in aiding cache locality.
The first paper may well have been L. Peter Deutsch: A LISP Machine with Very Compact Programs. IJCAI 1973, Pages 697 - 703
This is covered in 7.13 in the classic "Anatomy of Lisp", John Allen (1937-2022), 1978 (long out of print, and the author once replied to my query saying he didn't think it was worthwhile updating it for more modern times).
Has a lot on implemention, but tends to talk about abstractions in terms of M-Expressions, which is no longer in style.
ACM has it online:
https://dl.acm.org/doi/pdf/10.5555/542865
Glowing review of "Anatomy" on goodreads: https://www.goodreads.com/book/show/1537412.Anatomy_of_LISP
"John Allen (1937-2022) and Anatomy of LISP" by Paul McJones
https://mcjones.org/dustydecks/archives/2024/04/11/1249/
@dougmerritt CDR coding was only really used on the Lisp Machine, which did not have kb of memory .. but rather megabytes. It also didn't save much, while lists are useful, for large sets of data there are better representations.
@screwtape @riley@toot.cat
@amszmidt
Doug linked John Allen's book which spends about 50 pages asking people to please not use car and cdr as though they were intended as general list manipulation tools, even though they might be literally implemented as first and rest, since it's a failure of abstraction or something.
@screwtape I'll disagree with John Allen. Strongly. CAR/CDR are great abstractions on CONS cells.
@amszmidt @screwtape I still use cadr, cdar, cddar, etc. frequently when writing ad-hoc code to grovel through data; those would be cumbersome (to say the least) if they needed to be compositions of first and rest. I have also used cdr-coded lists, not only for space savings but to be able to refer to array data as a list (c.f. g-l-p) and to (in separate circumstances) interpolate less structured traditional cons list structure in the middle of compactly stored lists.
Both these practices fall in the category of "infrequently applicable but very useful when they do apply". I find that this category as a whole seems to be diminishing. When I try to explain this category to colleagues (usually in conjunction with explaining why I did something the way I'd chosen), they usually say that they'd never remember that it would apply.