Subleq refers to a kind of OISC where the one instruction is "SUBtract and branch if Less-than or EQual to zero", conventionally abbreviated to subleq.
Subleq is a simple one instruction language. Each Subleq instruction has 3 memory address operands. Since Subleq has only one instruction, the opcode itself is conventionally omitted, so each instruction is three addresses long. With how Input and Output are managed in most implementations written in C it could be argued that this is less of a OISC and instead instruction computer with the instructions being SUBLEQ, INPUT and OUTPUT. A SUBLEQ implementation does not have to be implemented like this however, most are.
Given three operands,
A B C
The execution of an instruction of this form subtracts the value in memory address A from the value in memory address B, storing the result into memory address B. If the result stored into memory address B is less than or equal to zero, the execution jumps to the memory address C; otherwise it continues to the next instruction.
For example, in
3 4 6 7 7 7 3 4 0
the first instruction, at address zero, subtracts 7 (address 3) from 7 (address 4). The result in address 4 is 0, so jump to 6. Starting at address 6 is the instruction 3 4 0 which again subtracts 7 from now 0 and jumps back to 0. Here is a trace of execution (leftmost column is program counter; A and B are shown after subtraction)
0: 3 4 6 A=7 B=0 6: 3 4 0 A=7 B=-7 0: 3 4 6 A=7 B=-14 6: 3 4 0 A=7 B=-21 0: 3 4 6 A=7 B=-28 ...
Tutorial: Hello, world!
In the following, we'll use an assembly-like syntax to make the presentation easier. We'll allow program points to be labelled, and for labels to be used in place of addresses, like so:
X Y 6 X:7 Y:7 7 X Y 0
On the first line X refers to a memory cell defined somewhere else. On the second line the address of X is actually defined, by X:7, which means that this address that initially holds 7 has name X.
We will also use ? to mean "the address of the current cell" and ?+1 to mean "the address of the next cell".
Also we'll allow comment lines that begin with #.
We'll also assume that the architecture has some memory-mapped facilities for output and control. In particular, subtracting a value from the contents of addresss -1 causes an ASCII character with that value (the value being subtracted) to be output. Also, jumping to this address (or any other negative address) stops execution of the program.
Note that this assembly-like syntax and these conventions are not a necessary part of the Subleq language.
With these conventions established, we can write a program that prints "Hi" and stops.
H -1 3 i -1 6 0 0 -1 H:72 i:105 0
Underneath the assembly syntax, the program's code is
9 -1 3 10 -1 6 0 0 -1 72 105 0
72 and 105 are ASCII codes for 'H' and 'i'. (These values are also stored at addresses labelled H and i.) The third line subtracts the value of the cell at address zero from itself and to jumps to the address -1 (since the result of subtracting a number from itself will always be 0). This last instruction could just as well be
5 5 -8
or any other instruction where A and B refer to the same address, and with any negative C.
Printing characters in a loop
Printing individual characters is fine, but it doesn't really show off the capabilities of the language. Here is a "Hello, world!" program which iterates over a string of characters instead.
# Output the character pointed to by p. a a ?+1 p Z ?+1 Z a ?+1 Z Z ?+1 a:0 -1 ?+1 # Increment p. m1 p ?+1 # Check if p < E. a a ?+1 E Z ?+1 Z a ?+1 Z Z ?+1 p a -1 Z Z 0 p:H Z:0 m1:-1 # Our text "Hello, world!\n" in ASCII codes H:72 101 108 108 111 44 32 87 111 114 108 100 33 10 E:E
Without the assembler syntax, the Subleq program is really this:
12 12 3 36 37 6 37 12 9 37 37 12 0 -1 15 38 36 18 12 12 21 53 37 24 37 12 27 37 37 30 36 12 -1 37 37 0 39 0 -1 72 101 108 108 111 44 32 87 111 114 108 100 33 10 53
Subleq itself does not specify how large memory cells must be, and if no limit is imposed on the size of a memory cell at runtime, then Subleq is Turing-complete.
This can be shown by giving a procedure for translating any given Minsky machine to Subleq. In a Minsky machine, two instructions are available:
- increment some register and jump to the next instruction
- decrement some register and jump to the next instruction, unless it is already zero, in which jump to some other instruction.
Incrementing a register is the same as subtracting -1 from it.
Checking if a register is already zero can be done by adding 1 to it, then subtracting 1 from it, then jumping somewhere if it is zero or negative.
From this we can see it is straightforward to translate any Minsky machine to a Subleq program, and since the set of Minksy machines is Turing complete, Subleq is therefore Turing complete as well.
It is not immediately obvious how one would implement the bitwise operators, AND, OR, and XOR, on top of the SUBLEQ machine. Implementing division (repeated subtraction), addition is trivial, and the looping constructs (a function of the assembler) should be fairly obvious to anyone, but the bitwise operators less so.
There are at least two ways of implementing bitwise operators, but they work in essentially the same way, that is they test an individual bit in both operands to the bitwise function to check if it is set or clear and build up an answer bit by bit.
The two ways of implementing this are:
- By testing whether an integer is negative, and thus the most significant bit is set (this requires a fixed width cell implementation).
- By using arithmetic operators that have previously been constructed, specifically the modulo operator, and performing a modulo 2, this lets us known the least significant bit.
Once one bit is known in both of the operand then you can decide what you want to do in the result bit. Adding the operand to itself performs a shift left by one, and dividing the operand by 2 performs a shift right.
More detail on both ways of implementing this are available at:
The resulting programs for performing a single operator, such as AND, would be too large to list here.
- Subleq/subleq.py public domain interpreter and simple assembler that can run the examples in this article
- Addleq Variation of Subleq
- P1eq Variation of Subleq
- BitBitJump Simpler OISC
- Higher Subleq C compiler into Subleq
- OISC One Instruction Set Computer
- DJN OISC Simple variation
- Subleq+ Subleq variation which is TC with no self-modification
- Cryptoleq Heterogeneous encrypted and unencrypted computation
- SIC-1 Assembly Language Browser-based subleq compiler and interpreter
-  The first known reference to a very similar form of OISC
- Wikipedia article on Subleq and other OISCs
- Mark II OISC Self-Interpreter
- Oleg Mazonka's Subleq page
- Subleq interpreter in Redcode
- 99 bottles of beer in Subleq
- Compiling C-style language into Subleq
- TechTinkering Articles about Subleq
- Subleq-based CPU, Subleq assembly libraries, and a very minimal Subleq interpreter
- Online Subleq compiler, assembler and emulator
- Python 3.3 Subleq Compiler and Virtual Machine
- Brad Barton's artificial life experiments using SUBLEQ
- Interpreter in Ruby (part of a quine relay)
- Online subleq programming game
- Unileq Variation of Subleq with unsigned integers
- A Forth interpreter running on top a 16-bit version of the SUBLEQ machine
- SUBLEQ in Excel