说一门新外语，O‘Caml（之二）（转于developerWorks 中国）

说一门新外语，O‘Caml（之二）
Functional 程序设计概要

文档选项

将此页作为电子邮件发送

拓展 Tomcat 应用

下载 IBM 开源 J2EE 应用服务器 WAS CE 新版本 V1.1
级别: 初级
赵蔚 (zhaoway@public1.ptt.js.cn), 自由职业者
2002 年 9 月 09 日
这是本系列中的第二篇文章。在上一篇文章中，可以说我们从高空鸟瞰了 O‘Caml程序设计语言中的一些显著特征。包括 O‘Caml 的跨平台特性，它在程序语言家族的族谱中的位置，它的 geeky factor，以及它所提倡的 Functional 程序设计方式。在本篇文章中，我们将要靠近一些，更加仔细的看一看 O‘Caml 中这个重要的程序设计方式，Functional 程序设计。
让我们引用著名的计算机科学家 Alan J. Perlis 为美国麻省理工学院 的程序设计入门课程的经典教材《计算机程序的结构及其解释》一书所著的序言，来开始我们今天对 O‘Caml 以及 Functional 程序设计方式的介绍。
"我认为有一件事对于我们这些从事计算机科学的人特别的重要，那就是我们应该让计算始终保持有趣。在刚开始的时候，计算是非常有趣的。当然，这让那些付了钱的顾客不时的感到不太满意。终于没过多久，我们就开始正经八百的对待他们的抱怨了。我们渐渐开始觉得我们应该对这些机器成功、无错的运行负起责任，我们应该好好的使用它们。我不认为我们应该如此。我认为我们应该折腾这些机器，带它们进入新的领域，让屋子里始终环绕着有趣的氛围。我希望计算机科学这个领域永远不要失去它寻找乐趣的本领。无论如何，我希望我们不要变成传教士。不要弄得好象你是在推销红宝书。这个世界上这种人已经太多了。关于计算方面，你所知道的，别人会学会的。不要觉得好象通往成功计算的大门钥匙掌握在你的手里。在你手里的，我想，我也这样希望，是智慧：比你第一次被领来看到这些机器时，更深入的了解它们，而且你还可以让这个认识更加的深入。"
这篇文章的目的就是带大家进入 Functional 程序设计这一有趣的领域。




回页首
Functional 程序设计的最吸引人注意的地方在于，"函数"现在可以被当作像整数（int）和浮点数（float）一样的数据类型。这就是说，我们可以把函数 func 赋值给一个变量；可以从子程序返回一个函数，就跟返回一个浮点数一样的容易；两个函数可以进行复合运算，就像两个整数可以进行加减乘除运算一样。我们将看到，在 Functional 程序设计里面，"函数"被提升为程序设计语言中的第一等（First Class）的公民，使用"函数"可以像使用整数和浮点数或者是字符串一样的随心所欲；不再象过去，函数只能被调用，没有其它的花样。
"函数"被提升成第一等的公民以后，引起了一连串的连锁反应。我们可以观察到，过去，调用一个子程序，子程序必须完成一定的计算效果，然后把计算的效果通过一定的办法返回给调用者。这个返回计算效果的办法，通常就是设置一个全局变量，或者是一个大局部的变量。而现在，由于可以把子程序的计算效果通过返回一个"函数"传递回调用者，我们可以不用设置全局变量了。那么，设置全局变量，和不设置全局变量而传递一个函数，这两种返回子程序计算效果的办法，这个区别是不是很重要？还是只是一个玩意儿而已呢？由于设置了全局变量（或者是一个大局部的变量），调用子程序之后再往下的计算过程，要根据全局变量的值做不同的反应，而全局变量往往离发生效果的代码段"距离"很远。这就带来这样一个难过的事情，由于任何一个程序员的注意力都不可避免的是局部的，这样的话，程序中的一段代码，每次运行都会根据"遥远"的全局变量，执行出难以预料的不同结果。这就使得调试这样的程序变得相当的费力。
反过来看 Functional 的程序设计方法，它把一个子程序的计算效果累积在一个函数里面，然后把这个函数返回给调用者，可以做到不用设置全局变量。这样使得调用者在继续往下计算的时候，它的计算只和传递回来的这个"函数"有关，而不会受到代码中"遥远"的其它地方的变量值的影响。影响 Functional 程序中代码执行效果的因素，一是程序代码本身，二是输入数据。而且这两个因素都是局部的，在程序员的注意力范围之内。当从代码段中不同的地方，用同样的输入数据调用同一段代码的时候，得到的输出是一模一样的。这就是所谓的"Referential Transparency"，它的主要好处是，让代码调试变得相对简单了。
如果一门程序设计语言，只允许上面说的 Functional 的调用子程序的方法，也就是说，它不允许你设置各种各样的全局或者是局部的变量，也就是说，如果它不允许边界效应（side effects），那么这门编程语言就叫做是 Pure 的、纯粹的 Functional 编程语言。我们所要关心的 O‘Caml 并不是 Pure 的，所以在 O‘Caml 里面可以混合这两种编程方式。读者朋友们不免要问，如果上面说的 Functional 的方式好，那怎么还要抓住"不好"的方式不放呢？这个问题是很难回答的，像 Pure 的 Functional 编程语言，有 Haskell 和 Clean 等，不那么 Pure 的有 Lisp 和 O‘Caml 等。上面说的 Pure 的好处是真的，但是编程的时候要考虑许多事情，Referential Transparency 只是一个方面，比如我要编写一个有限状态自动机的程序，用 Pure Functional 的程序设计方式就有些难过了，因为，毕竟给变量设置不同的值，这是编写一个有限状态自动机的很自然的方式。如果不允许设置边界效应，只允许数据在没有边界效应的管子（子程序）里流进流出，这样要表达出自动机的状态，就比较难过了。




回页首
上面讲了 Functional 程序设计中，"函数"可以被当作程序设计语言中第一等的公民来对待，就像 int 和 float 一样。下面，我们将通过一个例子，来看看这个概念是否真的是程序设计中的一个利器，还是说，这个概念只是说着玩玩，让人徒伤脑筋而已。
1: $ ledit ocaml 2: Objective Caml version 3.06 3: # let rec sum lst = 4: match lst with 5: [] -> 0 6: | head :: tail -> head + sum tail ;; 7: val sum : int list -> int = 8: # sum [ 1; 2; 3 ] ;; 9: - : int = 6
上面是一个在 BASH Shell 下面交互式的执行 O‘Caml 的一个屏幕快照。第一行的"$"是 BASH Shell 命令提示符；ledit 是 O‘Caml 的一个行编辑程序，用 ledit 来执行 ocaml 就可以获得行编辑的一些功能，这是运行交互式的 ocaml 的时候，必不可少的一个工具。下面几行中的"#"是 O‘Caml 的命令提示符，提示你输入新的 O‘Caml 语句。上面的第二行打印出 O‘Caml 的一个简单的 Banner，可以看到 O‘Caml 的全称是 Objective Caml，这个 3.06 版本是这个月刚刚推出的，就在本系列文章的第一篇和这个第二篇之间，O‘Caml 已经连续推出了 3.05 和 3.06 两个版本。上面的第三行，let rec sum lst 定义了一个函数，名为 sum，接受一个参数，记为 lst。在上面的 let 关键字后面的 rec 关键字，意思是 recursive，表示我们定义的这个 sum 函数，将要采用一个递归的定义，也就是说，在 sum 的定义中，我们将要调用 sum 本身。这里的 sum 函数是一个简单的求和的函数，它把一个 list 类型的变量，我们这里记为 lst，其中的各个项加起来，求和。
上面的第四行，match lst with，这里面 match 和 with 是关键字。这是 Functional 编程的一个有趣的风格，即大量的采用模式匹配的方法来写程序。（不过，本节标题中所说的模式并不是指这个，我们下面将会看到。）这个模式匹配的编程风格，很像 C 语言里面的 switch 和 case。这里的 match lst with，可以想象成就是 C 语言里面的 switch (lst)。第五行的 [] ->0，其中的 [] 表示一个空的 list。翻译成类似 C 语言的语法，就是 case [] : 0; break; 意思是，如果 lst 是一个空的 list 的话，这个 sum 函数就返回 0。第六行的 | head :: tail ->head + sum tail ;; 开头的竖杠是或者的意思，也就是另开一个 case。这个 case 是什么样的呢？我们要先看看 list 这个数据类型是怎么回事。
一个 list 就好像是一个链表，在 O‘Caml 里面，list 中的每个元素都必须是同一种类型。比如：
# let lst = [ 1; 2; 3 ] ;; val lst : int list = [1; 2; 3]
这里就定义了一个元素为 int 类型的 list 数据，名为 lst，它的第一个元素是 1，然后是 2 和 3。
# 0 :: lst ;; - : int list = [0; 1; 2; 3]
上面的 :: 是一个构造 list 的操作符，0::lst 把一个新的元素 0 加到一个 list 类型的数据 lst 前面，于是就返回一个新的 list 类型的数据。这个新的 list 类型的领头的元素现在是 0 了，它后面跟了一个 list 是 [ 1; 2; 3 ]，而这个 [ 1; 2; 3 ] 又是怎么个一回事呢？
# 0 :: 1 :: 2 :: 3 :: [] ;; - : int list = [0; 1; 2; 3]
这里，我们就看到 list 数据类型的本质了。我们用 list 构造操作符 ::，从 0，1，2，3 四个元素和一个空的 list 构造出了跟上面的一个一模一样的 list。原来 O‘Caml 里面的一个 list 又有点像 C 语言里面的单向链表，又有点像 C 语言里面的以 NULL 字符作为结尾标记的字符串。结合上面的几段文字的分析，我们看到，这里的这个 list [0; 1; 2; 3] 它的领头的元素是 0，后面跟着一个 list [1; 2; 3]，而这个 [1; 2; 3] 它的领头元素是 1，后面跟着 list [ 2;3 ]，这又是领头的元素 2 后面跟着 [3] 这个单元素的 list，而这个单元素的 list 其实是领头的 3 后面跟着一个空的 list []，这个空的 list 才表示这整个 list 的结尾。我们在对 list 数据类型有了这样的一个了解之后，接下来继续回到我们的 sum 函数。
我们看到第六行的 | head :: tail ->head + sum tail ;; 在竖杠后面的 head :: tail 这个模式匹配了我们关心的 sum 函数的变量 lst 不是一个空的 list 的情况。我们知道，变量 lst 或者为空，那么第五行的 [] ->0 给出了 sum 函数的返回值；或者 lst 不为空，那么它的构成必然是这样的：一个领头的元素，后面跟着一个 list 类型的数据。这里，我们就把这个领头的元素匹配成，或者说叫做命名成 head，而把后面跟着的 list 匹配成 tail。也就是说，如果 sum 函数的变量 lst 不是一个空的 list 的话，sum lst 其实就是 head 加上 sum tail。这样，我们就定义完成了我们的 sum 求和函数。上面程序的第八行做了一个简单的测试，果真得到了预期的结果。
这个小函数的定义，我们首先看到"递归"是一个强有力的工具，似乎还没有开始编程序，程序就已经编好了。我们还看到，模式匹配 match something with 是 Functional 程序设计里面使用很广泛的一种风格。这个模式匹配要远远超出 C 语言里面的 switch () 语句。但是这里的这个模式匹配，并不是本节的小标题所要说的模式，我们下面就来看看本节真正的想要说的模式是怎样的。
我们如果细心观察，就会发现，上面定义的这个求和函数，它把一个 list 拿过来，为 list 为空的情况定义一个返回值；然后，在 list 不为空的情况下怎么办呢？它使用了一个二元操作符，就是加法来处理。这就是我们所要说的模式。这个模式虽然简单，但显然是很有用的。如果这个 list 是一个字符串的 list 的话，我们可以用这个模式把 list 里面的各个字符串元素串在一起，连成一个大字符串。如果我们不求和，而要求乘积，这真是手到擒来。如果我们可以定义复杂的二元操作符，那么显然这个模式可以帮助我们完成复杂的 list 操作。但是，我们是不是每次要用到这个模式的时候，都要写上像前面的 sum 函数的定义一样那一大堆东西呢？如果是那样的话，即使我们注意到了这个模式，事实上也没有什么大的帮助。好在 Functional 程序设计可以把函数提到第一等公民的地位上来，我们来观察一下，看看有没有什么办法。
我们首先观察到，这个模式的有效输入，其实只有两个东西，一是在 list 为空的情况下的返回值，二就是在 list 不为空的情况下，使用哪一个二元操作符。事实上，如果把我们的模式定名为 pat 的话，我们希望把 sum 求和函数用一句话就写出来，就是 let sum = pat add 0 ;; 这样的话，我们关于这个模式的知识，就浓缩在 pat 这个函数的定义里面了。由于 Functional 程序设计里面函数被提高到最高的地位上，所以上面的这个 pat 才可以实现。它可以接受一个函数（add）作为参数，而它的返回值也可以是一个函数（sum）。看来，Functional 程序设计还是有点特别嘛！下面，我们就来看看如何定义这个 pat 函数。
# let rec pat func value lst = match lst with [] -> value | head :: tail -> func head (pat func value tail) ;; val pat : (‘a -> ‘b -> ‘b) -> ‘b -> ‘a list -> ‘b =
上面定义了 pat 这个函数。这个函数的定义过程很简单，就是把上面的 sum 函数的定义照葫芦画瓢一番，凡是遇到 sum 的地方，就换成 pat func value 就成了。这样一来，我们就把我们从 sum 的函数定义中观察到的一个简单的设计模式，浓缩到了 pat 这个函数的定义里面来了。如果现在再要我们来定义一个求和函数的，我们只需要提供一个加法的二元操作符，再提供一个初始值就可以了。这个初始值是 0；而这个二元操作符的定义如下：
# let add a b = a + b ;; val add : int -> int -> int =
下面，我们使用这个二元操作符，以及我们的 pat 函数，来重新定义一个求和函数。
# let patsum = pat add 0 ;; val patsum : int list -> int = # patsum [ 1; 2; 3 ] ;; : int = 6
测试的结果正如我们的所料。下面再来看另一个例子。先定义一个二元操作符：
# let dup a b = a * 2 :: b ;; val dup : int -> int list -> int list =
然后用初始值 [] 和上面定义的二元操作符 dup 来定义我们的翻倍函数：
# let patdup = pat dup [] ;; val patdup : int list -> int list =
测试：
# patdup [ 1; 2; 3 ] ;; - : int list = [2; 4; 6]
这个例子定义了一个新的函数，它把 [1;2;3] 中的每个元素翻倍变成了 [2;4;6]。我们注意到，这也是一个有用的模式，但是像上面那样使用前面定义的 pat 函数来完成，显然并不漂亮，上面的那个二元操作符的定义也很不自然。我们希望，像前面定义的 pat 一样，把这个新发现的模式也用一个函数来浓缩起来。
# let pat2 func lst = let op1 a b = func a :: b in let op2 = pat op1 [] in op2 lst ;; val pat2 : (‘a -> ‘b) -> ‘a list -> ‘b list =
这个第二个模式，它接受的参数只有两个，第一个是一个一元函数，第二个是一个 list。这第二个模式干的事情，就是把这个一元函数用到 list 里面的每个元素的身上，然后返回一个新的 list。下面我们来看看如何使用这个模式。先定义一个一元函数：
# let duplicate a = a * 2 ;; val duplicate : int -> int =
然后，把这个一元函数用到模式二的头上，来重新得到我们前面的把 [1;2;3] 变成 [2;4;6] 的函数：
# pat2 duplicate [1; 2; 3] ;; - : int list = [2; 4; 6]
上面的两个模式，在 functional 程序设计里面，被浓缩成了两个函数。而之所以能够做到这一步，这是因为在 functional 程序设计里面，函数被提升成了程序设计语言里面第一等的公民，可以被传递，可以被赋值。我们看到，程序设计语言里面一个粗看起来不明所以的特征，经过一些探究，竟带给我们一些意想不到有趣效果。




