30 oct 2021 @ justine's web page
SectorLISP Now Fits in One Sector
The SectorLISP project has achieved its goal of creating a LISP that's tiny enough to fit in the master boot sector of a floppy disk. To the best of our knowledge, this is the tiniest LISP to date. Since a master boot record is only 512 bytes, that means LISP is now tied with FORTH to be the most lightweight high-level programming language in the world. To put that into perspective, consider the following diagram:
Here's the SectorLISP REPL booting from BIOS in a PC emulator, and executing a simple LISP program which crawls a tree-like data structure to find the first symbol (or atom) in the tree. The tree in question is ((A) B C) so the correct answer is A.
Here's what happens if we wrap the program above in a LISP evaluator (i.e. LISP written in LISP) and then load that combined program into SectorLISP:
As we can see, it arrives at the same answer, which is A, except in a slower but more philisophically interesting way. The cool thing to pay attention to, in the above video, is the READ memory panel. You'll notice that once the metacircular evaluator is loaded (which enables LISP to start evaluating itself) the memory panel starts behaving the same way as the code panel. It becomes alive.
In order to make LISP as tiny as possible, we first needed to define the LISP program it'll run to demonstrate that it's capable of bootstrapping John McCarthy's meta-circular evaluator. Such a program would need to be written so it only uses the essential components of the language. Otherwise we'd need to add unnecessary bloat to the native interpreter.
Figuring out how to define LISP essentially is easier said than done. The original paper uses functions like (CAAR X) which is just a faster way of saying (CAR (CAR X)). It also defined a notation called (LABEL) which was added to the original evaluator by Nathaniel Rochester at IBM, who worked on FORTRAN and FLPL which was a competing list-processing language at the time. If you read the MIT research logs you can see people have been leaving feedback as far back as 1958 about LABEL being unnecessary. Chances are you've never heard of it, since the languages that grew out of LISP (e.g. Emacs LISP and Scheme) invented their own better notations to solve bindings.
The test program we settled on is this:
((LAMBDA (ASSOC EVCON PAIRLIS EVLIS APPLY EVAL) (EVAL (QUOTE ((LAMBDA (FF X) (FF X)) (QUOTE (LAMBDA (X) (COND ((ATOM X) X) ((QUOTE T) (FF (CAR X)))))) (QUOTE ((A) B C)))) ())) (QUOTE (LAMBDA (X Y) (COND ((EQ Y ()) ()) ((EQ X (CAR (CAR Y))) (CDR (CAR Y))) ((QUOTE T) (ASSOC X (CDR Y)))))) (QUOTE (LAMBDA (C A) (COND ((EVAL (CAR (CAR C)) A) (EVAL (CAR (CDR (CAR C))) A)) ((QUOTE T) (EVCON (CDR C) A))))) (QUOTE (LAMBDA (X Y A) (COND ((EQ X ()) A) ((QUOTE T) (CONS (CONS (CAR X) (CAR Y)) (PAIRLIS (CDR X) (CDR Y) A)))))) (QUOTE (LAMBDA (M A) (COND ((EQ M ()) ()) ((QUOTE T) (CONS (EVAL (CAR M) A) (EVLIS (CDR M) A A)))))) (QUOTE (LAMBDA (FN X A) (COND ((ATOM FN) (COND ((EQ FN (QUOTE CAR)) (CAR (CAR X))) ((EQ FN (QUOTE CDR)) (CDR (CAR X))) ((EQ FN (QUOTE ATOM)) (ATOM (CAR X))) ((EQ FN (QUOTE CONS)) (CONS (CAR X) (CAR (CDR X)))) ((EQ FN (QUOTE EQ)) (EQ (CAR X) (CAR (CDR X)))) ((QUOTE T) (APPLY (EVAL FN A) X A)))) ((EQ (CAR FN) (QUOTE LAMBDA)) (EVAL (CAR (CDR (CDR FN))) (PAIRLIS (CAR (CDR FN)) X A)))))) (QUOTE (LAMBDA (E A) (COND ((ATOM E) (ASSOC E A)) ((ATOM (CAR E)) (COND ((EQ (CAR E) (QUOTE QUOTE)) (CAR (CDR E))) ((EQ (CAR E) (QUOTE COND)) (EVCON (CDR E) A)) ((QUOTE T) (APPLY (CAR E) (EVLIS (CDR E) A) A)))) ((QUOTE T) (APPLY (CAR E) (EVLIS (CDR E) A) A))))))
It wraps the "find first atom" program in an evaluator program. Here it becomes clear that, in its most bare essential form, beneath the macros and abstractions, LISP actually has an unpleasant nature where name bindings (or assignments) look like a venus fly trap. This is probably the best evidence that LISP is a natural discovery rather than something someone designed, since no one would choose to design something unpleasant. But for the purposes of our project, we've chosen to love and accept LISP as it is. Since the focus is solely to bootstrap a LISP on hardware in the fewest number of bytes possible. Once we have a real LISP, we can build a nicer LISP on top of it that with a syntax of our choosing.
Now that we've defined the problem, all that's left to do is implement it in a native language. We built both a portable C implementation with a pleasant readline-like REPL for explainability, as well as an i8086 assembly language implementation, since it's a well understood architecture that runs natively on most modern machines and has a tiny instruction encoding format.
We needed to pull a few hacks to achieve our 512-byte goal. The first and most important of which, is we repurposed the %fs segment register as a monotonic allocator for storing tree nodes to an append-only immutable in-memory database. We'll leave it as a fun exercise for the reader to add garbage collection; see Nils Holm's book for help. As for the assembly notation below, if you haven't rote memorized the x86 ISA then you can hover over the instruction names to see a helpful tooltip.
int Cons(int car, int cdr) { int i, cell; i = g_index; g_mem[i + 0] = car; g_mem[i + 1] = cdr; g_index = i + 2; cell = OBJECT(CONS, i); return cell; } |
Cons: xchg %di,%ax mov %fs,%di push %di stosw xchg %si,%ax stosw mov %di,%fs pop %ax ret xchg %di,%ax ret |
One of the most important code size saving techniques has been to avoid the temptation of defining data structures in such a way that NIL is encoded as zero. For example, if the lowest bit of a word is a flag bit for telling atoms apart from cons, then that bit must be 1 for cons cells since NIL is an atom. In that case, all words representing cons cells effectively become a misaligned pointer and extra code needs to be written so the 1 bit can be cleared before addressing memory. Avoiding those address calculation woes by defining atoms as oddly-numbered words is far more profitable than avoiding explicit NIL compares.
Another hack we pulled relates to character comparison. For example, rather than saying isspace(c) we chose c <= ' '. That's actually a useful trick in general, since if you want to do something like accelerate an argument parser here in the modern world, you could say:
#if defined(__SSE2__) && defined(__GNUC__) && !defined(__STRICT_ANSI__) typedef unsigned char xmm_t __attribute__((__vector_size__(16), __aligned__(1))); for (; ga->j + k + 16 <= ga->mapsize; k += 16) { if ((m = __builtin_ia32_pmovmskb128( *(const xmm_t *)(ga->map + ga->j + k) > (xmm_t){' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '}) ^ 0xffff)) { k += __builtin_ctzl(m); break; } } #endif
Then, to check for parenthesis, we chose c <= ')'. This hack is a bit more brutish. While it helps with code size, it has the unfortunate side-effect of making the REPL behave in strange and unusual ways if an atom has a name like !! or ##. This is due to the way the ASCII table is laid out.
void GetToken(void) { int al; char *di; di = g_token; do { if (g_look > ' ') { *di++ = g_look; } al = g_look; g_look = GetChar(); } while (al <= ' ' || (al > ')' && g_look > ')')); *di++ = 0; } |
GetToken: mov $g_token,%di 1: mov %dl,%al cmp $' ',%al jbe 2f stosb xchg %ax,%cx 2: call GetChar xchg %ax,%dx cmp $' ',%al jbe 1b cmp $')',%al jbe 3f cmp $')',%dl ja 1b 3: mov %bh,(%di) xchg %cx,%ax ret |
One of the corner cases of LISP is how to print a list that doesn't have a NIL terminator. Most LISPs represent this using a space followed by a period and then another space:
* (CONS (QUOTE A) (QUOTE B)) (A . B)
So to save space, and avoid calling PutChar() thrice, we just replace the space we'd normally print with the bullet operator from IBM Code Page 437:
* (CONS (QUOTE A) (QUOTE B)) (A∙B)
Now it goes without saying that we didn't have room for floats and integers; but that's ok, since numbers can be encoded in a variety of different ways by a sufficiently smart user. According to The History of LISP, the same was true for LISP 1.0. Native integer support was added later as a performance optimization. However we sadly haven't found listings for it online. Integers also likely weren't that applicable to their use case, since one gets the impression reading the original materials that it was intended primarily as a theorem prover, using techniques like Wang's Algorithm. In any case, it would be interesting to see the LISP 1.0 sources to compare the binary footprint, should Steve Russel find it in his archives.
If you don't have a floppy disk drive, you can run SectorLISP in a PC emulator like Blinkenlights.
curl --compressed https://justine.lol/blinkenlights/blinkenlights-latest.com >blinkenlights.com curl https://justine.lol/sectorlisp/sectorlisp.bin >sectorlisp.bin chmod +x blinkenlights.com ./blinkenlights.com -rt sectorlisp.bin # then press 'c' to continue execution # then type code like (EQ (QUOTE A) (QUOTE A)) into the REPL
Be sure to full screen your terminal and make the font size small, so you can see all the panels. If you use Windows then you need to be running at least Windows 10. Otherwise you need to run it in MinTTY. Alternatively, you may run SectorLISP in QEMU as follows:
qemu-system-i386 -nographic -fda sectorlisp.bin
There's also an ANSI C translation of the SectorLISP source code that includes a pleasant bestline interface (a BSD-licensed readline replacement that's been adding paredit features). The C sources may be built an run as follows:
git clone https://github.com/jart/sectorlisp.git; cd sectorlisp make && ./lisp
Here's the full listing for SectorLISP.
It's 8 pages and available in PDF, TXT, HTML, BIN, or ELF.
You may also view the sources on GitHub as either ASM or C.
For comparison, here's the IBM 709 listing for LISP 1.5, a
LISP machine made by Steve Russel, John McCarthy, et al.
It's been edited and colorized for readability for the first time.
It's 257 pages and may also be downloaded as PDF, TXT, or HTML.
SectorLISP started off in the Cosmopolitan repository as an experiment written by Justine Tunney in using sed to get code built by a Linux x86_64 compiler to run in real mode (i.e. PC-BIOS i8086). Around that same time, Cesar Blum from EA unleashed SectorFORTH on Hacker News and Justine was so impressed that she decided to spin her demo code off into its own sister project: SectorLISP. What made SectorFORTH so impressive is that languages with the "tiny" or "small" sales pitch come along so frequently, and SectorFORTH was the first to do it with an objectively defined criterion.
SectorLISP received contributions from Scott Wolchok (an assembler blogger from Facebook, see wolchok.org), Ilya Kurdyukov (lead performance engineer at BaseALT), plus a FreeBSD fan who goes by the hacker alias Moonchild. We managed to get LISP down to around ~700 bytes (if you exclude the code that's needed to load additional sectors off disk). We were quite satisfied that we had made LISP smaller than it'd ever been before, but we were still short of our goal of 512 bytes. That last 200 bytes may not seem like much, but it felt like a tremendous gulf. Then we met Alain Greppin who's basically the Heisenberg of assembly language. He helped us look at the problem in a different way and submitted the change that brought our team across the finish line.
The musical track in the video above is the Bolivia Theme by Giorgio Moroder as performed by Chuy Flores.
Recursive Functions of Symbolic Expressions and their Computation by Machine by John McCarthy
The Roots of Lisp by Paul Graham
LISP From Nothing by Nils Holm
History of Lisp by John McCarthy
52nd Quarterly Progress Report of the MIT Research Laboratory
from Hacker News https://ift.tt/3EuHW8V
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.