I am trying to teach myself Rust and as a challenging learning project I want to replicate the design pattern of the C expression template library boost::yap. I don't want a full fledged implementation, I just want a small demonstrator to find out if Rust's generics are powerful enough to make it happen and learn something along the way.

I have come up with an idea but am currently stuck. My question is twofold:

Is there currently a principle barrier that makes expression templates with the transform feature (see boost::yap, or my code below) impossible in Rust?
If no, how can I make it work?

Here is what I have come up with so far.

I have an enum E that represents all supported operations. In practice, it would take two generic parameters representing the left and right hand side expressions of any binary operation and would have variants called Add, Mul, Sub and so on. I would implement the traits std::ops::{Add, Mul, Sub} etc. for E.

For demonstration purposes however, let's assume that we only have two variants, Terminal represents an expression wrapping a value, and Neg is the only supported unary operation as of now.

use std::ops::Neg;

enum E<U> {
    Terminal(U),
    Neg(U)
}

impl<U> Neg for E<U> {
    type Output = E<E<U>>;
    fn neg(self) -> Self::Output {
        E::Neg(self)
    }
}

Next, I implement a trait Transform that lets me traverse an expression via its subexpressions with a closure. The closure will stop the recursion once it returns Some(_). This is what I have come up with (code does not compile):

trait Transform<Arg = Self> {

    fn transform<R,F>(&self, _f: F) -> Option<R>
    where F: FnMut(&Arg) -> Option<R> 
    {
        None
    }
}

impl<U> Transform for E<U> 
where U : Transform<U>   Neg
{
    fn transform<R,F>(&self, mut f: F) -> Option<R>
    where F: FnMut(&Self) -> Option<R>
    {
        // CASE 1/3: Match! return f(self)
        if let Some(v) = f(self) { return Some(v); };

        match self {
            E::Terminal(_) => None, // CASE 2/3: We have reached a leaf-expression, no match!
            E::Neg(x) => {      // CASE 3/3: Recurse and apply operation to result
                x.transform(f).map(|y| -y) // <- error[E0277]: expected a `FnMut<(&U,)>` closure, found `F`
            }
        }
    }
}

Here is the compiler error:

error[E0277]: expected a `FnMut<(&U,)>` closure, found `F`
  --> src/main.rs:36:29
   |
36 |                 x.transform(f).map(|y| -y) // <- error[E0277]: expected a `Fn<(&U,)>` closure, found `F`
   |                             ^ expected an `FnMut<(&U,)>` closure, found `F`
   |
help: consider further restricting this bound
   |
28 |     where F: FnMut(&Self) -> Option<R>   for<'r> std::ops::FnMut<(&'r U,)>
   |

This is my Issue 1/2: I want to pass in a closure that can work on both Self and on U for E (and thus accepts also E<E> and E<E<E>>...). Can this be done for generic types in Rust? Or if my approach is wrong, what's the right way of doing this? In C i would use SFINAE or if constexpr.

Here is a little test for the expression template library, to see how this can be used:

fn main() {
    //This is needed, because of the trait bound `U: Transform` for `Transform`
    //Seems like an unnecessary burden on the user...
    impl Transform for i32{}

    // An expression template 
    let y = E::Neg(E::Neg(E::Neg(E::Terminal(42))));

    // A transform that counts the number of nestings
    let mut count = 0;
    y.transform(|x| {
        match x {
            E::Neg(_) => {
                count =1;
                None
            }
            _ => Some(()) // must return something. It doesn't matter what here.
        }
    });
    assert_eq!(count, 3);
    
    // a transform that replaces the terminal in y with E::Terminal(5)
    let expr = y.transform(|x| {
       match x {
           E::Terminal(_) => Some(E::Terminal(5)),
           _ => None
       } 
    }).unwrap();
    
    // a transform that evaluates the expression
    // (note: should be provided as method for E<U>)
    let result = expr.transform(|x| {
        match *x {
            E::Terminal(v) => Some(v),
            _ => None
        }
    }).unwrap();
    assert_eq!(result, -5);
}

My Issue 2/2 is not a deal breaker, but I am wondering if there is some way that I can make the code work without this line:

impl Transform for u32{}

I think having to do this is a nuisance for the user of such a library. The problem is, that I have the trait bound U: Transform on the implementation of Transform for E. I have the feeling the unstable specialization feature might help here, but it would be awesome if this could be done with stable Rust.

Here is the rust playground link.

Edit:

If anyone else stumbles over this, here is a rust playground link that implements the solution of the accepted answer. It also cleans up some minor buggy stuff in the code above.

CodePudding user response：

This looks like a Visitor pattern to me.

The solution here looks similar to what you are trying to do.

The difference from your attempt is that U type is placed on heap in Box (think of unique_ptr in C ), which makes the whole E size fixed (independent of a concrete U).

In addition to make the compiler happy to unify the type of F and Transform such that it can work with both E and U at the same time, the trait argument of F probably needs to be boxed as well as Box<dyn Transform> (this is roughly analogous to marking transform as a virtual method in C to be able to call it via a "smart" pointer that knows how to find a particular impl in runtime). Having unpacked x: U using match, it should be possible to make a Box::<dyn Transform>::new(x) from it since U : Transform. With that F would accept it.

Without Box I think that the only other solution is to use macros, and generate methods for each type explicitly.