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 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 (
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 adds three new capabilities:
evalfunction 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#
load-filefunction that reads a
JKLsource file and evaluates it in the current environment, e.g. to add new functions and values.
load-fileuses the new core functions
slurpwhich converts a named file into a Lisp string and
read-stringthat converts a Lisp string into a Lisp abstract syntax tree. The
load-filefunction 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 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 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
(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
isMacrodidn’t work. I looked at C#-Mal to realise that you can use
env.Getto 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 (
ifindentation) 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
defmacrodidn’t work. After some inconclusive tracing, I started re-implementing
EVALusing the C#-Mal logic to make it easier to spot the error. Halfway through this process I myself realised the simple solution, namely that
defmacroshould occur earlier in the
EVALthan 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
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.