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

A prime is a number that can only be divided by itself one, since these numbers can't be divided, they can considered the DNA of other numbers. The factoring of a number into prime numbers, for example: 18 = 2 × 3², exposes values which Fractran utilizes as registers. There are two parts to a Fractran program:

1. The Accumulator
2. The Fractions

The Accumulator

The Accumulator 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 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.

The Fraction

A Fraction represents an instruction that tests one or more registers by the prime factors of its numerator and denominator. To evaluate the result of a rule we take the the accumulator, if multiplying it by this fraction will give us an integer, we will update the accumulator with the result.

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;
}

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.

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 by venturing deeper into a relatively unexplored field of computation.

Wryl, who created Modal, demonstrated to me an interesting connection between Fractran and rewriting languages. We need only to compile our rules and point the prime registers to symbols in a dictionary to see this relationship more clearly.

:: left side > right side (compiled: 15/6 left.2 side.3 > side.3 right.5)

AC 6 left side (initial state)
00 6 × 15/6 = 15, side right (result state)

This documentation will represent registers with names(x, y, foo-bar, baz, ..). Fractions will be written as rewrite rules starting with ::, a left-side, a spacer(>) and a right-side. The notation indicates which registers to replace on the left-side, and what to replace them with on the right-side.

Programming In Fractran

In a rule definition, we find symbols to the left-side of the spacer(>) to be rewritten by what is found on the right-side. Each new symbol is added to the dictionary and represented internally as a prime number.

:: flour sugar apples > apple-cake
:: apples oranges cherries > fruit-salad
:: fruit-salad apple-cake > fruit-cake

sugar oranges apples cherries flour apples

Rules are tested in a sequence from the first to the last, when a valid rewrite rule is encountered, the accumulator is updated, and the PC moved back at the first rule. In other words, it helps to visualize the fractions in a program as a list of rewrite rules that tests the accumulator against its left-side, and starts back at the top of the list after updating the accumulator when it is a match, or keep going when it does not.

AC 21450 flour sugar apples apples oranges cherries 
00 21450 × 7/30 = 5005, apples apple-cake oranges cherries 
01 5005 × 17/715 = 119, apple-cake fruit-salad 
02 119 × 19/119 = 19, fruit-cake 

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

Logic & Arithmetic

Logic in rewrite rules is typically implemented as multiple rules, where each one is a potential combination, here is logical and as example:

:: x y and > true
:: x and > false
:: y and > false

AC 30 x y and 
00 30 × 7/30 = 7, true

You can get the sum of two registers by moving the value of one register into the other. The naming of the x register in advance ensures that the highest number will be stored in the lowest register:

:: x (Naming)
:: y > x

x x x x y y

You can get the difference between two registers by consuming the value of two registers at once, and moving the remains to the first:

:: x y >
:: y > x

AC 576 x x x x x x y y 
00 576 × 1/6 = 96, x x x x x y 
00 96 × 1/6 = 16, x x x x

You can get the product of two registers by keeping an intermediate result and state register. Keeping the resulting product, by naming the first register, prevents the accumulator grow too much in size:

:: r acc x y (Naming)
:: iter acc > x iter
:: iter >
:: x y > r acc y 
:: y > iter
:: x > 

AC 8575 x x y y y 
02 8575 × 42/35 = 10290, r acc x y y y 
02 10290 × 42/35 = 12348, r r acc acc y y y 
03 12348 × 11/7 = 19404, r r acc acc y y iter 
00 19404 × 55/33 = 32340, r r acc x y y iter 
00 32340 × 55/33 = 53900, r r x x y y iter 
01 53900 × 1/11 = 4900, r r x x y y 
02 4900 × 42/35 = 5880, r r r acc x y y 
02 5880 × 42/35 = 7056, r r r r acc acc y y 
03 7056 × 11/7 = 11088, r r r r acc acc y iter 
00 11088 × 55/33 = 18480, r r r r acc x y iter 
00 18480 × 55/33 = 30800, r r r r x x y iter 
01 30800 × 1/11 = 2800, r r r r x x y 
02 2800 × 42/35 = 3360, r r r r r acc x y 
02 3360 × 42/35 = 4032, r r r r r r acc acc y 
03 4032 × 11/7 = 6336, r r r r r r acc acc iter 
00 6336 × 55/33 = 10560, r r r r r r acc x iter 
00 10560 × 55/33 = 17600, r r r r r r x x iter 
01 17600 × 1/11 = 1600, r r r r r r x x 
04 1600 × 1/5 = 320, r r r r r r x 
04 320 × 1/5 = 64, r r r r r r

I/O

John Conway has not specified any way for the program to interface with the outside world, but others have offered schemes like assigning an alphabet to a series of registers. The advantage with symbolic rewriting is that registers are already assigned whole tokens, so we shall use those instead.

:: print foobar > hello world >

AC 6 print foobar 
00 6 × 35/6 = 35, hello world

>> hello world

This rule has a second spacer(>) which tells our interpreter to print the registers present in the accumulator after the application of the rule. For a more complete example, see fizzbuzz.

That's all!

Implementation

The rewriting implementation of the runtime can be implemented in about 200 lines.

cc fractran.c -o fractran view raw

• Fractran Interpreter(C89)
• Fractran Interpreter(Web)
• Intro to Fractran
• Article on Esolang
• Collatz function
• Remembering John Conway

incoming phutball firth primes fractions