为这篇文章评分

延迟求值和无穷(5)

发表于 2007-08-15 03:12 AM 作者: liuxinyu

4 Infinity

从上面一节给出的超市交易问题看出，使用延迟求值模型，能够减少不必要的计算次数，只有在真正需要某个数据时，才去进行计算。这样大大节约了计算成本，对于大量的数据处理，能提高不少效率。
实际上，延迟求值不仅可以应用于大量数据处理，甚至可以直接为无穷的概念建模。而针对无穷的计算是使用传统计算模型难以做到的。例如面对这样的需求：“建立一个列表，代表全部自然数”。这个需求，用C++的数组类型，或者vector容器类型，是难以满足的。而利用前面给出的stream_record 却可以非常简单的实现，如下：

代码:

template< typename Succ>  
stream_record<int>* create_series(int n, Succ f){ 
    return (new stream_record<int>(n)) ->setNext(create_series< Succ>, n, f); 
} 
 
template<class  T >  
struct AddTo{ 
    AddTo(int n):_n(n){} 
    T  operator()(T  x){ return x + _n; } 
    T  _n; 
}; 
 
//... 
 
stream_record<int>*  N =create_series(1, AddTo <int>(1)); 
std::cout<<”natural number created.n”; 
std::cout<<”7th:  ”<<getAt(N, 6)<<”n”;

并且，如果改变上面AddTo的参数为2,就可以生成全体正奇数的集合，再将起始数字遍为2,就可以产生全体正偶数。但是上述代码还需要针对stream_record做一些改动。第一个改动是必需将stream_record由普通类，改为类模板。以前的stream_record仅仅支持double 类型的内置数据，现在需要同时支持double和int。为此改动如下：

代码:

