#+TITLE: FRACTRAN

This is a library that implements the [[https://en.wikipedia.org/wiki/FRACTRAN][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.
#+BEGIN_SRC rust
// 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]);
#+END_SRC
** 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.
#+BEGIN_SRC rust
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]);
#+END_SRC
* 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.