为什么函数程序设计matter

《为什么函数程序设计matter》由会员分享，可在线阅读，更多相关《为什么函数程序设计matter（18页珍藏版）》请在金锄头文库上搜索。

1、为什么函数程序设计为什么函数程序设计 Matter？John Hughes Department of Computing Science Chalmers University of Technology 412 96 Goteborg Sweden rjmhcs.chalmers.se摘要摘要随着软件变得越来越复杂， 使软件具有良好的结构也显得越来越重要。结 构良好的软件易编写，易调试，并且提供了一组可以重用的模块，从而降低未 来的编程费用。传统的语言在将问题如何模块化方面有概念上的局限性。 函数 程序设计语言越过了这些局限性。在这篇论文中，我们将提出函数程序设计的 两个非常有助于模块化的

2、特性： 高阶函数和惰性计算。我们将以表和树，数值 算法，alpha-beta 启发算法（人工智能中用于博弈的算法）作为例子。因为模块 化是程序设计成功的关键，函数程序设计语言对现实世界是至关重要的。1. 简介简介本论文试图向“现实世界”证明函数程序设计是至关重要的,并且帮助函数 程序设计员充分探讨函数程序设计的优点。函数程序设计意指每个程序均为一个函数。 主程序本身也是一个函数, 它 将程序的输入作为函数的自变量, 程序的输出作为函数的结果。一般地, 主程序 是由其他函数定义的, 而这些函数也是由另外一些函数来定义的, 直到最底层由 程序设计语言提供的原始函数。 所有这些函数都非常类似于数学上

3、的函数, 在 本文中函数的定义将使用普通的等式。我们将沿用 Turner 设计的语言 Miranda(TM)Tur85的表示法, 但是, 即使没有函数程序语言背景的读者也是容 易理解的(Mirande 是 Resecrch Softwre Ltd. 的商标)。函数程序设计的特点和优点通常可以大致概括如下。 函数程序不包含赋值 语句, 所以, 一个变量一旦给定一个值, 其值将永远不变。 更一般地说, 函数程 序绝对没有副作用。 一个函数的调用只计算其值, 没有任何其他作用。这一特 点可以排除程序错误的一个主要渊源, 而且使得程序的执行顺序无关紧要-因为 没有副作用可以改变一个表达式的值, 表达式

4、可以在任何时候被计算。 因此, 程序员不需要担忧控制流的编写。因为表达式可以在任何时候被计算, 我们可 以自由地将变量用其值代替,或者将值代换为变量, 也就是说, 程序是“引用透 明的”(referential transparent)。这种自由度使得函数程序比传统的程序在数学上 更容易处理/但是, 如果函数程序设计外行并不认为这些是优点, 我们也不应该吃惊。这 些优点讲了许多函数程序设计不是什么(没有赋值语句, 没有副作用, 没有控制 流), 但没有说它是什么。对于那些更喜欢物质利益的人们, 这些“优点“不能非 常令人信服。函数程序设计宣称其具有极大的物质利益-函数程序设计员的生产效率比一

5、般程序员高一个数量级, 因为函数程序比普通程序短一个数量级。 为什么是这 样呢? 唯一似乎可信的理由是普通程序的 90% 由赋值语句构成, 而这些赋值 语句在函数程序中可以全部省去。这显然是荒唐的。如果省略赋值语句能带来 这么大的利益, FORTRAN 程序员不会编写了 20 年的程序。通过省略某些特征 而使得一个语言表达力更强, 无论这些特征如何糟, 这在逻辑上是不可能的。即使一个函数程序设计员也会对这些所谓的优点不满, 因为这些对于挖掘 函数程序语言的能力毫无帮助。我们不可能编写一个特别缺乏赋值语句, 或者 特别引用透明的程序。如果没有程序质量的尺度, 我们也便没有奋斗的目标。显然， 这样

6、刻画函数程序设计是不恰当的。我们必须既能解释函数程序设 计的表达力，又能给函数程序设计员清楚地指出应该追求的目标。2与结构程序设计的对比与结构程序设计的对比对比函数程序设计与结构程序设计是很有帮助的。在过去，结构程序设计 的特征与优点大致概括如下：结构化程序不包含 goto 语句。 结构程序中的程 序块没有多入口和多出口。结构程序在数学上比非结构程序更容易处理。结构 程序设计的这些优点非常类似于我们前面讨论的函数程序的优点。这些优点基 本上是否定语句，已经陷入了有关“基本 goto ”的无意义讨论之中。 作为事后诸葛亮， 显然，结构程序设计的这些性质并没有点到问题的核心。 结构程序与非结构程序

7、最重要的区别在于结构程序是由模块化的方式设计的。 模块化设计带来了生产率的极大提高。 首先，小模块容易快速编写。 其次， 通用模块可以被重用，因此加快了随后的开发过程。第三，模块可以被单独测 试， 减少了调试的时间。 Goto 语句的不存在及其效应与模块化没有多少关系， 它仅对“小规模程 序设计”有帮助，而模块化有助于“大规模程序设计” 。因此，尽管程序员需要 做更多的工作， 程序员仍然可以享受使用 FORTRAN 或者汇编语言进行结构 化程序设计带来的好处。 现在人们普遍认为模块化设计是程序设计成功的关键，程序设计语言如 Modula-IIWir82, AdaoD80和标准 ML 都包含了特

