Thoughts on Fractran

Reduction & Catalysts

Conway's 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. The support for catalysts, symbols found on both sides of a rewrite rule, makes for a simpler and faster implementation.

:: 15/6 red green > blue green
:: 5/2 red > blue

red green

These 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.

Deadcode Elimination

An unreachable rule is created when a rule's left-hand side is part of the left-hand side of a rule below it:

:: foo > baz
:: foo bar > baz

foo bar

For a rule to be reachable, all the symbols in the left-hand side must be present in either the right-hand side of an other valid rule, or in the accumulator.

:: violet > red
:: purple > violet

violet

Rules that are unreachable are considered comments and should not be part of the ruleset during evaluation.

Exhaustive Rules

When moving values between registers, each move takes one rewriting and thus can quickly become computationally expensive:

:: a > res
:: b > res

AC 1000, a^3 b^3 
00 1000 × 3/2 = 1500, a^2 res b^3 
00 1500 × 3/2 = 2250, a res^2 b^3 
00 2250 × 3/2 = 3375, res^3 b^3 
01 3375 × 3/5 = 2025, res^4 b^2 
01 2025 × 3/5 = 1215, res^5 b 
01 1215 × 3/5 = 729, res^6 

Completed in 6 steps.

A rule with a right-hand side that does not include symbols present in any of the left-hand sides of the rules above it can be run exhaustively and perform many applications without having to look for the next applicable rule:

AC 1000, a^3 b^3 
00 1000 × 3/2 = 3375, res^3 b^3 
01 3375 × 3/5 = 729, res^6 

Completed in 2 steps.

Reversibility

Fractran operators are reversible, meaning that a some programs can run backward to their original state. Evaluation is undone by applying rules and inverting their numerator and denominator, or right and left sides.

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

For a program to be reversible, two rules may not share identical numerators or denominators. The implementation of a reversible CNOT logic gate differs from the non-reversible logic gates in that we cannot rely on the absence of registers, rules must contain symbols for their absence:

:: c+ t+ cnot > c+ t- cnot
:: c+ t- cnot > c+ t+ cnot
:: c- t+ cnot > c- t+ cnot
:: c- t- cnot > c- t- cnot

Implementation

A basic implementation of the runtime core is a mere 20 lines:

cc framin.c -o framin view raw