FRACTRAN

Fractran is an esoteric programming language. The name is a combination of the words FORTRAN and fraction. What makes it interesting is its simplicity and the fact that it’s as powerful as any other programming language.

I wrote an interpreter back in 2013 in Python and C. In 2021, I wrote a program in Python that takes a Fractran program and translates it to Python.

In this post, we’ll explain what Fractran is all about.

Fractran programs

According to Wikipedia, a Fractran program is an ordered list of positive fractions together with an initial positive integer input n. The program is run by updating the integer n as follows:

For the first fraction f in the list for which nf is an integer, replace n by nf
Repeat this rule until no fraction in the list produces an integer when multiplied by n, then halt.

Example program

For example, consider the very trivial sequence of fractions: $({\frac {3}{2}})$ . Let’s assume the input to be 24 (which is $2^3 \cdot 3^1$ when factorized). Let’s now follow the rules:

$n = 24$
$24 \cdot ({\frac {3}{2}}) = (2^3 \cdot 3^1) \cdot ({\frac {3}{2}}) = (2^2 \cdot 3^2)$ , which is an integer, so we update $n = 36$
$36 \cdot ({\frac {3}{2}}) = (2^2 \cdot 3^2) \cdot ({\frac {3}{2}}) = (2^1 \cdot 3^3)$ , which is an integer, so we update $n = 54$
$54 \cdot ({\frac {3}{2}}) = (2^1 \cdot 3^3) \cdot ({\frac {3}{2}}) = (2^0 \cdot 3^4)$ , which is an integer, so we update $n = 81$
$81 \cdot ({\frac {3}{2}})$ is not an integer, so the program halts

Let’s recap: We started with input $n = 24 = 2^3 \cdot 3^1$ and ended up with $n = 81 = 3^4$ . The program $({\frac {3}{2}})$ actually represents addition of two numbers. The input is of form $2^{a}3^{b}$ , and the program will calculate $2^{a-1}3^{b+1}$ , $2^{a-2}3^{b+2}$ , etc., until eventually, after $a$ steps, it produces the final output $3^{a+b}$ .

Technical details

The example we showed reveals the structure of Fractran programs:

Using Gödel numbering, the product of some prime numbers is used to represent the mapping memory location -> value.
1. For example, the number $2^3\cdot3^5$ means that in the first memory location (2 is the first prime) we store the value 3, and in the second memory location (3 is the second prime) we store the value 5.
Numerators can be used to increase a value in the memory.
Denominators can be used to decrease a value in the memory, as well as control the program’s flow.

In general, the output of frac2py.py shows that all Fractran programs are of the following form:

while True:
  # the conditional is constructed by the factorization of the denominator
  if data[x1] >= y1 and data[x2] >= y2 and ...:
    # statements constructed by the denominator
    data[x1] -= y1
    data[x2] -= y2
    ...
    # statements constructed by the numerator
    data[a1] += b1
    data[a2] += b2
    ...
    continue

  if ...:
    ...
    continue

  break

Conclusion

Even though I blogged about something similar to this in the past, and also wrote a program or two around the idea, it is still interesting how much can be encoded with prime numbers, and the amount of information we can extract using prime factorization.

Considering my previous attempt at Advent of Code in which I used around 20 programming languages, it’d be fun to try solving some AoC challenges with a Fractran program 🙂