FRACTRAN

This is a library that implements the FRACTRAN esoteric programming language, invented by John Conway, in Rust. It supplies a basic way of running programs in FRACTRAN and additionally implements a custom numeric type that is better suited for the language than traditional types like u64.

This is a low-level crate: as you’ll see below, there’s a lot of boilerplate involved in actually running a program. Stay tuned for a crate that wraps this and provides a simple CLI for running FRACTRAN programs.

Quickstart

Sample Program

This is one of Conway’s original programs, used to generate the prime numbers. They appear as the exponents of the powers of 2 that the program produces.

// make the list of fractions
let nums: Vec<u64> = vec![17, 78, 19, 23, 29,
                          77, 95, 77, 1, 11,
                          13, 15, 15, 55];
let denoms: Vec<u64> = vec![91, 85, 51, 38, 33,
                            29, 23, 19, 17, 13,
                            11, 14, 2, 1];

// Fraction is generic because it can use types other than u64, as we'll see shortly

// this is probably the easiest way to make a big list of fractions
let fracs: Vec<Fraction<u64>> = nums.into_iter()
                                    .zip(denoms)
                                    .map(|(num, denom)| Fraction::new(num, denom))
                                    .collect();

// create the program from that list
let prog = Program::new(fracs);
let mut primes = vec![];

// lazy_exec() returns an iterator that runs as long as the program does, which in this case is forever
// we fix that by stopping early using take()
// note also that we feed in 2
for out in prog.lazy_exec(2).take(2000) {
    // Rust's integer methods are pretty neat!
    if out.is_power_of_two() {
        primes.push(out.trailing_zeros());
    }
}
assert_eq!(primes, vec![2, 3, 5, 7]);

Dealing with Overflow

You might notice that this only prints out 4 primes in 2000 executions. As it turns out, when you can only use a single instruction, programs run long! Additionally, the numbers can get big really quickly. u64 will overflow before you can output 11: try replacing .take(2000) with a larger number to see what I mean.

To fix the overflow issue, this crate has a PrimeBasis type that behaves like u64 in the ways that FRACTRAN needs, but stores the prime factorization of each number instead of the actual value. Because of the way FRACTRAN works, it’s very rare to use large primes, and so in practice this is a huge space improvement.

We can modify the above program pretty easily to use PrimeBasis, which lets us compute as many primes as we like.

let nums: Vec<u64> = vec![17, 78, 19, 23, 29,
                          77, 95, 77, 1, 11,
                          13, 15, 15, 55];
let denoms: Vec<u64> = vec![91, 85, 51, 38, 33,
                            29, 23, 19, 17, 13,
                            11, 14, 2, 1];

// we have to now create a PrimeBasis, which adds a little more boilerplate here
// try_new() returns a Result because there's a fixed number of primes that the program uses
// any number that requires a factor not in our list of primes can't be represented
// this is almost never an issue because it's very rare you want to use very large prime factors
let fracs: Vec<Fraction<PrimeBasis>> = nums.into_iter()
                                           .zip(denoms)
                                           .map(|(num, denom)| Fraction::new(
                                               PrimeBasis::try_new(num).unwrap(),
                                               PrimeBasis::try_new(denom).unwrap(),
                                           ))
                                           .collect();

let prog = Program::new(fracs);
let mut primes = vec![];

// now can run the program for a lot longer: 100,000 iterations is pretty fast on my machine still
// note that we need to feed in a PrimeBasis because that's the type our program is in
for out_pb in prog.lazy_exec(PrimeBasis::try_new(2).unwrap())
                  .take(100_000) {
    // we no longer have the integer methods, so we directly work with the list of exponents
    if out_pb.exps[1..].iter().all(|&exp| exp == 0) {
        primes.push(out_pb.exps[0]);
    }
}
// we have a lot more primes now!
assert_eq!(primes, vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]);

Notes

• This is hardly optimized, but it isn’t slow either, especially when using PrimeBasis. Each operation is essentially doing some very simple iteration over the number of prime factors being used. For programs where the largest prime factor is small, which is most programs, a single operation is going to be on the order of 10-20 basic operations.
• The number of primes allowed in a PrimeBasis is exported as MAX_REGS. It’s currently 1000, which is a lot. (The name is because it’s easiest to think of each prime exponent as a register in a more traditional program: this is the number of registers.)
• The list of primes used by PrimeBasis, in order, is exported as PRIMES: it’s generated at compile time using MAX_REGS and a basic sieve. Use this and MAX_REGS instead of hardcoding if it’s necessary.
• Note that PrimeBasis doesn’t store extra trailing zeroes in its list of exponents, so there’s no space cost if you aren’t using the extra register space. The reason I don’t let you use a million registers is because that would adversely affect compilation time.

Contributing/Issues

• If you have an issue, feature request, or anything like that, feel free to file one.
• I would elaborate, but I honestly can’t imagine what anyone’s use case for this would be and therefore can’t really imagine anyone having issues or feature requests.