延迟求值和无穷(3)
发表于 2007-08-15 03:04 AM 作者: liuxinyu
3 Implementation
实际上，延迟求值的实例在计算机应用中也有很多。例如，用户用某个字处理软件 （如MS Word）打开一篇包含图片的文档时，文档中的图片并不一下子全部读出来。 只有那些在第一页的图片才被读出并显示，随着用户向后面翻页。后面内容中的图片 才逐步被打开并显示。
在GoF的着作《设计模式》[6]中，给出了一个proxy模式实现上述延迟求值的例 子。本文将给出一个“超市问题”的延迟求值解法。transform程序和filter程序都具备 足够的抽象，它们是通用的程序，完全可以重用，所以问题的关键是record的实现， 要在record的内部，引入延迟求值。
目前的纪录包含两个部份，一个是该笔交易的金额，另一部分指向下一笔纪录。 所有纪录依次链结下去，形成完整的纪录表。对纪录表引入延迟求值的思路大致如 下：
在构造一笔纪录时，并不要求当前的金额和指向下一笔纪录的指针都准备好。只 要当前的金额准备好就可以构造了。而关于下一笔纪录的信息，直到明确地通 过next命令进行引用时，才真正对其进行求值。
考虑到filter和transform的通用性，延迟求值的引入不应该严重影响到这 两个程序的实现和使用。所以原来程序中的下述语句的应该表现为延迟求 值：
代码:
new record(f(r->value), transform(r-> next, f));
首先，为了防止C++在运行时，自动求值record构造函数的第二个参数，先将 此参数设置为空值0, 然后，在给record增加一个函数，该函数用来保存将 来延迟求值时需要使用的transform, r和f，但是仅仅是保存它们，而不立 即进行求值。只有在未来某个时候，用户通过next方法，明确要求获取下 一个纪录值时，才利用以前保存过的transform, r和f，求出下笔纪录的信 息。
才用上述方法，发现也适用于filter程序的下列语句：
代码:
return new record(r->value, filter(r-> next, f));
通过以上分析，就可以实现一个支持延迟求值的pos机纪录模型了，为了 和前面普通的record区别，这一新类被命名为stream_record。初步实现如 下：
代码:
class stream_record{
public:
stream_record():value(0), _next(0){}
stream_record(double v, stream_record* r=0):value(v), _next(r){}
virtual ˜stream_record(){
delete _next;
}
template<class Func, class Arg >
stream_record* setNext(Func f, stream_record* r, Arg arg);
virtual stream_record* operator()(){ return this;}
stream_record* next(){
if(_next)
_next=(*_next)();
return _next;
}
double value;
private:
stream_record* _next;
}; 根据这一解释，还可以了解到，延迟求值对象，必然是stream_record的派生类， 所以才能够根据Liskov原则，被当作一个strem_record保存在next指针里。同 时，由于延迟求值对象是通过setNext函数模板建立的，所以它必然是一个 类模板对象。根据这些分析，可以把延迟求值对象和setNext最终实现出 来：
代码:
template<class Func, class Arg >
class delayed_record: public stream_record{
public:
delayed_record(Func f, stream_record* r, Arg arg): _f(f), _r(r), _arg(arg){}
stream_record* operator()(){
stream_record* res= _f(_r->next(), _arg);
delete this;
return res;
}
private:
Func _f;
stream_record* _r;
Arg _arg;
};
template<class Func, class Arg >
stream_record* stream_record::setNext(Func f, stream_record* r, Arg arg){
_next = new delayed_record< Func, Arg>(f, r, arg);
return this;
} setNext函数模板，根据用户传入的不同求值函数类型，以及参数类型，构造初延 迟求值对象，并赋值给next指针。
通过上述延迟求值实现，filter和transform可以仅仅做很小的改动，就能处理延迟 求值的纪录了。
代码:
template< typename Record, typename F >
Record* transform(Record* r, F f){
if(r){
return (new Record(f(r->value))) ->setNext(transform< Record, F>, r, f);
}
return 0;
}
template< typename Record, typename F >
Record* filter(Record* r, F f){
if(r)
if(f(r->value))
return (new Record(r->value)) ->setNext(filter< Record, F>, r, f);
else
return filter(r->next(), f);
return 0;
} 为了使原先的普通record和支持延迟求值的stream_record都能被transform和filter 处理，可以也在普通的record中略微改动一下：
代码:
class record{
public:
record(double v, record* r=0): value(v), _next(r){}
template<class Func, class Arg >
record* setNext(Func f, record* r, Arg arg){
_next=f(r->next(), arg);
return this;
}
//… 
评论总数 0
评论
 发表评论 |
作者为 liuxinyu 的最新文章
- Solve a programming puzzle by permutation (1) (2009-01-07)
- beautiful code第20章和第29章翻译 (2007-11-06)
- 延迟求值和无穷(6) (2007-08-15)
- 延迟求值和无穷(5) (2007-08-15)
- 延迟求值和无穷(4) (2007-08-15)
