OISC
OISC is the One Instruction Set Computer (by analogy with RISC and CISC), a machine providing only one instruction. The abbreviation URISC (Ultimate RISC) has been used in some publications with the same meaning as OISC.
In some implementations the instruction is subtract and branch unless positive, abbreviated subleq (subtract and branch if less or equal to zero), or sometimes subtract and branch if negative (SBN), which only differ by zero-inclusion. Some languages use a memory mapped instruction pointer (as in RSSB). Branching is done by writing to IP in these implementations. More advanced memory mapping allows complex functionality such as arithmetic but with the benefit of having a simple copy operation (MOVE, or mov).
The subtract-and-branch-unless-positive operation usually has three parameters. subleq(a,b,c) (Subleq) subtracts a from b, stores the result in b, and then transfers control to the address in c if the result was non-positive.
The simplest known OISC is arguably BitBitJump. Its instruction has 3 operands as in Subleq, but the meaning is: copy the bit addressed by a to the bit addressed by b and jump to the address c. BitBitJump has a "big brother" ByteByteJump that copies 1 byte at a time instead of 1 bit. Both of these machines belong to a larger class of machines, WordWordJump, that copy b bits at a time but have address operands of size n*b, where n≥2 (e.g. 32-bit addresses and 8-bit data for a 32-bit WordWordJump machine). It is this feature that allows BitBitJump, ByteByteJump and similar machines to perform arithmetic and conditional jumps through the use of self-modifying code.
Some OISC languages are Turing-complete, making them Turing tarpits, while others are bounded-storage machines, more akin to physical CPUs. Turing-completeness requires the OISC to be defined with sufficient abstraction with respect to both addressing scheme and operand size. For example, Subleq uses absolute addressing and does not specify its operand size, so it is TC. BitBitJump, on the other hand, is defined to use bounded operand size and absolute addressing, so it is only a bounded storage machine. It is not known whether either of these languages with bounded operand size could achieve TC-ness by revising them to use relative addressing. It seems likely, however, because relative addressing is the Turing machine property.
Any OISC language belongs to either one of the two groups: with memory mapping (MOVE, RSSB) or without (Subleq, SBN, BitBitJump, ByteByteJump). Note, that a language from the second group may have an extension with memory mapped special addresses, but those addresses are not required for computations; they are used for IO or any other system calls.
List of OISCs
In this table, the OISC's command is given in C-like syntax. a, b, c, etc. are placeholders for arguments to the command, and are treated as literals (thus for example the INC command from x86 assembler would have its semantics written as (*a)++; it's incrementing the value at a specific address, so the address is literal and needs to be dereferenced once in order to produce the value at that address, which is the thing that is incremented). X, Y etc. are placeholders for "magic numbers" that allow multiple variants of an instruction, such as addressing modes. p, q, r, etc. are registers that are not memory-mapped. Many OISCs memory-map instructions (to allow for self-modifying code, often increasing their computational power), and/or the instruction pointer (to provide a method to implement loops). (Some OISCs also memory-map other things, like I/O, but this is not shown in the table below.)
| Name | Command | Addresses | Commands memory-mapped | IP memory-mapped |
|---|---|---|---|---|
| abcout | *a += *b; if (*a > 255) { *a %= 256; ip = *c; } | Absolute | No | No |
| BitBitJump | *b = *a; goto *c; | Absolute | Yes | No |
| Blues machine | ++*a; *b *= *c; *d /= *e; if(*f) goto (g ? h : *h); | Absolute | Yes | No |
| ByteByteJump | *b = *a; goto *c; | Absolute | Yes | No |
| Cryptoleq | *b = *b/*a; if (*b < 0) goto *c; | Absolute | Yes | No |
| Divrac | *e = (a*d)/gcf(a*d, b*c); *(e+1) = (b*c)/gcf(a*d, b*c); | Absolute (some magic numbers) |
No | Partially |
| DJN | (*b)--; if (*b ≠ 0) goto *a; | Relative | Yes | No |
| Flump | if (b & *a) *a -= (*a & ~(b-1)) / 2; else *a += (*a & ~(b-1)) + b; if (!*a) goto *c; |
Absolute | Yes | No |
| I/D machine | *p += a; p = *p; | Not used | No | No (implicit loop around program) |
| JCLN | b: if(a==-1)a=__LINE__; if(__LINE__==a) goto b; //There has to be a "b" tag on every command. |
Absolute | Yes | No |
| MISC | *a = ((d & X) ? b : *b) - ((d & Y) ? c : *c); goto *(d & ~X & ~Y); |
Relative | Yes | No |
| MOVE | ||||
| RSSB | *a = *1 = *a - *1; | Absolute | Yes | Yes |
| SBN (SBN2) | *a = p = p - *a; if (p < 0) goto *b; | Absolute | No | Yes |
| SBN (SBN3) | X = X - Y; if (X < 0) goto *p; (aka subneg) | Absolute | No | Yes |
| SBN (SBN4) | Z = X - Y; if (Z < 0) goto *p; (aka subneg4) | Absolute | No | Yes |
| Subleq | *b = *b - *a; if (*b <= 0) goto *c; | Absolute | Yes | No |
| Subskin | *c = *a - *b; if (*c < 0) goto *(ip + 1); |
Absolute | Yes | Yes |
| Simpler Subskin | *a -= *b; if (*a < 0) goto *(ip + 1); |
Absolute | No | No (implicit loop around program) |
| Three Star Programmer | (***a)++; | Absolute | No | No (implicit loop around program) |
| Tip | ip *= a; | Absolute | No (program repeats forever) | No (but halt on IP 0) |
| TOGA computer | *a = !*a; if (*a) goto *b; | Absolute | No | No |
| Unileq | if (*a <= *b) goto *c *a -= *b |
Absolute | Yes | No |
| XOṘ Mạchịne | a ^= b; /*or any command like this*/ printf("%d",a>b); | Absolute | Yes | No |
Additionally, the non-esoteric transport triggered architecture also has only one instruction, move.
Papers
- The Ultimate RISC - 1988 Describes MOVE
- Single Instruction Set Architectures for Image Processing - 2002
- URISC: The Ultimate Reduced Instruction Set Computer - 1988 Describes SBN
