XXIIVV

OISCs are One Instruction Set Computers.

Subleq is a One Instruction Set Computer(OISC) architecture.

The subleq instruction subtracts the contents at address a from the contents at address b, stores the result at address b, and then, if the result is not positive, jumps to address c. If the result is positive, execution proceeds to the next instruction in sequence.

if (mem[B] -= mem[A]) <= 0 
	goto C

Each subleq instruction has 3 operands which are memory addresses:

A B C

For example, in the following example, the first instruction subtracts 7 (address 3) from 7 (address 4). The result in address 4 is 0, so goto 6. On address 6 is the instruction 3 4 0 which again subtracts 7 from now 0 and jumps back to 0.

3 4 6
7 7 7
3 4 0

Instructions

JMP c
Z Z c
ADD a, b
a, Z
Z, b
Z, Z
MOV a, b
b, b
a, Z
Z, b
Z, Z
BEQ b, c
b, Z, L1
  Z, Z, OUT
L1:
  Z, Z
  Z, b, c
OUT:
  ...

Fractran is based on one of the most bizarrely elegant concepts of computation.

A Fractran program is an ordered list of positive fractions together with an initial positive integer input. The program is run by updating the accumulator.

The Book of Numbers, John Conway

Any number that can't be divided by any other number, apart from itself and one, is prime. Since primes can't be divided, we can think of them as the DNA of other numbers. In Fractran, each prime is a register and their exponent is their value.

The Accumulator

The state of the accumulator is held as a single number, whose prime factorization holds these registers(2, 3, 5, 7, 11, 13, 17, ..). If the state of the accumulator is 1008(2⁴ × 3² × 7), r2 has the value 4, r3 has the value 2, r7 has the value 1, and all other registers are unassigned.

AccumulatorRegisters
r2r3r5r7
611
1812
1008421
54022501234

The Operators

A fractran operation is a positive fraction, each fraction represents an instruction that tests one or more registers, represented by the prime factors of its denominator. The Fractran computer goes through each fraction in order, in terms of our current accumulator value.

18(21 × 32) 2/3 = 8(23) addition r2+r3->r2

To run the adder operation(2/3), we will take the state of the accumulator. If multiplying it by this fraction will give us an integer, we will do so and start again at the beginning of the program. Otherwise, we will stop and consider the program complete. We will do this repeatedly until we can no longer produce an integer with this method.

stepsstateregisters
r2r3
1181218 × 2/3 = 12/1INT, RESTART
2122112 × 2/3 = 8/1INT, RESTART
3838 × 2/3 = 16/3NOT INT, END

To add the values 1 and 2, we will store the values in registers 2 and 3, our starting state is therefore 18(21 × 32).

For each step of the program, we will multiply our state with the program(18 × 2/3 = 12, 12 × 2/3 = 8, ..) until our our working value cannot be reduced to a whole number(16/3), we have exhausted the program. Alternatively, the program 3/2 will do the same operation but store the result in the register 3.

576(26 × 32) 1/6 = 16(24) subtraction r2-r3->r2

Operations become more readable when broken down into their primes. We can think of every prime number as having a register which can take on non-negative integer values. Each fraction is an instruction that operates on some of the registers.

2/3 15/256 21/20
(21)/(31) (31 × 51)/(26) (31 × 71)/(22 × 51)
if(r3 >= 1){ 
	r3 -= 1;
	r2 += 1;
	return;
}
if(r2 >= 6){ 
	r2 -= 6;
	r3 += 1;
	r5 += 1;
	return;
}
if(r2 >= 2 && r5 >= 1){ 
	r2 -= 2; 
	r5 -= 1; 
	r3 += 1; 
	r7 += 1;
	return;
}

You can interpret a fraction as saying if the current value of each register is greater than or equal to the the value specified by the denominator, you subtract from the registers all of the values in the denominator, add all the values specified in the numerator, and then jump back to the first instruction. Otherwise, if any register is less than the value specified in the denominator, continue to the next fraction.

The Programs

