A compiler assigns the symbols left, side and right to the prime numbers 2, 3 and 5. The product of left(2) and side(3) for the denominator, side(3) and right(5) for the numerator, result in the fraction 15/6.
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 × 32, 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 |
|---|---|---|
| (21)/(31) | (31 × 51)/(28) | (31 × 71)/(22 × 51) |
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; } |
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 to venture deeper into a relatively unexplored field of computation.
Wryl, who created Modal, demonstrated to me an interesting connection between Fractran and rewriting languages which is made clearer by using a notation where prime registers are automatically assigned names, and fractions are defined in terms of transformations of these names:
:: left side > right side 15/6 left.2 side.3 > side.3 right.5 AC 6 left side accumulator 00 6 × 15/6 = 15, side right result
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 denominator left-side, and what to replace them with on the numerator right-side. Unlike John Conway's original specification of Fractran, fractions are not reduced.
Multiset sounds too technical.
Dijkstra's bag, not technical enough.
Programming In Fractran
In a rule definition, which is a fraction where prime factorization is written as names, we find names to the left-side of the spacer(>) to be rewritten by names found on the right-side. Each new name 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 rewrite rule gives us an integer when when multiplied by the accumulator, the accumulator is updated by the product of that multiplication, and search for the next rule starts back again from the beginning.
:: 7/30 flour.2 sugar.3 apples.5 > apple-cake.7 :: 17/715 apples.5 oranges.11 cherries.13 > fruit-salad.17 :: 19/119 apple-cake.7 fruit-salad.17 > fruit-cake.19 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
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.
Fractran has a single operation, and can be explained in 10 seconds.
- For each fraction in a 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.
That's all!
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)
print("Reached!");
return;
}
}
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:
:: year year autumn > Reached! :: spring > summer > autumn > winter > spring year spring
Looking at the trace of the evaluation, we can see the following transformations:
AC 7, spring 01 7 × 11/7 = 11, summer 02 11 × 3/11 = 3, autumn 03 3 × 13/3 = 13, winter 04 13 × 14/13 = 14, year spring 01 14 × 11/7 = 22, year summer 02 22 × 3/11 = 6, year autumn 03 6 × 13/3 = 26, year winter 04 26 × 14/13 = 28, year^2 spring 01 28 × 11/7 = 44, year^2 summer 02 44 × 3/11 = 12, year^2 autumn 00 12 × 5/12 = 5, Reached!
Arithmetic & Logic
The sum of two registers(x+y) can be reached by moving the value of one register into the other:
:: y > x AC 144 x^4 y^2 00 144 × 2/3 = 96, x^5 y 00 96 × 2/3 = 64, x^6
The difference between two registers(x-y) can be reached by consuming the value of two registers at once, and moving the remains to the first if we want the result inside x:
:: x y > :: y > x AC 576 x^6 y^2 00 576 × 1/6 = 96, x^5 y 00 96 × 1/6 = 16, x^4
The doubling of a register(x*2) can be reached by using a temporary catalyst register which keeps the evaluation in a specific state.To keep the accumulator size small, we can reserve lower registers by creating a pseudo-rule without a right-side:
:: x A :: double x > double A A :: double > :: A A > x x AC 80, x^4 double 00 80 × 45/10 = 360, x^3 A^2 double 00 360 × 45/10 = 1620, x^2 A^4 double 00 1620 × 45/10 = 7290, x A^6 double 00 7290 × 45/10 = 32805, A^8 double 01 32805 × 1/5 = 6561, A^8 02 6561 × 4/9 = 2916, x^2 A^6 02 2916 × 4/9 = 1296, x^4 A^4 02 1296 × 4/9 = 576, x^6 A^2 02 576 × 4/9 = 256, x^8
The halving of a register(x/2) can be reached by keeping a catalyst register and a temporary accumulator(A)
:: x A :: half x x > half A :: half > :: A > x AC 320, x^6 half 00 320 × 15/20 = 240, x^4 A half 00 240 × 15/20 = 180, x^2 A^2 half 00 180 × 15/20 = 135, A^3 half 01 135 × 1/5 = 27, A^3 02 27 × 2/3 = 18, x A^2 02 18 × 2/3 = 12, x^2 A 02 12 × 2/3 = 8, x^3
Logic in rewrite rules is typically implemented as multiple rules, where each one is a potential location in the truth table, here is logical and between two registers(x&y) as example:
:: and x y > true :: and x > false :: and y > false AC 30, and x y 00 30 × 7/30 = 7, true
The comparison operation greather-than of two registers(x>y) can be implemented in a non-destructive way that doesn't consume the inputs and returns the program to its initial state with the answer.
:: gth x y > gth A :: gth x > gth? true x :: gth > gth? false :: gth? A > gth? x y :: gth? > AC 20250, gth x^4 y^3 00 20250 × 14/30 = 9450, gth x^3 y^2 A 00 9450 × 14/30 = 4410, gth x^2 y A^2 00 4410 × 14/30 = 2058, gth x A^3 01 2058 × 429/6 = 147147, x A^3 gth? true 03 147147 × 165/77 = 315315, x^2 y A^2 gth? true 03 315315 × 165/77 = 675675, x^3 y^2 A gth? true 03 675675 × 165/77 = 1447875, x^4 y^3 gth? true 04 1447875 × 1/11 = 131625, x^4 y^3 true
Now, let's put it all together! Programs are made of the combination of operations. In rewrite systems, we need to ensure that the evaluation is done in the right order, which is not necessarily the order in which rules are defined. Say we want to get the result of the following nested operations:
(- (+ 2 (* 4 6)) (+ 3 5 7))
We've looked at a handful of arithmetic operations, we'll add catalysts(mul, add, sub, etc..) in order to make them reusable in a larger context, and create a state-machine that will run the combination of operations in the correct sequence. Here is how a larger program can be organized, including comments within parenthesis for the various functions:
:: res x y z A t (mul x y .. res=x*y) :: mul.move A > mul.move y :: mul.move > mul :: mul x y > mul x A res :: mul x > mul.move :: mul y > mul :: mul > (add x y z .. res=x+y+z) :: add x > add res :: add y > add res :: add z > add res :: add > (sub x y .. res=x-y) :: sub x y > sub :: sub x > sub res :: sub > (moving intermediate results) :: res-x res > res-x x :: res-x > :: res-t res > res-t t :: res-t > :: res-y res > res-y y :: res-y > :: t-x t > t-x x :: t-x > (main) :: 1) > mul x x x x y y y y y y res-x 2) :: 2) > add y y res-t 3) :: 3) > add x x x y y y y y z z z z z z z res-y t-x 4) :: 4) > sub AC 47, 1) .. 12 59392 × 1/29 = 2048, res^11
Example: Fibonacci
Let's have a look at a real 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:
(Keep going while the n register is present) :: fib n > fib.shift (Shift the scrolling window to show two numbers) :: fib.shift last > fib.shift B :: fib.shift res > fib.shift A B :: fib.shift > fib.move (Move the temporary registers back by one number) :: fib.move A > fib.move last :: fib.move B > fib.move res :: fib.move > fib (Cleanup temporary registers at the end of the program) :: last > :: fib > (Find the fib number equal to the value in n register) AC 6240, n^5 last res fib .. 08 15869140625 × 1/13 = 1220703125, res^13
Example: Tic-Tac-Toe
Fractran's output capability is limited to the resulting accumulator at the end of an evaluation. The advantage of symbolic rewriting is that registers are already assigned names, so we shall print those instead. As for input, we can type in new symbol tokens and appending their value to the accumulator between evaluations. We can implement a tic-tac-toe in a mere 16 rules:
(Reserve the first registers for the player moves)
:: x#a o#a x#b o#b x#c o#c
:: x#d o#d x#e o#e x#f o#f
:: x#g o#g x#h o#h x#i o#i
(This register remains active until the game ends)
game
(A symbol to draw the value of registers in a grid)
"
Set move in the format x#a, o#b, x#c, etc:
a b c | {x#a o#a .} {x#b o#b .} {x#c o#c .}
d e f | {x#d o#d .} {x#e o#e .} {x#f o#f .}
g h i | {x#g o#g .} {x#h o#h .} {x#i o#i .}
"
(Rules for each possible victory states)
:: game x#a x#b x#c > x#a x#b x#c "Player X wins!"
:: game o#a o#b o#c > o#a o#b o#c "Player O wins!"
:: game x#d x#e x#f > x#d x#e x#f "Player X wins!"
:: game o#d o#e o#f > o#d o#e o#f "Player O wins!"
:: game x#g x#h x#i > x#g x#h x#i "Player X wins!"
:: game o#g o#h o#i > o#g o#h o#i "Player O wins!"
:: game x#a x#e x#i > x#a x#e x#i "Player X wins!"
:: game o#a o#e o#i > o#a o#e o#i "Player O wins!"
:: game x#g x#e x#c > x#g x#e x#c "Player X wins!"
:: game o#g o#e o#c > o#g o#e o#c "Player O wins!"
:: game x#a x#d x#g > x#a x#d x#g "Player X wins!"
:: game o#a o#d o#g > o#a o#d o#g "Player O wins!"
:: game x#b x#e x#h > x#b x#e x#h "Player X wins!"
:: game o#b o#e o#h > o#b o#e o#h "Player O wins!"
:: game x#c x#f x#i > x#c x#f x#i "Player X wins!"
:: game o#c o#f o#i > o#c o#f o#i "Player O wins!"
Program don't need to specify anything other than these 16 rules, as players can already input their moves in the format of its register names: x#a, o#b, x#c, etc.
Set move in the format x#a, o#b, x#c, etc: a b c | x o o d e f | . x . g h i | . . x Player X wins!
A Fractran program specifies the wiring and logic of an interactive application, registers point to symbols in memory and so the bytecode itself is never localized as these strings reside in the application's front-end far from its logic.
Example: Fizzbuzz
Alternatively to getting the resulting program state at the end of an evaluation, we can emit the accumulator at a specific rate during the evaluation by checking if a register is active or not.
(Reserve the first registers for the increments and base-10)
:: +5 +3
:: 1# 2# 3# 4# 5# 6# 7# 8# 9# 0
:: 1 2 3 4 5 6 7 8 9
(Leave the printing register for no more than one rewrite)
:: print: fizz >
:: print: buzz >
:: print: fizzbuzz >
:: print: "{1# 2# 3# 4# 5# 6# 7# 8# 9# 0}{1 2 3 4 5 6 7 8 9}" >
(Fizzbuzz logic)
:: eval +3 +3 +3 +5 +5 +5 +5 +5 > print: fizzbuzz
:: eval +3 +3 +3 > print: fizz
:: eval +5 +5 +5 +5 +5 > print: buzz
:: eval > print: "{1# 2# 3# 4# 5# 6# 7# 8# 9# 0}{1 2 3 4 5 6 7 8 9}"
(Base-10 numbers)
:: 1# 9 > 2# 0 +3 +5 eval
:: 2# 9 > 3# 0 +3 +5 eval
:: 3# 9 > 4# 0 +3 +5 eval
:: 4# 9 > 5# 0 +3 +5 eval
:: 5# 9 > 6# 0 +3 +5 eval
:: 6# 9 > 7# 0 +3 +5 eval
:: 7# 9 > 8# 0 +3 +5 eval
:: 8# 9 > 9# 0 +3 +5 eval
:: 9# 9 >
:: 0 > 1 +3 +5 eval
:: 1 > 2 +3 +5 eval
:: 2 > 3 +3 +5 eval
:: 3 > 4 +3 +5 eval
:: 4 > 5 +3 +5 eval
:: 5 > 6 +3 +5 eval
:: 6 > 7 +3 +5 eval
:: 7 > 8 +3 +5 eval
:: 8 > 9 +3 +5 eval
:: 9 > 1# 0 +3 +5 eval
(The initial state)
0
During the evaluation, these 27 fractions will toggle r79(print:) giving us a trigger when the accumulator state might be read. This is demonstrated here as an alternative approach for emitting programs and debugging where the runtime is masking lower registers to the printing register.
07 25338 × 7979/103 = 1962834 01 07 159444 × 7979/103 = 12351492 02 05 1045656 × 6557/2781 = 2465432 fizz 07 262032 × 7979/103 = 20298576 04 06 1750176 × 7031/3296 = 3733461 buzz 05 339282 × 6557/2781 = 799954 fizz 07 82812 × 7979/103 = 6415116 07 07 526536 × 7979/103 = 40788648 08 05 3248208 × 6557/2781 = 7658576 fizz 06 1829280 × 7031/3296 = 3902205 buzz 07 380070 × 7979/103 = 29442510 11 05 2391660 × 6557/2781 = 5639020 fizz 07 580920 × 7979/103 = 45001560 13 07 3930480 × 7979/103 = 304478640 14 04 26252640 × 7663/88992 = 2260585 fizzbuzz 07 188490 × 7979/103 = 14601570 16 07 1242180 × 7979/103 = 96226740 17 05 7898040 × 6557/2781 = 18621880 fizz ..
To explore further, try running these examples yourself:
Reversibility
The laws of physics are intrinsically reversible at a microscopic level, in contrast to most models of computation which are intrinsically irreversible. The discrepancy between the laws of physics and our computer models might be an indication that we might be doing things wrong.
AC 19, fruit-cake 02 19 × 119/19 = 119, apple-cake fruit-salad 01 119 × 715/17 = 5005, apples apple-cake oranges cherries 00 5005 × 30/7 = 21450, apples apples flour sugar oranges cherries
Fractran operators are reversible, meaning that a some programs can run backward to their original state. Evaluation is undone by testing and applying rules by inverting their right and left sides. For a program to be reversible, two rules may not share the same right-side.
:: a > c :: a b > c
In the program below in which a mirror of the issue occurs, a compiler may throw a warning when a left-side is found in multiple rules.
:: a > b :: a > b c
Catalysts
Fractran traditionally compares the accumulator against reduced fractions, but computationally-speaking, getting to the gcd of a fraction does little more than getting rid of otherwise valuable information used during comparison to match against a restricted set of fractions. A strict mode allows for catalysts which are symbols found on both sides of a rewrite rule.
The following two fractions are not equal and reducing the first into the second, eliminates the capability to match against it only when the catalyst green is present in the accumulator:
:: 15/6 red green > green blue :: 5/2 red > blue red green
Nested Stack Machines
A stack-machine can be implemented in Fractran, but it's not for the faint of heart. This computation model keeps an entire program state in a single number, and the following stack machine allocates a whole stack into a single register of that number. The theory is that it is possible to keep a stack of zeros and ones in a single register using a binary encoding for that number.
- Pushing a 0 onto the stack is equivalent to doubling the number.
- Pushing a 1 is equivalent to doubling and adding 1.
- Popping is equivalent to dividing by 2, where the remainder is the number.
If we begin with push, we can see that we are doubling the x register, same as demonstrated above. After the evaluation, our LIFO stack has a value of 30, and is equal to 1 1 1 0, where the right-most one is the item on top. Now, for pop, we can halve the x register, again, same as demonstrated above, and keeping the result of the value in a register for 0, and a register for 1.
:: push 1 x > A A push 1 :: push 1 > x :: push 0 x > A A push 0 :: push 0 > :: pop x x > A pop :: pop x > 1 :: pop > 0 :: A A > x x :: A > x x push 1 = x^3 x^3 push 1 = x^7 x^7 push 1 = x^15 x^13 push 0 = x^30 x^30 pop : 0 x^15 x^15 pop : 1 x^7 x^7 pop : 1 x^3 x^3 pop : 1 x
We can build on these two primitives and define temporary register to keep the result of popping, extra stack operations dup and swap, and a little state-machine to input some of these commands:
:: ?#a 0 > 0#a :: ?#a 1 > 1#a :: ?#b 0 > 0#b :: ?#b 1 > 1#b :: dup > pop ?#a dup-next :: dup-next 0#a > 0#a 0#a push-a push-a :: dup-next 1#a > 1#a 1#a push-a push-a :: swap > swap-next pop ?#a :: swap-next > swap-last pop ?#b push-a :: swap-last > push-b :: push-a 0#a > push 0 :: push-a 1#a > push 1 :: push-b 0#b > push 0 :: push-b 1#b > push 1 :: 1) > push 1 2) 1 :: 2) > push 1 3) 1 1 :: 3) > push 1 4) 1 1 1 :: 4) > push 0 5) 1 1 1 0 :: 5) > swap 6) 1 1 0 1 :: 6) > dup 1 1 0 1 1 1) x
Implementation
A basic implementation of the runtime core is a mere 20 lines:
cc framin.c -o framin view raw
An implementation of the full symbolic runtime is about 300 lines:
cc fractran.c -o fractran view raw
The wise marvels at the commonplace.Confucius
- Fractran Interpreter(C89), used for this documentation.
- Fractran Interpreter(Web)
- Intro to Fractran
- Remembering John Conway
- On Esolang
incoming pocket rewriting phutball firth binary primes fractions