#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 I might have garbled it, but he was talking about structured programming. So when the data structure being operated on is a cons cell, use car and cdr, and when the data structure being operated on is a list, use list functions like first and last (for example, but also consider something like subseq). I'm open to not necessarily agreeing with Allen's book (for undergraduates).
@simon_brooke
@screwtape FIRST/LAST .. make it confusing when working on improper lists. Which is why I disagree with Allen. CAR/CDR have very good names, and explain exactly what happens, similar with all the CnnnnR versions.
@amszmidt @screwtape Hah, this reminds me of this craziness from my early days:
First is first, last is a list of last.
When given the list ((10 (20 30 40) 50) 60 70)), output the first of the last of the first of the last of the first element, and name the accessor.
(The answer is 30, and CADADAR, but of course you all already knew that right away)
@ksaj This is a great example of why CnnnnR (and in turn CAR/CDR) work so well in Lisp.
@ksaj Compare to ...
(first (last (first (last (first ....)))))
Brain hurts from counting, and FLFLF .. doesn't sound as nice. Specially when you have a list structure where it is relatively common to access that specific element.
@amszmidt @screwtape I thought you'd like the example.
It was one of the first things I learned (and definitely not the easiest way to learn!). I don't use it very often, but when I need it, it is so much nicer to look at. It just confuses the hell out of people who don't understand, or ignore the List part of LISp.
Using CnnnnR accessors is awesome when coding something like a Sudoku solver, where you have to consider rows, blocks and columns.
@ksaj Absolutley, and _if_ the names don't fit, DEFSUBST!
@amszmidt @screwtape I'm not an emacs guy, so I'll take your word on that. 
@ksaj @screwtape Lisp Machine Lisp!
@amszmidt @screwtape Ah, much more cool than emacs.
Just kidding. I like to rile peeps up sometimes. 
@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.
@lispwizard @amszmidt @screwtape Want to drive a Lisper mad? Mix them.
(first (cadr (some-list)))
lol.
@ksaj @lispwizard @amszmidt @screwtape Why mad? If that's what it conceptually /is/ at each level, then this can be the obviously correct accessor combination.
@Ardubal @lispwizard @amszmidt @screwtape How about this, then:
(eval (read-from-string (format nil "(+ ~a ~a)" 1 2)))
@ksaj @lispwizard @amszmidt @screwtape
There should be Special Compiler Warnings from Hell for people who do this.
I mean, sure, compile their program. But not without some verbal abuse.
@weekend_editor @lispwizard @amszmidt @screwtape Instead of ending with a NIL, it could be a WTF.
@ksaj @lispwizard @amszmidt @screwtape
On the Symbolics system, the type tags were all encoded in the microcode source and recognized in the hardware (ok, really the microcode). The type tag names were constants whose names all began with "DTP-" (for "data type", probably).
There was a type calld DTP-NULL (see below, page 7, though I think that's for the Ivory chip).
It didn't *quite* mean WTF, but almost. :-)
(No, it was not used this way.)
https://bitsavers.org/pdf/symbolics/I_Machine/Lisp-Machine_Data_Types.pdf
@screwtape @ksaj @lispwizard @amszmidt
Oh, you have no idea!
That's the *toned down* version.
There was a certain species of paranoid manager, not terribly sophisticated technically, who didn't want it photocopied anywhere that used Xerox brand copy machines. They were *absolutely convinced* that everything that went in the front door to be copied also went out the back door to Xerox headquarters.
Sometimes ya gotta just shrug and say, "Ok, I'll keep it secret."
That document was issued in 1987, so after 38 years I think they can unclench a bit.
@weekend_editor Which is like on the CADR.
But I wouldn't call DTP-NULL a WTF typ, since it is used for unbound variables.
"Actually, a void binding contains a weird internal value, which the system interprets as meaning “there is no value here”. (This is the data type code dtp-null)." https://tumbleweed.nu/r/lm-3/uv/chinual.html#dtp_002dnull_002dvar
DTP-TRAP on the other hand ...
@screwtape
Etymology doesn't necessarily prove anything, but it *is* pretty weird that "CAR" was the mnemonic for "Contents of A Register" and "CDR" for "Contents of D Register" -- literal machine registers, not originally an abstraction at all.
BTW
> CDR coding was only really used on the Lisp Machine
That's 100% false.
@dougmerritt ok, instead of being a jerk .. where else was it used? @screwtape @ksaj
@dougmerritt CDR was one of those things which the LispM hackers wanted to flush on the LispM cause it was just a pain in the ass .. slow, the benefits of it was nil.
@dougmerritt @screwtape @amszmidt @riley Is this like when AX and DX referred to an Accumulator and a Data register? It would make sense, since RPN makes it fit that way.
(CX referring to a counter and EX for an "extra" register)
@ksaj @screwtape @amszmidt @riley
A little. The Accumulator register dates all the way back to the 4004; over time the 8008 then the 8080/8085 then the x86 registers became increasingly general purpose.
The A & D register meaning is retained somewhat more closely. Lisp was originally developed for the IBM 704, which had 15 bit "address fields" and 15 bit "decrement fields" in 36 bit words (plus 6 tag bits).
Something like that, anyway.
Extracting the "address field of register" and extracting the "decrement field of register" had pretty much the same meaning back then that CAR and CDR do today.
@dougmerritt Your timeline is so broken that I was hoping for a joke.
@riley
Which part? The 4004 did have an accumulator. Lisp was originally designed for the 704.
https://en.wikipedia.org/wiki/Intel_4004
https://en.wikipedia.org/wiki/Lisp_(programming_language)
I don't need two people to simultaneously give me shit.
@dougmerritt 4004 is far, far newer than the IBM 704. The concept of accumulators predates computers entirely — they flow naturally from the original Hollerith process for automatic card-counting. (And even so, some early computer theorists were un-fond of them, so there were attempts to make machines with instruction sets that wouldn't imply a user-visible accumulator register.)
Before registers got names in their own, the single letters that eventually become some registers' names were single letters in the mnemonic codes of instructions, something on the order of lai for Load Accumulator Indirect.
@infosec.exchange @screwtape @amszmidt
@riley
That's all true -- NOR DID I SAY ANY DIFFERENT.
@riley
You assumed bad faith and that I was saying that the concept of an accumulator was invented for the 4004.
But I didn't say that.
The context was someone else bringing up accumulators in the x86 family.
That's a very very large reading comprehension failure.
@dougmerritt You described 4004 as "all the way back" and then swiftly moved on to 704. 4004 is not "all the way back" from 704.
@riley
I've got an idea. Fuck you. Blocked.
@dougmerritt A for address, D for decrement. It wasn’t for A/D. Etymology is clear from the IBM 704. Now care to substantial the “100% false” wrt where CDR coding was used?
@screwtape @ksaj @riley@toot.cat