Numbo
I finally got around to finishing GEB. I think I bought a copy 10-15 years ago and either gave up or got distracted during a couple of attempts to finish it; at my birthday last year I vowed to complete the thing, and I kept my promise a few months back.
Many of Hofstadter’s then-novel ideas (e.g. perception as the basis of cognition) seem more mainstream nowadays, but I got interested in some projects from his lab (FARG, the Fluid Analogies Research Group) around cognitively plausible architectures operating in microdomains.
A follow-up book, Fluid Concepts and Creative Analogies, goes into these in more detail, and I thought I’d have a go at reimplementing of one of their projects, initially for giggles but then to play with some of the underlying ideas a bit more.
Numbo is a simple number puzzle solver (UK readers: it’s the number puzzle from Countdown): given a set of 5 integers, apply mathematical operations to them to make a 6th target value. Classically a computer scientist might treat this as a search problem, but FARG was more interested in cognitive plausibility. You can find Daniel Defays’ original paper on Numbo here. I’m sure I’ve seen an OCR scan of the original source code at some point, but can’t find it now.
Numbo uses an architecture they called Copycat (from another project, called err Copycat, which investigated analogies like “abc is to pqr as bcd is to…?”). Numbo’s version of the Copycat architecture has 3 parts:
- The Pnet, a network of static information: numbers, operations and basic calculations of a kind a child might learn by rote e.g. 2 + 2 = 4, 7 * 10 = 70.
- The coderack, a store of priority-weighted processes (called codelets) which is sampled from probabilistically, and thus run in a slightly random order, effectively emulating parallelism even when run serially. Codelets operate on the cytoplasm and can create other codelets. They are independent processes and do not communicate with one another directly.
- The cytoplasm, a working memory which is operated on by codelets sampled from the coderack, and stores current theories and constituent numbers.
My implementation is written in Clojure, partly because the original was Common Lisp but more because I enjoy writing Clojure. You can find it here; it can be run from the command-line, or there’s a GUI to help visualize a single run, plus a script which tries to solve each of 10 puzzles 100 times, which I’m using to track the effectiveness of changes I make. Because there’s a lot of random processes underlying Numbo, different runs can and do produce different results - or sometimes no results.
I’ve /just/ managed to get Numbo to a point where it solves 7/10 of the original sample puzzles, which in the spirit of “launching early enough to be embarrassed by my first version” seems like the right time for a push to GitHub. I have some ideas about the remaining 3 and other improvements - I suspect that speedy puzzle-solving is influenced by some of the decisions around decay rates of nodes in the Pnet and cytoplasm. There are a few other jumping-off points for future work:
- The contents of the Pnet are important; I’m interested in working out how you might construct a viable Pnet from e.g. educational materials;
- I wonder how codelets might be evolved rather than hand-coded;
- I wonder how transferable the architecture might be to a new micro domain.
Lots to think about! The process of writing this was also quite fun. It’s the largest program I’ve written since my Master’s dissertation on superoptimization (code, dissertation, paper). A few observations:
- I wrote the cytoplasm 3 times: the first one was too simple, the second too complex (but I got to learn about Clojure zippers) and the third one OK so far - but I think I’ve just found a bug which points to a error in my data model (around how secondary targets are treated)
- Writing a GUI to examine the state of runs was a good move: it’s saved me so a ton of time in debugging, as I can visually run through the evolving state of the cytoplasm, identify odd points by eye and dive in to debug them. Swing is still a PITA, even with Seesaw wrapping it.
- After starting to read Paul Graham’s On Lisp, I regret not having pulled key abstractions beyond library functions into macros. My codelets contain a ton of boilerplate and whilst I pulled out some functions to handle probabilistic sampling, I feel like this could be made into a part of the language a bit more.
- In a lovely demonstration of Conway’s Law, the needs of real life meant I had to write Numbo in tiny non-cooperating chunks which made individual sense. I left messages to future-me on what to do next but otherwise frequently lost state when I returned to work on it. Given all this, I became a set of tiny discrete processes acting towards a greater goal…