第5章 函数式程序设计语言 过程式程序设计语言由于数据的名值分离， 变量的时空特性导致程序难于查错、难于修改 第5章 函数式程序设计语言 过程式程序设计语言由于数据的名值分离， 变量的时空特性导致程序难于查错、难于修改 命令式语言天生带来的三个问题只解决了一半 滥用goto已经完全解决 悬挂指针没有完全解决 函数副作用不可能消除

问题是程序状态的易变性(Mutability)和顺序性(Sequencing) Backus在图灵奖的一篇演说《程序设计能从冯·诺依曼风格下解放出来吗？》中极力鼓吹发展与数学连系更密切的函数式程序设计语言

5.1 过程式语言存在的问题 （1）易变性难于数学模型 代数中的变量是未知的确定值，而程序设计语言的变量是对存储的抽象 根本解决： 能不能不要程序意义的“变量”只保留数学意义的“变量”？ 能不能消除函数的副作用？

例：有副作用的函数 int sf_fun(int x) static int z = 0； //第一次装入赋初值 return x + (z++)； sf_fun(3) = {3 |4 | 5 | 6 | 7 …} //随调用次数而异，不是数学意义的确定函数。

（2）顺序性更难数学模型 顺序性影响计算结果， 例如， 前述急求值、正规求值、懒求值同一表达式就会有不同的结果。有副作用更甚， 因而难于为程序建立统一的符号数学理论。 应寻求与求值顺序无关的表达方式 理想的改变途径 没有变量， 就没有破坏性赋值， 也不会有引起副作用的全局量和局部量之分。 调用通过引用就没有意义。 循环也没有意义， 因为只有每次执行循环改变了控制变量的值， 循环才能得到不同的结果。 那么程序结构只剩下表达式、条件表达式、递归表达式。

5.2 λ演算 λ演算是符号的逻辑演算系统， 它正好只有这三种机制， 它就成为函数式程序设计语言的模型 λ演算是一个符号、逻辑系统，其公式就是符号串并按逻辑规则操纵 Church的理论证明， λ演算是个完备的系统， 可以表示任何计算函数， 所以任何可用λ演算仿真实现的语言也是完备的。

λ演算使函数概念形式化，是涉及变量、函数、函数组合规则的演算。 λ演算基于最简单的定义函数的思想： 一为函数抽象λx.E， 一为函数应用(λx.E)(a)。 一切变量、标识符、表达式都是函数或(复合)高阶函数。如λx.C(C为常量)是常函数。

λ演算公式举例 x 变量、公式、表达式。 (λx.((y)x)) 函数， 体内嵌入应用。 (λz.(y(λz.x))) 函数， 体内嵌入应用， 再次嵌入函数。 ((λz.(z y))x) 应用表达式。 λx.λy.λz.(x λx.(u v)w) 复杂表达式

由于λ演算中一切语义概念均用λ表达式表达。 为了清晰采用命名替换使之更易读。 T = λx.λy.x //逻辑真值 F = λx.λy.y //逻辑假值 1 = λx.λy.x y //数1 2 = λx.λy.x(x y) //数2 zerop = λn.n(λx.F)T //判零函数 注：zerop中的F、T可以用λ表达式展开

形式语法 核心的λ演算没有类型， 没有顺序控制等概念， 程序和数据没有区分。 语法极简单： <λ-表达式> :: = <变量> | λ<变量>.<λ-表达式> | (<λ-表达式><λ-表达式>) | (<λ-表达式>) <变量> :: =<字母>

