➗ FRACTRAN_rs ➗

Because why not?

📜 The Language

Each FRACTRAN program consists of a finite ordered tuple of positive rational numbers (fractions). It takes as input a natural number and either outputs another natural number or does not halt. To do this, take the input number n and compare it to each fraction f in turn. If nf is an integer, then restart the procedure with that number as input. If we reach the end of the list of fractions without that ever being an integer, halt.

For example, here is a program that takes in a number and outputs its largest odd divisor.

1/2

On the other hand, this program takes an input of the form 2^a3^b and outputs 5^a+b.

5/2  5/3

We could think of this as the program to add two numbers together. Similarly the single instruction 5 / 6 takes 2^a3^b to 5^max(a,b).

The most famous example of a FRACTRAN program is PRIMEGAME:

17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/2 1/7 55/1

Given the input of 2, this program never halts, but every time it hits a power of two, it does so in the form 2^p for successive primes p.

🦄 Using FRACTRAN_rs

For examples of usage, see the examples folder. Simple programs can be constructed as using the fractran! macro:

#[macro_use]
use fractran_rs::*;

let program : FractranProgram<usize, usize> = fractran!(5/2 5/3);
let result = program.run(24);

On the other hand, you may wish to provide encoding and decoding to the natural numbers for arbitrary datatypes. For example here we consider a hypothetical "find in array" program:

#[macro_use]
use fractran_rs::*;

struct Input<'a>(usize, &'a [usize]);

impl<'a> Into<usize> for Input<'a> {
  fn into(self) -> usize { todo!() }
}

struct Output(Option<usize>);

impl From<usize> for Output {
  fn from(_: usize) -> Self { todo!() }
}

fn main() {
    let program : FractranProgram<Input, Output> = fractran!(/* ... */);
    let input = Input(3, &[2, 3, 5, 7, 11]);
    let result = program.run(input);
}

You can also "step through" your programs. To do this, call start on the program, followed by next:

#[macro_use]
use fractran_rs::*;

let primegame : FractranProgram<usize, usize> = fractran!(/* ... */);
let mut program_run = primegame.start(2);
program_run.next(); // Some(15)
program_run.next(); // Some(825)
// etc.

This is implemented as an iterator interface, so you can run through the entire program with

#[macro_use]
use fractran_rs::*;

let program : FractranProgram = fractran!(/* ... */);

for intermediate_result in program.start(3) {
  // ...
}

🎨 Prior art and alternatives

You may be intersted in fractran and fractran_macros if you'd like to write fractran but have it compile to machine code. Both use prime factorised representations of numbers internally.

I would like to recommend reading Michael Malis' excellent article on writing a compiler that targets FRACTRAN.

🚨 Limitations

Currently FRACTRAN_rs is limited to working with usizes as numerators and denominators of fractions. This is to keep the codebase to under 100 LOC. Besides, 64 bits (at time of writing) should be enough for anyone.

Due to the current economic climate, all FRACTRAN_rs programs must be finite.

👩🏼‍💻 Contributing

FRACTRAN_rs is considered feature-complete by the author. However, pull requests to fix bugs or suggest new features are welcome.