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. 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!

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 address -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 Minsky machines is Turing complete, Subleq is therefore Turing complete as well.

Bitwise Operators

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:

  1. By testing whether an integer is negative, and thus the most significant bit is set (this requires a fixed width cell implementation).
  2. 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:

https://stackoverflow.com/questions/34120161/bitwise-operations-in-subleq/66266935

The resulting programs for performing a single operator, such as AND, would be too large to list here.

Subleq2

There is another variant with two operands and an internal accumulator, where the accumulator is subtracted from the memory location specified by the first operand. The result is stored in both the accumulator and the memory location, and the second operand specifies the branch address. Although this variant uses only two (instead of three) operands per instruction, correspondingly more instructions are then needed to effect various logical operations. On the other hand, this variant may substantially simplify hardware implementation.

A computer named Izhora 1, based on Subleq2 and implemented as a large cellular automaton pattern, was produced by Yoel Matveyev in 2021. It has 256kb of 32-bit addressable RAM and a 128*64 pixel display. Each 32-bit memory cell is interpreted as a 16-bit jump address and a 16-bit pointer to an operand. The computer is supplied with an emulator and a basic assembler written in Common Lisp. As of November 9, 2021, its repository has several versions of "Hello World", prime numbers generator, Fibonacci numbers generator, and 128-bit factorials using a triple carry. The computer can be loaded as a Golly pattern; programs can be downloaded and uploaded by custom scripts. In January 2022, Yoel Matveyev released an upgraded version of his computer that has a 256x128 display and a virtual keyboard mapped to one of the RAM addresses of the machine [1].

See also

  • 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
  • FlipJump More basic OISC
  • 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
  • Izhora A cellular automation computer implementing a variety of Subleq
  • SIC-1 Assembly Language Browser-based subleq compiler and interpreter
  • OISC:2 Obfuscated indirect subleq with coprocessor: 2 word instructions
  • OISC:2bis Improved OISC:2
  • OISC:3 Obfuscated indirect subleq with coprocessor: 3 word instructions

External resources

  1. ↑ https://github.com/yoelmatveyev/Izhora
Retrieved from "https://esolangs.org/w/index.php?title=Subleq&oldid=140861"