Writing Your OS in Lisp

How to write an OS in Lisp is beyond the scope of a single post in this blog, and I don‘t have a series prepared. However, I can drop some hints of how you can overcome some problems.

If you are writing your OS in Lisp, it helps to have some idea of how Lisp compiles your program to machine code. The disassemble function prints out the disassembly of a Lisp function. It is obviously implementation dependent.

The inner dispatch of the compiler, when it is called, will be given a target location in which to deposit the result of evaluating the compiled expression. The target location given to the compiler will typically be a register, the top of stack, a fixed offset within the stack, or a global memory location, that sort of thing. The compiler should generate code that ultimately results in the value of the expression ending up in the target location.

A number of Lisp primitive functions can be implemented as a single CPU instruction. (Alternatively, you can create quirky Lisp “CPU subprimitive” functions out of each of the non-jump CPU instructions.) When compiling a function call to such a subprimitive function, the compiler emits code that fetches each argument from its location and places the value in a register, and then emits the single CPU instruction that the subprimitive consists of. It arranges for the result of the CPU instruction to be placed in the target location. What I’m describing here is basically what is known as a “compiler intrinsic” in other languages.

If you have a tree of compound expressions, each of which is one of these CPU subprimitive functions, the compiler will assign locations to all the intermediate computed values, determine an order in which to compile the primitives (linearized left to right), and then emit linear code that carries out the primitive operations. If all your code consists of calls to CPU primitives, then the compiler can generate straight-line assembly code CPU instructions. The compiler in this case only acts as a register allocator. From here, you can bootstrap yourself to a set of primitive procedures each of which is written in straght-line assembly code.

When writing an OS, you occasionally run into places where you want a very specific sequence of CPU instructions. You have a couple of options: some Lisp compilers offer a way to insert literal assembly code instructions in the compiled code instruction stream in a progn like manner. Naturally such code is “unsafe”, but it nicely solves the problem where you need hand-crafted assembly code in your solution. The other solution is to write the code as a compound expression of CPU primitives and let the compiler sort out the register allocation.