Fractran

这是一个在 Rust 中实现 John Conway 发明的神秘编程语言 FRACTRAN 的库。它提供了一种基本的运行 FRACTRAN 程序的方法，并且还实现了一个更适合该语言的自定义数字类型，比传统的类型如 u64 更好。

这是一个底层 crate：正如你下面将看到的，运行程序实际上涉及大量的样板代码。敬请期待一个封装此库并提供简单 CLI 以运行 FRACTRAN 程序的 crate。

快速入门

示例程序

这是 Conway 的原始程序之一，用于生成素数。它们作为程序产生的 2 的幂的指数出现。

// 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 fractio
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]);

处理溢出

你可能注意到，这个程序在 2000 次执行中只打印出 4 个素数。实际上，当你只能使用一个指令时，程序会运行很长时间！此外，数字会迅速变大。《tt class="src-rs">u64 在你输出《tt class="src-rs">11 之前就会溢出：尝试将 .take(2000) 替换为更大的数字，看看我的意思。

为了解决溢出问题，此 crate 有一个 PrimeBasis 类型，它在 FRACTRAN 所需的方式上表现得像 u64，但存储每个数的素数分解而不是实际值。由于 FRACTRAN 的工作方式，实际上很少使用大素数，因此在实践中这是一个巨大的空间改进。

我们可以很容易地修改上述程序以使用 PrimeBasis，这使我们能够计算任意多的素数。

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]);

注意

• 这几乎未经过优化，但也不慢，尤其是当使用PrimeBasis时。每个操作本质上是对使用的素因子数量进行一些非常简单的迭代。对于最大素因子较小的程序，这在大多数情况下都是如此，一个操作将大约有10-20个基本操作。
• 在PrimeBasis中允许的素数数量被导出为MAX_REGS。目前是1000，这是一个很大的数字。（名称是因为将每个素数指数视为更传统程序中的寄存器是最容易想到的：这是寄存器的数量。）
• PrimeBasis使用的素数列表按顺序导出为PRIMES：它是在编译时使用MAX_REGS和一个基本筛子生成的。如果需要，请使用这个和MAX_REGS而不是硬编码。
• 请注意，PrimeBasis不存储其指数列表中的额外尾随零，所以如果不使用额外的寄存器空间，就没有空间成本。我不允许你使用一百万个寄存器的理由是，这将不利于编译时间。

贡献/问题

• 如果你有问题、功能请求或其他类似内容，请随时提出。
• 我会详细说明，但老实说，我实在想象不出任何人会使用这个，因此也无法想象任何人会存在问题或功能请求。