Elements Of Programming (Stepanov, Mc Jones) In Rust

000-eop

Elements Of Programming (A.Stepanov, P.McJones) implemented in Rust

Generic programming Rust using traits and generic functions

000-foundation.rs

/// requires(BinaryOperation(Op))
fn square<T : Copy, Op : Fn(T, T) -> T>(x : Op::Output, op : Op) -> Op::Output {
    return op(x, x);
}

fn square_i64(x: i64) -> i64 {
    return x * x;
}

fn multiply_i64(a : i64, b : i64) -> i64 {
    return a * b;
}

fn xor(a : bool, b : bool) -> bool {
    return a ^ b;
}

#[derive(PartialEq,Copy,Clone)]
struct vec2 {
    x : f64,
    y : f64
}

fn vec2_add(a : vec2, b : vec2) -> vec2 {
    return vec2 { x: a.x + b.x, y: a.y + b.y }
}

impl std::fmt::Display for vec2 {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(f, "({}, {})", self.x, self.y)
    }
}

fn main() {
    let x = 3;
    println!("square: {} = {}", x, square_i64(x));
    println!("generic square (mul): {} = {}", x, square(x, multiply_i64));
    let y = true;
    println!("generic square (xor): {} = {}", y, square(y, xor));
    let p = vec2 { x: 0.0, y : 1.0 };
    println!("generic square (vec2_add): {} = {}", p, square(p, vec2_add));
}

001-transformations.rs

/// models(UnaryOperation)
fn abs(x : i64) -> i64 { 
    return x.abs();
}

/// models(BinaryOperation)
fn euclidean_norm2(x : f64, y : f64) -> f64 {
    let n = x * x + y * y;
    return n.sqrt();
}

/// models(TernaryOperation)
fn euclidean_norm3(x : f64, y : f64, z : f64) -> f64 {
    let n = x * x + y * y + z * z;
    return n.sqrt();
}

trait SemiRegular : PartialEq + Copy {}

impl SemiRegular for i64 {}
impl SemiRegular for u64 {}

/// zero : additive unit
/// one : multiplicative unit
trait Integer : SemiRegular {
    // doesn't work: const zero : Self;
    // doesn't work: const one : Self;
    fn zero() -> Self;
    fn one() -> Self;
    fn add(Self, Self) -> Self;
    fn sub(Self, Self) -> Self;
}

impl Integer for i64 {
    fn zero() -> Self { return 0; }
    fn one() -> Self { return 1; }
    fn add(a : Self, b : Self) -> Self { return a + b; }
    fn sub(a : Self, b : Self) -> Self { return a - b; }
}

impl Integer for u64 {
    fn zero() -> Self { return 0; }
    fn one() -> Self { return 1; }
    fn add(a : Self, b : Self) -> Self { return a + b; }
    fn sub(a : Self, b : Self) -> Self { return a - b; }
}

trait Transformation {
    type Distance : Integer;
}

impl Transformation for fn(i64) -> i64 {
    type Distance = u64;
}

impl Transformation for Fn(i64) -> i64 {
    type Distance = u64;
}

/// requires(Transformation(F) && Integer(N))
fn power_unary<F : Fn(T) -> T, T, N : Integer>(mut x : F::Output, mut n : N, f : F) -> F::Output {
    // Precondition n>=0 && (\forall i \in N) 0 < i <= n \implies f^i(x) is defined
    while n != N::zero() {
        n = <N as Integer>::sub(n, N::one());
        x = f(x);
    }
    return x;
}

// requires(Transformation(F))
fn distance<F : Transformation + Fn(T) -> T, T : PartialEq>(mut x : F::Output, y : F::Output, f : F) -> <F as Transformation>::Distance {
    // doesn't compile: type N = F::Distance;
    let mut n = F::Distance::zero();
    while x != y {
        x = f(x);
        n = <F::Distance as Integer>::add(n, F::Distance::one());
    }
    return n;
}

fn collision_point<F : Transformation + Fn(T) -> T, T : SemiRegular, P : Fn(T) -> bool>(x : F::Output, f : F, p : P) -> T {
    // Precondition: p(x) \equiv f(x) is defined
    if !p(x) { return x; }
    let mut slow = x;
    let mut fast = f(x);
    while fast != slow {
        slow = f(slow);
        if !p(fast) { return fast; }
        fast = f(fast);
        if !p(fast) { return fast; }
        fast = f(fast);
    }
    return fast;
}

// we need to cast a function (fn(i64)->i64 {function_name}) to its more general type (fn(i64)->i64) in order to let the compiler find our Transformation trait's implementation
macro_rules! unary_transformation {
    ($f : ident, $T : ident) => ($f as fn($T) -> $T);
}

fn main() {
    let x = 1.0;
    let y = 2.0;
    let z = 3.0;
    println!("{} == {}", euclidean_norm3(x, y, z), euclidean_norm2(euclidean_norm2(x, y), z));
    {
        let x : i64 = -5;
        let n : i64 = 8;
        let y = power_unary(x, n, abs);
        println!("power_unary(abs, {}, {}) = {}", n, x, y);
        println!("distance({}, {}, abs) = {}", x, y, distance(x, y, unary_transformation!(abs,i64)));
        let always_defined = |_| true;
        println!("collision_point({}, abs) = {}", x, collision_point(x, unary_transformation!(abs,i64), always_defined));
    }
}