This note is part of a series.
I rewrote the entire thing. Using arenas for my implementation was a mistake as it enforced a style of allocating memory into the project that didn't suit it. I also made the mistake of modelling s-expressions as a dynamic array of expressions. This made it difficult to grow s-expressions, and i can't even think of how much it would've complicated garbage collection down the line.
I took a break from the project, which is why I hadn't written about it recently. It was demotivating to find that my implementation was plainly wrong, and living with the fact that I hadn't forseen this issue felt bad.
However, I went ahead and tried again from scratch, this time doign things simpler. S-expressions, for example, were modelled as cons pairs. I have dropped the idea of using arenas at each stage of the evaluation: one for parsing, one for evaluating, and one for printing. Looking back, this didn't make sense. Lisp requires a garbage collector, and a Lisp program allocates memory willy-nilly, so it was best to optimize for that, looking back. The fixed-sized nature of arenas, and reclaiming memory being tricky makes arenas unfit for the task.
I still imagine I'll be using arenas for allocating cons pairs, I think, once I get around to doing the garbage collector. Cons pairs have a fixed size (32 bytes in my case), and are frequently allocated, so it makes sense to have a sort of cons pool, per sé.
Another thing I didn't like about my previous implementation was that I did reading in 2 passes: lexing and then parsing. I ended up with duplicated logic in the end, and the whole thing felt too redundant. Perhaps this was a fault on my part. After changing my approach to a more intertwined manner—where parsing involves lexing the rest of the input to acquire a single token and to make decisions based on that—I found it natural to support more syntax. Adding quoting was trivial, for instance: Lex a TOK_Quote, and construct a cons pair where the car was quote and the cdr is the next expression. In a way, I'm glad I was forced to rewrite the whole thing.
Currently, I'm at a point where conditionals, functions, definitions, and such forms exist. I've provided a list of builtin functions too. I've succesfully implemented basic algorithms including insertion sort. There's a surreal feeling in interacting with the repl I wrote and watching it do its thing. Of course, when things go wrong it can feel rank but when everything falls into place and I see the following piece of code work, it feels a peculiar kind of sweet. I know nothing I'm doing is novel or extra-ordinary, it's been done a million times before. It's just something about doing it yourself that makes it special.
It can be hard, and often demotivating and puzzling, but the key is to remember to keep at it.
Here's my "standard library" that I use by entering (load "std.lisp") in the repl, as a treat.
(defn map (f xs)
(if (nilp xs)
xs
(cons (f (car xs))
(map f (cdr xs)))))
(defn filter (f xs)
(if (nilp xs)
xs
(if (p xs)
(cons p (filter p (cdr xs)))
(filter p (cdr xs)))))
(defn reduce (f acc xs)
(if (nilp xs)
acc
(reduce f (f (car xs) acc) (cdr xs))))
(defn zero? (x) (= 0 x))
(defn iota (n)
(if (zero? n)
(cons n nil)
(cons n (iota (- n 1)))))
(defn nth (n xs)
(if (nilp xs)
nil
(if (zero? n)
(car xs)
(nth (- n 1) (cdr xs)))))
(defn min (a b)
(if (< a b) a b))
(defn max (a b)
(if (> a b) a b))
(defn elem? (x xs)
(if (nilp xs)
NIL
(if (= (car xs) x)
T
(elem? x (cdr xs)))))
(defn rev (xs)
(reduce cons nil xs))
(defn join (a b) (reduce cons b (rev a)))
(defn take (n xs)
(if (nilp xs)
nil
(if (zero? n)
nil
(cons (car xs) (take (- n 1) (cdr xs))))))
(defn drop (n xs)
(if (nilp xs)
nil
(if (< 1 n)
(drop (- n 1) (cdr xs))
(cdr xs))))
(defn sorted-insert (n xs)
(if (nilp xs)
(cons n nil)
(if (< n (car xs))
(cons n xs)
(cons (car xs)
(sorted-insert n (cdr xs))))))
(defn insertion-sort-impl (sorted xs)
(if (nilp xs)
sorted
(insertion-sort-impl
(sorted-insert (car xs) sorted)
(cdr xs))))
(defn insertion-sort (xs)
(insertion-sort-impl NIL xs))