Fractran is a computer architecture based on the multiplication of fractions.

A prime is a number that can only be divided by itself and one, since these numbers can't be divided, they can considered the atoms of other numbers. The factoring of a number into prime numbers, for example: 18 = 2 × 3²(r2 = 1, r3 = 2), exposes values which Fractran utilizes as registers.

The Bag is a single number whose prime factorization holds the value of registers(2, 3, 5, 7, 11, 13, 17, ..). For example, if the state of the bag 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 empty.

A Rule is represented by a fraction that tests one or more registers. To evaluate the result of a fraction, if multiplying the bag by this fraction gives an integer, in other words, if the bag contains the symbols in the denominator, we remove them and add the symbols in the numerator.

if(r3 >= 1){ 
	r3 -= 1;
	r2 += 1;
	return;
}

if(r2 >= 8){ 
	r2 -= 8;
	r3 += 1;
	r5 += 1;
	return;
}

if(r2 >= 2 && r5 >= 1){ 
	r2 -= 2; 
	r5 -= 1; 
	r3 += 1; 
	r7 += 1;
	return;
}

To summarize: the bag holds the state of the program. The state is expressed as symbols in a bag encoded as prime factors. Each fraction acts as a rewrite rule that transforms the number of symbols in the bag.

A Notation

While Fractran is commonly reduced to just another opaque esoteric language, portraying it as such is doing a disservice to the relatively simple idea at its core and to the researchers who might otherwise benefit to venture deeper into a relatively unexplored field of computation.

If we think of Fractran as a rewriting language in which prime registers can be assigned a name, and fractions as symbolic rewrite rules, we can de-obfuscate a program. For the documentation below, we will use the Rejoice Notation.

Programming In Fractran

Evaluation consists of testing each fraction in a sequence from the first to the last, when a fraction multiplied by the value of the bag gives a whole number, the bag is updated by the product of that multiplication, and search for the next rule starts back again from the beginning.

• For each fraction in a list for which the multiplication of the bag and the fraction is an integer, replace the bag by the result of that multiplication.
• Repeat this rule until no fraction in the list produces an integer when multiplied by the bag, then halt.

sugar oranges apples cherries flour apples

@t
	( 7/30 )   [t apple-cake]/[flour sugar apples]
	( 17/715 ) [t fruit-salad]/[apples oranges cherries]
	( 19/119 ) [t fruit-cake]/[fruit-salad apple-cake]

21450                flour.2 sugar.3 apples.5 apples.5 oranges.11 cherries.13
21450 × 7/30 = 5005  apples.5 apple-cake.7 oranges.11 cherries .13
5005 × 17/715 = 119  apple-cake.7 fruit-salad.17
119 × 19/119 = 19    fruit-cake.19

Loops

Loops are a useful and common construct in programming, here is an example program in the imperative style that cycles through the four seasons until it reaches the autumn of the year two:

while(year++) {
	for(season = 0; season < 4; season++) {
		if(year == 2 && season == 3)
			return print("Reached!");
	}
}

To create a loop, a rewriting program relies on cycling back onto a term and the boundary of a loop is done by catching the ending case. Now, if we translate the above program into rewrite rules:

spring

@t
	[t .Reached!]/[autumn year^2]
	[t summer]/spring 
	[t autumn]/summer 
	[t winter]/autumn 
	[t spring year]/winter

Looking at the trace of the evaluation, we can see the following transformations:

7                spring 
7 × 11/7 = 11    summer 
11 × 3/11 = 3    autumn 
3 × 13/3 = 13    winter 
13 × 14/13 = 14  year spring 
14 × 11/7 = 22   year summer 
22 × 3/11 = 6    year autumn 
6 × 13/3 = 26    year winter 
26 × 14/13 = 28  year^2 spring 
28 × 11/7 = 44   year^2 summer 
44 × 3/11 = 12   year^2 autumn 
12 × 5/12 = 5    Reached!

Logic

Binary logic is typically implemented as multiple rules, where each is a potential location in the truth table, notice how it needs a sentinel symbol and? to catch the absence of inputs.

x y and?

@t
	[t true]/[x y and?]
	[t false]/[x and?]
	[t false]/[y and?]
	[t false]/[and?]

The comparison operations are implemented using a loop that drains the registers until only the offset remains:

x^4 y^3 gth?

@t
	[t gth?]/[x y gth?]
	[t true]/[x gth?]
	[t false]/[gth?]

2160 × 5/30 = 360  x^3 y^2 gth?
360 × 5/30 = 60    x^2 y gth? 
60 × 5/30 = 10     x gth? 
10 × 7/10 = 7      true 

