Programming journey

SBNZ, a single instruction virtual machine for fun

I have always loved playing with programming languages, compilers, and interpreters. One of my favorite languages to play with is a single instruction assembly language called SBNZ. In this programming journey, we first implement a virtual machine for SBNZ and then explore the power of the language.

If you would like company on this journey, I streamed my implementation live, follow this link to watch the video from that: https://www.youtube.com/watch?v=N2Kkk2sdpXI

In order to have a programming language, we need to have a machine that can execute code. Therefore we start by making our own machine, a virtual machine. A virtual machine takes code as input and outputs the memory layout after executing the code.

The machine we want to implement has only a single instruction: Subtract and Branch if Not Zero (SBNZ). This virtual machine works on memory locations (or cells). The SBNZ instruction takes 4 arguments, SBNZ a b c d, it subtracts the content of cell a from the content of cell b and stores the result in cell c. If the result is not zero it jumps to the instruction at position d, otherwise just go to the next instruction. We could write it is:

[c] <- [b] - [a]

To terminate a program we just jump to a position outside the memory. For this demonstration, I have 1024 cells in my memory. Therefore jumping to cell 1024 terminates the program.

An SBNZ program could look like this:

SBNZ [5] 1023 1023 4
SBNZ [0] [1] [1] 1024

This program subtracts 5 from what is in cell 1023 (the last cell), and stores the result in cell 1023. If that is zero it goes to the next instruction, otherwise it “jumps” to location 4, which is also the next instruction. The second instruction subtracts 0 from 1 and stores the result where 1 is because 1–0 is not zero it then jumps to cell 1024.

When we write [a] we really mean a cell that contains a. This means that the program actually would be:

SBNZ 10 1023 1023 4
SBNZ 8 9 9 1024
0 1 5

Notice that because our machine only has one instruction there is no need to write it. The final SBNZ program becomes:

10 1023 1023 4 8 9 9 1024 0 1 5

Exercise 1. Read a file containing up to 4x1024 numbers separated by spaces. Store these numbers in an int array of size 4x1024.

Exercise 2. Execute the solution to exercise 1 as an SBNZ program.

Exercise 3. Output the final memory to a file.

Exercise 4. Finish this SBNZ program:

SBNZ [5] [42] 1023 4
SBNZ [0] [1] [1] 1024

Exercise 5. Finish this SBNZ program:

SBNZ [1] [5] [5] 4
SBNZ [1] [5] [5] 8
SBNZ [1] [5] [5] 12
SBNZ [0] [1] [1] 1024

In the previous exercise we used the cell containing 5 as a variable, we can expand this principle:

Exercise 6. Finish this SBNZ program:

SBNZ [0] [5] [a] 4
SBNZ [1] [a] [a] 8
SBNZ [1] [a] [a] 12
SBNZ [1] [a] [a] 16
SBNZ [0] [a] 1023 20
SBNZ [0] [1] [1] 1024

Because the program consists merely of numbers, and the data is also numbers, we can actually have the program change itself. Here #a means the cell a.

Exercise 7. Finish this SBNZ program:

SBNZ [0] [1023] #a 4
SBNZ [0] [5] a 8
SBNZ [0] [1] [1] 1024

Hint:

SBNZ [0] [1023] 6 4
SBNZ [0] [5] 99999 8
SBNZ [0] [1] [1] 1024

❤ Exercise 8. Try putting other numbers instead of 99999. What changes?

Exercise 9. Translate this into SBNZ:

0: if a != 0 goto 8
4: jmp end
8: r = r — (-b)
12: a = a — 1
16: jmp 0

Having variables a, -b, and r.

What is the result if a = 3 and -b = -4?

Exercise 10. It is a bit weird that our variable is -b and not just b. Add this line to the beginning of the program from the last exercise; b = 0 — b .

Exercise 11. Translate this into SBNZ:

0:
if a != 0 goto 8
jmp end
8:
r = r * b (insert code for multiplying)
a = a — 1
jmp 0

What is the result if a = 3 and b = 2?

If you got this far you must also enjoy compilers and programming. In my book, I discuss many useful ways to play with compilers and object-oriented programming. You can check it out:

Or directly on Manning: https://www.manning.com/books/five-lines-of-code