xpr

Disclaimer: This is a toy project that was developed mainly for procrastination purposes.

xpr is a rust library that allows you to use expression templates with your custom type. It is inspired by boost::yap. Expressions can be lazily evaluated and manipulated using a Fold trait.

Example usage

use xpr::*; 

// An expression representing an operation
let y = -Xpr::new(2)*Xpr::new(-21);

// lazy evaluation
assert_eq!(y.eval(), 42);

License

Dual-licensed to be compatible with the Rust project.

Licensed under the Apache License, Version 2.0 or the MIT license, at your option. This file may not be copied, modified, or distributed except according to those terms.

lib.rs:

This crate allows you to use expression templates with your custom type. It is inspired by the C++ expression template library boost::yap.

To use xpr, all you need to do is wrap all input variables to an expression in calls to Xpr::new and apply any supported operation to them. The result will be an object representing the operations you performed. Any possible chain of operations will be represented by their own specific type.

Usage

Evaluation of the expression is be performed lazily by calling Xpr::eval:

use xpr::Xpr;

// create an exression. x will be a type representing the
// addition of 7 and 5, not the result of the calculation
let x = Xpr::new(7) + Xpr::new(5);

// lazily evaluate the expression
assert_eq!(x.eval(), 12);

In the above example, the type of x is Xpr<Add<(Xpr<Term<{integer}>>, Xpr<Term<{integer}>>)>>[^note]. It is a type representing the addition of two integers. To actually evaulate the expression, we call x.eval().

[^note]: All crate and nested module names have been omitted in the type for better readability.

In addition to lazy evaluation, you can manipulate expressions using the Fold trait. A struct implementing Fold can replace terminals (leaf expressions) and perform operations along the way. It can be stateful or a zero-sized type, depending on your needs.

use xpr::{Xpr, Fold, ops::Term};

struct Fortytwoify;

impl Fold<Term<f64>> for Fortytwoify {

    // We will replace these terminals by terminal expressions wrapping f64 values
    type Output = Xpr<Term<f64>>;

    // replaces terminals with terminals wrapping the value 42.
    fn fold(&mut self, _: &Term<f64>) -> Self::Output {
        Xpr::new(42.)
    }
}

// create an expression
let x = -Xpr::new(2.)/Xpr::new(5.);

// fortitwoify the expression
let y = Fortytwoify.fold(&x);

// lazily evaluate the expression
assert_eq!(y.eval(), -1.);

Refer to the documentation of Fold for more useful examples.

Limitations

Current limitiations of the library are

• that only expression holding terminals of the same type can be transformed using Fold,
• that terminals are the only expressions that can be transformed using Fold.

As a consequence, we can not mix e.g. scalars, vectors and matrices in expressions, which is a major limitation.

These restrictions could easily be lifted, once Rust supports specialization, which is probably not any time soon.

Performance

xpr allows us to write arithmetic operations like we would expect and hide away ugly implementation details like optimizations, which the user should neither have to worry about, nor interfere with.

What is the overhead of this? Spoiler alert: xpr provides zero-cost abstraction!

Similarly to the analysis in the boost::yap documentation, we can compare the assembly code of an xpr implementation to a native implementation. The following code introduces two functions, eval_native and eval_as_xpr, were the former performs some arithmetic calculation directly and the latter creates an xpr expression and evaluates it.

use xpr::Xpr;

#[derive(Debug, Copy, Clone)]
struct Num(f64);

impl std::ops::Add for Num {
    type Output = Num;
    #[inline]
    fn add(self, other: Num) -> Num {
        Num(self.0 + other.0)
    }
}

impl std::ops::Mul for Num {
    type Output = Num;
    #[inline]
    fn mul(self, other: Num) -> Num {
        Num(self.0 * other.0)
    }
}

fn eval_native(a: Num, x: Num, y: Num) -> Num {
    (a * x + y) * (a * x + y) + (a * x + y) +
    (a * x + y) * (a * x + y) + (a * x + y) +
    (a * x + y) * (a * x + y) + (a * x + y) +
    (a * x + y) * (a * x + y) + (a * x + y)
}

fn eval_as_xpr(a: Num, x: Num, y: Num) -> Num {
    let a = Xpr::new(a);
    let x = Xpr::new(x);
    let y = Xpr::new(y);
    (
        (a * x + y) * (a * x + y) + (a * x + y) +
        (a * x + y) * (a * x + y) + (a * x + y) +
        (a * x + y) * (a * x + y) + (a * x + y) +
        (a * x + y) * (a * x + y) + (a * x + y)
    ).eval()
}

fn main() {
    let a = Num(1.);
    let x = Num(2.);
    let y = Num(3.);
    // println!("{:?}", eval_as_xpr(a, x, y));
    println!("{:?}", eval_native(a, x, y));
}

We can look at the assembly code after optimization by building in release mode and using the --emit=asm option for rustc. If we comment the last line in the main function and uncomment the second to last line, we will get the exact same assembly. This does not change if you add more operations to the expression (You might have to add #![recursion_limit = "256"] to the top of the file).

That being said, this analysis only checks a special case using simple data types and only evaluation. The performance still needs to be tested for more complex data types, expressions and fold operations.