(Yet Another) Lisp In Go

code lisp clojure l1 .....

Later: Tests by Example in Clojure and Common Lisp
Earlier: Migrating, Again

For the past month I've been spending some free time writing another Lisp implementation, this time in Go. My previous attempt was a subset of Scheme made in preparation for a class on the classic Structure and Interpretation of Computer Programs. That project was great fun and I learned a lot.

I started learning Go late last year and began thinking about writing another Lisp. Go has garbage collection, a feature that has long been an essential part of most Lisps1. Getting GC essentially for free would save a lot of time and effort.

Go is also extremely fast. For applications where startup performance is not an issue, I'm pretty happy with Clojure most of the time. But working with Common Lisp in recent years, and Go more recently, has spoiled me and made me hungry for more performance, especially for short-running command-line utilities.

There are obviously other Lisps written in Go already, including Joker, a Clojure interpreter and linter. But I wasn't particularly interested with implementing a particular Lisp dialect; rather, I wanted to try to implement a language core that one could extend in a variety of different directions, including implementing the language in itself. Other possible directions include graphics programming, text-based games, and scripting. The working name of this Lisp is l1 ("el-one"), hinting at a possible series of small, experimental Lisps.


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

l1 has doesn't have will have might get
integers (essentially unlimited size) keywords macros curses
comments (;; ....) maps syntax quote graphics
atoms strings reader macros (`, ', …) subprocess / shells
lists namespaces REPL / editor integration big floats
4 special forms: cond, def, lambda, quote exceptions let (as a macro) error equiv.
16 built-in functions loops defun / defn (as a macro) tail call optimization
closures byte code compilation/interpretation


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))



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)
      (* 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:

Language Running It Execution Time (ms)
Clojure clojure -M fact.clj 1729
Babashka bb fact.clj 200
smallscheme scheme.py fact.scm 120
Common Lisp ./fact 68
Joker joker fact.clj 59
l1 l1 fact.l1 8

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).

Fun With Atoms and Lists

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)))
> (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))


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))},
                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.

Further Work

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.

A Final Note on Performance, and Conclusion

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.


I met a speaker at LambdaJam 2015 who used his own Lisp for music performance. It was not garbage-collected, for real-time performance.

Later: Tests by Example in Clojure and Common Lisp
Earlier: Migrating, Again