Friday, May 09, 2014

writing a tiny register machine interpreter in Go

I was feeling kind of blue at the end of April; it's probably pretty normal in the tail end of a PhD. I thought a good thing to perk me up might be a little Matt Cutts-style month-long challenge!

I thought it would be nice to make myself do some side projects unrelated to my research, so I decided that for the month of May, every day I'd write a little bit of Go! I've been meaning to get good at Go anyway.

The first interesting bit of stuff to come out of this is go-rodrego, a reimplementation of the RodRego register machine, which is basically the tiniest thing that you could imagine being Turing Complete and easy to understand in terms of imperative programs. Dan Dennett uses it to teach philosophy students (and readers of his lovely Intuition Pumps and Other Tools for Thinking) the basics of what it means to do computation.

And the virtual machine they distribute for their class is in RealBASIC and a pain to run on Linux. But now, here's a Go version!

The instruction set is so tiny: it just has "increment register", "decrement register, or failing that, do a conditional branch" and "end program". And that's all you need for it to be Turing Complete.

It's not conceptually hard to implement this interpreter, of course, but it was a nice exercise for getting used to working with the Go standard library and Go ways of doing things.

I'll write more about what I'm learning as the month progresses; there should be a few more potentially-interesting packages. So far the other thing I've been working on has been homeworks from the Functional Programming Principles in Scala class, getting a sense about how it feels to do them in Scala vs Go.

So, for your consideration, amusement, and possibly, edification: go-rodrego.


Chris Martens said...

Hm, I realize that explaining RodRego wasn't exactly the point of your post, but do you know offhand whether it requires an unbounded number of registers in order to be Turing-complete? Or if not, what's the smallest number it needs?

Alex Rudnick said...

I believe it would need an unbounded number, like a Turing machine needs unbounded tape; those registers are the only storage it's got!