I’m keen on learning Go. I’ve kicked around the sample programs and understand the syntax. I can write code that compiles but I’m not yet to the point where I feel comfortable programming it. You could say that I know that grammar but not the idioms.
I’m going to change that by writing a good sized program in Go. I love LISP, so that’s a natural choice for me. Luckily for me, Leo Howell wrote a very nice series of articles on building a LISP interpreter in C. I’ve gone through that and think that I understand it well enough to rework it in Go. There’s enough to it that I should learn how to express myself in Go.
I’m keen on learning Go, so I am building Leo’s interpreter with it. It’s a good opportunity since there’s a lot more to it than the typical “Hello, Universe” examples. Luckily, I understand the interpreter well enough that the challenge will be expressing myself in Go. (Well, I think that I understand it; this will prove it.)
As a bonus, I watched Rob Pike’s lecture on lexing with goroutines, and that looks like a lot of fun to try.
I plan to follow Leo’s outline, so feel free to compare against the original.
Test Driven Development
Leo’s articles include a lot of useful tests, which is great. When I built it, I used them to add tests to it. That’s useful because I was able to make changes to the code and have confidence that I didn’t break something.
Go has native support for testing. I’m using their harness to define the first test case. It’s simple: verify that we have a package named “leo.”
The Go Environment
Let’s set up the Go environment for the program, which I’m naming “leo.”
$ env | grep GOPATH
GOPATH=/Users/quoha/go
$ mkdir -p $GOPATH/leo ; cd $GOPATH/leo
The Test
Note: I’m learning Go, so I’m not sure how best to organize my test cases. I’m taking the easy out and starting with everything in a single file. Later on, if I need to refactor the test cases, then I will.
That file is interpreter_test.go
.
package leo
import (
"testing"
)
func TestLeo(t *testing.T) {
}
Running it shows that we pass.
$ go test -v
=== RUN TestLeo
--- PASS: TestLeo (0.00 seconds)
PASS
ok github.com/quoha/leo 0.004s
Atoms
LISP supports many types of atoms. In this article, I’ll add integers, symbols, the empty list (NIL), and CONS cells (though we’ll call them “pairs”).
I should mention that these aren’t all atoms. Leo called them atoms to make the code simpler. It works. It works well enough to leave be until it doesn’t work.
It shouldn’t be too much work to add other types (like strings) later. (As a bonus, doing so will test out my plans to make atoms an interface so that it’s easy to embed/extend the interpreter (big dreams already).)
By the way, there’s a lovely article about creating “variant structs“ in Go. That’s a future refactor since I don’t have the wisdom to apply it yet.
Integers
We need two bits of data for an atom that is an integer: a type flag saying that it is an integer and the value of the integer.
The Test
Let’s verify that creating an atom from an integer creates the atom correctly. I’m going to start with a test case that I know will fail and then update the code to make it work.
Note: I’m starting AtomType with an upper-case letter, so I’m expecting that my package will export it. I know that’s controversial, but I’m planning on making the package extensible, so I’m starting out with everything exported.
package leo
import (
"testing"
)
func TestLeo(t *testing.T) {
}
func TestMake_Int(t *testing.T) {
i := 42
a := Make_Int(i)
if a.aType != AtomType_Integer {
t.Errorf("Make_Int(%v).aType = %v, want %v", i, a.aType, AtomType_Integer)
}
if a.integer != 42 {
t.Errorf("Make_Int(%v).integer = %v, want %v", i, a.integer, i)
}
}
If you’re not used to TDD, then this is going to seem like a pointless waste of time. I believe that it’s helpful in the long run. If you don’t agree, just skip ahead.
Running the updated test does produce the expected error:
$ go test -v
# github.com/quoha/leo
./interpreter_test.go:12: undefined: Make_Int
./interpreter_test.go:13: undefined: AtomType_Integer
./interpreter_test.go:14: undefined: AtomType_Integer
FAIL github.com/quoha/leo [build failed]
There are compiler failures because the package doesn’t have the function or constants that we’re using.
Let’s write the code to pass the tests.
The Code For Integers
Here’s interpreter.go
. It creates an unadorned struct that holds our bits of data. I created a new type,
AtomType
as a sort of “enum” for what the atom holds. I know that I’ll be replacing that at some point
in the future. Even so, my goal is to make the tests pass and this is the simplest solution makes that happen.
package leo
// based on the articles at www.lwh.jp/lisp
type AtomType int
const (
AtomType_Integer AtomType = iota
)
type Atom struct {
aType AtomType
integer int
}
func Make_Int(i int) Atom {
return Atom{aType: AtomType_Integer, integer: i}
}
Proof of that is in re-running the test case:
$ go test -v
=== RUN TestLeo
--- PASS: TestLeo (0.00 seconds)
=== RUN TestMake_Int
--- PASS: TestMake_Int (0.00 seconds)
PASS
ok github.com/quoha/leo 0.004s
Symbols
Symbols have names. LISP allows pretty much any character in the name, so Go’s UTF-8 support will work nicely.
We’ll also need a new flag to say that the atom holds a symbol.
The Test
As before, I’m creating the test case before writing the code. I’m adding a test case for Go’s iota
. It’s
not needed (I’m not testing the compiler) and could be called bad style since I’m not testing the compiler.
I put it in because I have a habit of sorting enum definitions. Done casually, that can break
the iota constant generator.
I put the test in as a defense against that.
package leo
import (
"testing"
)
func TestLeo(t *testing.T) {
if AtomType_Integer == AtomType_Symbol {
t.Errorf("AtomType_Integer = AtomType_Symbol, want them to be different")
}
}
func TestMake_Int(t *testing.T) {
i := 42
a := Make_Int(i)
if a.aType != AtomType_Integer {
t.Errorf("Make_Int(%v).aType = %v, want %v", i, a.aType, AtomType_Integer)
}
if a.integer != 42 {
t.Errorf("Make_Int(%v).integer = %v, want %v", i, a.integer, i)
}
}
func TestMake_Symbol(t *testing.T) {
s := "foo"
a := Make_Symbol(s)
if a.aType != AtomType_Symbol {
t.Errorf("Make_Int(%v).aType = %v, want %v", s, a.aType, AtomType_Symbol)
}
if a.symbol != s {
t.Errorf("Make_Int(%v).symbol = %v, want %v", s, a.symbol, s)
}
}
Running the test gives the expected compilation errors:
$ go test -v
# github.com/quoha/leo
./interpreter_test.go:8: undefined: AtomType_Symbol
./interpreter_test.go:26: undefined: Make_Symbol
./interpreter_test.go:27: undefined: AtomType_Symbol
./interpreter_test.go:28: undefined: AtomType_Symbol
FAIL github.com/quoha/leo [build failed]
The Code For Symbols
The code for this is very similar to the code for integers. I’m adding a new constant to flag symbols plus a string to hold the name of the symbol.
package leo
// based on the articles at www.lwh.jp/lisp
type AtomType int
const (
AtomType_Integer AtomType = iota
AtomType_Symbol
)
type Atom struct {
aType AtomType
integer int
symbol string
}
func Make_Int(i int) Atom {
return Atom{aType: AtomType_Integer, integer: i}
}
func Make_Symbol(s string) Atom {
return Atom{aType: AtomType_Symbol, symbol: s}
}
And that passes the tests:
$ go test -v
=== RUN TestLeo
--- PASS: TestLeo (0.00 seconds)
=== RUN TestMake_Int
--- PASS: TestMake_Int (0.00 seconds)
=== RUN TestMake_Symbol
--- PASS: TestMake_Symbol (0.00 seconds)
PASS
ok github.com/quoha/leo 0.004s
CONS Cells
Yes, CONS cells aren’t atoms. I’m storing them in the same struct as a matter of convenience. To avoid confusion (and endless diversions), we’re going to call them pairs.
Pairs hold a pair of atoms. Since we’re treating pairs as atoms, pairs can hold other pairs. That’s what enables us to build up lists.
We’ll also need a new flag to say that the atom holds a pair.
The Test
package leo
import (
"testing"
)
func TestLeo(t *testing.T) {
if AtomType_Integer == AtomType_Symbol {
t.Errorf("AtomType_Integer = AtomType_Symbol, want them to be different")
}
if AtomType_Integer == AtomType_Pair {
t.Errorf("AtomType_Integer = AtomType_Pair, want them to be different")
}
}
func TestMake_Int(t *testing.T) {
i := 42
a := Make_Int(i)
if a.aType != AtomType_Integer {
t.Errorf("Make_Int(%v).aType = %v, want %v", i, a.aType, AtomType_Integer)
}
if a.integer != 42 {
t.Errorf("Make_Int(%v).integer = %v, want %v", i, a.integer, i)
}
}
func TestMake_Symbol(t *testing.T) {
s := "foo"
a := Make_Symbol(s)
if a.aType != AtomType_Symbol {
t.Errorf("Make_Int(%v).aType = %v, want %v", s, a.aType, AtomType_Symbol)
}
if a.symbol != s {
t.Errorf("Make_Int(%v).symbol = %v, want %v", s, a.symbol, s)
}
}
func TestMake_Pair(t *testing.T) {
i := 42
s := "foo"
a := Make_Pair(Make_Symbol(s), Make_Int(i))
if a.aType != AtomType_Pair {
t.Errorf("Make_Pair(%v).aType = %v, want %v", s, a.aType, AtomType_Pair)
}
}
Running the test gives the expected compilation errors:
$ go test -v
# github.com/quoha/leo
./interpreter_test.go:11: undefined: AtomType_Pair
./interpreter_test.go:41: undefined: Make_Pair
./interpreter_test.go:42: undefined: AtomType_Pair
./interpreter_test.go:43: undefined: AtomType_Pair
FAIL github.com/quoha/leo [build failed]
The Code For Pairs
package leo
// based on the articles at www.lwh.jp/lisp
type AtomType int
const (
AtomType_Integer AtomType = iota
AtomType_Symbol
AtomType_Pair
)
type Atom struct {
aType AtomType
integer int
symbol string
pair *Pair
}
type Pair struct {
first, rest Atom
}
func Make_Int(i int) Atom {
return Atom{aType: AtomType_Integer, integer: i}
}
func Make_Pair(first Atom, rest Atom) Atom {
p := new(Pair)
p.first, p.rest = first, rest
return Atom{aType: AtomType_Pair, pair: p}
}
func Make_Symbol(s string) Atom {
return Atom{aType: AtomType_Symbol, symbol: s}
}
Coming from C, the Make_Pair
function gives me the willies. In C, we’re returning locals and leaking memory.
Go is garbage collected, though, so we’ll reclaim that memory. Go also returns a valid copy of those locals.
(To be fair, C will copy a struct on the stack, too, so it’s not an issue there, either.)
This passes the tests:
$ go test -v
=== RUN TestLeo
--- PASS: TestLeo (0.00 seconds)
=== RUN TestMake_Int
--- PASS: TestMake_Int (0.00 seconds)
=== RUN TestMake_Symbol
--- PASS: TestMake_Symbol (0.00 seconds)
=== RUN TestMake_Pair
--- PASS: TestMake_Pair (0.00 seconds)
PASS
ok github.com/quoha/leo 0.004s
The Hidden Truth
My initial version of this failed the test badly:
$ go test -v
# github.com/quoha/leo
./interpreter.go:28: cannot assign to p.first
./interpreter.go:28: cannot assign to p.rest
./interpreter_test.go:41: cannot use Make_Symbol(s) (type Atom) as type *Atom in argument to Make_Pair
./interpreter_test.go:41: cannot use Make_Int(i) (type Atom) as type *Atom in argument to Make_Pair
./interpreter_test.go:42: a.aType undefined (type *Pair has no field or method aType)
./interpreter_test.go:43: a.aType undefined (type *Pair has no field or method aType)
./interpreter_test.go:43: too many errors
My C muscle memory was the cause. I’d created the variables as first, rest *Atom
instead of just
plain Atom
. The compiler was nice enough to point out my mistake.
NIL - The Empty List
Last on our list is NIL.
package leo
import (
"testing"
)
func TestLeo(t *testing.T) {
if AtomType_Integer == AtomType_Symbol {
t.Errorf("AtomType_Integer = AtomType_Symbol, want them to be different")
}
if AtomType_Integer == AtomType_Pair {
t.Errorf("AtomType_Integer = AtomType_Pair, want them to be different")
}
}
func TestMake_Int(t *testing.T) {
i := 42
a := Make_Int(i)
if a.aType != AtomType_Integer {
t.Errorf("Make_Int(%v).aType = %v, want %v", i, a.aType, AtomType_Integer)
}
if a.integer != 42 {
t.Errorf("Make_Int(%v).integer = %v, want %v", i, a.integer, i)
}
}
func TestMake_Symbol(t *testing.T) {
s := "foo"
a := Make_Symbol(s)
if a.aType != AtomType_Symbol {
t.Errorf("Make_Int(%v).aType = %v, want %v", s, a.aType, AtomType_Symbol)
}
if a.symbol != s {
t.Errorf("Make_Int(%v).symbol = %v, want %v", s, a.symbol, s)
}
}
func TestMake_Pair(t *testing.T) {
i := 42
s := "foo"
a := Make_Pair(Make_Symbol(s), Make_Int(i))
if a.aType != AtomType_Pair {
t.Errorf("Make_Pair(%v).aType = %v, want %v", s, a.aType, AtomType_Pair)
}
}
func TestMake_Nil(t *testing.T) {
a := NIL;
if a.aType != AtomType_Nil {
t.Errorf("Make_Nil().aType = %v, want %v", a.aType, AtomType_Nil)
}
}
Running the test gives the expected compilation errors:
$ go test -v
# github.com/quoha/leo
./interpreter_test.go:48: undefined: NIL
FAIL github.com/quoha/leo [build failed]
The Code
Our implementation of NIL is simple. It’s a global to the package.
We need to add a new flag to indicate that the atom is NIL, just like we did for the other types.
I put AtomType_Nil
at the top of the constant list to give it the value of zero.
In Go, variables are zeroed out when they’re created, so Atom
s will automatically be initialized to the NIL value.
package leo
// based on the articles at www.lwh.jp/lisp
type AtomType int
const (
AtomType_Nil AtomType = iota
AtomType_Integer
AtomType_Symbol
AtomType_Pair
)
type Atom struct {
aType AtomType
integer int
symbol string
pair *Pair
}
type Pair struct {
first, rest Atom
}
var NIL = Atom{}
func Make_Int(i int) Atom {
return Atom{aType: AtomType_Integer, integer: i}
}
func Make_Pair(first Atom, rest Atom) Atom {
p := new(Pair)
p.first, p.rest = first, rest
return Atom{aType: AtomType_Pair, pair: p}
}
func Make_Symbol(s string) Atom {
return Atom{aType: AtomType_Symbol, symbol: s}
}
That passes all of the test cases:
$ go test -v
=== RUN TestLeo
--- PASS: TestLeo (0.00 seconds)
=== RUN TestMake_Int
--- PASS: TestMake_Int (0.00 seconds)
=== RUN TestMake_Symbol
--- PASS: TestMake_Symbol (0.00 seconds)
=== RUN TestMake_Pair
--- PASS: TestMake_Pair (0.00 seconds)
=== RUN TestMake_Nil
--- PASS: TestMake_Nil (0.00 seconds)
PASS
ok github.com/quoha/leo 0.004s
Next Up
In the next article, we’ll discuss why my implementation of NIL is flawed and we’ll also create a symbol table to hold our symbols.