initial commit

git: commit

Well, not really :-) But so many repository stories start with this one, that when I decided to keep a blog in my git log entries for this repository, I could not resist.

So, what is this blog about?

  1. It is about my explorations into a world of implementing a LISP virtual machine.
  2. It is actually a commit log of this repository, so future lyrics will be organized around the code changes: why? how?

I will explain both bullet points in further details.

  1. Exploration into LISP VM

It all started last month when a colleague of mine told another one about the existence of fascinating Brainfuck language. While it is indeed a fascinating language, my sympathies lay in a different venue. Namely, I recalled that there was a LISP interpreter fitting into 512 boot sector; and indeed I quickly googled secorlisp 1. To explain how I ended up writing my own interpreter, we need to get on a detour.

One truly mysterious process for me is bootstrapping. Imagine, we have a new processor architecture, and we would like to port large volume of the already written code to it. This means, that we need several basic utilities such as assembler compiler, linker, loader and a compiler of a higher level language. Well, THE higher level language, in practice. You absolutely need a C compiler. How do you do it?

A typical way to bootstrap is to take a compiler suite on a different platform (like your desktop), and cross-compile the basic suite of utilities to your platform. You might in the process have to write your own code generator, if your processor is truly knew.

So, we use a large volume of truly amazing software on a different architecture to produce a binary image, suitable for our platform. The question that has tingled me for a while regards the minimum amount of such a binary image.

Getting back to the LISPM: I think the answer is somewhere in the low kilobytes needed to get a working LISP machine and a minimalistic runtime routines, allowing to read and write bytes into the machine memory, and execute native code with its own heap and stack.

And THAT is what I really want to try: bootstrap a good enough C compiler, to then bootstrap make and binutils.

I need a LISP machine for my purpose. I initially started with sectorlisp and The Roots of Lisp paper by Paul Graham 2, and tried to mend the code to my needs. This turned out to be harder than I thought, as the code is written in the very minimalistic way, and I also needed some additional capabilities like integers, which would be challenging to implement while adhering to the style of that code.

So, I started my own implementation. It’s been a great journey up till now. I’ve had some mindblowing revelations along the way. Just yesterday evening I was deeply thoughtful about the nature of recursion. On other occasions I read chapters of SICP 3, and generally looked around. Of course, I have this other page 4 open :-)

Somewhere along the way I started leaving more and more extended notes in my personal notebook (the paper one). Then I realized, that it would be great to write a blog based on these notes. Except, it is tedious to write a coherent story after the fact based on a couple of notes in the notebook, and any blog post series would require some means to organize the writing. Both tasks are much less tempting to me than doing the next thing I have on the top of my mind.

And then today another revelation came: I’ve already started paying more attention to the git log entries in the repository, and started providing more than just half-assed one-liner non-explanation to a commit. Why would not I extend it further to make a blog out of it? It solves both of the challenges mentioned above: it keeps notes in electronic form, and even more importantly it already is a part of workflow every time I do git commit, which does not fill distruptive to writing the code, and is the most context-rich environment I have.

And here we are.

  1. The actual log

This entry is inherently long and not very connected to the changes at hand, because I needed to explain some history and context. Later entries will likely be organized very differently.

Since blog can increase publicity of this whole thing, it is good time to make a basic cleanup: update the README, and provide at least some testing - github is a public place, and it would be shameful to appear there not covered with at least rudimentary testing.

So I implemented testeval.c that runs through all the tests in evaltests/ repository. Those verify that the machine evaluates the way I expect. In future series I plan to test the actual lispm.c code, although my big dream would be to formally prove its correctness, so maybe I will make another attempt to Coq 5 some time later as well :-)

  1. https://github.com/jart/sectorlisp ↩

  2. https://paulgraham.com/rootsoflisp.html ↩

  3. https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/6515/sicp.zip/full-text/book/book.html ↩

  4. https://en.wikibooks.org/wiki/Haskell/Understanding_monads/State ↩

  5. https://coq.inria.fr/ ↩