A similar set of rules can check if a register is odd or even:

x^7 even?

@t
	[t even?]/[x^2 even?]
	[t false]/[x even?]
	[t true]/[even?]

Arithmetic

The sum of two registers(x+y) can be reached by writing the result in a third register(sum):

x^4 y^2 add 

@t
	[t sum add]/[x add]
	[t sum add]/[y add]
	t/add

2352 × 15/6 = 5880     x^3 add sum y^2 
5880 × 15/6 = 14700    x^2 add sum^2 y^2 
14700 × 15/6 = 36750   x add sum^3 y^2 
36750 × 15/6 = 91875   add sum^4 y^2 
91875 × 15/21 = 65625  add sum^5 y 
65625 × 15/21 = 46875  add sum^6 
46875 × 1/3 = 15625    sum^6

Alternatively, the result can also be reached by moving the value of one register into the other:

x^4 y^2 add 

@t
	[t y add]/[x add]

The difference between two registers(x-y) can be reached by consuming the value of two registers at once, and moving the remains into a third(pos) and fourth(neg) to get the signed result:

x^4 y^6 sub 

@t
	[t sub]/[x y sub]
	[t sub pos]/[x sub]
	[t sub neg]/[y sub]
	t/sub

58320 × 5/30 = 9720  x^3 y^5 sub 
9720 × 5/30 = 1620   x^2 y^4 sub 
1620 × 5/30 = 270    x y^3 sub 
270 × 5/30 = 45      y^2 sub 
45 × 55/15 = 165     y sub neg 
165 × 55/15 = 605    sub neg^2 
605 × 1/5 = 121      neg^2 

The doubling of a register(x*2) is a matter of incrementing an output register twice for each input register values:

x^4 double 

@t
	[t res^2 double]/[x double]
	t/double

48 × 75/6 = 600         x^3 double res^2 
600 × 75/6 = 7500       x^2 double res^4 
7500 × 75/6 = 93750     x double res^6 
93750 × 75/6 = 1171875  double res^8 
1171875 × 1/3 = 390625  res^8

The halving of a register(x/2) is a matter of decrementing an input register twice for each output register value:

x^4 half 

@t
	[t res half]/[x^2 half]
	t/half

The product is reached from a series of additions, by copying the input register, into a temporary register and third result register.

x^3 y^2 

@t
	[t x i]/[z i]
	t/i
	[t y z res]/[x y]
	[t i]/y
	t/x

675 × 70/15 = 3150      res x^2 y^2 z 
3150 × 70/15 = 14700    res^2 x y^2 z^2 
14700 × 70/15 = 68600   res^3 y^2 z^3 
68600 × 11/5 = 150920   res^3 y z^3 i 
150920 × 33/77 = 11880  res^3 x^3 y i 
11880 × 1/11 = 1080     res^3 x^3 y 
1080 × 70/15 = 5040     res^4 x^2 y z 
5040 × 70/15 = 23520    res^5 x y z^2 
23520 × 70/15 = 109760  res^6 y z^3 
109760 × 11/5 = 241472  res^6 z^3 i 
241472 × 33/77 = 19008  res^6 x^3 i 
19008 × 1/11 = 1728     res^6 x^3 
1728 × 1/3 = 64         res^6

Example: Fizzbuzz

To implement Fizzbuzz, we can increment registers for thirds and fifths to emit fizz and buzz at the proper intervals, while decrementing the upper boundary:

times^100

@t ( times -- num f b )
	[t num f b .FizzBuzz\n]/[times f^3 b^5]
	[t num f b .Fizz\n]/[times f^3]
	[t num f b .Buzz\n]/[times b^5]
	[t num f b .#num .\n]/times

Example: Fibonacci

Let's have a look at a program to generate the Fibonacci Sequence(1, 1, 2, 3, 5, 8, 13, 21, 34..). This program uses catalysts(fib, fib.shift, fib.move) to keep the program state which has 3 phases(shift, move and back to fib) and ensures the correct evaluation order:

res n^5 last fib

@t
	[t fib n B]/[fib n last]
	[t fib n A B]/[fib n res]
	[t fibrec]/[fib n]
	[t fibrec last]/[fibrec A]
	[t fibrec res]/[fibrec B]
	[t fib]/fibrec
	t/last

To dive deeper, have a look at the Fractran devlog.

• Intro to Fractran
• Remembering John Conway
• On Esolang

incoming: pocket rewriting tote binary primes fractions tropical arithmetic paper games reversible computing rejoice rejoice devlog rewriting thue bagel 2024 2021 malleable computing