Skip navigation

Monthly Archives: February 2010

I’ve just got a Lisp (well, Lisp or Scheme, or somewhere in between) interpreter that I wrote in Go to a stable state. It doesn’t have very many features and it’s hardly documented at all. It’s also, most likely, full of bugs. You can grab it here. This post will briefly summarise some of my experiences in writing the thing.

Defining the basic behaviour is quite straightforward, and requires significantly less ceremony than many other languages, particularly static ones. The type system, in particular, is quite friendly to this task. For instance, defining an environment (a mapping from symbols to values) is as simple as

type Environment map[Symbol] Any

where symbols are just aliases on strings, and Any is an alias for the empty interface. Not bad, although to get the full behaviour for lexical scoping, some mechanism of threading environments together had to be found. I came up with a Context object, that links an environments to a “parent” environment. Then looking up a symbol is a breadth-first search through this structure. When Lisp manipulates environments, it is actually affecting Context objects. The Context type doubles as an interpreter: creation via NewContext is for threading environments together, while creation via New creates a Context that can be used as an interpreter.

Of course, functions are a crucial part of any Lisp system. Anything that follows the Function interface can be called by Lisp:

type Function interface {
    Apply(args Any) Any

The args parameter there is a list.

Two such types are provided. There is a Primitive type, that’s just a function with the same signature as that Apply method. There is also a closure type, which is not directly accessible from outside the library, and is created by lambda expressions within the language. A function, WrapPrimitive, takes a function that could take up to five arguments, and returns a Primitive object that parses the arguments passed in as well as some basic error checking. A WrapPrimitives function takes a map from strings to such functions, and returns an Environment object. The primitives.go file demonstrates how pleasant these two functions make writing primitive functions for this Lisp system. Functions created by lambda expressions are tail-recursive.

I defined the syntax in terms of two other libraries I had written, a simple Thompson NFA (à la grep or awk) and a PEG parser. This made the description of the syntax feel quite declarative. It certainly felt easier to write than previous forays into parsing Lisp expressions. Given how easy they are to parse, that means it was pretty darned easy. A few things are missing, like the quoting shorthand syntax. Evaluation proceeds in two steps: there is an expansion step, where applicable macros are executed (note: this is currently untested) and an eval step, which is a pretty naïve interpreter design. There are seven built-in syntactic forms: quote, if, lambda, set!, define and begin. I believe the rest can be implemented in terms of the language itself, but we’ll see. I haven’t yet written a standard library for it, to make programming in it even vaguely pleasant.

So far, of the things people seem to moan about most about Go, I haven’t missed generics at all, and exceptions only slightly. Having to manually check if an error has been raised all the time does get tiresome, but honestly the rest of the language more than makes up for their absence. I essentially added exceptions into the Lisp interpreter, which sounds OK, but compared to conditions/restarts or continuations are a bit humble really. When I tested out recursion not in tail position, I was greeted with lots of paging, rather than any error informing me that I’d blown the stack, so I may need to add that in manually as well.

Go is a pretty good language to write an interpreter for a dynamic language in. Given that it has garbage collection, first-class functions, a hashmap type and support for dynamic types built-in, you’re off to a running start.