8、别用于改善模块化设计的特 征。然而，有一点经常被忽视了。当我们编写一个模块化程序以解决一个问题 时，通常将一个问题分解为一些子问题， 然后解决这些子问题，并将这些解结 合起来。分解问题的方法直接依赖于将这些解粘合在一起的方法。 因此，欲在 概念上增强模块化问题的能力，我们必须在程序设计语言中提供新的粘合方法。 复杂的作用域规则和分别编译只对书写细节有帮助， 而并没有提供分解问题的 新概念工具。让我们返回函数程序设计。我们将在下面论证函数程序设计提供了两个新 的、非常重要的粘合方法。我们将给出许多可以用新方法模块化的， 而且大大 简化的程序例子。这是函数程序设计的能力的关键- 它能极大地改进模块

9、化。 这也是函数程序设计员应该争取的目标-设计简短和更通用的模块，然后用我 们即将描述的新方法将其粘合在一起。3将函数粘合在一起将函数粘合在一起第一种粘合方法可以将简单的函数粘合在一起形成更复杂的函数。 我们 将用一个简单的表处理问题-把表中的元素加在一起-来解释之。 我们定义表 如下：listof X : = nil | cons X (listof X) 其意义为：一个 X（X 是任意的）上的表或者是 nil，即一个不含任何元素的表； 或者是 X 的一个元素及 X 上的一个表的 cons。一个 cons 表示其第一个元素为 X, 其第二个及其后的元素为 X 上的表的元素。X 在这里表示任意

10、类型， 例如， 如果 X 是“整数” ，那么， 以上的定义表示一个整数表或者是空，或者是一个 整数和另一个整数表的 cons。 我们将按照惯例， 将一个表的元素列在一对方 括弧内表示之， 而不显式地使用 nil 和 cons。 这只是为了表示的方便。例如， 表示 nil 1 表示 cons 1 nil 1,2,3 表示 cons 1 (cons 2 (cons 3 nil) 我们可以用一个递归函数 sum 将一个表的元素加在一起。Sum 需要定义在 两种参数上：一个空表(nil)， 以及一个 cons。 因为空表的和为 0， 我们定义sum nil = 0 因为一个 cons 的和是其第一个元

11、素与另一个表之和相加。 故有 sum (cons num list) = num + sum list 检查以上定义，我们发现在计算和时只有带筐的部分是特定的：+-+ sum nil = | 0 |+-+-+ sum (cons num list) = num | + | sum list+-+ 这表示 sum 的计算可以通过把一个一般递归模式与带框部分粘合起来模块化。 这种递归模式通常称为归约（reduce） ， 因此 sum 可以表示为 sum = reduce add 0 为方便起见，我们给 reduce 传递了一个二元函数 add 而非一个运算符号。 Add 的定义如下：add x y

12、 = x + y 函数 reduce 的定义可以将 sum 参数化， 由下列方程式导出：(reduce f x) nil = x (reduce f x) (cons a l) = f a (reduce f x) l)这里我们使用了括号（reduece f x）以表示其代表 sum。 通常括号可以省略， 所以(reduce f x) l) 可写作（reduce f x l） 。 像 reduce 这样的三元函数只作用于 两个参数时可视为一元函数。 一般地，一个 n 元函数作用于 m（ number 因为博弈树是一个（treeof position） ， 它可以被函数（maptree stat

13、ic）转换为一 个(treeof number)。 函数（maptree static）静态地计算树上的所有局势（这里的 树可以是无穷的） ，函数 maptree 在第二节有定义。| |-+-+-gametree | |-+-+-| | |-+-+-= | |-+-+-| | | | | | | | X| | |X| | |-+-+- -+-+- -+-+-| | | | |X|-+-+- -+-+- -+-+-| | | | | | | . . O| | |O|-+-+- -+-+-|X| |X|-+-+- -+-+-| | | | |. .图 1：博弈树 给定一个静态计算树，树中各局势的真

14、正值（true value）是什么呢？特别地， 根的局势应该赋什么样的值呢？静态值是不合适的，因为它只是大概的估计。 一个节点之值应该由其子节点之值来决定。 我们假定每个选手都选择最理想的 步骤。因为一个节点的值越大，表明此节点表示的局势对计算机越理想，所以， 当计算机在此结点着子时， 它将在其子节点中选择具有最大值的子节点。 类 似地，对手也将选择走到其具有最小值的子节点。假定计算机和其对手轮流着 子，那么当计算机走子时一个节点的值由函数 maximise 计算，否则由 minimise 计算：maximize (node n sub) = max (map minimize sub)min

15、imize (node n sub) = min (map maximize sub) 其中，max 和 min 是返回数列中最大值和最小值的函数。以上定义是不完全的， 因为它们相互递归调用但无初始定义。我们必须定义无后继的节点之值， 并将 其定义为静态值。因此，静态值用于当一个选手已经取胜或者不能继续走子时 的节点。函数 maximise 和 minimise 的完整定义如下：maximize (node n nil) = nmaximize (node n sub) = max (map minimize sub)minimize (node n nil) = nminimise (node n sub) = min (map maximise sub)