A Fractran program is a list of fractions together with an initial positive integer input n. The program is run by updating the integer n as follows:

Let's put together an adder program similar from the one above(2/3) but which writes to a third register. The following program first moves the content in r2 to r3, and then the content of r3 to r5.

18(21 × 32) 3/2 5/3 = 125(53) addition r2+r3->r5(9 steps)

Alternatively, a faster way to do this would be to directly move powers of 2 over to 5, then powers of 3.

18(21 × 32) 5/2 5/3 = 125(53) addition r2+r3->r5(7 steps)

Each of the 7 steps of this last program looks like:

18 5/2 5/3           [18]  r2=01 r3=02
------------------   -----------------
18 × 5/2 = 45/1      [45]  r3=02 r5=01
45 × 5/2 = 225/2 
45 × 5/3 = 75/1      [75]  r3=01 r5=02
75 × 5/2 = 375/2 
75 × 5/3 = 125/1     [125] r5=03
125 × 5/2 = 625/2 
125 × 5/3 = 625/3    [125] r5=03

Both of these programs are destructive, meaning that they drain the registers of their original values. We can make (2/3) less destructive with (10/3) by storing a copy of r3 in r5. And we can create a non-destructive adder but this requires coming in with the program with the flag r7 set:

126(21 × 32 × 71) 7/11 715/14 935/21 1/7 2/13 3/17 = 2250(21 × 32 × 53)

As an extra demonstration, let us consider the following programs representing all the logic gates:

Program07142142
AND Gate5/42 1/21 1/14 1/71115
OR Gate5/42 5/21 5/14 1/71555
XOR Gate1/42 5/21 5/14 1/71551
NAND Gate1/42 5/21 5/14 5/75551
NOR Gate1/42 1/21 1/14 5/75111
XNOR Gate5/42 1/21 1/14 5/75115

Extras

I've been scratching at trying to fit a fractran-inspired vm hosted in uxn's 16-bit space where these fractions operate differently to facilitate running with low values in registers.

*/*Jump
*/0Push Acc/Load from memory
0/*Pop Acc/Save in memory
0/0Pop, or Break
A wise person marvels at the commonplace. Confucius

Thue is a matrioshka esoteric computer based on string rewriting rules.

A Thue program consists of two parts: a list of substitution rules, which is terminated with a line having both sides of the operator empty, followed by a string representing the initial program state.

#::=Unused rules are comments
a::=~Hello Thue!
::=
[a] []

Execution consists of picking, from the list of rules, an arbitrary rule whose original string exists as a substring somewhere in the program state, and replacing that substring by the rule's replacement string. This process repeats until there are no rules that can be applied, at which point, the program ends.

#::=Increment binary number
1_::=1++
0_::=1
01++::=10
11++::=1++0
_0::=_
_1++::=10
::=
_10010011_ _10010100

Thue represents one of the simplest possible constraint-based programming language. It is to the constraint-based paradigm what languages like OISC are to the imperative paradigm.

Input

Added to this simple system are two strings which are used to permit Thue to communicate with the outside world. The first of these is the input symbol (":::"). The input symbol is actually the lhs of an implicit rule of which the user (or system's "input stream") is a component. The input symbol, therefore, is replaced by a line of text received from the "input stream."

Output

As a counterpart of input, the output symbol ("~") is supplied. Like the input symbol, the output symbol triggers an implicit rule which, in this case, encompasses the "output stream." The specific effect is that all text to the right of the output symbol in the rhs of a production is sent to the output stream.

Note that either (or both) of these implicit rules may be overridden by providing explicit rules that perform some other task.

#::=Sierpinski's triangle, backticks are linebreaks
X::=~_
Y::=~*
Z::=~`
_.::=._X
_*::=*_Y
._|::=.Z-|
*_|::=Z
..-::=.-.
**-::=*-.
*.-::=*-*
.*-::=.-*
@.-::=@_.
@*-::=@_*
::=
@_*...............................|
It is pitch black. You are likely to be eaten by a Thue.

Incoming: thue