注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

天地不仁,以万物为Googol!

天行有常,不以物喜,不以己悲……

 
 
 

日志

 
 

尝试用C++实现Y Combinator(之二)  

2007-09-06 22:40:30|  分类: 积累 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
恩……上篇没写完……

其实,上篇还写错了……

那个combinator::operator()的返回值是int,但是,看那个Python实现:
 def _1(factorial):
     def _fn(n):
         if n == 0: return 1
         else:
             return n*factorial(n-1)
     return _fn

很明显,这个返回值是一个函数……

那么,现在是到了仔细想想_1返回值类型的时候了。简单来说,返回的是个函数,这个函数以一个int为参数,返回一个int值。也就是_1的返回值是int (*)(int)类型。

很明显, _1的返回值和combinator::operator()的返回值不一致。

问题是,怎么才能把他们写的一致呢?由于_fn函数保存了_1传入的参数factorial,所以_fn一定不是一个传统意义上的C++函数,而应该是个仿函数。由于_fn是个仿函数,那就必然有类的实例的生命周期的问题存在,一个不考虑释放内存的_fn应该是这样:
class _fn
{
public:
    typedef int(*func_type)(int);

    _fn(func_type factorial) : func_(factorial), type_(FUNCTION), functor_(0)
    {}

    _fn(_fn *factorial) : type_(FUNCTOR), func_(0), functor_(factorial)
    {}

    int operator()(int n)
    {
        if (n == 0)
            return 1;
        else
        {
            switch (type_)
            {
            case FUNCTION:
                return n * func_(n - 1);
                break;
            case FUNCTOR:
                return n * (*functor_)(n - 1);
                break;
            }
        }
        throw;
    }

private:
    enum
    {
        FUNCTION,
        FUNCTOR,
    } type_;
    func_type func_;
    _fn *functor_;
};

对应的_1有两个,分别对应传入参数为函数和仿函数的情况:
_fn* _1(_fn::func_type factorial)
{
    return new _fn(factorial);
}

_fn* _1(_fn *factorial)
{
    return new _fn(factorial);
}

实验一下:
int error(int n)
{
    throw;
}

int main(int argc, char* argv[])
{
    _fn* f1 = _1(error);

    cout << (*f1)(0) << endl; // print 1
    //cout << (*f1)(1) << endl; // throw

    _fn* f2 = _1(_1(error));
    cout << (*f2)(0) << endl; // print 1
    cout << (*f2)(1) << endl; // print 1
    //cout << (*f2)(2) << endl; // throw

    _fn* f3 = _1(_1(_1(_1(error))));
    cout << (*f3)(0) << endl; // print 1
    cout << (*f3)(1) << endl; // print 1
    cout << (*f3)(2) << endl; // print 2
    cout << (*f3)(3) << endl; // print 6
    //cout << (*f3)(4) << endl; // throw

    return 0;
}

看上去成功了耶~~~~~

当然,我也考虑过不使用指针,而是使用实例,也就是_fn的构造类似:
_fn(_fn &factorial) : type_(FUNCTOR), func_(0), functor_(factorial) // need copy ctor here
{}

但这是对应functor_(factorial),就需要一个类_fn的拷贝构造函数,又由于_fn(_fn &factorial)实际就是_fn的拷贝构造函数,也就是说这里递归了……(x,又是递归!)由于Y Combinator的本意就是不用递归而写出递归,所以这里我就不考虑这种情况了。

另一个不考虑的,就是每个_1都会在堆上建一个_fn的实例,这个实例何时销毁?当然是在最后一个_fn销毁的时候销毁。但是……谁有保证不会有人写出"_fn *f4 = _1(f3)"呢?f4销毁的时候,可能有别的地方还在用f3……所以说,gc啊gc,开门吧~~~~~~(就是说,期待C++ 0x的gc吧)

再有,就是诡异的语法了。(*f1)()之类的东西实在看的别扭。或者也可以写"_fn &f1 = *_1(_1(...))"……总之,甘蔗不能两头舔,大床不能两头睡,凑合吧……

不管怎么说,总算实现了看上去像Y Combinator的东西,下次总该能真正实现个浪费内存诡异语法的Y Combinator了吧?
  评论这张
 
阅读(198)| 评论(3)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017