https://wiki.xxiivv.com/site/fractran.html

XXIIVV

  * assembly
  * two dimensional
  * concatenative
  * functional
  * imperative
  * rewriting

  * fractran
  * interaction nets
  * thue
  * modal

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

 1. The Accumulator
 2. The Fractions

Liu Xing Tong Xin  Typical Fractran Programmer

The Accumulator

+------------------------+
|            | Registers |
|Accumulator |-----------|
|            |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(24 x 32 x 7), r2 has the value
4, r3 has the value 2, r7 has the value 1, and all other registers
are unassigned.

The Fraction

[fractran]

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 x 5^1)/(2^6)|(3^1 x 7^1)/(2^2 x 5^1) |
|----------------+-----------------+------------------------|
|                |if(r2 >= 6){     |if(r2 >= 2 && r5 >= 1){ |
|if(r3 >= 1){    |        r2 -= 6; |        r2 -= 2;        |
|        r3 -= 1;|        r3 += 1; |        r5 -= 1;        |
|        r2 += 1;|        r5 += 1; |        r3 += 1;        |
|        return; |        return;  |        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  15/6 left.2 side.3 > side.3 right.5

AC 6 left side  accumulator
00 6 x 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 left-side, and what to replace them
with on the right-side.

[fractran]

Programming In Fractran

In a rule definition, which is a fraction where prime factorization
is written as symbols, we find symbols to the left-side of the spacer
(>) to be rewritten by symbols 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 by the
product of the multiplication of the accumulator with the fraction,
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 x 7/30 = 5005, apples apple-cake oranges cherries
01 5005 x 17/715 = 119, apple-cake fruit-salad
02 119 x 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!

[fractran] The Book of Numbers, John Conway

Logic & Arithmetic

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:

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

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

You can get the sum of two registers(x+y) 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
:: y > x

AC 144 x^4 y^2
00 144 x 2/3 = 96, x^5 y
00 96 x 2/3 = 64, x^6

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

:: x y >
:: y > x

AC 576 x^6 y^2
00 576 x 1/6 = 96, x^5 y
00 96 x 1/6 = 16, x^4

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

:: r acc x y

:: iter acc > x iter
:: iter >
:: x y > r acc y
:: y > iter
:: x >

AC 8575 x^2 y^3
.. r^6

Similarly to the multiplication, you can get the quotient and
remainder of two registers(x/y) by doing a series of subtractions:

:: x y res rem div1 acc1 div2 acc2

:: x y div1 > rem acc1
:: acc1 > div1
:: y div1 >
:: div1 > res div2
:: rem div2 > y acc2
:: acc2 > div2
:: div2 > div1
:: y >

AC x^7 y^2 div1
.. res^3 rem

To explore Fractran further, have a look at some of the examples:

  * Fizzbuzz
  * Tic-Tac-Toe
  * Game Of Life(video)

Example: Tic-Tac-Toe

To handle output, nothing special is to be done, the resulting
accumulator at the end of an evaluation is a valid output value, some
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.

To handle input, we can type in new symbol tokens and appending their
value to the accumulator when evaluation halts. 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!

Notes

Fractran operators are reversible, meaning that some programs can be
run backward, back to its original state. To undo an operation,
evaluation is undone by inverting the numerator and denumerator:

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

Implementation

The rewriting implementation of the runtime can be implemented in
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 phutball firth primes fractions

WebringMerveillesNoNazis!UxnPowered Devine Lu Linvega (c) 2008-2024
BY-NC-SA 4.0CreativeCommons
---------------------------------------------------------------------