## 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^{2},
exposes values which Fractran utilizes as *registers*. There are two parts to a Fractran program:

### The Accumulator

Accumulator | Registers | |||
---|---|---|---|---|

r2 | r3 | r5 | r7 | |

6 | 1 | 1 | ||

18 | 1 | 2 | ||

1008 | 4 | 2 | 1 | |

5402250 | 1 | 2 | 3 | 4 |

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.

2/3 | 15/256 | 21/20 |
---|---|---|

(2^{1})/(3^{1}) |
(3^{1} × 5^{1})/(2^{6}) |
(3^{1} × 7^{1})/(2^{2} × 5^{1}) |

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

The wise marvels at the commonplace.Confucius

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