template<class  T >  
class stream_record{ 
public: 
    //... 
    stream_record(T  v, stream_record* r=0):value(v), _next(r){} 
    //... 
    T  value;

其次，根据C++标准，由于变成了模板类，所以setNext必需改为类内联实现，否则编译无法通过。但是原实现中使用的delayed_record】类模板由于从stream_record派生，所以必需在stream_record后声明，这就出现了矛盾。为了解决这一矛盾，可以引入一个专门用来构造delayed_record对象的函数，如下：

代码:

template<class  T =double>  class stream_record; 
 
template<class Func, class Obj, class Arg, class  T >  
stream_record< T >* create_delay_record(Func f, Obj x, Arg arg); 
 
template<class  T >  
class stream_record{ 
public: 
    //…

这样的前置声明(forward declaration)放在类模板stream_record和delayed_record 前面，就可以在stream_record类模板内部的setNext中使用了。于是setNext改变为：

代码:

template<class  T >  class stream_record{ 
public: 
    //... 
        template<class Func, class Obj, class Arg >  
        stream_record* setNext(Func f, Obj x, Arg arg){ 
    _next  =  create_delay_record< Func, Obj, Arg,  T >(f, x, arg); 
    return this; 
        }

而函数create_delay_record的实现，就可以放到delayed_record的定义后面：

代码:

template<class Func, class Obj, class Arg, class  T >  
stream_record< T >* create_delay_record(Func f, Obj x, Arg arg){ 
    return new delayed_record< Func, Obj, Arg,  T >(f, x, arg); 
}

另外一个重要的改变是延迟求值的方式，对于以前的transform和filter延迟求值的形式是统一的，都是：

代码:

f(r->next(), arg)

的形式，其中，f是用于延迟求值的函数，r是延迟求值的对象，arg是f所需的参数。但是自然数序列的延迟求值的形式却是：

代码:

create_series(Increase(n), Increase); ==> f(arg(n), arg)

也就是要让延迟求值的参数，以函数形式作用于求值对象，这和前面的transform及filter 是不一样的。为了支持这以改变，可以利用模板的偏特化，使得delayed_record针对不同的类型，有不同的实现，如下：

代码:

template<class Func, class Obj, class Arg, class  T >  
class delayed_record: public stream_record< T >{  
public: 
    delayed_record(Func f, Obj x, Arg arg): _f(f), _x(x), _arg(arg){} 
    stream_record< T >* operator()(){ 
        std::cout<<”nlazy eval: ”; 
        stream_record< T >* res  =  _f(_arg(_x), _arg); 
        delete this; 
        return res; 
    } 
 
private: 
    Func _f; 
    Obj  _x; 
    Arg  _arg; 
}; 
 
//partial instatiate 
template<class Func, class Arg, class  T >  
class delayed_record< Func, stream_record< T >*, Arg,  T >: public stream_record< T >{  
public: 
    delayed_record(Func f, stream_record< T >* x, Arg arg): _f(f), _x(x), _arg(arg){} 
        stream_record< T >* operator()(){ 
        std::cout<<”nstill empty, eval: ”; 
        stream_record< T >* res  =  _f(_x ->next(), _arg); 
        delete this; 
        return res; 
        } 
 
private: 
    Func _f; 
    stream_record< T >* _x; 
    Arg  _arg; 
};

普通情况下，delayed_record会把arg作用于求值对象x上，这适用于自然数建模的情形；当求值对象是stream_record指针时，偏特化起作用，求值过程会作用到求值对象的next 指针所指向的内容上。
经过上述改动，全体自然数的延迟求值模型就可以正常使用了，程序输入如下结果：
natural number created.

lazy eval:
lazy eval:
lazy eval:
lazy eval:
lazy eval:
lazy eval: 7th: 7

既然延迟求值可以给自然数这类的无穷序列建模，一个进一步的想法是，直接对无穷序列进行操作，完成各种计算任务。例如下面的程序，可以将两个无穷序列加起来：

代码:

template<class Record>  
Record* add_series(Record* a, Record* b){ 
    return (new Record(a ->value+ b ->value)) ->setNext(add_series< Record>, a, b); 
}

为了使这段程序工作正常，还必需增加一个针对两个stream_record进行操作的偏特化，使得add_series可以延迟递归地运行下去。这一偏特化版本如下：

代码:

template<class Func, class  T >  
class delayed_record<  
    Func, 
    stream_record< T >*, stream_record< T >*, 
    T >: public stream_record< T >{  
public: 
    delayed_record(Func f, stream_record< T >* x, stream_record< T >* y): _f(f), _x(x), _y(y){} 
    stream_record< T >* operator()(){ 
        stream_record< T >* res  =  _f(_x ->next(), _y ->next()); 
        delete this; 
        return res; 
    } 
 
private: 
    Func _f; 
    stream_record< T >* _x; 
    stream_record< T >* _y; 
};

使用这个add_series就可以将两个无穷序列相加了，例如，将无穷常数序列和自然数序列加以，可以得到从那个常数开始的无穷递增序列：

代码:

typedef stream_record<int>  IntStream; 
IntStream* ones=create_series(1, AddTo <int>(0)); 
IntStream* N1 =add_series(ones,  N); 
std::cout<<”7th:  ”<<getAt(N1, 6)<<”n”;

这段程序会输出：

代码:

lazy eval:  
lazy eval:  
lazy eval:  
lazy eval:  
lazy eval:  
lazy eval: 7th: 8

更加有趣的是，无穷序列的定义本身也可以是递归的，例如可以这样定义自然数的无穷序列：自然数的第一个元素是1,后面的序列是自然数与常数序列1的和。写成表达式就是：

代码:

IntStream* integers= new IntStream(1); 
integers->setNext(add_series(ones, integers));

当然，还需要增加一个setNext接收一个stream_record指针类型的重载形式：

代码:

template<class  T >  
class stream_record{ 
        //... 
        stream_record* setNext(stream_record* r){ 
                _next  =  r; 
                return this; 
        }

这样，如果使用getAt(integers, 4)，获得第四个自然数并打印，程序就会输出5.

评论总数 0

发表评论

作者为 liuxinyu 的最新文章

论坛存档
< > 十一月 2008
日	一	二	三	四	五	六
26	27	28	29	30	31	1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	1	2	3	4	5	6