A small LISP interpreter in C

git: repo

This study is devoted to a C implementation of a small VM for a dialect of Lisp. It is accompanied by a series of blog posts, that I kept directly in the commit messages of the main branch.

The easiest way to try it out on a Linux system is to install libreadline.so and its headers using system’s package manager, after which one can do make repl && build/repl/repl from the repo root.

I aimed to fit the implementation in 4K of code for the core language on x86-64 platform. The core language in lispm.c supports lambda, let, letrec constructs, has syntax for unsigned numbers 2 bits shorter than the native, implements tail call optimization, a compacting garbage collector, tracks the overflow of native call stack and machine’s value stacks, and provides panic! builtin to immediately abort the computation. The funs.c expands the language with builtin functions for lists and integers.

As of writing debug.c needs some tl&c, same goes for tracing capabilities. I also want to eventually properly unit test the functions in lispm.c and lispm.h.

Since I tend to hack-hack-hack much more than write blog posts, I experimented with blogging right-there-and-then, i.e. directly in the commit messages of the main branch. I wittingly called this approach git blogging. Later though I discovered some elements of blog-chaining, since all my ridiculous mistakes are now ingrained into the commit history. I was so embarrassed to discover word “anigmatic” in one of the messages, that opted for some minimal post-processing :-)

Below is the full list of commit posts.

• initial commit
• remove long numeric objects
• report errors via trace mechanism
  I saw the angel in the marble and carved until I set him free
• tighten the rules about special forms
  here be undecidable dragons
• fix captures evaluation algorithm
  on virtue of attentive reading and on my favorite mantra
• specify trace event in LISPM_EVAL_CHECK args
• introduce a proper parsing stage
  on multiple birds and one stone
• inroduce self-referrential symbols
• re-implement keyword feature
  haste makes waste
• implement letrec
  how a "simple" feature can guide VM development
• reorganize the code
  on how cleanup drives further development
• monitor stack depths
  on measurements
• optimize tail calls and implement shallow gc
  one does not simply
• merge in a finalized version of garbage collector
  and tell more about objects and their lifetime
• clean up internals of lispm.c
  it's Sunday cleanup time!
• implement a minimalistic REPL
  ... and tell about its shortcomings
• several binary size optimizations
  on arranging some space for a new feature
• avoid stack growth during tail calls
  on how I accidentally missed the point
• implement custom destructors for extensions