The world’s leading publication for data science, AI, and ML professionals.

Build a One Instruction Set Computer (OISC) on a Spreadsheet

Excel Fun: Let's see how a spreadsheet can simulate a whole computer at the instruction set level

Photo by Pineapple Supply Co. on Unsplash
Photo by Pineapple Supply Co. on Unsplash

In Data Science we often use a spreadsheet to analyze data and prototype algorithms, but what else can a spreadsheet do? Let’s see how a spreadsheet can simulate a whole computer at the instruction set level.

How many instructions must we support? Well, Intel x86 chips (used by most PCs) understand 1500 instructions. ARM chips (used in most phones, tablets, and in new Macs) reduce that number to about 50. A workable computer, however, can be made from just one instruction called SUBLEQ. We’ll use Excel to see how this can work. (Here is the the complete spreadsheet on OneDrive.)


A typical computer chip offers instructions to

  • load and copy values in a memory locations
  • compare values in two memory locations,
  • jump to new section of memory and start evaluating instructions there.
  • do math operations such as addition and multiplication on integers, floating-point numbers, and sometimes even arrays of numbers

Some computer chips offer instructions to do even more, for example, instructions related to AI, 3D graphics, cryptography.

But instead of adding more instructions, what if we remove instructions? How few instructions can we get away with? Computer Scientists, including Oleg Mazonka and Alex Kolodin, say the answer is one. Mazonka and Kolodin recommend choosing SUBLEQ to be that one instruction because it

