"circlisp" "Lisp in Dart" "Lisp in TypeScript" Japanese

A revised Lisp interpreter in Go

March 18 - September 8, 2016 (鈴)

1. Introduction

In the previous article (in Japanese), I presented a rather big interpreter of Lisp, which was written in Go and organized into several packages. It implemented mixed mode arithmetic including arbitrary-precision integers. It implemented also concurrent computations with goroutines. Here I present a Lisp implementation which is organized smaller again into one file and restricts numbers in Lisp to double precision floating point numbers just like as my Lisp interpreter in TypeScript, while it still enjoys the concurrent computations. It also reflects recent minor revisions of my Lisp interpreter in Dart.

Below is an example to build and execute the Lisp interpreter. Provided that you have installed Go anyway, you can try the Lisp right away without any preparations nor internet connections.
01:~/tmp$ go build lisp-light.go
01:~/tmp$ ./lisp-light
> (+ 5 6)
> (exit 0)

2. Features

Some features of the implementation common to my Lisp interpreters in Dart and TypeScript are:

By the last feature above, you can avoid variable captures in any macro definitions, provided that you use the result of (gensym) for any symbol newly introduced to the expansion result. See the section 5 of my Dart Lisp article.

I believe this feature delivers the ideal behavior for a Lisp-1 Lisp, which has one name space for both variables and functions, to make use of traditional macros. As a benefit of macros being partially hygienic, you can define anaphoric macros [ashahi-net.or.jp] by introducing a symbol (it in the following example) not by using (gensym) insistently to the expansion result.
> (defmacro aif (test then else)
    `(let ((it ,test))
       (if it ,then ,else) ))
> (aif (+ 7 8 9)
     (print it)
    (print "?"))

A feature common to my TypeScript Lisp is:

That is why I call it Light like the implementation before the last. Maybe I should call it Lite, but I followed the usage of Light in the famous Caml Light [inria.fr].
> *version*
(1.42 "go1.7.1 darwin/amd64" "Nukata Lisp Light")

In addition, a feature common to my several Go Lisp since 2013 is:

The following example calculates Fibonacci numbers [oeis.org] concurrently.
It computes (fib (- n 1)) and (fib (- n 2)) in each goroutine separately and adds the results by (+ (force a) (force b)).
> (defun fib (n)
    (if (<= n 1)
      (let ((a (future (fib (- n 1))))
            (b (future (fib (- n 2)))))
        (+ (force a)
           (force b) ))))
> (fib 10)
> (fib 20)
> (fib 30)

3. Inner Representations of Data

The inner representations of data are the same as the previous implementation except for numbers. All numbers are represented by float64. To represent data of the implemented language (Lisp), native types of the implementing language (Go) are used as they are as possible. They are all treated as interface{}.

Lisp Expression Inner Representation
numbers 1, 2.3 float64
strings "abc", "hello!\n" string
t true
nil nil of *Cell
symbols x, + Sym (user-defined)
keywords lambda, cond Sym (Iskeyword flag is true)
lists (x 1 "2"), (y . 3) Cell (user-defined)

Below is the definition of the type Cell.

// Cell represents a cons cell.
// &Cell{car, cdr} works as the "cons" operation.
type Cell struct {
    Car interface{}
    Cdr interface{}

// Nil is a nil of type *Cell and it represents the empty list.
var Nil *Cell = nil

Below is the definition of the type Sym.

// Sym represents a symbol (or an expression keyword) in Lisp.
// &Sym{name, false} constructs a symbol which is not interned yet.
type Sym struct {
    Name      string
    IsKeyword bool

A map is used to intern symbols. Exclusive locking of Lock/Unlock is performed here for the sake of the concurrent computations with goroutines.

// symbols is a table of interned symbols.
var symbols = make(map[string]*Sym)

// symLock is an exclusive lock for the table.
var symLock sync.RWMutex

// NewSym2 constructs an interned symbol (or an expression keyword
// if isKeyword is true on its first construction) for name.
func NewSym2(name string, isKeyword bool) *Sym {
    sym, ok := symbols[name]
    if !ok {
        sym = &Sym{name, isKeyword}
        symbols[name] = sym
    return sym

4. Implementations of some major Lisp functions

The core of Lisp interpreter is represented by the structure Interp. It consists of a map for global variables and an exclusive lock for the map.

// Interp represents a core of the interpreter.
type Interp struct {
    globals map[*Sym]interface{}
    lock    sync.RWMutex

Each built-in Lisp function is defined with the utility function below. The carity argument takes the arity of the function to be defined. If the function has &rest, the carity takes -(number of fixed arguments + 1).

// Def defines a built-in function by giving a name, arity, and body.
func (interp *Interp) Def(name string, carity int,
    body func([]interface{}) interface{}) {
    sym := NewSym(name)
    fnc := NewBuiltInFunc(name, carity, body)
    interp.SetGlobalVar(sym, fnc)

Below is the head of the function NewInterp corresponding to the constructor of Interp. The excerpt shows the implementation of five basic functions of Lisp.

// NewInterp constructs an interpreter and sets built-in functions etc. as
// the global values of symbols within the interpreter.
func NewInterp() *Interp {
    interp := &Interp{globals: make(map[*Sym]interface{})}

    interp.Def("car", 1, func(a []interface{}) interface{} {
        if a[0] == Nil {
            return Nil
        return a[0].(*Cell).Car

    interp.Def("cdr", 1, func(a []interface{}) interface{} {
        if a[0] == Nil {
            return Nil
        return a[0].(*Cell).Cdr

    interp.Def("cons", 2, func(a []interface{}) interface{} {
        return &Cell{a[0], a[1]}

    interp.Def("atom", 1, func(a []interface{}) interface{} {
        if j, ok := a[0].(*Cell); ok && j != Nil {
            return Nil
        return true

    interp.Def("eq", 2, func(a []interface{}) interface{} {
        if a[0] == a[1] { // Cells are compared by address.
            return true
        return Nil

The function dump takes no arguments and returns a list of all global variables. Read-locking with RLock/RUnlock, the implementation of (dump) reads the keys from the map globals held by the Interp object and constructs a list of them.

    interp.Def("dump", 0, func(a []interface{}) interface{} {
        defer interp.lock.RUnlock()
        r := Nil
        for key := range interp.globals {
            r = &Cell{key, r}
        return r
Below is an example of running (dump).
> (dump)
(or caddr *version* / < numberp letrec cdddr cdadr memq setcdr mapcar <= identit
y make-symbol caadr cadr defun apply cons dotimes setcar _append cdar prin1 list
 eq and force * nconc last *gensym-counter* terpri princ stringp cdr if /= print
 when >= eql atom consp caar dump equal not intern gensym - while listp append a
ssq > exit mod length dolist assoc caaar truncate car null = % rplacd cddar cdaa
r cadar + rplaca nreverse member let _nreverse cddr defmacro symbol-name)
Neither setq nor lambda occur here since they are special forms, while defun, defmacro and let occur here since they are global variables bound to macro expressions.

Several functions and macros of Lisp are defined within the initialization script Prelude. It runs in the main function as follows.

// Main runs each element of args as a name of Lisp script file.
// It ignores args[0].
// If it does not have args[1] or some element is "-", it begins REPL.
func Main(args []string) int {
    interp := NewInterp()
    ss := strings.NewReader(Prelude)
    if !Run(interp, ss) {
        return 1
    if len(args) < 2 {
        args = []string{args[0], "-"}
    for i, fileName := range args {
        if i == 0 {
        if fileName == "-" {
            Run(interp, nil)
        } else {
            file, err := os.Open(fileName)
            if err != nil {
                return 1
            if !Run(interp, file) {
                return 1
    return 0

func main() {

Below is the head of Prelude.

// Prelude is an initialization script of Lisp.
// Each "~" is replaced by "`" at runtime.
var Prelude = strings.Replace(`
(setq defmacro
      (macro (name args &rest body)
             ~(progn (setq ,name (macro ,args ,@body))

(defmacro defun (name args &rest body)
  ~(progn (setq ,name (lambda ,args ,@body))

(defun caar (x) (car (car x)))
(defun cadr (x) (car (cdr x)))
(defun cdar (x) (cdr (car x)))
(defun cddr (x) (cdr (cdr x)))

Below is the tail of Prelude. Since "`" cannot occur in a raw string literal of Go, "~" is substituted for it. Each "~" is replaced by "`" at runtime with strings.Replace.

(defmacro dotimes (spec &rest body) ; (dotimes (name count [result]) body...)
  (let ((name (car spec))
        (count (gensym)))
    ~(let ((,name 0)
           (,count ,(cadr spec)))
       (while (< ,name ,count)
         (setq ,name (+ ,name 1)))
       ,@(if (cddr spec)
             ~(,(caddr spec))))))
`, "~", "`", -1)

5. Conclusion

I presented a small Lisp interpreter in Go with almost all the basic features. No files other than a single source file lisp-light.go are needed to build and execute it.

I hope it will be popular as a little more sensible program than "hello world" which can be tried right away without any preparations after the installation of Go.

Copyright (c) 2016 OKI Software Co., Ltd.