Lazy Evaluation in CPP

惰性求值的概念来自于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 前方高能,请做好防护措施,本人狗眼已瞎)。

参考链接

Published:
2015-04-28 20:22
Category:
Tag:
CPP15