Computation book example code implemented in Rust

announcements
1

About a year ago, I read the book , which I found very inspiring. The book built up my basic thought toward computation.
The example code in this book are all open source, implemented in Ruby
I rewrite the code in the book using rust. The repository is here:
computationbook-rust
Most of the implementation is quite straightforward, just translate the code from Ruby to Rust. The only chapter that I cannot implement is Chapter 6, that uses lambda function only to write a fizzbuzz. I try to implement it but failed to pass compilation. If there are someone interesting to implement it, any patch or PR is welcome.

4 Likes
2

A start

use std::rc::Rc;

type Rp = Rc<Pol>;
enum Pol {
    C(Rc<Fn(Rp) -> Rp>),
    I(i32),
}
use Pol::{C, I};
macro_rules! r {
    ($cl:expr) => {Rc::new(C(Rc::new($cl)))}
}
impl Pol {
    fn call(&self, x: Rp) -> Rp {
        match self {
            &C(ref c) => c(x),
            _ => panic!(),
        }
    }
}

fn to_integer(p: Rp) -> i32 {
    // p(|n|{n+1})(0)
    let np1 = r!(|n: Rp| {
        let np1 = {
            let n = match n.as_ref() {
                &I(n) => n,
                _ => panic!(),        
            };
            n + 1
        };
        Rc::new(I(np1))
    });
    let ans = p.call(np1).call(Rc::new(I(0)));
    match ans.as_ref() {
        &I(n) => n,
        _ => panic!(),
    }
}

fn main() {
    // |_p| {|x| { x } }
    let zero = r!(|_p| r!(|x| x));
    println!("{}", to_integer(zero.clone()));

    // |p| { |x| { p(x) } }
    let one = r!(|p: Rp| r!(move |x| p.call(x)));
    println!("{}", to_integer(one.clone()));

    // |p| { |x| { p(p(x)) } }
    let two = r!(|p: Rp| r!(move |x| p.call(p.call(x))));
    println!("{}", to_integer(two.clone()));

    // |n| { |p| { |x| { p(n(p)(x)) }  } }
    let increment = r!(|n: Rp| {
        let n = n.clone();
        r!(move |p: Rp| {
            let n = n.clone();
            let p = p.clone();
            r!(move |x| p.call(n.call(p.clone()).call(x)))
        })
    });

    // |m| { |n| { n(increment)(m) } }
    let increment_for_add = increment.clone();
    let add = r!(move |m: Rp| {
        let increment = increment_for_add.clone();
        let m = m.clone();
        r!(move |n: Rp| n.call(increment.clone()).call(m.clone()))
    });

    // add(one)(two)
    let a = add.clone().call(one.clone()).call(two.clone());
    println!("1+2={}", to_integer(a));
}
3

That is ... awesome. I never thought that I can implement it like this.

Actually I tried to implement it in a ... dump way, here is the link to branch
https://github.com/yodalee/computationbook-rust/tree/ch6-fizzbuzz/programming_with_nothing/fizzbuzz

Which use native function as lambda. I fight with the compile error when implement Predicat (IS_ZERO). I give up in the end.
Thank you for give me a hint. I will dig into your code recently.

1 Like
4

What I wrote could be cleaned up further. It evolved from an old edit so see after posting; the closure only needs to be in a box (no real harm with rc though.) The helper macro could take the closures identifier. I added at least one errant clone call (only harms performance.) Although implementing the rest would still require many clones. Should also have wrote instead;

let add = { 
    let increment = increment.clone();
    r!(...
})};

It is also not the only way;

  • fn call could be replaced with Deref (or Index, if you like keep the same brace as ruby.)
  • enum Pol could be trait Pol
5

I just had a look through that second link you posted and the way you build "type level" numbers and booleans up from nothing is quite ingenious.

I'm not sure what the rules of the game are, but are you able to somehow use traits with a default impl for the IS_ZERO predicate?

trait MaybeZero {
  fn is_zero(&self) -> bool { false }
}

impl MaybeZero for ZERO {
  fn is_zero(&self) -> bool { true }
}

impl MaybeZero for ONE {}

fn IS_ZERO<T: MaybeZero>(n: T) -> bool { n.is_zero() }

struct ZERO;
struct ONE;

fn main() {
  println!("ZERO is zero? {}", IS_ZERO(ZERO));
  println!("ONE is zero? {}", IS_ZERO(ONE));
}

Although that uses types instead of functions like you have...

6

First, I would like to thank @jonh, I use your proposed initial code and implement the example in the book. It is not complete yet, but so far so good.
Except that my multiply become power and I don't know why. (yay)(yay)(yay)(yay)
I put the source code at a new branch here:
ch6-fizzbuzz-new
There are two major problem: first I have to put everything in main function. I try to put the implementation in another file as const, but Rc cannot be created as const object. The main function is growing very fast, I estimated that when complete, the main function may be 1000 lines. Second, there are many clone need to be added. Pass one layer of closure, another clone is required to tame the compiler XD.

Here is some question I faced, and ask for suggestion:

  1. Is it possible to print out closure? Implement Display for Pol type so I can directly use {} to print out a structure of a closure?
  2. Maybe it is possible to make Rp more general that it can receive multiple argument, so we can reduce the number of clone when passing one layer of closure.
  3. How do you determine that when do add move to closure, and when do not?

To @Michael-F-Bryan. Thank you for your response, it is great too.
However I cannot implement MaybeZero for all the number I created, also IS_ZERO cannot respond rust bool type directly, it should return a lambda function we defined as TRUE, and FALSE. Otherwise other lambda function cannot use the return from IS_ZERO.
However, it is still inspiring response.

:slight_smile:

1 Like
7

Just fix the bug of multiply become power, this is the patch:
https://github.com/yodalee/computationbook-rust/commit/e63bf9cefe1cd9e41d570d7cac40fba4e0659353
though I don't know why this cause multiply transferred to power