(Yet Another) Lisp In Go

code lisp clojure .....


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.

Features

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
recursion
closures byte code compilation/interpretation

Performance

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:

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.

Lexing

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

Testing

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.

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.


1

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


Earlier: Migrating, Again