Make a Lisp [3] Technical SITREP

14 Apr 2019

This is the third SITREP for my ongoing Make-a-Lisp project. The first post in this series describes the background and goals, and SITREP 2 describes what happened in steps 0 to 4.


I’ve now completed steps 5, 6, 7 and 8. The headlines are:

The source code is on Github.

Step 5

Step 5 adds an under-the-bonnet performance enhancement - Tail-Call Optimisation (TCO) - rather than new programmer-visible language features. Specifically, JKL includes an EVAL function that implements the Lisp special forms (if, let, etc), and several of these call EVAL recursively. In those forms that call EVAL as the last thing they do before returning, TCO loops back to the beginning of EVAL rather than calling EVAL recursively. This significantly reduces the chances of runtime stack overflow.

Step 6

Step 6 adds three new capabilities:

During Step 6 I also fixed a couple of bugs (string handling, Lisp (do...) forms) that had crept in during earlier steps but which hadn’t been detected by the tests for those steps.

Step 7

Step 7 adds mechanisms that allow programmers to change the way that EVAL operates on forms, e.g. to quote a symbol so that EVAL uses its name rather than its value, or to splice one lisp form into another.

Step 8

Step 8 adds a Lisp macro implementation. Macros, in conjunction with the quoting mechanism from Step 7, allow programmers to directly manipulate Lisp code and thus dynamically extend the language syntax (in effect defining new special forms). Macros are the primary mechanism by which Lisp can be used to create Domain-Specific Languages. Here is an example - the definition of or:

(defmacro! or (fn* (& xs)
   (if (empty? xs)
      (if (= 1 (count xs))
        (first xs)
        (let (condvar (gensym))
           `(let* (~condvar ~(first xs))
               (if ~condvar
                  (or ~@(rest xs)))))))))

This step has taken the longest to date and was the most frustrating. There were several weeks where other commitments prevented me from doing anything at all, reducing my familiarity with the code base. There were two places where I had to check C#-Mal to get past a problem:

The final problem took more five weeks of elapsed time to fix (mainly because of the other commitments that stopped all progress). The problem manifested when I tested the or macro provided in the Mal guide: (or false false 1) returned false rather than 1. I spent a lot of time tracing the Step 8 code, not helped by the enforced downtime. Step-wise debugging was challenging because of the deeply recursive EVAL calls due to the or macro itself. I eventually spotted the problem when idly looking at the Step 7 reader functions of the relevant reader macros and comparing them with the Mal guide’s descriptions. It turned out that I’d made a very small mistake - omitting a ~ character when implementing backquote (!!!) - and that I hadn’t run the (optional) Step 7 test that would have uncovered the problem. It took about five minutes from finding and understanding the cause to writing and testing the fix.

The expensive lesson here is John, always run ALL of the tests. Luckily I realised the error before re-implementing the entire macro mechanism from the ground up. On the plus side, the debugging fixed a minor problem in the way that EVAL handles non-special forms that start with a non-numeric constant (e.g. (true 1)) rather than a number, function name or symbol.

Now that I’ve got this done and written up, I’ll continue with Step 9, which is to add an exception handling mechanism.