11 ms·
A piece of more recent history that people might not know: the 32-bit SPARC chips had some special instructions for adding and subtracting integers, assuming a
by ScottBurson 9y ago
A piece of more recent history that people might not know: the 32-bit SPARC chips had some special instructions for adding and subtracting integers, assuming a representation in which the two low-order bits were used as tag bits, and a value of 00 in those bits indicated a fixnum (Lisp-speak for an immediate integer). The TADDCC instruction ("Tagged ADD and set Condition Codes") was just like ADD, except that it would also set the overflow condition code if either operand had a tag value other than 00 (it would also be set if the addition overflowed). The next instruction would call a handler if the overflow bit was set; the handler would determine whether (a) this was a case of actual integer overflow requiring construction of a "bignum" (a heap-allocated integer); (b) one or both operands were already heap-allocated integers (or perhaps other kinds of numbers) requiring some other form of addition; or (c) one or both operands were not numbers at all, a runtime error. But the point is, the most common case was handled in two instructions, and those could even be combined into one using the TADDCCTV variant, which trapped automatically on overflow. (There were also TSUBCC and TSUBCCTV, of course.)
My understanding of the history here is that a lot of Sun people, notably Bill Joy, came from Berkeley, where Franz Lisp was also developed; and in the mid-1980s (the first SPARC came out in 1987) it still seemed possible that Lisp would be of great commercial importance. AFAIK, these instructions were dropped for the 64-bit SPARC.
But the point of posting this is to underscore that the use of "fixnums", tagged immediate integers, is well known. Not only, as Juho has helpfully uncovered, does it date back to the 1960s, but it had explicit support in what was once a major microprocessor architecture.
I'll digress a little further and add that I really wish Java had used the Lisp approach for arbitrary-precision integers. Then Joshua Bloch would never have had to write this blog post: [0], among many other benefits.
[0] https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html https://research.googleblog.com/2006/06/extra-extra-read-all...
- pjmlp 9y agoSadly Java was only half way to Lisp, as Guy Steele puts it. Thanks for sharing the experience. Ada was also another example of having Ada Machines, that is how Rational was created.
- FullyFunctional 9y agoFurthermore, SPARC, like most RISC at the time, didn't support unaligned accesses, so to a large extent you got tag checking for free. Eg. assuming "01" tags for pointers and a simple two-word CONS cell, car would simple be one load instruction. ld %rd, [%r1 - 1] if %r1 didn't have a "01" tag, this would trap. Finally, SPARC reserved 8 registers for "global" use, that is registers what wouldn't be otherwise used by the compiler. Use was as simple as register int *sp asm("%g3"); which was immensely valuable for VM implementations (and others). Unfortunately, the tagged add instructions didn't get much use; perhaps SPARC wasn't a big enough base to justify designing around it.
- ScottBurson 9y agoThere certainly were Lisp implementations that used it -- notably Franz Allegro Common Lisp, which I used for years, FWIW.
- lispm 9y agoEric Benson claimed that this was added for Lucid CL: https://compilers.iecc.com/comparch/article/91-04-082 https://compilers.iecc.com/comparch/article/91-04-082 > Yes, the tagged arithmetic instructions were put in the SPARC architecture for Lucid Common Lisp.
- ScottBurson 9y agoThat could be true. But I'd like to hear what the Franz people have to say about it before I accept it as the whole truth.
- lispm 9y agoDon't forget that Lucid was the OEM for the Lisp implementation in SUN Common Lisp and the SUN Symbolic Programming Environment. http://ftp.lanet.lv/ftp/sun-info/sunflash/1990/Aug/20.01.lisp http://ftp.lanet.lv/ftp/sun-info/sunflash/1990/Aug/20.01.lis... http://3e8.org/pub/scheme/doc/lisp-pointers/v2i2/p5-endelman.pdf http://3e8.org/pub/scheme/doc/lisp-pointers/v2i2/p5-endelman...
- rjsw 9y agoSome of the ideas in SPARC came from SOAR, described in David Ungar's thesis [1]. He suggests that the Rice University R2 was the first machine with tags though the R1 [2] seems to have used tags too. [1] https://books.google.co.uk/books/about/The_design_and_evaluation_of_a_high_perf.html?id=gVcZAQAAIAAJ&redir_esc=y https://books.google.co.uk/books/about/The_design_and_evalua... [2] https://en.wikipedia.org/wiki/Rice_Institute_Computer https://en.wikipedia.org/wiki/Rice_Institute_Computer