"is the oldest, the most popular and, arguably, the most efficient [one instruction set computer]"[A Simple Multi-Processor Computer Based on Subleq (arxiv.org)

SUBLEQ

The SUBLEQ instruction contains three parts:

  • the memory location of A, the value to subtract away
  • the memory location of B, the value from which to subtract A
  • the memory location to jump to if B ends up less than or equal to 0. If B is positive, we jump 3 memory positions forward.

Let’s look at an example in Excel based on Subleq – Esolang (esolangs.org). We put the numbers 3,5,6,7,7,7,3,4,0 into memory.

A computer’s instruction pointer points to the memory location of the next instruction to execute. Suppose our instruction pointer points to memory location 0, so the computer looks at the three values, starting at memory location 0, namely 3, 4, and 6. This means 3 is the memory location of A, the value to subtract away and that value is 7. Moreover, 4 is the memory location of B, the value from which to subtract A. That value starts at 7, but will become 0 after subtracting A. Finally, 6 is the memory location to jump to if B becomes 0 or less which it does, so the instruction pointer will become 6.

Setting Up Excel

In Excel, let’s add this:

We want to be able to set the instruction pointer to any memory location and have Excel fill in the rest of this table. How is that possible? Here is the formula I use for part1:

=INDIRECT(ADDRESS(ROW(D19)+D9,COLUMN(D19)))

where D9 is the cell of the Instruction Pointer and D19 is the cell of memory location 0. The formula says to find the value Instruction Pointer rows down from the start of memory. Since the Instruction Pointer is 0, this finds memory location 0, which contains value 3. The formula for part2 is the same except we add 1 to the row. For part3 we add 2. The formula for A is almost the same, namely:

=INDIRECT(ADDRESS(ROW(D19)+D10,COLUMN(D19)))

where D10 is the cell for part1. So, this says to find the value part1 rows down from the start of memory. That is memory location 3, which contains 7. For B we use the A formula but with D11 instead of D10. Finally, of course, the value of the B-A cell is just the value of the B cell less the value of the A cell.

Moving Forward

The next problem is how do we update the Instruction Pointer and B with their new values? We could imagine turning off Excel’s Recalc setting, changing their values in place, and then using the F9 key to step the program forward. I didn’t do that. Instead, I created a new column for the next step of the program. I call the original step of the program "Step 0" and the next step "Step 1".

The spreadsheet looks like this.

Yellow shows user inputs (the original memory values and Instruction Pointer). Notice, in step 1, the change in the Instruction Pointer and the value in memory position 4 (shown in red). The formula for the new value of the Instruction Pointer is:

=IF(D9<0,D9,IF(D15<=0,D12,D9+3))

where D9 is the old value of the Instruction Pointer, D15 is the value of B-A and D12 is the part3 of the previous instruction. This says:

  • If the instruction pointer is negative, keep it the same (signaling that the program is done).
  • Otherwise, if B-A is less than or equal to 0, set the Instruction Pointer to part3.
  • Otherwise, increase the Instruction Pointer by 3.

The formula for the new value of memory location 4 is

=IF($C23=D$11,D$15,D23)

where C23 is the cell containing the location number, namely 4. The cell D11 is part2. The cell D15 is B-A. The cell D23 is the previous value in this memory location. So, this says: If this memory location is the previous step’s B, then set its value to B-A, otherwise keep the value the same. All the memory locations get an analogous formula.

We can copy the column for step 1 to the right to get columns for any number of future steps (up to Excel’s limit of about 16,000). We can copy the last memory row down to get locations for any amount of memory (up to Excel’s limit of about 1,000,000).

Hello World!

One last big issue remains: How do we output anything? By convention, SUBLEQ creates output by writing a number to special memory address -1. We can interpret that number as an ASCII character. Here is an example from Subleq – Esolang (esolangs.org) that outputs "Hi":

At step 0, the Instruction Pointer says start at memory location 0, which gives us 9, -1, 3. Because the second number is -1, this means output the value at memory location 9, namely 72, and then set the Instruction Pointer to 3. ASCII 72 is the character "H".

At step 1, the Instruction Pointer says start at memory location 3, which gives us 10, -1, 6. This means output the value at memory location 10, namely 105 (ASCII for "i") and set the instruction pointer to 6.

At step 2, the Instruction Pointer says start at memory location 6, which gives us 0, 0, -1. That means subtract the value at memory location 0 (namely, 9) from itself and set the Instruction Pointer to -1.

At step 3, the Instruction Pointer says start at -1, which is a negative number, so the program is done.

To support output, I made these changes to the spreadsheet:

  • Added memory location "-1". Its formula for step 1 is =IF(D11=-1,D13,"") which says if part2 is -1, then output A, otherwise be blank.
  • Added an Output row below B-A. It is just the ASCII version of the memory location -1. Its formula for step 1 is =IF(E18<>"",CHAR(E18),"") which says if memory location -1 is not blank, display its ASCII value, otherwise be blank.
  • Change the formula for B-A to =IF(E9<0,"HALT",IF(E11>=0,E14-E13,E13)) which says 1) if the Instruction Pointer is less than 0, display "HALT", 2) if the memory location for A is at least 0, subtract A from B, 3) otherwise, be B. I also changed the formulas for part1, part2, part3, A, and B to display "HALT" when the Instruction Pointer is negative.

With this in place, we can run more interesting SUBLEQ programs. For example, the "Hello World!" example from Subleq – Esolang (esolangs.org) uses a loop to copy the desired string to output and stops when it reaches the end of the string. Here is the top corner of the spreadsheet. You can see the "H" and the "e" in the output row.

Find the the full spreadsheet on OneDrive. On the web or after downloading, you can play with the spreadsheet. You can also put in your own SUBLEQ programs or see what happens if you change the initial Instruction Pointer value.

Discussion

Implementing SUBLEQ on a spreadsheet lets us see how a computer chip can be designed with just one instruction. Demonstrating SUBLEQ in a more conventional language, say Python, would have been easier, but the spreadsheet offers two bonuses:

  • First, putting each step of the computation into its own column lets us see a program in a new way. Instead seeing the program and computer as a one-dimensional vector that changes over time, we can see the whole history of a program as a two-dimensional array.
  • Second, we can change a single input cell and Excel will efficiently update only those cells that need to change. For example, in the full "Hello World!" example, change the initial Instruction Pointer from 0 to 1. Surprisingly, the program still works. Change it to 3 and you’ll see that not only does the program still work, but it even runs a little faster.

If you’d like more Excel Fun, please see my article Excel Fun – Build 3D graphics from a spreadsheet – Microsoft 365 Blog. I show how to implement and understand 3D graphics. You can interactively rotate a square and cube just by changing spreadsheet values.


Related Articles