Skip navigation

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.

About these ads

7 Comments

  1. When you say you tested recursion I’m assuming you caused your Go program to recurse. If yes, then the reason you encountered paging is because Go uses a stack chaining strategy that places stack blocks on the heap. This is primarily to make it possible to have very small stacks for individual goroutines but a side effect is that your total stack size is equal to your heap size..

    • I suspected it could be something like that. Thanks for the info.

  2. It seems your repository misses a few files.

    • Peter, yes it does, although they are all publicly available. I’ll add a README that will tell you how to compile it.

  3. Informative and interesting writeup. Thanks!

  4. Are you building against the latest commited revision of the bwl libs, or some other version?

    The current version looks unbuildable.

    • The just pushed version. Sorry!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: