循环迭代器和闭包
通常, C 程序员使用如下代码对 a 数组的每个元素进行操作:
for (i = 0; i < n; i++) func(a[i]);
这行代码有三个独立的逻辑, for 循环控制了对 a 的访问顺序, a[i] 控制了对 a 数组的元素访问方式, func() 函数控制了对 a 元素的操作. 这个三个逻辑是彼此独立的. 然而, 问题逐渐浮出水面. 首先是 for 循环的次序. 对于随机存取的数组 a, 访问顺序应当是没有关系的. for( i=n-1; i>=0; i–) 也是可以的. 一个简洁的语言应当突出逻辑, 丢掉不必要的代码. 因此, 最好能写成
foreach (k in a) func(k);
这个解一石二鸟, 第一是把访问顺序逻辑彻底抛弃, 第二是改变了访问方式, 从此没有烦人的 ArrayIndexOutOfBoundException, 不需要担心访问越界. 在函数式编程语言中, 类似的形式是:
map(func, a)
我们希望 foreach 能够遍历一个数据结构的每个元素一次. 可是这个终究是一个语法糖, 因为它只能胜任特定的数据结构. 对于用户自己设计的一些数据结构, 比如树, 想同时拥有先序和后序遍历, foreach 就无能为力了. 与此同时, 我们也不想用 for 那样简单粗暴的方式去控制访问顺序 (因为很容易导致内存越界, 而且很多数据结构不支持随机存取). 这时候, 就需要迭代器的帮助了. 因为不同的数据结构要求不同的访问顺序, 我们希望数据结构本身能够提供一些访问顺序. 这种对于数据结构上元素访问顺序的抽象, 被称为迭代器. 一般来说, 迭代器通过 getIterator() 被数据结构构造, 具有一个 hasNext() 的判断和一个 next() 的函数. 对一个数据结构的访问可以四海一家的写成:
for (i = a.getIterater(User’s_Order); i.hasNext(); i.next() ) func(i.current());
迭代器把访问逻辑从数据结构上分离出来, 是一个常用的设计方法. Design Pattern 也把它作为23个Pattern之一.在 STL 中也到处都是了它的身影. 但对一个完美主义者来说, 这个代码还是太冗长, 既然对数据结构的访问能够四海一家的写成如此, 为何不直接规定一个简洁的语法访问呢? 是的, 我们希望返朴归真, 回到原来的形式:
for i in a.SomeIterator(): func(i)
好消息是现代语言都支持这样的方法. [注: 在C/C++ 语言中, 还不能支持上面的写法. C#有类似的写法. 在 Ruby 和 Python 中很常见. ] 可是能不能再简化呢, 能不能连 i 这个中间变量都不要呢? 我们简直希望写成:
a.SomeIterator(func)
是呀, 这样的世界多美好啊. 可是, 别忘了在面向对象的语言中间, 一切都是对象. 在 C 的时代, 我们可以通过函数指针把 func 参数传递进去. 可是这里是对象, 怎么办呢. 很简单, 只要构造一个只有一个方法的对象, 传进去就行了. 这样的构造方法, 居然也是一个设计模式, 叫做函数对象(Function Object), 或者叫函数子 (Functor). 被 Java 的匿名内部类这个概念折腾到崩溃的读到这里, 应该知道所谓的匿名内部类, 就是为了在面向对象的环境中做函数传递这个事情而想出来的小花招. Java 的写法就是
a.SomeIterator( new FunctionObject()
{ public func(a)
{return something;}
});
［为了引用这样一个函数, 使用了天书一般的不必要代码, 可想有多少人真的喜欢这个方法］
逃离了Java 的世界, 我们来到 Python 或者 Ruby 或者其他函数式语言的世界, 激动的发现原来函数也是一种对象, 和其他对象一样在 Python 中坐上头等舱. 如此好事怎么能错过呢. 于是, 大摇大摆写上:
a.SomeIterator(func)
没有类型检查, 也没有复杂代码, 连一个辅助变量都不多谢, 真舒服. 在 Python 中间, 这样的模式比比皆是, 比如 os.path.walk(path, visit, arg) 可以对path目录下所有的文件遍历, 并且调用 visit 函数处理, 还可以夹带一个私货 arg 进去, 非常方便. [注: os.walk() 则反其道行之, 提供一个 generator, 外部用 for 访问]
从外面夹带私货不算特别困难, 毕竟可以通过修改函数的定义方式来实现. 可是假如想从迭代器里面夹带一些私货出来给函数用, 就有点困难了. 比如说, func 函数需要访问迭代器的一个私有的变量. 显然把迭代器作为参数传给函数是不行的. 只能反其道行之, 让迭代器把函数当成自己人, 以迭代器为主, 把函数包含到迭代器的作用域内才能玩转. 这个就是所谓的闭包. 也就是说, 一个函数被包入另一个更大的作用域, 并且可以访问大的作用域里面的变量. C/C++ 是不允许在函数里面定义函数的, 所以只好望着闭包干羡慕. Java 算不错了, 用内部类解决了这个问题.
我们说个具体的例子: 函数 func(x) 需要另一个值 y, 返回 x*y, 另一个值 y 在外部作用域定义了. 写成 Python 代码
a= [1, 2, 3]
def func(x):
return x*yfor y in a:
print func(2)
会出现 2,4,6
我们可以看到, 函数func 的定义和使用是独立的. 而静态语言是不能随便在什么位置都能定义函数闭包的, 原因不难解释: 编译器会跳出来告诉你 y 这个变量没有定义. 因为动态语言在运行时才能得到 y 的值, 从而使用 func, 所以不存在这个问题. 动态语言的灵活性在此充分展现. 最后, 既然我们知道迭代器后面必然要加一个闭包, 还要括号干啥? 不如直接写成 (实际上, Groovy 语言就是这样的):
a.each func
从简单的循环, 到迭代器, 到生成器, 到内部类, 到函数作为一级对象, 再到闭包, 过程式编程语言, 对象编程语言和函数编程语言越来越呈现融合的趋势.
chenyufei said,
March 7, 2008 @ 3:17 am
a.SomeIterator(func)
这种迭代实际上就使用了内部迭代器，迭代的过程完全由迭代器来控制，在 Head First Design Patterns 中有解释。但是这种迭代方式在不能同时遍历多个容器时，如果使用类似 Lisp 里面的 map，以多个容器作为参数，就可用同时遍历多个容器了。但即使这样仅仅使用内部迭代器还是不够的。
外部迭代器（如传统的 C++，Java 中的 iterator）有用的地方就在我们想完全控制控制迭代过程的时候，比如发现某个元素不满足某个条件时马上停止迭代过程，再比如写一个 merge 来来合并多个已经排序的容器的时候，我们必须自己控制什么时候需要取下一个元素。另外在我们希望删除容器内某些元素的时候外部迭代器也更为方便。
我在学设计模式的时候写过一篇关于内部迭代器和回调函数的文章，有很多想法跟你是一样的。广告一下，有兴趣的话可以看看。http://chenyufei.name/blog/2006-11-23/glqivdhfznivketminoibourjzcauicausjq/
关于 closure。在我看来 closure 一个很有用的地方在于使得函数可以带有状态，就像对象一样，可以利用 function builder 来创建带有不同状态的函数。因此在 Lisp 这样的语言里面没有对象日子照样非常美好。比如用 a.each max 来找到一个 a 中的最大值，函数 max 必须要能够记录迭代过程中遇到的最大值，有 closure 的话是非常方便的。在 C++ 里面用 functor 固然可以做到，但是单独定义一个类实在是麻烦，用全局变量加函数指针则在多线程时会有麻烦。在 Java 里面引入匿名内部类实际上就方便了这种用法。（当然，Java 不支持函数指针使它更迫切的需要匿名内部类。）
Python 为了保持语言简单放弃了很多特性，比如它对 closure 的支持并不完全，函数所引用的自由变量（即函数作用域外的变量）不能被修改。比如下面的代码在 Python 中是不合法的：
def stamp(t):
return lambda : t += 1
st1 = stamp(0)
print st1()
print st1()
st2 = stamp(10)
print st2()
print st2()
执行的时候会直接在 t = t + 1 这里报语法错误。
Ruby 支持 full closure，所以在 Ruby 里面这样写是可以的：
def stamp(t)
return lambda { t += 1 }
end
st1 = stamp(0)
p st1.call() # 1
p st1.call() # 2
st2 = stamp(10)
p st2.call() # 11
p st2.call() # 12
不过 Ruby 里面返回的是一个 Proc 对象，要通过 call 来调用而不能像普通的函数一样来调用。
SICP 对 closure 的解释和应用都非常清楚，有疑问或者想要深入了解的人可以看它第三章的环境求值模型来理解 closure。不过现代语言为了效率和程序的清晰一般都使用 lexical scope，SICP 第三章里的环境模型是针对 dynamic scope 的，但也有助于对 closure 的理解。（实际上 dynamic scope 里也能实现 closure，Ansi Common Lisp 一书的脚注提到，closure 的名字来源于早期 Lisp 使用 dynamic scope 时实现 closure 的方式。）
shallwe said,
March 7, 2008 @ 8:12 am
从简单的语句映射出背后的设计哲学, 很是受益.
Eric said,
March 7, 2008 @ 8:48 am
@yufei
感谢留言，我写的时候没有细致的区分内部迭代器和外部迭代器，的确应该区分开来看。
关于Python 中的 closure, 平时这方面特性没用过，我都不知道那个语法在 Python 中不行，
SICP 的确是一本好书，羡慕你在本科就读过
zz said,
March 9, 2008 @ 10:06 pm
不错的文章….最近对于选择正确的工具/语言做正确的事情有点感悟。
如果说sap的软件古老而陈旧，但是能够存活这么多年，多多少少和ABAP这种灵活的石器语言有关。
ABAP在操作数据(有的时候是海量)时候的迭代技巧非常tricky, 却很得劲…
Shiyuan said,
March 18, 2008 @ 11:58 pm
一直关注你的blog,受益非浅。
我不懂函数语言，但语法确实简洁漂亮，逻辑层次清晰。但漂亮的语法背后是否以运行效率为代价？暑假要参加一summer program, 要求python, 可否推荐一phython经典