Lazy Evaluation in CPP

https://ift.tt/LQw3AiT

惰性求值的概念来自于lambda calculus，并在一些函数式编程语言中得到了实现，如Miranda,Haskell中惰性求值是默认的。惰性求值的主要思想就是尽可能的避免不必要的计算，如果这些计算的结果并没有被使用的话。惰性求值除可以得到性能的提升外，惰性计算的最重要的好处是它可以构造一个无限的数据类型（例如处理无穷列表，流式计算等）。而C++脱胎于面向过程和面向对象两种编程范式，本来与惰性求值是格格不入的。不过，短路操作符倒是挺符合惰性求值的特点的。例如a||b，如果a被求值为真的时候，b的值则不需要再去求了，直接返回true。但是如果我们在类的内部将短路操作符重载的话，则求值的短路性质将不再被满足。因为重载之后，原来的操作符退化成为了函数，操作数退化成为了参数。在函数应用时，参数必须已经求值。所以，任何企图重载短路操作符的举动都是在自寻死路。

难道除了短路操作符我们就无法惰性求值了么？

惰性求值简单实现

struct Point
{
    int x;
    int y;
}

为了简化讨论，只实现加法版本的惰性求值。此时，我们引入一个辅助类AddOp，这个类的定义如下：

template<typename Lhs, typename Rhs>
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; }
};

这是一个模板类，用来存储加法两边的操作符。现在，我们来修改加法，使得它能够处理这个新的类型。

template<typename Lhs, typename Rhs> 
AddOp<AddOp<Lhs, Rhs>, Point> 
operator+(AddOp<Lhs, Rhs> const& lhs, Point const& p)
{
    return AddOp<AddOp<Lhs, Rhs>, Point>(lhs, p);
} 
// add expression template with point at the left
template<typename Lhs, typename Rhs> 
AddOp< Point, AddOp<Lhs, Rhs> > 
operator+(Point const& p, AddOp<Lhs, Rhs> const& rhs)
{
    return AddOp< Point, AddOp<Lhs, Rhs> >(p, rhs);
}
// add two points, yield a expression template 
AddOp< Point, Point > 
operator+(Point const& lhs, Point const& rhs) 
{
    return AddOp<Point, Point>(lhs, rhs);
}

以下是测试代码，可以通过编译：

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

看上去很完美。但是，看看下面的这种情况

Point p1 = { 1, 2 }, p2 = { 3, 4 }, p3 = { 5, 6 },p4={7,8};
(p1 + p2） + （p3+p4); //error no operator + match AddOp<Point,Point> +AddOp<Point,Point>

惰性求值完整版

为此，我们还需要做一个修改，为加法操作符增加一个左右操作数都是AddOp的重载，修改如下：

template <typename LLhs, typename LRhs, typename RLhs, typename RRhs>
AddOp<AddOp<LLhs, LRhs>, AddOp<RLhs, RRhs>> operator+(const AddOp<LLhs, LRhs> & leftOperandconst, const AddOp<RLhs, RRhs> & rightOperand)
{
    return  AddOp<AddOp<LLhs, LRhs>, AddOp<RLhs, RRhs>>(leftOperandconst, rightOperand);
}

至此，类型的错误都已经完全解决了。剩下的问题就是如何从AddOp中拿出结果。因此，我们需要给Point增加一个类型转换函数：

template<typename Lhs, typename Rhs>
Point(AddOp<Lhs, Rhs> const& op)
{
    x = op.get_x();
    y = op.get_y();
}
template<typename Lhs, typename Rhs>
Point& operator=(AddOp<Lhs, Rhs> const& op)
{
    x = op.get_x();
    y = op.get_y();
    return *this;
}

同时，我们需要把get_x,get_y都实现出来。因此，在上述的两个类中分别增加这两个函数的代码。在Point中，增加如下代码：

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

在AddOp中，增加如下代码：

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

同时，我们用下面的代码进行测试：

int main()
{
    Point p1 = { 1, 2 }, p2 = { 3, 4 }, p3 = { 5, 6 }, p4 = { 7, 8 };
    Point a=(p1 + p2) + (p3+p4); 
    cout << a.x << endl;
}

耶，大功告成。当前我们只做到了特定数据结构特定操作下的惰性求值，其实实现的不是很完整。真正的惰性求值还牵涉到一个对象的多次求值。在多次求值的情况下，当前的实现会导致每一次都重新求一遍，效率很低。完整的AddOp实现中会有一个bool值来记录当前对象是否已经求过值了，初始为false。同时用xvalue,yvalue来记录已经求过的值。在第一次求值之后，bool改为true，同时将所求得值写入xvalue,yvalue。之后再进行求值则直接访问这两个域。如果读者想了解更多的话，可以参考Boost.phoenix库（warning 前方高能，请做好防护措施，本人狗眼已瞎）。

参考链接

via spirits away

November 13, 2024 at 09:50AM

guevara / read-it-later

Lazy Evaluation in CPP #11885

惰性求值简单实现

惰性求值完整版

参考链接