I’ve always found esoteric programming languages pretty amusing – they’re silly, occasionally witty, but most of all there’s the ones which take a lot of thinking, like Golfcode or Whitespace.
Today I had a bit of fun and tried writing a Fibonacci number generator in FRACTRAN. FRACTRAN, invented by the infamous John Conway, is a programming language where programs are just a list of fractions, and input is a single positive integer n. At each iteration, n is updated by multiplying it by the first fraction in the list which results in another positive integer, until this is no longer possible.
For instance, one of the simplest FRACTRAN programs is just:
3/2
Given input in the form of n = 2a × 3b, the program will continue multiplying n by 3/2 until n is no longer divisible by 2. This will happen when n is of the form 3a+b, so the single instruction program 3/2 is actually an addition program which stores the result of a+b as the exponent of 3 in the output.
The reason why FRACTRAN works is that what you really have is a bunch of registers labelled by prime numbers. For example, 3072 = 210 × 31 represents a state where register 2 has the value ten, and register 3 has the value one. Each fraction is then an instruction to increase or decrease the register values, provided that the result doesn’t make any register have a negative value. So for 3/2, if n is divisible by two then register 3 is incremented by one and register 2 is decremented by one. This shows how if statements are possible in FRACTRAN.
The Fibonacci program I wrote is the following:
39/55 33/65 78/77 66/91 1/11 1/13 5/2 7/3 11/1
The program starts with the initial value 3 = 20 × 31 and if at any iteration a number of the form 2a × 3b appears, then a and b are successive Fibonacci numbers.
It’s my first FRACTRAN program so it could probably be improved, but hey I’m pretty happy that I got it working. The hardest part was figuring out how to do loops in FRACTRAN, which is a surprisingly tough challenge.
My program works like so:
- Initially, registers 2 and 3 store a and b respectively, which are consecutive Fibonacci numbers (with a < b by the initial condition).
- a and b are then transferred to registers 5 and 7 respectively.
- a is added from register 5 to register 2, while b is added from register 7 to both registers 2 and 3.
- The result is that registers 2 and 3 now hold b and a+b respectively
This is how the fractions work:
- 11 and 13 are indicator variables. If either of the registers are set to something nonzero, then one of the first four fractions will trigger, either subtracting 1 from register 5 and adding 1 to register 2, or subtracting 1 from register 7 and adding 1 to both registers 2 and 3. There’s two indicator variables because I couldn’t figure out how to do loops well – here registers 11 and 13 alternate from being 0, 1 and 1, 0 respectively so that one of them will always be set while this addition step is being performed.
- This addition will continue until n is no longer divisible by 2 or 3, in which case 1/11 and 1/13 nullify the indicator variables
- After this, 5/2 and 7/3 do the transferring from registers 2,3 to registers 5,7
- Once the transfer is complete, 11/1 retriggers the indicator variable and we go again
Of course, if you want the program to actually terminate, then a slight modification can be made (to make register 2 the only input, the other registers got shifted up by one):
85/91 65/119 255/143 195/187 1/13 1/17 7/3 11/5 13/2 1/11
This version takes in input of the form 2n × 5 and returns 7F(n).
I think the nice thing about FRACTRAN is how easy programs are to explain to people, even if they don’t do computer science. Unfortunately though, explaining how the program actually works is a lot harder.
For some additional FRACTRAN trivia, somebody actually created a FRACTRAN interpreter in FRACTRAN, which goes to show that even a language that is easy to describe can be capable of quite a lot.
One-day Attention Span 