Subleq

From Esolang
Jump to navigation Jump to search

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.

Overview

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.

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!

Preliminaries

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.

Printing "Hi"

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

Computational class

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.

See also

External resources