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 simulator in Clojure rather than Scheme. Immutable data structures and higher-level concepts available to us in Clojure compressed the solution, to the point where 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:
Let’s see if we could build factorials using physical devices.
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. Conversely, the incoming charge "b" is "on", but the bulb is off. If our device can do this, it means that whatever the charges for the light bulbs are inside 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”, and the light bulb "b" changed from "off" to "on".
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:
Now, if we hooked those outgoing charges to some other device, that device would receive the “number” that was stored in this one.
Registers
What we just described is analogous to a computer’s register (1). Registers let us store and share information.
Now, we could use three registers to store the value of rescounter and n.
B: Adding Numbers
Next up, we’ll need a device that that can “add” two registers. Imagine a device that had two register’s worth of incoming wires, and one register’s worth of outgoing wires:
Adder
If the device could connect those incoming wires in such a way, that the outgoing wires represented the “addition” of those registers, we’d have an “adder” device!
In the example above, the left register represents “10101” (21), and the right represents “00001” (1). The output wires are charged as “10110”…which represent 22!
C: Multiplying numbers
Similarly, we could have a device that has two register’s worth input wires, and one register’s worth of output wires:
Multiplier
If we could connect the incoming wires in such a way, that the outgoing wires represent the result of a multiplication, boom we would have a multiplying device!
The left register above represents “00101” (5), the right register represents “00010” (2), and the charge of the outgoing wire is “01010” (10). Nice! That gives us a multiplier machine.
Comparator
We need one more device. Imagine a device that takes two register’s worth of input wires, and only has one output wire:
If we could combine the input wires in such a way, that the output wire was “on” when the left register was bigger, and off otherwise, we could use this as a comparator machine!
E: Data Paths
If we had all these machines, we can wire them in such a way, that lets us compute factorials:
Here, we wired the output wires of res and counter to the * machine. We wired the output wires of the * machine, to be the input wires of res.
This way, if we press “A”, we would “store” the result of multiplying counter with res!
Similarly, we wired up the output wires of counter and a register that keeps the value 1, to the + machine. We wired the output wires of the + machine, to be the input wires of counter.
Now, If we pressed “B”, counter would be stored with the result of adding 1!
Next up, we also wired up counter and n with the > machine. If we hooked up a light bulb to the output wire of the > machine for example, then whenever it was on, we would know that counter was larger than n.
We’ve just drawn out the “data path” of our machine.
Imagine if we had our “data path” machine. What would happen if we followed the following recipe:
Take a look at the output of the > machine.
If the light bulb connected to the > machine is on, stop
Otherwise…
"Press A". This will update res with the result of the * machine on res and counter
“Press B“. This will update counter with the result of the + machine on 1 and counter
Go back up to the start of the recipe
If we did this over and over again, once the light bulb connected to the output of the>machine turns on,reswould contain the result of factorial!
Automation
Pretty cool, but this kind of manual work would be annoying. If you look at these instructions though, there’s a pretty significant insight: all of those instructions are simple: "look at charge of light bulb", "press button..."
In fact, they’re so simple that we could wire up a machine that goes through that recipe! Imagine if we created a machine that could “press” buttons for us, depending on whether the output wire of the > machine is on:
We would be able to automate computing factorials 🙂
Balls and Hills
Now, at this stage, you may be wondering: exactly how would * produce output wires that represent the multiplication? How would + work, and how would the controller move along?
If you think about it, these can all be reduced to very simple machines. They don’t even necessarily have to be electronic:
Imagine you had a ball rolling down some hill. You could construct something like the > machine, by putting res and counter on a scale: based on what’s bigger, the ball would take a different path
With sufficient energy, space, time, and ingenuity you really could build all of this with a ball on a hill. Now, you wouldn’t necessarily do that (2), but you can imagine how the electronic parts that make up our machines are similarly simple, logical machines: turn on if off, turn off if on, etc. These logical machines are called “logic gates”. You can look them up, but hopefully I’ll have an essay for you about these machines soon 🙂.
Language Simulation
Now, we drew out our machine and saw how we could build them with simple devices. How could we simulate these machines?
To simulate these machines, we need to transform our picture descriptions into something that computers can manipulate. Computers can manipulate text much better: let’s create a language for describing these machines.
If we remember the pictures again:
we could transform them into a language that looks like this:
When the test instruction runs, we run the > machine with counter and n.
Our branch instruction checks if the test instruction said yes. If it did, it moves to done. Otherwise it no-ops and the machine moves forward by one.
After that, our (assign res expression is analogous to “press A”. (assign counter is analogous to “press B”, and (goto (label start) is analogous to the arrow bringing us back to the start.
With this textual representation, we can build an interpreter and simulate our machine. Let’s do this!
0: Machine State
What does the state of our machine look like in Clojure? Well, how do we represent most things in Clojure? With maps! Let’s represent the state of our machine as a map:
When our simulator sees these instructions, it’ll need to look up the machine that corresponds to the op, and run it with the primitive arguments that were provided.
We now have a idx state, that tracks the machine’s current index in the instruction list. This will let us “move” forward, by simply incrementing the index.
Remember that when test runs, we need to figure out whether the op returned a yes or no, and we move the machine forward. When branch runs, we need to see if the last test instruction said yes. If it did, we jump to the branch destination. Otherwise we no-op and move the instruction list forward by one.
To implement this, we need to evolve our machine state one final time:
But we require label→idx mapping. For these indexes to make sense, we’ll also want some representation of just the executable instructions. Let’s write those:
Once we have these…we are ready to put it all together.
10: loop
Okay, exec can take a machine-state and an instruction, then return a whole new machine state. extract-label→idx can create our label→idx mapping, and extract-instructions can provide us with just the executable expressions.
We take in a registry, an op-map, and some raw instructions. After that, we run in a loop, executing the instruction, based on the idx, and return when idx no longer returns an executable instruction.
Wow, that was a journey. Hope you had fun! 🙂. If you’d like to see the whole thing, take a look at the github repo.
Up for a challenge? Try implementing a few other machines: fibonacci sequences, exponentiation, etc. Try writing the recursive version of these algorithms: to do that, you’ll need a stack construct in our machine-state, and a (save <reg-name>)(restore <reg-name>) instruction. After that, heck you could implement a lisp evaluator!
If this kind of stuff interests you, reach out on twitter or email — am always happy to chat with like-minded hackers 🙂
Thanks to Joe Averbukh, David Magaltadze, Ian Sinnot, Raghavan Lakshmana for reviewing drafts of this essay.
(1) Computer registers also have an enabler, but I decided not to include that in the essay. I didn’t think it was necessary to grasp the essence. I plan on writing another essay that would go lot deeper : )
(2) The maximum speed you could probably get on a ball is ~200 km / hour, while light travels 300 000 km… in one second. You can imagine how this kind of speed can change the game: from making calculating machines impractical to producing iphones.
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 simulator in Clojure rather than Scheme. Immutable data structures and higher-level concepts available to us in Clojure compressed the solution, to the point where 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:
Let’s see if we could build factorials using physical devices.
A: Storing Numbers
Well, we need a way to keep track of
counter
,res
, andn
. 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. Conversely, the incoming charge "b" is "on", but the bulb is off. If our device can do this, it means that whatever the charges for the light bulbs are inside 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”, and the light bulb "b" changed from "off" to "on".
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:
Now, if we hooked those outgoing charges to some other device, that device would receive the “number” that was stored in this one.
Registers
What we just described is analogous to a computer’s register (1). Registers let us store and share information.
Now, we could use three registers to store the value of
res
counter
andn
.B: Adding Numbers
Next up, we’ll need a device that that can “add” two registers. Imagine a device that had two register’s worth of incoming wires, and one register’s worth of outgoing wires:
Adder
If the device could connect those incoming wires in such a way, that the outgoing wires represented the “addition” of those registers, we’d have an “adder” device!
In the example above, the left register represents “10101” (21), and the right represents “00001” (1). The output wires are charged as “10110”…which represent 22!
C: Multiplying numbers
Similarly, we could have a device that has two register’s worth input wires, and one register’s worth of output wires:
Multiplier
If we could connect the incoming wires in such a way, that the outgoing wires represent the result of a multiplication, boom we would have a multiplying device!
The left register above represents “00101” (5), the right register represents “00010” (2), and the charge of the outgoing wire is “01010” (10). Nice! That gives us a multiplier machine.
Comparator
We need one more device. Imagine a device that takes two register’s worth of input wires, and only has one output wire:
If we could combine the input wires in such a way, that the output wire was “on” when the left register was bigger, and off otherwise, we could use this as a comparator machine!
E: Data Paths
If we had all these machines, we can wire them in such a way, that lets us compute factorials:
Here, we wired the output wires of
res
andcounter
to the*
machine. We wired the output wires of the*
machine, to be the input wires ofres
.This way, if we press “A”, we would “store” the result of multiplying
counter
withres
!Similarly, we wired up the output wires of
counter
and a register that keeps the value1
, to the+
machine. We wired the output wires of the+
machine, to be the input wires ofcounter
.Now, If we pressed “B”,
counter
would be stored with the result of adding1
!Next up, we also wired up
counter
andn
with the>
machine. If we hooked up a light bulb to the output wire of the>
machine for example, then whenever it was on, we would know thatcounter
was larger thann
.We’ve just drawn out the “data path” of our machine.
F: Controller
Manual Recipe
Let’s remember our code for factorial:
Imagine if we had our “data path” machine. What would happen if we followed the following recipe:
>
machine.>
machine is on, stopOtherwise…
res
with the result of the*
machine onres
andcounter
counter
with the result of the+
machine on1
andcounter
If we did this over and over again, once the light bulb connected to the output of the
>
machine turns on,res
would contain the result of factorial!Automation
Pretty cool, but this kind of manual work would be annoying. If you look at these instructions though, there’s a pretty significant insight: all of those instructions are simple: "look at charge of light bulb", "press button..."
In fact, they’re so simple that we could wire up a machine that goes through that recipe! Imagine if we created a machine that could “press” buttons for us, depending on whether the output wire of the
>
machine is on:We would be able to automate computing factorials 🙂
Balls and Hills
Now, at this stage, you may be wondering: exactly how would
*
produce output wires that represent the multiplication? How would+
work, and how would thecontroller
move along?If you think about it, these can all be reduced to very simple machines. They don’t even necessarily have to be electronic:
Imagine you had a ball rolling down some hill. You could construct something like the
>
machine, by puttingres
andcounter
on a scale: based on what’s bigger, the ball would take a different pathWith sufficient energy, space, time, and ingenuity you really could build all of this with a ball on a hill. Now, you wouldn’t necessarily do that (2), but you can imagine how the electronic parts that make up our machines are similarly simple, logical machines: turn on if off, turn off if on, etc. These logical machines are called “logic gates”. You can look them up, but hopefully I’ll have an essay for you about these machines soon 🙂.
Language Simulation
Now, we drew out our machine and saw how we could build them with simple devices. How could we simulate these machines?
To simulate these machines, we need to transform our picture descriptions into something that computers can manipulate. Computers can manipulate text much better: let’s create a language for describing these machines.
If we remember the pictures again:
we could transform them into a language that looks like this:
When the
test
instruction runs, we run the>
machine withcounter
andn
.Our
branch
instruction checks if thetest
instruction saidyes
. If it did, it moves todone
. Otherwise it no-ops and the machine moves forward by one.After that, our
(assign res
expression is analogous to “press A”.(assign counter
is analogous to “press B”, and(goto (label start)
is analogous to the arrow bringing us back to the start.With this textual representation, we can build an interpreter and simulate our machine. Let’s do this!
0: Machine State
What does the state of our machine look like in Clojure? Well, how do we represent most things in Clojure? With maps! Let’s represent the state of our machine as a map:
registry-map
could keep a mapping of registers to values.label→idx
could keep a mapping of labels to theiridx
in the instruction list1: primitive
With this, we can get the most foundational part of our language to work: We use
(const…
(reg...
and(label…
all over the place.(const 1)
, it should return the actual value1
(reg foo)
, it should look up whatever is in thefoo
register, and return that(label foo)
, it should return the correct index in our instruction list.Let’s write this out in Clojure:
Our
parse-primitive
function takes the machine-state, and does the right thing based on thetag
of the expression.2: operation
Okay, we have primitives working, let’s move up a level. Our simulator gives us access to some other machines, like
*
+
and>
When our simulator sees these instructions, it’ll need to look up the machine that corresponds to the
op
, and run it with the primitive arguments that were provided.To do this, let’s evolve our machine-state:
We’ve now introduced
op-map
. This mapsop symbols
to these other machines.Now we could implement a function that parses operations:
And with that, our simulator can run operations:
3: assign
Now it’s time to move up even higher, and start implementing our actual instruction expressions.
Let’s start with assign. Assign has two forms. We can either assign a primitive value:
Or the result of an operation:
Once assign completes, our machine state needs to “move forward” to the next instruction.
To implement assign, we need to evolve our machine state again:
We now have a
idx
state, that tracks the machine’s current index in the instruction list. This will let us “move” forward, by simply incrementing the index.Here’s how assign can look:
And badabing badaboom, assign works as we expect:
Note how
counter
changed, andidx
moved up by 14: goto
Next up, let’s make
goto
work:(goto <primitive-exp>)
should set theidx
in our machine to the resulting value of a primitive expression:Easy peasy:
idx
was set to the value ofdone
.5: test-passed?
We are so close! Next up, let’s consider the
test
andbranch
instruction:Remember that when
test
runs, we need to figure out whether theop
returned ayes
orno
, and we move the machine forward. Whenbranch
runs, we need to see if the lasttest
instruction said yes. If it did, we jump to thebranch destination
. Otherwise we no-op and move the instruction list forward by one.To implement this, we need to evolve our machine state one final time:
test-passed?
keeps track of the result of atest
instruction.6: test
With that, we can implement
test
:And bam:
the machine’s
test-passed?
state is is set to the value of the operation.7: branch
We can also implement
branch
:Let’s try it out:
When
test-passed?
was true,idx
was set to the value ofdone
8: exec
We’ve now implemented all the instructions we need to make our factorial machine work. Let’s create a function that puts them all together:
Now, we can use this function to
route
to the right instruction:9: extract instructions
Oh boy, Okay, we are ready to go…almost!
Now, remember we started out with a language that looks like this:
But we require
label→idx
mapping. For theseindexes
to make sense, we’ll also want some representation of just the executable instructions. Let’s write those:Here’s what our factorial instructions would return:
Once we have these…we are ready to put it all together.
10: loop
Okay,
exec
can take a machine-state and an instruction, then return a whole new machine state.extract-label→idx
can create ourlabel→idx
mapping, andextract-instructions
can provide us with just the executable expressions.Let’s put it all together:
We take in a registry, an op-map, and some raw instructions. After that, we run in a loop, executing the
instruction
, based on theidx
, and return whenidx
no longer returns an executable instruction.Let’s try it out!
…You’ve just made your own machine simulator!
Fin
Wow, that was a journey. Hope you had fun! 🙂. If you’d like to see the whole thing, take a look at the github repo.
Up for a challenge? Try implementing a few other machines: fibonacci sequences, exponentiation, etc. Try writing the recursive version of these algorithms: to do that, you’ll need a
stack
construct in our machine-state, and a(save <reg-name>)
(restore <reg-name>)
instruction. After that, heck you could implement a lisp evaluator!If this kind of stuff interests you, reach out on twitter or email — am always happy to chat with like-minded hackers 🙂
Thanks to Joe Averbukh, David Magaltadze, Ian Sinnot, Raghavan Lakshmana for reviewing drafts of this essay.
(1) Computer registers also have an
enabler
, but I decided not to include that in the essay. I didn’t think it was necessary to grasp the essence. I plan on writing another essay that would go lot deeper : )(2) The maximum speed you could probably get on a ball is ~200 km / hour, while light travels 300 000 km… in one second. You can imagine how this kind of speed can change the game: from making calculating machines impractical to producing iphones.