January 2, 2018

Writing a Small LISP Interpreter

Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp. -- Philip Greenspun, 1993

TeX Writer uses a half-baked lisp for configuring its editor. Since we are going to reimplement the editor, the lisp engine needs to be updated as well. For the entire December, I had been working on the new lisp implementation (well, to be honest, took me some time to building a retro 486 PC too). Actually I had tried to rewrite it many times before, but every single time I abandoned because it didn't feel pretty. This time, with all those failures under my belt, the implementation goes smoothly. Start from the tokenizer, then parser, simple expression evaluation, lambda, macro, tail recursion, error callstack, then the tests. Features unfold naturally, and it's done with about 3500 lines of C code, though I may need to add some more in the following weeks.

The lisp dialect is modeled after Scheme, but conforming to standard is not our goal. It has some special features. For instance, it's easy to write a self printing program:

((lambda (&label p) (write (cons (cons (quote lambda) (cdr p)) ()))))

The argument modifier &label binds p to the lambda closure itself, and (cdr p) returns the source of lambda. I don't have any real use for it, but seeing it run gives me smile.

Now I have no more reason to postpone the real work here -- new editor, better editor.