Introducing Germ Lisp – NgyroIntroducing Germ Lisp<br>Presenting my tiny, self-hosted Lisp.<br>Background<br>For many years, I’ve been helping to make software more<br>“bootstrappable”. This has all been done in the<br>context of the GNU Guix project. Guix makes the data flow from<br>source code to running software environment explicit: these sources<br>become these binaries by way of this compiler, whose sources become<br>binaries by way of this other compiler, etc. How deep into compilers<br>of compilers of compilers can you go? For many programs, all the way<br>back to a 357-byte proto-compiler (on x86 Linux). There<br>is a bit of hand waving here, as all of the builds are scripted in<br>Scheme and need a compiled version Guile to run. Guile is<br>several mebibytes. We’re close to getting rid of Guile, too, but that<br>will have to wait for another post.<br>The 357-byte proto-compiler, hex0, simply turns ASCII hex digits into<br>binary form. From there, we work up to a primitive assembler called<br>M0. Then, with M0, we can build a compiler for a C-like language (a<br>subset of C, really). This process is iterated a few times as the tools<br>become more sophisticated, resulting in more capable compilers, standard<br>libraries, assemblers, linkers, and several other programs. Then, we<br>can build Mes. Mes is a Scheme interpreter. With Mes, we can<br>run an even more capable C compiler called MesCC and use a more complete<br>standard library. From here, we can build TinyCC, which can<br>build an earlier version of GCC, which can build a later version of GCC, and so<br>on until we have built the latest GNU build system.<br>This is all great! Really! It’s all ready to be integrated into Guix<br>and make the bulk of the distro bootstrappable from soup to nuts. But<br>sometimes I find myself wondering why we go from C to Lisp and then back<br>again? Especially in Guix, where we end up going from C to Lisp, then<br>back to C, and then finally back to Lisp. In fact, I’ve often wondered<br>if we could insert Lisp immediately after hex0. A primitive Lisp<br>interpreter is not much more complicated than a primitive assembler.<br>It’s much more powerful, though!<br>This question has been in the back of my mind for several years now.<br>I’ve built a few prototypes and explored various ways to pack a lot of<br>punch in a small Lisp interpreter. Recently, I built a functional proof<br>of concept which I’m delighted to present to you, dear reader, in this<br>blog post.<br>Germ Lisp<br>I call the thing Germ Lisp (think “germinate”). It is<br>written in assembly, runs on x86 Linux, and weighs in at about 2.25KiB. It works in two stages. The first stage<br>is the kernel which is a tree-walking interpreter with a garbage<br>collector, system interfaces, and enough of a parser to read basic<br>S-expressions. The second stage runs directly on that kernel, adding a<br>more sophisticated parser (apostrophe for quote, hex numbers,<br>character literals, etc.) and a basic Lisp-style macro system. This<br>second stage is Germ Lisp, and if you run it, you will be inside of a<br>REPL, ready to send<br>expressions to the interpreter.<br>System interface<br>The system interface is very Spartan, but extremely capable. It<br>includes:
Testing pointer equality (eq?)
Manipulating pairs (cons, car, set-cdr!, etc.)
Arithmetic on machine integers (combine-numbers)
Calling the interpreter (eval and apply)
Execution environment (command-line and environment-variables)
General system calls (syscall with buf-ref and buf-set!)
The combine-numbers procedure provides an indexed interface in to<br>the various operations on machine integers. For example, you give it<br>0 for addition, 1 subtraction, and so on. It exposes 12 operations in<br>total, including comparison. This is wonky, but saves space and goes<br>away with a few simple definitions like:<br>(define + (lambda (x y) (combine-numbers 0 x y)))<br>The syscall procedure invokes the Linux kernel. In order to<br>manipulate C-style strings, the Germ kernel provides a fixed-size buffer<br>that can be read and written to using the buf-ref and buf-set!<br>procedures. The syscall procedure takes a specification string for<br>argument types. If the string has an “n”, the corresponding argument is<br>a number and should be passed to the Linux kernel as-is. If the string<br>has a “p” the corresponding argument is an index into the buffer and<br>should be converted to a pointer before going to the Linux kernel. For<br>example, to write the letter “A” to standard output, you could write:<br>(define %sys-write 4)<br>(define %stdout-handle 1)
(buf-set! 0 65)<br>(buf-set! 1 0)<br>(syscall "nnpn" %sys-write %stdout-handle 0 1)<br>Of course users of Germ wouldn’t usually use combine-numbers or<br>syscall directly. The bootstrap script renames all the basic<br>arithmetic procedures and provides a very primitive “ports” interface<br>for input/output.<br>Memory management<br>To save space, the kernel only supports three types of objects: pairs,<br>numbers, and “special” values (sigils, essentially). Since numbers<br>and special values are atomic, the garbage collector only has to worry<br>about pairs. This means that strings have to be...