随笔-341  评论-2670  文章-0  trackbacks-0

    已经忘了是去年还是前年听到微软说要在C# 3.0里为C#添加lambda表达式,与此同时Java的团队也一直在说想为Java添加lambda表达式。到了今天,C#似乎已经把这个特性加进去了,Java还没有。Java说这个特性还在计划列表之中,不过暂时可以使用匿名类来代替。想必是因为在Java中表示函数指针的方法比较奇怪罢……

    其实无论是lambda表达式(事实上应该叫匿名函数)或是匿名类,都能归属到一种叫闭包的东西上面。闭包原来是代数中的用语,只是那些研究理论的老大们觉得这玩意儿也能拉到“闭包”里面去,于是就叫闭包了。匿名函数原本是丘奇发明的一个lambda-calculus的其中一部分,后来计算机的老大们突然发现lambda-calculus非常适合用来充当程序设计语言的模型,于是就对它进行了非常多的扩充,还弄了个什么类型理论出来。好像扯远了。

    想象一下如下使用闭包的代码:

    MyClosure=func(Number1)
    {
        return func(Number2)
        {
            return Number1+Number2;
        };
    };

    a=MyClosure(1);
    b=MyClosure(2);
    writeln(a(10));
    writeln(b(10));

    输出的结果是11和12。MyClosure函数接受一个参数,返回一个新的函数。新的函数将MyClosure的参数与自己的参数相加,返回结果。我们会看到a和b在接受相同的参数的时候,产生了不同的结果。所以实际上MyClosure返回的内部函数已经把MyClosure的参数“记下来”了。所以在具有闭包功能的语言,函数不能仅仅用一个函数指针来表示,还需要一些其他的东西。

    考察一下a(10)的运行过程。首先程序将参数10传递给闭包a,闭包a接收到参数之后,执行代码“return Number1+Number2;”此时Number2必然是10,但是Number1是什么呢?要找。在一般的语言里,函数的参数都是放在堆栈的。如果闭包也将参数放在堆栈的话,那么Number1在MyClosure运行结束的时候就会消失掉,这个时候a(10)再通过堆栈去搜索Number1显然就是不可能的。既然“参数放在堆栈”导出了矛盾,那么参数也就不能放在堆栈了。放在哪里呢?需要一张表。

    对于形式化有所了解的人应该立刻能想到解决的办法了。因为有关形式化的读物在描述对一个名字进行求值的时候使用的方法是“在环境中通过名字搜索出一个指向某空间的引用”。如果我们可以在运行的时候一边跑代码,一边建立一张变量表附着在闭包上的话,这个问题就能够顺利解决了。那怎么做呢?

    可以想象一下在程序执行的过程之中有一张全局的表,表内放了若干变量(MyClosure,a,b,writeln)。MyClosure在返回内部函数的时候,将全局的表跟自己的参数构成的表联通内部函数的指针一起传递给变量a(或者b)。内部函数看得见Number1,全局部分却看不见Number1,因此我们可以知道在程序的执行过程中,表并不只有一张。那么一张表加上一张表还是等于一张表,所以表本身是递归的。我们可以用一个链表来实现它。


    现在知道了表的结构之后,让我们看一下程序的执行过程中究竟发生了什么事情。现在我们定义一张全局表global,global在刚开始的时候仅仅有writeln一项。执行了MyClosure=func...的时候global添加了MyClosure,执行到a=MyClosure(1)的时候,MyClosure内部构造了一张表链接到global身上,我们把这张表命名为internal。程序如果能够访问internal就能够访问global,反之不可。所以外部的代码连接到的环境节点是global,而MyClosure里面的东西链接到的节点是internal -> global。这个时候闭包已经构造好了,其结构是<内部函数的指针,internal->global>。这个时候a=MyClosure(1)已经执行完毕了,global添加了a。

    现在,global=(writeln,MyClosure,a),internal=(Number1)->global。a附带的环境是internal。同理,b也执行完毕,b得到的表是internal2=(Number1)->global。a和b具有两张不同的表internal和internal2,但是它们都连接到了global身上,因此可以共同访问到相同的MyClosure、a、b和writeln,但是访问到的Number1确是不同的。

    于是执行a(10)和b(10)能够访问不同的结果的机制也就很明朗了。调用a和b的时候,他们各自通过自己的Number2与自己附带的表的Number1相加。10+internal[Number1]=10+1=11,10+internal2[Number1]=10+2=12。这个时候我们发现,MyClosure的参数Number1并不在堆栈上面,而在不同的internal和intenral2上。这就是为什么用有闭包的语言,函数的参数不能放进堆栈的原因。因为堆栈的作用仅仅跟寄存器相似——用来保存临时数据,而不能用来保留整个call stack上的函数的参数。

    好像听微软说过,C#并不存在堆栈?好象是吧……
posted on 2008-04-20 21:55 陈梓瀚(vczh) 阅读(7681) 评论(5)  编辑 收藏 引用 所属分类: 脚本技术

评论:
# re: 如何实现语言中的闭包(Closure) 2008-10-06 23:15 | Kenny Yuan
闭包的概念映射其实挺直接的,至少我这么认为
比如transitive closure的概念,非常直接  回复  更多评论
  
# re: 如何实现语言中的闭包(Closure) 2008-12-16 09:04 | 小不点
能不能理解成 用数据库保存的样式,比如当a=MyClosure(1);的时候在数据库样的表里存入MyClosure和1,返回一个数据库的唯一标识,把他赋值给a,调用的时候 直接用a的参数,加上用a找数据库表中保存的1呢?
没用过c#,只是看到你文章自己的一点理解~  回复  更多评论
  
# re: 如何实现语言中的闭包(Closure) 2008-12-16 18:59 | 陈梓瀚(vczh)
你说的只是一个部分,其实需要保存的东西还有很多。不过这么理解也算是可以的。  回复  更多评论
  
# re: 如何实现语言中的闭包(Closure) 2008-12-16 19:15 | 小不点
对,我只是打个比方,那么如果一个程序运用相当多的闭包,也就是用这种函数,那么保存的数据就狠狠多了,占用的内存控件就不得而知了~,高手能指点下么?  回复  更多评论
  
# re: 如何实现语言中的闭包(Closure) 2008-12-16 20:09 | 陈梓瀚(vczh)
结果就是会多占用内存了。至于怎么计算,这是很难的……  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理