Early Ideas: A Modern Lisp Machine from Scratch

Written in Sep 15, 2018 by Alchemist
alchemist@sdf.org

Introduction

I am often fascinated by old tech.

While I do not have the experience nor the expertise on the subject, in the last months, some very specific stuff has caught my eye, and those are the Lisp Machines.

I've been using Common Lisp for about three years and a half and, though only now I began to make cool stuff using the language, the fact that it is not very used bothers me a lot. I mean, of course, it is not something as welcoming in terms of first impression. Lisp is known for its overwhelming parentheses, which often hide the true power of the language.

But this bad first impression cloaks the possibilities of a mature language such as Common Lisp, of Lisps in general, and of specialized hardware and systems, built to ensure performance on Lisp execution.

On this post, I try to present very early ideas in a project of a new, modern Lisp Machine of sorts; one which might have the potential to make true hackers feel at home with the idea of running a highly customizable, but also efficient Unix-like system built to run Lisp on specialized, modern hardware.

Lisp Machines

Lisp Machines were computers specially designed to run Lisp code efficiently. This is justified by the way the language works: Lisp stands for "List Processor". Since Lisps stand over heavy usage of list data structures, it is only natural that someone would want fine-tuned hardware to deal with those, so these machines carefully reduced execution costs with specific hardware, CPU instructions, and specific memory management.

The Lisp Machines rose inside the MIT AI labs, which gave birth to its first forms, only to pretty much die after the fall of Symbolics, the company bred from the same labs, which produced them commercially, leaving a legacy and orphaned lispers who are still waiting for Lisp Machines to rise once again. The original Lisp Machines, as I was told, were built using processors with reduced instruction sets (RISC), and a very specific way to manage memory.

This whole story bothered me to the point which I though I should try building one, from scratch, since RISC processors seem to be rising once again (a little more on that later in this post). It is old stuff, but it seems interesting, given that it pretty much operates different than the way modern computers do. But it also needed to be something that I would be able to use, and enjoy using. And it might even serve as base for next projects, which I will explain in the following paragraphs.

However, this "Lisp Machine" I intend to build is not the first example of what a fully-functional computer running an OS built using Lisp in the present days could be. Lukas F. Hartmann already built something like this for the Raspberry Pi 2, pretty much in the model which I want to follow: the resulting experiment is a board, attached to a custom-made keyboard. Interim OS (as the operational system is called) is a full-fledged Lisp system, running its own dialect (do not confuse with the recent Interim Lisp, which is a low-level Lisp with compile-time memory management, much like Rust language). This OS also has the interesting aspect of having been inspired by Plan 9, the operational system which is the true spiritual successor to the original Unix.

Hardware optimizations

My main concern is about the kind of hardware-level optimizations that such an operational system, built using Lisp, might require. Therefore, I have decided that I should go ahead and try building custom instructions atop a flexible architecture which would allow me to do so. And this is where the plain new RISC-V architecture comes in – praised by media, open, hackable, exactly what I want. And this is what would set it apart: While Interim OS is an awesome project, it is built for ARM processors, therefore it is stuck to the ARM instruction set. With RISC-V, not only could those instructions be extended, but it would also be didatic enough so that hackers with sufficient knowledge could mess with.

System architecture

For the user experience, my intention is to create a Unix-like environment, though I do not intend to follow POSIX, not even remotely. The user would be presented with what seems to be a Unix environment, mimicking Plan 9 as best as possible – this does not only mean good old Unix experience, but also possibly 9p integration, so that building clusters could also be possible with ease.

The system, of course, would also have openness and simplicity in its code as fundaments. Files can be precompiled (though I still need to give it careful thinking, since I do not want to replicate the old MIT LispM's and Mezzano's mistake of taking hours to boot for the first time – the former one requiring such big time every day; this goal also implies simplicity on kernel development itself), though hacking them should be easy: if you want to change anything, just go ahead and change the source code, then recompile the file, or even only the form. This would allow not only the experience of live debugging while running the code (given that I also implement something as powerful as Common Lisp's conditions and SBCL's debugger), but would also make possible to create a fun environment in which I may bootstrap the whole system while I'm running it! Just imagine developing a kernel atop itself.