回页首
学习一门新的编程语言，重要的学会这门程序语言带来的新的程序设计方式。当你真正的学会了这些新的程序设计方式的时候，你可以丢开这门刚刚学会的程序语言，换回你原先熟悉的一门编程语言。在这门你早已经学会的程序语言里面试一试你刚刚学会的这些新的程序设计方式。这样你就会了解这门新的编程语言提供的这些抽象到底是怎么一个玩意儿。这门新的编程语言在后台默默的为你做了哪些事情。你也就会了解它为你做的这些事情在什么时候会是你真正需要的，在另外一些场合又有可能你会不太需要它为你做的这些事情。直到你可以把程序设计方式从编程语言里面剥离出来以后，你才算真正的理解了这门新的编程语言。请读者朋友们记住，仅仅知道一门编程语言的语法可是万万不够的。
在学会了一门新的程序语言之后，如何判断付出的努力是否值得呢？你可以想一想这门新的程序语言是否为你带来了看待计算过程的一个新的角度。我们可以说，程序语言就是对计算过程的一个抽象，不同的程序语言表达的是不同的抽象。你可以尝试着判断一下这个新的刚刚获得的抽象是否足够有力，是否可以在足够多的场合应用这个抽象。如果学习一门新的编程语言没有为你带来任何新的见解，那样的话，这门新的编程语言对你来说有多大的使用价值，这实在是要打上一个大大的问号的。这种情况的话，十有八九，你原先掌握的编程语言对你来说要更好一些。而另一方面，如果你的确获得了新的见解，那么这门新的编程语言对你来说就肯定蕴含了有价值的、有趣的技术。这样的话，即使你以后一时没有机会或者没有可能使用这门新的编程语言，你还可以在被迫使用不合适的程序语言的时候，仍旧使用上合适的抽象、合适的技术。
在下一篇文章里，我们将要介绍用 O‘Caml 在 Linux 系统上进行编程的一些实际的例子，并看到用 O‘Caml 进行跨平台开发的威力。我们的实例将轻易的可以在 Linux 和 Windows 两个系统平台上运行。那么，下次再见！
O‘Caml 编程语言的主页，http://www.ocaml.org Harold Abelson and Gerald Jay Sussman,《计算机程序的结构及其解释》，即著名的 SICP。http://mitpress.mit.edu/sicp/full-text/book/book.html O‘Caml 的参考手册，http://caml.inria.fr/ocaml/htmlman/index.html Haskell 编程语言主页。Haskell 是纪念逻辑学家 Haskell Curry 的。本系列文章的第一篇里面提到 过 Curry 这个技术，这个 Curry 也是纪念这位逻辑学家而起的名字。Haskell 同 O‘Caml 不同，是一 门Pure 的 Functional 程序设计语言。http://www.haskell.org/ Clean 编程语言，这也是一门 Pure 的 Functional 编程语言。http://www.cs.kun.nl/~clean/ 关于 Scheme 编程语言，在http://www.schemers.org/可以找到大量的有用的信息。Scheme 是 Lisp 这一族编程语言中的一种。在 SICP（见上）这本书中，就是使用的 Scheme 编程语言来做的解说。 Why Functional Programming Matters，水平高的朋友们可以看看这篇 John Hughes 的文章，http://www.math.chalmers.se/~rjmh/Papers/whyfp.ps这是本文作者在自学 Functional Programming 的过程中，读到的最有启发的一篇文章。

 

赵蔚，自由职业者。欢迎大家通过我的电子邮件zhaoway@public1.ptt.js.cn和我进行交流，我的兴趣包括 Lisp，C++，O‘Caml，Concurrent Clean，Haskell 还有其它的好多编程语言。在编程语言之外，我对 Linux Kernel，OpenGL 和 Quake III 也都颇有兴趣。我的网络日记位于http://www.advogato.org/person/zhaoway/。上面列有我在网络上发表的其它的文章。欢迎读者朋友们批评指教。