Embed Notice

@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/