Make a Lisp [3] Technical SITREP

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.

Summary

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

• Steps 5, 6 and 7 were done in an intense two week burst (compared with two months for earlier steps)
• Unfortunately, Step 8 took two another months because of commitments that stopped Lisp work altogether coupled with some subtle bugs. I resorted to cheating (looking at C#-Mal - the C# reference implementation) to get past two of these
• I’ve continued to make minor improvements to the guide version, notably error checking and diagnostics

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:

• an eval function available to code written in JKL, which can at run-time evaluate a list representing a Lisp abstract syntax tree. This of course is defined in terms of the internal C# EVAL function
• a load-file function that reads a JKL source file and evaluates it in the current environment, e.g. to add new functions and values. load-file uses the new core functions eval (as above), slurp which converts a named file into a Lisp string and read-string that converts a Lisp string into a Lisp abstract syntax tree. The load-file function is itself implemented in JKL (rather than C#) using a function that is defined using def! when the initial Lisp environment is instantiated but before the REPL is started:

  (def! load-file (fn* (f) (eval (read-string (str "(do " (slurp f) ")")))))
  

• a representation of atoms: mutable, stateful data structures that can be updated with new values (JKL’s other values are immutable, as is often the case in functional languages)

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)
      nil
      (if (= 1 (count xs))
        (first xs)
        (let (condvar (gensym))
           `(let* (~condvar ~(first xs))
               (if ~condvar
                  ~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:

• My definition of isMacro didn’t work. I looked at C#-Mal to realise that you can use env.Find before env.Get to avoid an exception on a failed lookup. I genuinely think it would have taken me ages to spot this. The cheat got me on the right lines before I wasted time building a complicated bodge. I also spotted that I had incorrect logic (if indentation) in the quasi-quoting added in Step 7. In my defence the Mal guide wasn’t very clear here, and the Mal test suite didn’t cover the exact problem that I’d introduced

• My initial implementation of defmacro didn’t work. After some inconclusive tracing, I started re-implementing EVAL using the C#-Mal logic to make it easier to spot the error. Halfway through this process I myself realised the simple solution, namely that macroexpand and defmacro should occur earlier in the case statement in EVAL than the special forms they expand into. This took days, and was the biggest gotcha to date. I then lost more time redoing all the error handling that I’d stripped out when simplifying EVAL

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.