基本函数 TRUE 和FALSE的λ表达式 T = λx.λy.x F = λx.λy.y 整数的λ表达式： 0=λx.λy.y 1=λx.λy.x y 2=λx.λy.x(x y) n=λx.λy.x(x(…(x y)) n个

基本操作函数 以下是算术操作函数举例： not=λz.((zF)T)=λz.((zλx.λy.y)(λx.λy.x)) and=λa.λb.((ab)F) = λa.λb.((ab)λx.λy.y)) or = λa.λb.((aT)b) = λa.λb.((a λx.λy.x)b) 以下是算术操作函数举例： + = add = λx.λy.λa.λb.((xa)(ya)b) * = multiply = λx.λy.λa.((x(ya))) ** = sqr = λx.λy.(yx) identity = λx.x //同一函数 succ = λn.(λx.λy.nx(x y)) //后继函数 zerop = λn.n(λx.F)T =λn.n(λz.λx.λy.y)(λx.λy.y) //判零 函数

例：3+4就写add 3 4， add 3返回“加3函数”应用到4上当然就是7。写全了是： （λx.λy.λa.λb.((x a)(y a) b )） (λp.λq.(p(p(p q)))(λs.λt.(s(s(s(s t))) λa.λb.(a(a(a(a(a(a(a b)))))))

归约与范式 归约将复杂的表达式化成简单形式， 即按一定的规则对符号表达式进行置换。 例：归约数1的后继 (succ 1) => (λn.(λx.λy.n x(x y))1) => (λx.λy.1 x(x y)) => (λx.λy.(λp.λq. p q) x(x y)) => (λx.λy.(λq. x q)(x y)) => (λx.λy.x(x y))=2 注：succ和1都是函数(1是常函数)，第一步是λn束定的n被1置换。 展开后， x置换p， (xy)置换q， 最后一行不能再置换了， 它就是范式， 语义为2。

关键的问题是注意函数体中要置换的变量是否自由出现，如： （1）β归约：β归约的表达式是一个λ应用表达式(λx.M N)， 其左边子表达式是λ函数表达式，右边是任意λ表达式。β归约以右边的λ表达式置换函数体M中λ指明的那个形参变量。形式地，我们用[N/X,M]表示对（λx.M N）的置换（规则略）。 关键的问题是注意函数体中要置换的变量是否自由出现，如： ((λx.x(λx.(xy)))(zz)) =>(zz)(λx.((zz)y)) //错误，第二x个非自由出现。 =>(zz)(λx.(xy)) //正确

例5-5 高层表示的β归约 (λn.add n n) 3 => add 3 3 //3置换n后取消λn => 6 (λf.λx.f(f x)) succ 7 => λx.succ (succ x) 7 => succ (succ 7) => succ (8) = 9 注：add，3， succ， 7， 9是为了清晰没进 一步展开为λ表达式。 但β归约有时并不能简化， 如：(λx.xx)(λx.xx)，归约后仍是原公式， 这种λ表达式称为不可归约的。 对应为程序设计语言中的无限递归。

(2)η归约是消除一层约束的归约:λx.Fx => F (3)α换名:归约中如发生改变束定性质， 则允许换名(λ后跟的变量名)， 以保证原有束定关系。 例如： (λx. (λy.x)) (z y) //(zy)中y是自由变量 => λy.(zy) //此时(zy)中y被束定了， 错误！ => (λx.(λw.x))(zy) //因(λy.x)中函数体 无y， 可换名 => λw.(zy) // 正确！

(4)归约约定 顺序:每次归约只要找到可归约的子公式即可归约， λ演算没有规定顺序。 范式:符号归约当施行（除α规则外）所有变换规则后没有新形式出现，则这种λ表达式叫范式。 解释:范式即λ演算的语义解释， 形如 x x，(y (λx.z))就只能解释为数据了。 上述基本函数均为范式， 在它的上面取上有意义的名字可以构成上一层的函数， 如：pred =λn.(subtract n 1)

（5） 综合规约例题：以λ演算规约3**2 3**2=**(3)(2) =λx.λy.(y x)(3)(2) >β(λy.(y 3))(2) >β((2)3) = (λf.λc.f ( f c ) ) (3) >βλc.(( 3 ( 3 c ) ) = λc.(λf.λc.(f(f(f(c)))))(3 c)) // 有c不能置换c >αλc.(λf.λz.(f (f (f (z)))))(3 c) >βλc.(λz.((3 c)((3 c)((3 c)(z))))) // 再展3

=λc.λz.((( λf.λc.(f(f(f(c)))c)((3c)((3c)(z)))) λf.λw.(f( f( f(w)))c)((3c)((3c)(z)))) >βλc.λz.(((λw.(c(c(c(w))))((3c)((3c)(z)))) //同理展开第二个c,第三个c =λc.λz.(((λw.(c(c(c(w))))(( λp.(c(c(c(p)))))(( λq.(c(c(c(q)))))(z)))) >βλc.λz.(((λw.(c(c(c(w))))(( λp.(c(c(c(p)))))(((c(c(c(z)))))) (c(c(c(c(c(c(z))))))))))) >β λc.λz.(c(c(c(c(c(c(c(c(c(z))))))))))= 9

增强λ演算 只用最底层λ演算是极其复杂的。用高层命名函数，语义清晰。不仅如此，保留一些常见关键字，语义更清晰。例如，我们可以定义一个if_then_else为名的函数：if_then_else =λp.λm.λn.p m n，当p为'真'时， 执行m否则为n。我们先验证其真伪。 例：当条件表达式为真时if_then_else函数的归约 (if_then_else) T M N => (λp. λm. λn. p m n) T M N => (λm.λn. ( T m n))M N => (λm. λn. (λx.λy.x) m n) M N => (λm. λn. (λy.m) n) M N => (λm. λn. m) M N => (λn. M) N =>M

if表达式 可保留显式if-then-else形式： (if_then_else) E1 E2 E3= if E1 then E2 else E3 其中E1， E2， E3为λ表达式。

Let/where表达式 如果有高阶函数： (λn. multiply n (succ n)) (add i 2 ) => multiply (add i 2) (succ (add i 2)) //n 和 add i 2置换变元得 => multiply n (succ n) // let n = add i 2 in let a = b in E ≡ (λa. E) b ≡ E where a=b (λf. E2) (λx.E1) = let f = λx.E1 in E2 = let f x = E1 in E2 其中形如f=λx.E1的λx. 可移向左边为f x = E1 。 如: sqr = λn. multiply n n //整个是λ函数表达式 sqr n = multiply n n //两应用表达式也相等 let表达式在ML. LISP中直接采用， Miranda用where关键字使程序更好读， let直到E完结构成一个程序块。Miranda只不过把where块放在E之后.

元组表达式 一般情况下n元组是p=(x1,x2,…xn), 建立在p上函数有： let f(x1,x2,…xn)=E1 in E2 ≡ let fp=E1 in let x1=first p in let x2=second p in . let xn=n_th p in E2

5.3 函数式语言怎样克服命令式语言的缺点 5.3.1 消除赋值 赋值语句在过程语言中起什么作用。 在函数式 语言中取消会有什么问题： [1] 存储计算子表达式的中间结果。 [2] 条件语句的重要组成。 [3] 用于循环控制变量。 [4] 处理复杂数据结构(增删改某个成分)。

解决办法 [1]：保留全局量、局部量(符号名)以及参数名。 [2]：用条件表达式代替条件语句，其返回值通过 参数束定或where子句束定于名字 [3]:函数式语言都要定义表数据结构， 因为归约 和递归计算在表上很方便。 对整个表操作实 则是隐式迭代。 不用循环控制变量。 对于 顺序值也都用表写个映射函数即可隐式迭代。 部分达到作用[3]， 其它显式循环要用递归。

[4]:禁止赋值意味着数据结构一旦创建不得修改,故采用如下函数式语言结构数据修改方式 A A B C B’ C D E F F’ I J G H

5.3.2 以递归代替while_do 组织仿真的要点是把递归函数体写入条件表达式。 循环终止条件是条件测试部分， 函数如有返回值放在then部分， 递归函数体放在else部分， 如果不需返回值则取消一部分(else)。 5.3.3 消除顺序 一旦语义相关无法传递数据， 非得写成嵌套函数不可(返回值自动束定到外套函数的变元上)

5.3.4用嵌套代替语义相关的顺序 例:pascal实现： c：=a+b； s：=sin(c * c)； 。 write(a，b， c， s)； //上面计算不进行是无法打印 //的逻辑上要有顺序。 LISP 实现： (print (let ((c(+ a b))) let ((s (sin (* c c)))) list a b c s )))) //仍有顺序但在一个 //表达式内。自左至右处理即隐式顺序。 Miranda实现： Answere a b = (a b c s ) where s= sin (c* c) c= a+b //多么清晰， 全然没有顺序

用懒求值代替顺序 利用卫式进一步消除顺序性 Miranda的卫式表达式 gcd a b= gcd (a-b) b， a>b = gcd a (b-a)， a<b = a， a=b LISP的条件选择 （define GCD (a b) （cond (( greaterp a b) (GCD ((diference a b ) b))) ((Lessp a b) (GCD (a (diference b a )))) （ T a )))

5.3.5 输出问题 利用数据对象内部原有的顺序 结构对象是第一类对象， 语言支持的任何形式(交互、非交互)的输出都可以用在表和元组上。Miranda就是用无限表动态实现的 无限表尾不表示任何值， 它是函数对象， 每当调用到它时， 它按规定计算表头值， 并构造 一新的函数对象放在表尾， 以便再展其它项， 它就是新的无限表尾的头， 这个过程一直延续到需要的表长已达到。 输入输出流就是一个值的无限表， 每次处理输入流一个新值就附在表尾并为程序访问。同样， 也用无限表模型输出流。

5.4 函数式语言Miranda 11.4.1 数据结构 简单的Miranda手本 Miranda λ演算 sq n = n * n sq = λn. * n n z=sq x/sq y z=/(sq x)(sq y) Miranda的基本类型有字符(char类型， 加单引号的字母)， 真值(bool类型， 值为True和False)和数(num 类型， 包括整数、实数)， 数据结构只有表和元组， 串是字符表 11.4.1 数据结构 元组(tuple) 树类型定义 tree::= Leaf Integer | Node tree tree [1] leaf1 = (Leaf 3) [2] tree1 = (Node leaf1 (Node (Leaf 17) (Leaf 49))) [3]

tree 1 leaf 1 3 3 leaf 1 第[2]行执行后 17 49 第[3]行执行后 多态函数定义及调用 设函数 max_tree 为求树中叶子值最大 max_tree (Leaf ldata) = ldata [1] max_tree (Node n1 n2) = max1， max1 > max2 [2] = max2， max2 > max1 [3] = max1， otherwise where max1 = (max_tree n1) [4] max2 = (max_tree n2) [5] 如有应用： (max_tree leaf1) //结果值为3， leaf1用上例 (max_tree tree1) //结果值为49，tree1用上例

odd_number = [1，3，..100] //1到100内奇数表，头两项及最后项必写 表(list) Miranda表的表示法 [ ] //空表 [1..n] //1到n,域表示 odd_number = [1，3，..100] //1到100内奇数表，头两项及最后项必写 eleven_up = [11...] //10以上， 无限表表示 evens = [10，12...100] //10以上偶数表至100，头两项及最后项必写 evens_up = [12，14...] //10以上偶数无限表， week _days = [“Mon”，“Tue”，“Wed”，“Thur”，“Fri”] //五个串值的表

5.4.2 内定义操作 Miranda定义了常规的算术运算符(+、-、*、/、div、mod)并按中缀表示使用。故内定义了一些有用的表操作： L1 ++ L2 // 表L2并接到表L1的末尾 item:List // 将项item加到表List的头前 List ！ n // 从表List中选取第n项 L1 -- L2 // 从表L1中剔出L2的值 #List //返回表List的项(基)数

5.4.3 定义函数 Miranda把函数定义叫方程(equation)。 例： 斐波那契数的函数定义， 用卫式表达式实现递归 Fibonacci n = 1， n=0 = 1， n=1 = Fibonacci (n-1)+Fibonacci (n-2) n>1 卫式表达式的值集应复盖所有的可能， 否则用otherwise。

例： 利用where解二次方程 quadroot a b c = error “complex roots”，delta < 0 = [term1] , delta = 0 = [term1 + term2，term1 - term2]， delta >0 where delta = b*b - 4*a*c radix = sqrt delta term1 = -b/(2*a) term2 = radix /(2*a)

Miranda完全按λ演算模型，每个函数都是一元运算，当有多个变元时， 函数名也是第一类对象， 它逐一应用到各个参数， 中间返回函数可以任意取名， 这种中间函数称Curry函数。 例： 直角三角形求斜边长函数 hypotenuse a b = sqrt (a * a + b * b) 调用时 hypotenuse 3 4 //=5 也可写作： (hypotenuse 3 ) 4  f 4 Miranda则写作为： f 4 where f = hypotenuse 3 //f=sqrt(9 + b*b)即 Curry 函数。

例: Miranda用变阶函数实现类型参数化。 type row_type=array[0..9] of Integer; function Reduce(functionf(x:Integer,y:Integer):Integer; ar:row_type):Integer;//函数f是参数化的。 var sum,k:Integer; begin sum:=ar[0]; for k=1 to 9 do sum:=f(sum,ar[k]); reduce:=sum end; function MyOp(s:Integer,y:Integer):Integer; //此处定义一实例函数。 MyOp:=abs(x)+abs(y) function MySum(ar:row_type):Integer; begin MySum:=Reduce(MyOp,ar) end;

上程序仅将 Reduce函数操作参数化。数组元素类型、长度还是固定的。Miranda都可以，它设3个参数：操作、表、单位元。单位元的值可用于归约过程的初始化值，也是空表时的返回值： reduce f[] n = n [1] reduce f(a : x) n = f a (reduce x n) [2] 为了理解上不引起岐意，写明reduce的类型： reduce::(numnumnum) //第一变元f是函数类型（有 括号）,它是二元算子 [num] //返回值是表，表元素是num类型  num //若空表映射为数，类型是num.  num //最后映射返回值是num类型。 [2]行中（a:x）是表头a和表尾x，右边函数体是表尾归约后与表头归约。[1]行指明空表规约 n 次是单位元的 n 次复合。

5.4.4 表闭包 表闭包是一个任意复杂结构的(无限)表。其语法是： <ZF表达式>::=‘[’<体>‘|’<限定符表>‘]’ <限定符表>::=<产生器>{‘；’<产生器>|<过滤器>} <产生器>::=<变量>←<表_表达式> <过滤器>::=<布尔表达式> <体>::= <表_表达式>

表闭包示例： ZF 表达式 解释 [n*2 | n←[2，4，6，8，10]] [4，8，12，16，20] [1] [n*n | n ←[1，2，...]] [1，4，9，...] [2] [x+y | x← [1..3]； y←[3，7]] [4，5，6，8，9，10] [3] [x*y | x ←[1..3]； y←[1..3]；x>=y][1，2，4，3，6，9] [4] [1]行只有一个生成器， 表值2，4，6，8，10束定于n得出2倍表。[2]行是无限表也只有一产生器，[3]行[4]行有两个产生器， [4]行还有一过滤器， 否则要对称出9个数。

例： 用Miranda编写快速分类 sort [ ] = [ ] [1] sort (pivot：rest) = sort [y | y ← rest； y<=pivot] [2] ++ [pivot] ++ [3] sort [ z | z ← rest； y>pivot] [4] [1]行定义函数sort的变元是空表它返回一空表(调用同一函数)， 一般定义递归它都有[1]行。 它同时指出sort是表变元。[2]行的圆括号不是表， 而是说明变元一个表， 它由元组pivot和rest组成，即表头、表尾。 以局部的名字给出了与之结合的实参表表头、表尾。

5.4.5 无限表 可以把无限表看作两部分： 有限的头部， 它放λ已经算好了的值， 和一个无限的尾， 它由生成新表尾的代码组成。这相当于一个函数， 也采用懒求值， 即不到表不够时不计算它。

5.5 问题与讨论 (1) 模拟状态不易 (2) 效率还是问题 从过去比顺序的命令式语言慢200-1000倍到近来的3-5倍， 其原因是： 函数是第一类对象， 局部于它的数据一般要在堆(heap)上分配， 为了避免悬挂引用， 要有自动重配的检查。 无类型(如LISP)要在运行中检查类型，即使是强类型的(如ML， Miranda)减少了类型动态检查， 但函数式语言天然匹配选择模式的途径也是运行低效原因。 懒求值开销大 中间复合值一多费时费空间。 无限表动态生成， 计算一次增长一个元素！ 效率也很低。

(3) 并发性 函数式语言被认为是非常适用于处理并发性问题的工具， 共享值不需加特殊保护， 因为他们不会被更新、并行进程之间不会互相干扰。 还有一些困难问题要解决。 在将表达式求值分配给不同的处理器这一点上就有隐藏的额外开销： 用于求表达式值的数据必须从一个处理器传到另一个处理器， 而表达式的计算结果还得被传回来。 寻找解决这个问题的先进技术是一个热门的研究课题。

Haskell 语言 Haskell是一种标准化的，通用纯函数式编程语言，有非限定性语义和强静态类型。它的命名源自美国逻辑学家Haskell Brooks Curry，他在数学逻辑方面的工作使得函数式编程语言有了广泛的基础。在Haskell中，函数是一等公民。作为函数式编程语言，主要控制结构是函数。Haskell语言是1990年在编程语言Miranda的基础上标准化的，并且以λ演算（Lambda-Calculus)为基础发展而来。具有“证明即程序、结论公式即程序类型”的特征。这也是Haskell语言以希腊字母「λ」（Lambda）作为自己标志的原因。

Scheme 语言 Scheme 语言是 Lisp 的一个现代变种、方言，诞生于1975年，由 MIT 的 Gerald J. Sussman and Guy L. Steele Jr. 完成。与其他lisp不同的是，scheme是可以编译成机器码的 。 Scheme语言的规范很短，总共只有50页，甚至连Common Lisp 规范的索引的长度都不到，但是却被称为是现代编程语言王国的皇后。它与以前和以后的 Lisp 实现版本都存在一些差异，但是却易学易用。

Clojure 语言 Clojure 是一种运行在 Java™ 平台上的 Lisp 方言，它的出现彻底颠覆了我们在Java虚拟机上并发编程的思考方式改变了这一现状。如今，在任何具备 Java 虚拟机的地方，您都可以利用 Lisp 的强大功能 作为Lisp方言，Clojure或许拥有最灵活的编程模型，因此绝不缺乏号召力。与其他Lisp方言不同的是，它不会带那么多括号，还有众多Java库和在各平台上的广泛部署作为坚强后盾

Scala 语言 Scala是一种函数式面向对象语言，它融汇了许多前所未有的特性，而同时又运行于JVM之上。随着开发者对Scala的兴趣日增，以及越来越多的工具支持，无疑Scala语言将成为你手上一件必不可少的工具。 Scala为Java系统引入了强大的函数式思想，同时也并未丢弃面向对象编程。回顾历史，我发现C++和Scala有着惊人的相似之处，因为从过程式编程过渡到面向对象编程期间，C++同样起到了举足轻重的作用。当你真正融入Scala社区之后，你就会明白，为什么对于函数式语言程序员来说，Scala是异端邪说，而对于Java开发者来说，Scala是天降福音。