* FRACTRAN interpreter written by Viktors Berstis
* FRACTRAN - one of the most compact programming languages. A John Conway discovery.
* A FRACTRAN program is simply a list of rational fractions
* The Fractran computer tries multiplying the accumulator by the
* fractions in the list until one gets an integer result.
* Then the process repeats. The accumulator starts with 2 in it.
* The computer is extremely inefficient and needs to handle very large integers.
* The demo program here computes a sequence of all prime numbers.
* The answers occur when the accumulator is a power of 2, and the exponent is
* the prime number found. You will be lucky to get past 5 unless you implement
* long integer arithmetic with strings.
* A FRACTRAN program (not shown), about three times larger, can implement a
* universal turing machine.
* Hint for those trying to figure out how this works:
* Look at the prime factorization of all of the numbers involved
* Array of the fractions in the FRACTRAN program
* The fractions are stored as a string of primes, each to the appropriate power
Frac = ARRAY('14')
* Fractran program to calculate all prime numbers:
( 17 / 91) ; Frac< 1> = " 7^-1 13^-1 17^1 "
( 78 / 85) ; Frac< 2> = " 2^1 3^1 5^-1 13^1 17^-1 "
( 19 / 51) ; Frac< 3> = " 3^-1 17^-1 19^1 "
( 23 / 38) ; Frac< 4> = " 2^-1 19^-1 23^1 "
( 29 / 33) ; Frac< 5> = " 3^-1 11^-1 29^1 "
( 77 / 29) ; Frac< 6> = " 7^1 11^1 29^-1 "
( 95 / 23) ; Frac< 7> = " 5^1 19^1 23^-1 "
( 77 / 19) ; Frac< 8> = " 7^1 11^1 19^-1 "
( 1 / 17) ; Frac< 9> = " 17^-1 "
( 11 / 13) ; Frac<10> = " 11^1 13^-1 "
( 13 / 11) ; Frac<11> = " 11^-1 13^1 "
( 15 / 2) ; Frac<12> = " 2^-1 3^1 5^1 "
( 1 / 7) ; Frac<13> = " 7^-1 "
( 55 / 1) ; Frac<14> = " 5^1 11^1 "
* Pow2 is a pattern to check when Acc is a power of two
Pow2 = POS(0) SPAN(' ') '2^' SPAN(&DIG) . pow SPAN(' ') RPOS(0)
* Fact is a pattern to extract one term from the fraction
Fact = SPAN(' ') SPAN(&DIG) . base '^' SPAN(&DIG '-') . pow
* Function to multiply the symbolic fractions:
DEFINE('MULT(x,y)')
* Starting value for the accumulator:
Acc = " 2^1 "
LOOP J = 1
TEST s = MULT(Frac,Acc)
J = J + 1
* If there is a negative power, it is not an integer
s '-' :S(TEST)
Acc = s
Acc Pow2 :F(LOOP)
OUTPUT = Acc ' = Accumulator, prime = ' pow :(LOOP)
* Multiply two symbolic fractions:
MULT x Fact = ' ' :F(done)
y ' ' base '^' SPAN(&DIG '-') . p = ' ' base '^' (p + pow) :S(MULT)
y = y ' ' base '^' pow ' ' :(MULT)
done y ' ' SPAN(&DIG) '^0 ' = ' ' :S(done)
db y ' ' SPAN(' ') = ' ' :S(db)
MULT = y :(RETURN)
END