Subleq is a one-instruction set computer. That one instruction is to: subtract (and) branch (if) less (than or) equal (to zero)
Let's start at what memory is - essentially a big list of numbers. Real machines are more complicated, but subleq doesn't run on real machines. For us all we care is that we have a list of numbers and each number has a memory address telling us how far along that list it is. So if memory was the list:
9 8 2 15
we'd have a value of 9 at address 0, 8 at address 1,
2 at address 2, and 15 at address 3
Ok, now we have a bunch of numbers in memory, but what can we do with it? We'd like to do some computation on some data, but how do we do that with only numbers?
Instructions are the tasks a machine knows how to do directly. For instance, subtracting numbers. They are key to doing any computation on a machine. You chain together instructions to do more complicated tasks, but can only directly run the instructions a machine knows. When you make a machine, you have to choose what instructions you'll have in what's called an instruction set. For us, we'll be using subleq as our instruction set
When we choose our instructions sets, we also define how we can read numbers from memory and convert them into an instruction. In subleq, we only have one instruction which makes that conversion simpler
An instruction in Subleq could look like this 9 4 15. Uh...
what does that mean?
First, subleq chooses to uses the first two numbers
to do subtraction. The value at memory address 9 (1st number) is subtracted
from the value at memory address 4 (2nd number). Once we compute that we replace the existing value
at address 4 (2nd number) with the subtracted number we computed.
Before we can understand last part, we need to know how instructions are run in general. We keep track of where we are with something called the instruction pointer. It points to the address holding the start of the instruction we're running right now. At the very start, we'll set it to address 0 by convention.
After each instruction we need to choose where to go. What happens after most instructions is that move over by the size of our instruction (3 numbers) to get to the next instruction. But there is another case where we can instead make our instruction pointer go somewhere else
Now for the last part. Subleq looks at the output of our subtraction from the first part of the instruction. If the result is less than or equal to zero, we set the instruction pointer to be the last number in our instruction. If not, we carry on and read the next instruction as normal.
This lets us run different instructions depending on the output of that subtraction, so the code has a branch because it could go to one instruction or to another.
This might seem a little arbitrary, and it kind of is, but you can use this to compute anything you want. The proof of that is a bit beyond this, but it can be done. Is it practical to compute this way? Probably not, but you've already read this far, so let's add more arbitrariness to make it slightly more useful
We have a convention that when the address -1 is subtracted
to, we treat that as an output. We look up the amount we subtracted in a table of characters
(the ASCII table) and use that in our output.
If we ever point the instruction pointer to a negative address, we treat that as the program telling us we want to halt and stop running any more code
Ok, sure maybe we can sort of understand that, but let's see it in practice. Below is a tool where we can step through subleq running any program you want. By default, it's running a program that prints out "Hi " in an infinite loop. You can enter a new program by typing in a new list of starting memory values at the bottom and hitting enter
To make it easier to understand what's going on, we highlight and underline the memory values with a color coding system. The instruction itself is highlighted in green and yellow. In green for the subtraction part, yellow for the branch part
The blue text is the address we'll subtract. The orange text points to the address we subtract the other value from. The underlined portions are the values at those addresses and match the colors used in the instruction. The yellow underline, similarly is the place we'll go to if our subtraction is less than or equal to 0