I was thinking about implementing these using some kind of layer. The very base of the system would be implemented in Forth, which could be implemented directly using RISC-V assembly, with minimal extra words for its dictionary, which harness the power of the custom processor instructions that are required for the Lisp Machine. From Forth, we may then bootstrap a basic Lisp interpreter; and from the interpreter, we bootstrap the rest of the system. I am not entirely sure what to make of the dialect which should be implemented itself, but I'm almost certain that it will be a subset of Common Lisp, which I believe is the descendant of the dialects used on old Lisp Machines. I am not naive enough to think that I will be able to implement Common Lisp on this system with so much to do already, but the intention is to leave the dialect itself somewhat open, so the features of Common Lisp may be slowly implemented as needed.

I'm also thinking carefully on what to do about concurrency on this new system. Some folks once told me that the problem with praised systems languages such as C and C++ is that they still make you pretend that you're programming on a machine which works like a PDP-11, something that is not justifiable given the current state of industry. While I like C and C++, I cannot find a counter-argument, therefore it is probably important that I take it seriously from the beginning of system development, even though the first implementation might be built atop a 1-core RISC-V processor. For that reason, I am carefully looking into the topic of coroutines, and this might even imply a scheduler for the system to make those work, and possibly take advantage of the processor as much as it can, according to its number of cores.

Extensibility and hackability

Another interesting thing which I'm giving a lot of thought is the ability to change dialects and paradigms in a per-app basis. Of course there would be a common interface for inter-application communication, but imagine a single directive which, when evaluated, changes the interpreter only for that application so you can write it in, say, Clojure, for example (minus all the Java bloat, of course!). This might even be a way to enforce functional principles such as immutability to enhance performance even more on certain situations.

We would also need a basic text editor in order for all of this to happen. For that, the intention is to implement a small variation of Emacs or Zmacs editors, so that coding is made simpler. Scripting language would need to be the system's own dialect, although maybe Emacs Lisp support could be implemented using the idea from the last paragraph.

Graphical interface

Finally, as for GUI applications, Common Lisp has the fantastic CLIM, which is very underrated and has a lot of good principles. CLIM could be implemented using the system's dialect, and then GUI applications could be created using it, much like someone would do with Qt on any platform, for example.

Internet

I've been discussing a lot with friends about the possibility of "web" pages built using S-expressions instead of HTML itself. This would probably be a huge break in the way a browser works, however this might be just perfect for a system running Lisp as its main language, since the page itself is already arranged as a tree. It would also be interesting to allow that same idea of changing dialects for a scripting language on those pages, however I would opt to sandbox Lisp web scripts like this so they cannot manipulate many things, while also using the system interpreter itself to optimize the execution of said scripts. With such a feature, the webpages are but lists of lists, and scripts could be external files written in Scheme, for example, or even lambdas attached directly into the document tree.

Another interesting feature would be to support a dialect of WebAssembly of sorts which could compile to machine code directly, just like a Lisp file would. This way, the script's safety could be enforced before compilation, and then the page script could take full advantage of the system's native performance.

Conclusion

Those are ideas for something that has proven difficult to do, specially given the fact that I lack a lot of experience and knowledge in most of the things I have described above. Most of the difficult would be on actually learning the RISC-V low-level stuff to even begin building such a system; and then, implementing Forth using nothing but assembly, which will also be a pain; then finally, implementing Lisp atop Forth, which might also be a huge problem. Plus, the whole system and kernel is another big effort that will take much more time, and having a minimal environment for me to have fun bootstrapping the system as suggested (which would be crucial so I don't get bored) would also require that Emacs/Zmacs clone to work well.

This is a huge project comprised, right now, mostly of ideas I've been maturing on the last months, and discussing with friends over the internet. I'm already collecting books and articles on all of those subjects to read in my free time, but I know it is gonna take time. However, it would be really nice to see this stuff working, specially if the community could make good use of it.