munificent
commented
3 years ago This is so good. Thank you!
I am 100% with you that various tagging and packing schemes (heh) have been around since the earlist Lisp days. But the aside is about NaN boxing specifically as a mechanism for storing a type tag and other data inside an unboxed IEEE 754 floating point number. It's that technique whose origin I wasn't able to find. As far as I can tell, the floating point representation on the IBM 704 has no notion of NaNs and IEEE 754 didn't come out until the 80s.
I'm not sure if there's any place in the book to capture this write-up, but I certainly really enjoyed reading it. :)
texdraft
Chapter 30 discusses “NaN boxing” as an optimization, and there is an aside mentioning how the source of this kind of technique is obscure.
The first use was in the original Lisp implementation at MIT in the early 1960s. The IBM 704 and its descendants had thirty-six-bit words and a fifteen-bit address space. Thus two pointers could fit in one word with five bits left over. Cons cells were represented by storing the car and cdr in a single word; certain machine instructions made linked list operations easy. For obscure historical reasons that are irrelevant to the current topic, the first pointer (known as the decrement) occupied bits 3 to 17, and the second pointer (known as the address) occupied bits 21 to 35. The bits in a word were numbered from 0 to 35, except that bit 0 was called bit S because it functioned as a sign. (The terms “address” and “decrement” give us the “a” and the “d” in car and cdr. It might be surprising, however, that the decrement part precedes the address part in a word.)
Representations of atoms (i.e., things that weren't lists) were distinguished from conses by setting the address part of a word to octal 77777, which is −1 in fifteen-bit two's complement. Originally, the only kind of atom was the symbol; the decrement part of a symbol's representation was a pointer to the symbol's property list.
When support for arithmetic was added to Lisp, the implementors needed a way to tell numbers and symbols apart; furthermore, they had to be able to deal with both fixed-point values and floating-point values. The three bits between the address and decrement parts was known as the “tag” (in machine instructions these bits were used to specify indexing), and they were 0 for symbols. In the end, it was decided to set the tag to 1 or 5 for fixed-point numbers (“fixnums”) and to 2 for floating-point numbers. The decrement of number representations held a pointer to the numbers value. An extra indirection was therefore needed to unbox a number, giving rise to Lisp's reputation as a language with slow arithmetic. (Things were made even worse by the fact that boxing a number required calling
cons!)It wasn't until Maclisp in the 1970s that Lisp got fast arithmetic. Documents regarding the method used for implementing it show the ridiculous things that were done to make Lisp numbers efficient. See for example Guy Steele's “Fast arithmetic in Maclisp” and Bernard S. Greenburg's “The Multics MACLISP compiler: The basic hackery”. The SBCL Common Lisp compiler gets up to the same tricks (with a bit more sophistication and many more tags).
Here are my sources for this.
The LISP 1.5 listing is particularly interesting because it shows exactly how things worked. See the
NUMVALroutine for details.Numeric representation is explained very, very succinctly in section 7.3 of the LISP 1.5 Programmer's Manual. See also a blog post discussing this topic in greater detail.