Good Math, Bad Math

OISC, aka the "One Instruction Set Computer" is based on the idea of the Minsky Machine. The Minsky machine is an extremely simply Turing complete machine proposed by Marvin Minsky. Back at the original GM/BM, I wrote an article on the Minsky machine and a simple Minsky interpreter. A Minsky machine is a register machine with two basic instructions: increment, and decrement-and-branch.

OISC does it one better. You don't need the increment instruction. Given an unbounded set of registers, you can be Turing complete with only one instruction: subtract and branch if less than or equal to zero. (aka SUBLEQ.) SUBLEQ takes 3 operands: two registers A and B, and a jump location, C. What SUBLEQ does is subtract the contents of B from the contents of A; and if the resulting value in A is less than or equal to zero, it jumps to C; otherwise, it proceeds to the next instruction. For simplicity of notation, if C is the next instruction, we'll just leave it blank. So if instruction N is "SUBLEQ 2, 4, N+1", we'll just write it as "SUBLEQ 2, 4"

To make things easy, we'll use numbers for the registers, and assume that register 0 contains the value 0 at all times. We can initialize it that way pretty easily; just start off the program with:

       SUBLEQ 0, 0

So how do we do anything real with this bugger? Let's build some instructions. We definitely want to be able to do addition, right? So let's suppose we want to add registers X and Y.

Add(X,Y) =  SUBLEQ 0, Y ;; R0 now contains (-Y)
            SUBLEQ X, 0 ;; X now contains X-(-Y) = X+Y
            SUBLEQ 0, 0 ;; Restore R0=0

Storing a specific value in a register:

Store(X,V) = SUBLEQ X,X ;; clear X so that it contains 0
             SUBLEQ 0, V ;; put -V in 0
             SUBLEQ X, 0 ;; put -(-V) in X
             SUBLEQ 0, 0 ;; restore 0

How about a non-conditional jump to C? That's an easy one.

Jump(C) = SUBLEQ 0, 0, C

Branch to T if X=Y, or F otherwise, using

 BranchIfEquals(X, Y, T, F) =
       Store(1, X) ;; Store copies of X and Y that we can alter
       Store(2, Y)
       SUBLEQ 1, Y, L1 ;; subtract Y from X. If true, then x <= y.
       Jump(F) ;; X was not <= y, so branch to false
   L1: SUBLEQ 2, X, T ;; subtract X from Y. If true, then Y <= X, and
                      ;; we already know X <= Y, so X = Y
       Jump(F) ;; Y was not <= X, so X != Y.

So now, we've got a useful conditional branch, addition, subtraction, unconditional branch, and copying values. That's pretty much the whole story - you don't need any more than that to be turing complete.

Want to see a real OISC program? There's an OISC Interpreter written in OISC, which is quite cute:

# Written by Clive Gifford, 29/30 August 2006 based on the Wikipedia
# description of a OISC using the "subleq" instruction.
# 3 Sep 2006: did some "constant folding", removing a few instructions.
# 8 Sep 2006, a few more changes resulting in smaller memory footprint.

start:
# [A1] = [PC]
       subleq A1   A1
       subleq PC   ZERO
       subleq ZERO A1
       subleq ZERO ZERO
# Code below (after modification from above) is equivalent to [A] = [[PC]]
       subleq A    A
A1:    data   0
       data   ZERO
       data   A2
A2:    subleq ZERO A
       subleq ZERO ZERO
# [A] = [A] + [LEN]
       subleq NEGL A
# [PC] = [PC] + 1
       subleq NEG1 PC
# [B1] = [PC]
       subleq B1   B1
       subleq PC   ZERO
       subleq ZERO B1
       subleq ZERO ZERO
# Code below (after modification from above) is equivalent to [B] = [[PC] + 1]
       subleq B    B
B1:    data   0
       data   ZERO
       data   B2
B2:    subleq ZERO B
       subleq ZERO ZERO
# [B] = [B] + [LEN]
       subleq NEGL B
# We have to copy [C] now, just in case the emulated subtraction modifies [[PC] + 2].
# [PC] = [PC] + 1
       subleq NEG1  PC
# [C1] = [PC]
       subleq C1    C1
       subleq PC    ZERO
       subleq ZERO  C1
       subleq ZERO  ZERO
# Code below (after modification from above) is equivalent to [C] = [[PC] + 2]
       subleq C    C
C1:    data   0
       data   ZERO
       data   C2
C2:    subleq ZERO C
       subleq ZERO ZERO
# [[B]] = [[B]] - [[A]];
# if [[B]] <= 0 goto LEQZ
# Earlier code referring to addresses A and B has modified the next
# couple of words to create the equivalent of "subleq [A] [B] LEQZ"
# This is where we're "emulating" the subtraction...
A:     data   0
B:     data   0
       data   LEQZ
# [PC] += 1
       subleq NEG1  PC
       subleq ZERO  ZERO START
# We come to address LEQZ when the emulated subleq is going to take
# the branch to the emulated address C.
LEQZ:
# First save the "raw" new PC
# [PC] = [C]
       subleq PC    PC
       subleq C     ZERO
       subleq ZERO  PC
       subleq ZERO  ZERO
# Check if [C] is less than zero. Halt if it is. 
# We don't care about changing [C] as we've already copied the value to [PC] above.
       subleq NEG1  C     -1
# [PC] = [PC] + [LEN]
       subleq NEGL  PC
# Go back to the start of the loop ready for the next instruction
       subleq ZERO  ZERO  START
NEGL:  data  -119   # make this == -PROG (my assembler is too primitive!)
NEG1:  data  -1
ZERO:  data   0
C:     data   0
PC:    data   PROG
# Code for the program to be interpreted must start at the PROG address...
PROG: