在C++中的懒惰评估

C++没有对延迟评估的本机支持(如Haskell所做的那样).

我想知道是否有可能以合理的方式在C++中实现延迟评估.如果是的话,你会怎么做？

编辑:我喜欢Konrad Rudolph的回答.

我想知道是否可以以更通用的方式实现它,例如通过使用参数化类lazy,它基本上适用于矩阵矩阵的矩阵.

对T的任何操作都会返回惰性.唯一的问题是将参数和操作代码存储在惰性本身中.任何人都可以看到如何改善这一点？

1> Konrad Rudol..：

---

我想知道是否有可能以合理的方式在C++中实现延迟评估.如果是的话,你会怎么做？

是的,这是可能的并且经常进行,例如用于矩阵计算.促进这一点的主要机制是运算符重载.考虑矩阵加法的情况.函数的签名通常如下所示:

matrix operator +(matrix const& a, matrix const& b);

现在,为了使这个函数变得懒惰,它足以返回代理而不是实际结果:

struct matrix_add;

matrix_add operator +(matrix const& a, matrix const& b) {
    return matrix_add(a, b);
}

现在需要做的就是编写这个代理:

struct matrix_add {
    matrix_add(matrix const& a, matrix const& b) : a(a), b(b) { }

    operator matrix() const {
        matrix result;
        // Do the addition.
        return result;
    }
private:
    matrix const& a, b;
};

神奇之处在于方法operator matrix(),它是一个隐式转换运算符,从matrix_addplain到plain matrix.这样,您可以链接多个操作(当然,通过提供适当的重载).仅在将最终结果分配给matrix实例时才进行评估.

编辑我应该更明确.实际上,代码没有任何意义,因为尽管评估是懒散的,但它仍然发生在同一个表达式中.特别是,除非将matrix_add结构更改为允许链接添加,否则另一个添加将评估此代码.C++ 0x通过允许可变参数模板(即可变长度的模板列表)极大地促进了这一点.

但是,这个代码实际上具有真正直接好处的一个非常简单的例子如下:

int value = (A + B)(2, 3);

这里,假设A和B是二维矩阵,并且以Fortran表示法进行解除引用,即上面计算矩阵和中的一个元素.添加整个矩阵当然是浪费.matrix_add救援:

struct matrix_add {
    // … yadda, yadda, yadda …

    int operator ()(unsigned int x, unsigned int y) {
        // Calculate *just one* element:
        return a(x, y) + b(x, y);
    }
};

其他例子比比皆是.我记得不久前我已经实现了一些相关的东西.基本上,我必须实现一个应该遵循固定的预定义接口的字符串类.但是,我的特定字符串类处理的是实际上并未存储在内存中的大字符串.通常,用户只需使用函数从原始字符串访问小子串infix.我为我的字符串类型重载了这个函数,以返回一个代理,该代理保存对我的字符串的引用,以及所需的开始和结束位置.只有在实际使用此子字符串时,它才会查询C API以检索字符串的这一部分.

---

@Steve:不,不是.Haskell在任何地方都使用惰性求值,但这并不意味着每次需要值时都会重新评估所有内容.相反,某些功能*期望*如果没有必要,重新评估不会发生.例如,查看Fibonacci序列的"规范"实现:`1:1:[a + b | (a,b)< - zip fib(tail fib)]` - 使用这个定义来执行`take 50 fib`清楚地表明不会发生重新评估,否则运行时将是指数而不是线性的(如所观察到的).

---

@Chris - 这实际上是懒惰评价的重点.因此,您可以更改其中一个值,并且每次都会重新评估.如果你不想要这个,那么只要具体一次.

2> j_random_hac..：

---

Boost.Lambda是非常好的,但Boost.Proto是正是你所期待的.它已经具有所有 C++运算符的重载,默认情况下,它们在proto::eval()调用时执行其常用函数,但可以更改.

---

+1,任何对Boost库的引用都可以通过便携和安全的方式为您完成一半的工作.

3> Johannes Sch..：

---

Konrad已经解释过的内容可以进一步支持运算符的嵌套调用,所有这些都是懒惰地执行的.在Konrad的例子中,他有一个表达式对象,它可以存储两个参数,正好是一个操作的两个操作数.问题是它只会懒惰地执行一个子表达式,这很好地解释了懒惰评估中的概念,简单来说,但并没有大幅提高性能.另一个示例也很好地展示了如何operator()使用该表达式对象仅应用于添加一些元素.但是为了评估任意复杂的表达式,我们需要一些可以存储结构的机制.我们无法绕过模板来做到这一点.而这个名字就是expression templates.这个想法是一个模板化的表达式对象可以递归地存储某个任意子表达式的结构,就像一棵树,其中操作是节点,操作数是子节点.对于我今天刚刚发现的一个非常好的解释(在我写下面的代码后几天),请看这里.

template
struct AddOp {
    Lhs const& lhs;
    Rhs const& rhs;

    AddOp(Lhs const& lhs, Rhs const& rhs):lhs(lhs), rhs(rhs) {
        // empty body
    }

    Lhs const& get_lhs() const { return lhs; }
    Rhs const& get_rhs() const { return rhs; }
};

这将存储任何添加操作,甚至是嵌套操作,如下面的操作符+定义所示,对于简单的点类型:

struct Point { int x, y; };

// add expression template with point at the right
template AddOp, Point> 
operator+(AddOp const& lhs, Point const& p) {
    return AddOp, Point>(lhs, p);
} 

// add expression template with point at the left
template AddOp< Point, AddOp > 
operator+(Point const& p, AddOp const& rhs) {
    return AddOp< Point, AddOp >(p, rhs);
}

// add two points, yield a expression template    
AddOp< Point, Point > 
operator+(Point const& lhs, Point const& rhs) {
    return AddOp(lhs, rhs);
}

现在,如果你有

Point p1 = { 1, 2 }, p2 = { 3, 4 }, p3 = { 5, 6 };
p1 + (p2 + p3); // returns AddOp< Point, AddOp >

您现在只需要重载operator =并为Point类型添加合适的构造函数并接受AddOp.将其定义更改为:

struct Point { 
    int x, y; 

    Point(int x = 0, int y = 0):x(x), y(y) { }

    template
    Point(AddOp const& op) {
        x = op.get_x();
        y = op.get_y();
    }

    template
    Point& operator=(AddOp const& op) {
        x = op.get_x();
        y = op.get_y();
        return *this;
    }

    int get_x() const { return x; }
    int get_y() const { return y; }
};

并将相应的get_x和get_y作为成员函数添加到AddOp中:

int get_x() const {
    return lhs.get_x() + rhs.get_x();
}

int get_y() const {
    return lhs.get_y() + rhs.get_y();
}

请注意我们是如何创建Point类型的临时代码的.它可能是一个有许多领域的大矩阵.但是在需要结果的时候,我们懒洋洋地计算它.

---

在完整表达之后会被破坏,然后我们将留下悬空引用.所以很容易毛茸茸:)

---

除了对普通Point对象的引用,它们仍将通过引用保存.这样它可以工作.将表达式存储到lazy_expr中需要它具有模板化构造函数,并在内部创建包装表达式的多态类型.在实际评估时,......

---

是的，这实际上是当前C ++中的一个遗憾。您将不得不写出类型，或者必须使用多态来存储它而不写出。下一个C ++具有自动功能，因此您可以执行自动操作p = a + b; 但这会带来其他问题：“ a + b”（表达式模板）创建的临时对象...

---

您可以参数化表达式模板是否使用引用。那么您可以创建一个“惰性表达式类型” lazy_expr e = a +（b + c）; 当分配给那个模板时，表达式模板将被深复制。也就是说，将复制所有对子表达式的引用。

---

您将需要一个虚拟函数调用来启动机器。

4> 小智..：

---

我没有任何东西可以添加到Konrad的帖子中,但你可以在真实的应用程序中查看Eigen,以获得正确的懒惰评估示例.它非常令人敬畏.