(Yet Another) Lisp In Go

Here is a summary of what's implemented & planned:

The current implementation is on GitHub. Its speed surprises me a bit.

Consider the following program in l1, which computes a factorial:

;; fact.l1: Return the factorial of `n`:
(def fact
     (lambda (n)
       (cond ((eq 0 n) 1)
             (t (* n (fact (- n 1)))))))

(print (fact 100))

outputting

933262154439441526816992388562667004907159682643816214685929638
952175999932299156089414639761565182862536979208272237582511852
10916864000000000000000000000000

Its equivalent in Clojure (or its nimble alternative implementations, Babashka or Joker) can be written as follows:

;; fact.clj: Return the factorial of `n`:
(def fact
  (fn [n]
    (cond (= 0 n) 1
          :else (*' n (fact (- n 1))))))

(println (fact 100))

… and in my Python Scheme implementation as

;; fact.scm
(define (fact n)
  (if (= n 1)
      1
      (* n (fact (- n 1)))))

(display (fact 100))

I also did the equivalent for Common Lisp. I used Oatmeal to make a skeleton Lisp project and used that to create an executable program called fact.

The execution times break down thusly:

This is a very limited benchmark! However, it does give a flavor for start-up times. Note that l1 is a tree-walking interpreter; I wonder what speed might be possible if implemented with a byte code interpreter.

I started the journey by writing the lexer. A post on Hacker News led me to this video where Rob Pike, of the core Go language team, describes an elegant design for a lexer used in the Go templating library. I was able to extract the relevant bits into a fairly general-purpose library that I then used for this Lisp with relatively little code (of course, one shouldn't expect too much code when lexing a Lisp, since there is not much syntax).

You may have noticed the lack of character strings in the feature table, above. Many interesting Lisp programs don't use traditional strings (arrays of characters encoded as bytes), and I am curious to see what can be done strictly without them, though I could see adding them at some point.

Without strings, one will probably want to manipulate atoms in various ways. As a start, l1 introduces the notion of "splitting" (creating a list from an atom or number) and "fusing" (joining such a list back together again):

> (split (quote greenspun))
(g r e e n s p u n)
> (split 1395871)
(1 3 9 5 8 7 1)
> (fuse (quote (1 2 3 4 5)))
12345
> (randigits 10)
(6 1 5 4 4 8 8 3 0 1)
> (randigits 10)
(2 7 5 4 7 9 1 6 6 1)
> (fuse (randigits 1000))
797522288353215977146173184650097900747324790200919947108552266
896559408664559755127840959435738695979408193086120089317097735
733247509700258597497415541421859295990446300938230591278544826
160148998280910399112793807480556810085222871423786728939605143
312291343715625109027024093962060686621901049553518883581864852
832439160531395519838325036388642484613231265974048363263732041
737675913066537856875008449087672272329301144164887429770199070
521721230755123684155760268379043481645391533460833091119801604
531684362848585264816725347753593965869286499060052823295397069
598147167103689429912992818647290966641807288375144076084638850
885562168375457674623070776900707693203757775691854059277861315
130019383408298242102129643369889134587749005021251080452606062
217504938911721968545635428643266561957454859338694605115003758
001930119736513921576952435852918640253473323143920762789645830
700672642264667728965761815048634636071828415705273836146286590
4892309215088593977646507232497245814663081971549675531
>

As with previous Lisps I've worked on, most of the tests were represented in Go code as strings containing Lisp code and the expressions they evaluate to. Here are some examples, taken more or less at random.

        ...
        // `split` function
        {Cases(S("(split)", "", "expects a single argument"))},
        {Cases(S("(split 1)", "(1)", OK))},
        {Cases(S("(split -1)", "(-1)", OK))},
        {Cases(S("(split -321)", "(-3 2 1)", OK))},
        {Cases(S("(split (quote a))", "(a)", OK))},
        {Cases(S("(split (quote (a b c)))", "", "expects an atom or a number"))},
        {ECases(S("(split (quote greenspun))", "(g r e e n s p u n)", OK))},
        {ECases(S("(split (* 12345 67890))", "(8 3 8 1 0 2 0 5 0)", OK))},
        {ECases(S("(len (split (* 99999 99999 99999)))", "15", OK))},
        {ECases(S("(split (quote greenspun))", "(g r e e n s p u n)", OK))},
        {ECases(S("(split (* 12345 67890))", "(8 3 8 1 0 2 0 5 0)", OK))},
        {Cases(S("(fuse (quote (1 2)))", "12", OK))},
        {ECases(S("(+ 2 (fuse (quote (1 2 3))))", "125", OK))},
        {ECases(S("(fuse (split 1295807125987))", "1295807125987", OK))},
        {ECases(S("(len (randigits 10))", "10", OK))},
        {ECases(S("((lambda (x) (+ 1 x)) 1)", "2", OK))},
        {ECases(
                S("(def incrementer (lambda (n) (lambda (x) (+ x n))))", "<lambda(n)>", OK),
                S("(def inc (incrementer 1))", "<lambda(x)>", OK),
                S("(inc 5)", "6", OK),
                S("(def add2 (incrementer 2))", "<lambda(x)>", OK),
                S("(add2 5)", "7", OK),
        )},
        ...

Here Cases is a utility function that create a local environment (a possibly nested set of variable bindings) and evaluates one or more expressions in that environment; ECases (E for Exemplary) is the same, but saves its test cases in an examples.txt file which stores a reduced set of illustrative cases, e.g. for adding to the README. S is a function which takes an expression to evaluate, the result that should obtain, or an error message fragment which is expected if the expression should fail.

This seems to be a good way to test a new language implementation, though I plan to implement some generative / "fuzzing" tests as well, since I doubt all the bugs have been found yet.

Macros are next. I'm pretty sure I know how I want to do them, and for me the power of macros is the whole point of Lisp, or at least a big part of the point.

To return to the performance discussion, above: a reasonable person might object that l1 is so lean on features, that it's not at all surprising that it starts fast. Clojure, on the other hand, leverages the JVM, which has been tuned for decades for speed in long-running processes, and also provides a thoughtful and comprehensive language design that does many things no hobby language could easily support.

That being said, one thing I am excited about with this project is this: pretty much anything I can do in Go (which is very many things) can be added to my Lisp without too much effort. Conversely, to add features to a Common Lisp or Clojure implementation would be very difficult indeed. Building a small language core that you can extend in a variety of directions is a fun, if not necessarily entirely practical, way to go.