My cofounder Joe and I recently finished SICP. It was a mind-bending experience: you start from just 3 concepts, and you recursively build up algebraic equation solvers, circuit simulators, 4 interpreters, and a compiler.
At some point you experience a visceral feeling: If you were dropped in a forest…you could create your own computer. The project that contributed most significantly to this feeling was creating a machine simulator.
We diverged from the book by writing the simulating in Clojure rather than scheme. Immutable data structures and higher-level concepts available to us in Clojure compressed the solution, to the point that I think you can build your own in a few days worth of hacking.
This essay will guide you through doing just that: let’s build a machine simulator, over a good few days worth of hacking! I hope this inspires you to play with Clojure and to take a deeper look at SICP.
Concrete Machine
Before we simulate general machines, let’s think about a concrete machine. How could we create a machine that could figure out factorials?
If we were writing code, factorial could look something like this:
(defn factorial [n]
(loop [res 1
counter 1]
(if (> counter n)
res
(recur
(* counter res)
(inc counter)))))
Let’s see if we could build a physical devices that computes factorials.
A: Storing Numbers
Well, we need a way to keep track of counter, res, and n. To do that, we’ll need a device that stores information.
Bulbs
Imagine a device that has some light bulbs inside of it.
We can say that if a light bulb is on, that represents the number 1, and if a light bulb is off that represents the number 0.
If we had a bunch of light bulbs in the device, we could interpret the state of these bulbs as larger and larger binary numbers. The light bulbs in the device I just showed you for example, would represent“10101”, which is binary for“21”.
Incoming Current
Now, imagine that at all times there are a bunch of other wires connected to this device. These wires carry“new” charges for the light bulbs, but with a twist: the incoming charges do not affect the light bulbs inside just yet.
Notice how the incoming charge for the“a” light bulb is“off”, but the bulb inside is still on. If the device can do this, it means that whatever the charges for the light bulbs are inside the device is a stored value. Very cool!
Save
Now, we need these incoming wires to do something at some point. What if this device had a“save” button.
Once we pressed“save”, the incoming current would transfer inside the box:
Here, light bulb“a” changes from“on” to“off”.
Great, now we have a way to“save” new numbers inside!
Outgoing current
We also need a way to share the state of what’s inside to other devices. All we’d need to do to make that work, is to have a bunch of wires that leave our device, which carry the sames charges as the light bulbs:
Concrete Machine
(defn factorial [n] (loop [res 1 counter 1] (if (> counter n) res (recur (* counter res) (inc counter)))))A: Storing Numbers
Bulbs
Incoming Current
Save
Outgoing current