generics - Rust 中的表达式模板实现类似于 boost::yap

Question

我正在尝试自学 Rust，作为一个具有挑战性的学习项目，我想复制 C++ 表达式模板库的设计模式 boost::yap .我不想要一个完整的实现，我只想要一个小型演示程序来了解 Rust 的泛型是否足够强大以实现它并在此过程中学到一些东西。

我想出了一个主意，但目前卡住了。我的问题是双重的:

• 目前是否存在使表达式模板具有转换功能 (参见 boost::yap，或下面我的代码)在 Rust 中不可能的原则障碍？
• 如果没有，我怎样才能让它发挥作用？

这是我到目前为止的想法。

我有一个枚举 E表示所有支持的操作。在实践中，它将采用两个通用参数来表示任何二元运算的左侧和右侧表达式，并且会有称为 Add 的变体。 , Mul , Sub等等。我会实现特征 std::ops::{Add, Mul, Sub}等 E<U> .

然而，为了演示目的，我们假设我们只有两个变体，Terminal表示一个包含值的表达式，Neg是目前唯一受支持的一元运算。

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)
    }
}

接下来，我实现一个特征 Transform这让我可以通过带有闭包的子表达式来遍历表达式。一旦返回Some(_)，闭包将停止递归。 .这就是我想出的(代码无法编译):

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`
            }
        }
    }
}

这是编译错误:

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,)>
   |                                        +++++++++++++++++++++++++++++++++++

这是我的问题 1/2: 我想传递一个可以同时处理 Self 的闭包和 U对于 E<U> (因此也接受 E<E<U>> 和 E<E<E<U>>> ...)。可以对 Rust 中的泛型类型这样做吗？或者，如果我的方法是错误的，那么正确的做法是什么？在 C++ 中，我会使用 SFINAE 或 if constexpr .

下面是对表达式模板库的一个小测试，看看如何使用它:

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);
}

我的问题 2/2 不是一个交易破坏者，但我想知道是否有某种方法可以让代码在没有这一行的情况下工作:

impl Transform for u32{}

我认为必须这样做对这样一个库的用户来说是一件麻烦事。问题是，我有特征绑定(bind) U: Transform关于执行Transform对于 E<U> .我觉得不稳定的特化功能可能会在这里有所帮助，但如果这可以用稳定的 Rust 来完成，那就太棒了。

这是 rust playground link .

编辑:

如果其他人遇到这个问题，这里是一个 rust playground link实现已接受答案的解决方案。它还清除了上面代码中的一些小问题。

Answer 1

这看起来像一个 Visitor pattern对我来说。

解决方案here看起来与您正在尝试做的相似。

与您尝试的不同之处在于，U 类型放在Box<U> 中的堆上(想想 C++ 中的 unique_ptr<U>)，这使得整个 E 大小固定(独立于具体的 U)。

除了让编译器乐于统一 F 和 Transform 的类型以便它可以同时处理 E 和 U 之外，F 的特征参数可能需要像 Box<dyn Transform> 一样被装箱。 (这大致类似于将 transform 标记为 C++ 中的虚拟方法，以便能够通过知道如何在运行时查找特定实现的“智能”指针调用它)。打开包装x: U使用匹配，应该可以制作 Box::<dyn Transform>::new(x)从它开始 U : Transform .有了那个 F 就会接受它。

如果没有 Box，我认为唯一的其他解决方案是使用宏，并为每种类型显式生成方法。