Code Golf: Fractran

Question

The Challenge

Write a program that acts as a Fractran interpreter. The shortest interpreter by character count, in any language, is the winner. Your program must take two inputs: The fractran program to be executed, and the input integer n. The program may be in any form that is convenient for your program - for example, a list of 2-tuples, or a flat list. The output must be a single integer, being the value of the register at the end of execution.

Fractran

Fractran is a trivial esoteric language invented by John Conway. A fractran program consists of a list of positive fractions and an initial state n. The interpreter maintains a program counter, initially pointing to the first fraction in the list. Fractran programs are executed in the following fashion:

1. Check if the product of the current state and the fraction currently under the program counter is an integer. If it is, multiply the current state by the current fraction and reset the program counter to the beginning of the list.
2. Advance the program counter. If the end of the list is reached, halt, otherwise return to step 1.

For details on how and why Fractran works, see the esolang entry and this entry on good math/bad math.

Test Vectors

Program: [(3, 2)]
Input: 72 (2³3²)
Output: 243 (3⁵)

Program: [(3, 2)]
Input: 1296 (2⁴3⁴)
Output: 6561 (3⁸)

Program: [(455, 33), (11, 13), (1, 11), (3, 7), (11, 2), (1, 3)]
Input: 72 (2³3²)
Output: 15625 (5⁶)

Bonus test vector:

Your submission does not need to execute this last program correctly to be an acceptable answer. But kudos if it does!

Program: [(455, 33), (11, 13), (1, 11), (3, 7), (11, 2), (1, 3)]
Input: 60466176 (2¹⁰3¹⁰)
Output: 7888609052210118054117285652827862296732064351090230047702789306640625 (5¹⁰⁰)

Submissions & Scoring

Programs are ranked strictly by length in characters - shortest is best. Feel free to submit both a nicely laid out and documented and a 'minified' version of your code, so people can see what's going on.

The language 'J' is not admissible. This is because there's already a well-known solution in J on one of the linked pages. If you're a J fan, sorry!

As an extra bonus, however, anyone who can provide a working fractran interpreter in fractran will receive a 500 reputation point bonus. In the unlikely event of multiple self-hosting interpreters, the one with the shortest number of fractions will receive the bounty.

Winners

The official winner, after submitting a self-hosting fractran solution comprising 1779 fractions, is Jesse Beder's solution. Practically speaking, the solution is too slow to execute even 1+1, however.

Incredibly, this has since been beaten by another fractran solution - Amadaeus's solution in only 84 fractions! It is capable of executing the first two test cases in a matter of seconds when running on my reference Python solution. It uses a novel encoding method for the fractions, which is also worth a close look.

Honorable mentions to:

• Stephen Canon's solution, in 165 characters of x86 assembly (28 bytes of machine code)
• Jordan's solution in 52 characters of ruby - which handles long integers
• Useless's solution in 87 characters of Python, which, although not the shortest Python solution, is one of the few solutions that isn't recursive, and hence handles harder programs with ease. It's also very readable.

Answer 1

Fractran - 1779 fractions

(Edit: fixed)

(I hope people are still following this thread, because this took a while!)

It appears SO won't let me post something as long as this, so I posted the Fractran source here.

Input is specified as follows:

First, we encode a fraction m/n = p_0^a0... p_k^ak by:

• Start with 1. Then, for each ai:
• Multiply by p_2i^ai if ai > 0
• Multiply by p_2i+1^{-ai} if a_i < 0

This way, we encode any fraction as a positive integer. Now, given a progoram (sequence of encoded fractions F0, F1, ...), we encode that by

p_0^F0 p1^F1 ...

Finally, input to the interpreter is given by:

2^(program) 3^(input) 5

where program and input are encoded as above. For example, in the first test problem, 3/2 gets encoded to 15, so the program gets encoded to 2^15; and 108 gets encoded to 500. So, we pass

2^{2^15} 3^500 5

to the program. The output, then is of the form

2^(program) 3^(output)

so in the first example, it'll be

2^{2^15} 3^3125

---

How does it work?

I wrote a meta-language that compiles down to Fractran. It allows for functions (simple Fractran and sequences of other functions), and a while loop and if statement (for convenience!). The code for that can be found here.

If you want to compile that code down to Fractran yourself, my (C++) program can be found here [tar.gz]. In a stunning display of dogfooding (and showing off), I used my C++ YAML parser yaml-cpp, so you'd have to download and link with that. For both yaml-cpp and the "compiler", you'll need CMake for cross-platform makefile generating.

The usage of this program is:

./fracc interpreter.frp

The it reads the name of a function from standard input, and writes the corresponding "pseudo-Fraction" (I'll explain that in a second) to standard output. So to compile the interpreter (the Interpret function), you could run

echo "Interpret" | ./fracc interpreter.frp > interpret

The output ("pseudo-Fractran") will be a sequence of lines, each with a string of space-separated digits. A line corresponds to a fraction: if the nth digit in the line is an, then the fraction is the product of p_n^an.

It's very easy to convert this to Fractran, but if you're lazy, you can use to-fractions.py. [Note: earlier I had a C++ program, and I had carelessly ignored integer overflow. I translated it to Python to avoid this.]

Note about input: if you want to test out a different function this way, the convention is always the same. It has a number of parameters (usually the comment above the function explains this) in pseudo-Fractran, so give it what it wants, plus a 1 on the very next slot (so in ordinary Fractran, multiply once by the first prime that it won't use). This is a "signal" bit to the function to start going.

---

However,

I don't recommend actually trying to run the Fractran interpreter (alas). I tested many of its components, and, for example, the function IncrementPrimes, which takes a pair of primes and returns the next two primes, takes about 8 minutes to run, using my silly C++ interpreter (no need to post that :). Plus, it goes (at least) quadratically in the number of function calls - doubling the number of function calls makes it take at least four times as long (more if there are while loops or if statements). So I'm guessing that running the interpreter will take at least days, if not years :(

So how do I know it works? Well, of course I'm not 100% certain, but I'm pretty close. First of all, I tested many, many of its components, and in particular, I tested all of the elements of the meta-language (sequences of functions and if and while statements) very thoroughly.

Also, the meta-language is easy to translate into your favorite language, and even easier to translate to C++, since all parameters of functions are passed by reference. If you're feeling lazy again, you can download my translation here [tar.gz] (there's no makefile; it's just two .cpp files, so directly calling gcc is fine).

So you can compare the two interpreters, run the C++ version (it also takes input/output in pseudo-Fractran), check that that works, and then convince yourself that the meta-language works too.

---

Or!

If you're feeling inspired, and really want to see this interpreter interpreted, you can write a "clever" Fractran interpreter based around the type of Fractran output that we get. The output is very structured - sequences of functions are implemented using signals, so if you somehow cache where the interpreter was, you could jump there immediately if nothing important changed. This, I think, would dramatically speed up the program (perhaps cutting down running time by one or more powers).

But, I'm not really sure how to do this, and I'm happy with what's done, so I'll leave it as an exercise for the reader.