Donald Knuth's Man or Boy test is missing for Rust

help
1

Seems like no one has implemented this classical old problem in Rust.

I would have no idea on how to do it, but maybe someone else do?

2 Likes
2

Beside being able to write it there are two additional tasks:

  • Make it sufficiently easy to write the function;
  • Make the function light&efficient enough when you pump the k value up to 25+ as in the D language solution, without changing the algorithm.
3

Here's one solution: playground

This solution is closer to C than Algol or D, because in Rust it is not possible to create a recursive closure; this doesn't compile:

let b = || a(b);

There are various ways around it, but emulating a closure with an explicit type is probably the simplest.

This version uses an enum to represent a value that can be either simple isize or a pending invocation to B. A very similar version can be written to use trait objects instead of enum, but since trait objects are twice as large as normal references, it uses almost twice as much memory, and runs longer.

3 Likes
5

There is an implementation in the rust-rosetta repository here.

We're always looking for more contributors!

1 Like
6

Neat trick to give b and tmp the same lifetime!

7

The best solution I've seen so far on Reddit is this one, with small changes:

use std::{env, thread};
use std::cell::Cell;

enum Val<'a> {
    Imm(isize),
    Bfn {
        k: &'a Cell<isize>,
        x1: &'a Val<'a>,
        x2: &'a Val<'a>,
        x3: &'a Val<'a>,
        x4: &'a Val<'a>,
    },
}

impl<'a> Val<'a> {
    fn eval(&self) -> isize {
        match *self {
            Val::Imm(v) => v,
            Val::Bfn { k, x1, x2, x3, x4 } => {
                k.set(k.get() - 1);
                a(k.get(), self, x1, x2, x3, x4)
            }
        }
    }
}

fn a<'a>(k: isize, x1: &Val, x2: &Val, x3: &Val, x4: &Val, x5: &Val) -> isize {
    let k = &Cell::new(k);
    let b = Val::Bfn { k, x1, x2, x3, x4 };

    if k.get() > 0 {
        b.eval()
    } else {
        x4.eval() + x5.eval()
    }
}

fn main() {
    let k = match env::args().nth(1) {
        Some(k) => k.parse().unwrap(),
        None => 10,
    };

    thread::Builder::new()
    .stack_size(6 * 1024 * 1024 * 1024)
    .spawn(move || {
        let z = Val::Imm(0);
        let p = Val::Imm(1);
        let n = Val::Imm(-1);
        println!("{}", a(k, &p, &n, &n, &p, &z))
    })
    .unwrap()
    .join()
    .unwrap();
}

It generates smaller stack frames compared to the object trait versions. For me it runs up to k=26 in few seconds.

2 Likes