函数式程序设计语言ppt课件.ppt

《函数式程序设计语言ppt课件.ppt》由会员分享，可在线阅读，更多相关《函数式程序设计语言ppt课件.ppt（68页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章 函数式程序设计语言过程式程序设计语言由于数据的名值分离，变量的时空特性导致程序难于查错、难于修改命令式语言天生带来的三个问题只解决了一半滥用goto已经完全解决悬挂指针没有完全解决函数副作用不可能消除问题是程序状态的易变性(Mutability)和顺序性(Sequencing)Backus在图灵奖的一篇演说程序设计能从冯诺依曼风格下解放出来吗？中极力鼓吹发展与数学连系更密切的函数式程序设计语言5.1 5.1 过程式语言存在的问题过程式语言存在的问题（1 1）易变性难于数学模型易变性难于数学模型代数中的变量是未知的确定值，而程序设计语言的变量是对存储的抽象根本解决：能不能不要程序意义的“

2、变量”只保留数学意义的“变量”？能不能消除函数的副作用？例例：有副作用的函数有副作用的函数 int sf_fun(int x)int sf_fun(int x)static int z=0 static int z=0；/第一次装入赋初值第一次装入赋初值 return x+(z+)return x+(z+)；sf_fun(3)=3|4|5|6|7 sf_fun(3)=3|4|5|6|7 /随调用次数而异随调用次数而异，不是数学意义的确定函数。不是数学意义的确定函数。（2）顺序性更难数学模型顺序性更难数学模型顺序性影响计算结果，例如，前述急求值、正规求值、懒求值同一表达式就会有不同的结果。有副作

3、用更甚，因而难于为程序建立统一的符号数学理论。应寻求与求值顺序无关的表达方式理想的改变途径没有变量，就没有破坏性赋值，也不会有引起副作用的全局量和局部量之分。调用通过引用就没有意义。循环也没有意义，因为只有每次执行循环改变了控制变量的值，循环才能得到不同的结果。那么程序结构只剩下表达式、条件表达式、递归表达式。5.2 演算演算是符号的逻辑演算系统，它正好只有这三种机制，它就成为函数式程序设计语言的模型演算是一个符号、逻辑系统，其公式就是符号串并按逻辑规则操纵Church的理论证明，演算是个完备的系统，可以表示任何计算函数，所以任何可用演算仿真实现的语言也是完备的。演算使函数概念形式化，是涉及变

4、量、函数、函数组合规则的演算。演算基于最简单的定义函数的思想：一为函数抽象x.E，一为函数应用(x.E)(a)。一切变量、标识符、表达式都是函数或(复合)高阶函数。如x.C(C为常量)是常函数。5.2.1 5.2.1 术语和表示法术语和表示法(1)(1)演算有两类符号演算有两类符号：小写单字符用以命名参数，也叫变量。外加四个符号：(、)、。、。大写单字符、特殊字符（如+、-、*、/）、大小写组成的标识符代替一个表达式。（2 2）公式公式 变量是公式，如y。如y是变量F是公式，则y.F也是公式。如F和G都是公式，则(FG)也是公式。（3 3）表达式表达式 形如y.Fy.F为函数表达式，以关键字开

5、始，变量y为参数。形如(FG)FG)为应用表达式为了清晰，表达式可以任加成对括号。演算公式举例x x 变量、公式、表达式。(x.(y)x)x.(y)x)函数，体内嵌入应用。(z.(y(z.x)z.(y(z.x)函数，体内嵌入应用，再次嵌入函数。(z.(z y)x)z.(z y)x)应用表达式。x.y.z.(x x.(u v)w)x.y.z.(x x.(u v)w)复杂表达式(4)(4)简略表示简略表示 缩写与变形表达 下例各表达均等效：a.b.c.z.E=abcz.E =(abcz).E =(a，b，c，z).E =a.(b.(c.(z.E)命名:以大写单字符或标识符命名其表达式 G=(x.(

6、y(yx)(x.(y(yx)(x.(y(yx)=(G G)=H由于演算中一切语义概念均用表达式表达。为了清晰采用命名替换使之更易读。T=x.y.x /逻辑真值F=x.y.y /逻辑假值1=x.y.x y /数12=x.y.x(x y)/数2zerop=n.n(x.F)T /判零函数注：zerop中的F、T可以用表达式展开形式语法形式语法核心的演算没有类型，没有顺序控制等概念，程序和数据没有区分。语法极简单：:=|.|()|():=5.2.2 5.2.2 约束变量和自由变量约束变量和自由变量(x.(b x)x)x.(b x)x)自由变量 约束变量（x.y.(a x y)(b(y.(x y)表达式

7、中的作用域复盖（x.(x.(x x.(.(x x a)(a)(x x b)(b)(x x c)c)）PMNROQ第1个x约束于P第2个x x约束于O第3个x x在M中自由，约束于O，P第4个x x在N中自由，约束于P第5个x x在R中自由，在Q中这5个x均约束出现,b，c自由出现。基本函数基本函数TRUE 和FALSE的表达式 T=x.y.x T=x.y.x F=x.y.y 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.(zx.y.y)(x.y.x)not=z.(zF)T)=z

8、.(zx.y.y)(x.y.x)and=a.b.(ab)F)=a.b.(ab)x.y.y)and=a.b.(ab)F)=a.b.(ab)x.y.y)or=a.b.(aT)b)=a.b.(a x.y.x)b)or=a.b.(aT)b)=a.b.(a x.y.x)b)以下是算术操作函数举例：+=+=add=x.y.a.b.(xa)(ya)b)add=x.y.a.b.(xa)(ya)b)*=multiply=x.y.a.(x(ya)*=multiply=x.y.a.(x(ya)*=sqr=x.y.(yx)*=sqr=x.y.(yx)identity=x.x /identity=x.x /同一函数同一

9、函数 succ=n.(x.y.nx(x y)/succ=n.(x.y.nx(x y)/后继函数后继函数zerop=n.n(x.F)T zerop=n.n(x.F)T =n.n(z.x.y.y)(x.y.y)/=n.n(z.x.y.y)(x.y.y)/判零判零 函数函数 例：例：3+43+4就写就写add 3 4add 3 4，add 3 add 3返回返回“加加3 3函数函数”应用到应用到4 4上当然就是上当然就是7 7。写全了是：。写全了是：（x.y.a.b.(x a)(y a)b)x.y.a.b.(x a)(y a)b)）(p.q.(p(p(p q)(s.t.(s(s(s(s t)(p.q

10、.(p(p(p q)(s.t.(s(s(s(s t)a.b.(a(a(a(a(a(a(a b)a.b.(a(a(a(a(a(a(a b)归约与范式归约与范式归约将复杂的表达式化成简单形式，归约将复杂的表达式化成简单形式，即按一定的即按一定的规则对符号表达式进行置换。规则对符号表达式进行置换。例例：归约数归约数1 1的后继的后继 (succ 1)=(succ 1)=(nn.(x.y.n x(x y).(x.y.n x(x y)1 1)=(=(x.y.1 x(x y)x.y.1 x(x y)=(x.y.(=(x.y.(pp.q.p q).q.p q)x x(x y)(x y)=(=(x.y.(q.

11、x q)(x y)x.y.(q.x q)(x y)=(x.y.x(x y)=2 =(x.y.x(x y)=2注：注：succsucc和和1 1都是函数都是函数(1(1是常函数是常函数)，第一步是，第一步是nn束定的束定的n n被被1 1置换。置换。展开后，展开后，x x置换置换p p，(xy)(xy)置换置换q q，最后一行不能再置换了，最后一行不能再置换了，它就是范式，它就是范式，语义语义为为2 2。（1 1）归约归约：归约的表达式是一个归约的表达式是一个应用表应用表达式达式(x.M N)x.M N)，其左边子表达式是其左边子表达式是函数表函数表达式，右边是任意达式，右边是任意表达式。表达式

12、。归约以右边的归约以右边的表达式置换函数体表达式置换函数体M M中中指明的那个形参变量。指明的那个形参变量。形式地，我们用形式地，我们用 N/X,MN/X,M表示对（表示对（x.M Nx.M N）的的置换置换（规则（规则略）。略）。关键的问题是注意函数体中要置换的变量是否关键的问题是注意函数体中要置换的变量是否自由出现，如：自由出现，如：(x.x(x.(xy)(zz)x.x(x.(xy)(zz)=(zz)(x.(zz)y)=(zz)(x.(zz)y)/错误，第二错误，第二x x个非自由出现。个非自由出现。=(=(zz)(x.(xy)/zz)(x.(xy)/正确例例11-5 11-5 高层表示的

13、高层表示的归约归约(n.add n n)3n.add n n)3 =add 3 3 /3 =add 3 3 /3置换置换n n后取消后取消nn =6 =6(f.x.f(f x)(f.x.f(f x)succsucc 7 7 =x.succx.succ(succsucc x)7 x)7 =succsucc(succsucc 7)7)=succsucc(8)=9(8)=9注注：addadd，3 3，succsucc，7 7，9 9是为了清晰没进是为了清晰没进 一步展开为一步展开为表达式。表达式。但但归约有时并不能简化归约有时并不能简化，如如：(x.xx)(x.xx)x.xx)(x.xx)，归约后仍

14、是原公式，归约后仍是原公式，这种这种表达式称为不可归约的。表达式称为不可归约的。对应为程序设对应为程序设计语言中的无限递归。计语言中的无限递归。(2)(2)归约是消除一层约束的归约归约是消除一层约束的归约:x.Fx=Fx.Fx=F (3)(3)换名换名:归约中如发生改变束定性质，归约中如发生改变束定性质，则允则允许换名许换名(后跟的变量名后跟的变量名)，以保证原有束定以保证原有束定关系。关系。例如：例如：(x.(y.x)(z y)/(zy)x.(y.x)(z y)/(zy)中中y y是自由变量是自由变量 =y.(zy)/y.(zy)/此时此时(zy)zy)中中y y被束定了，被束定了，错误！错

15、误！=(=(x.(w.x)(zy)/x.(w.x)(zy)/因因(y.x)y.x)中函数体中函数体 无无y y，可换名可换名 =w.(zy)/w.(zy)/正确！正确！(4)(4)归约约定归约约定顺序顺序:每次归约只要找到可归约的子公式即可归每次归约只要找到可归约的子公式即可归约，约，演算没有规定顺序。演算没有规定顺序。范式范式:符号归约当施行（除符号归约当施行（除规则外）所有变换规则外）所有变换规则后没有新形式出现，则这种规则后没有新形式出现，则这种表达式叫范式。表达式叫范式。解释解释:范式即范式即演算的语义解释，演算的语义解释，形如形如 x xx x，(y(x.z)(y(x.z)就只能解释

16、为数据了就只能解释为数据了。上述基本函数均为范式，上述基本函数均为范式，在它的上面取上有意义在它的上面取上有意义的名字可以构成上一层的函数，的名字可以构成上一层的函数，如：如：pred=n.(subtract n 1)pred=n.(subtract n 1)（5）综合规约例题综合规约例题：以以演算规约演算规约3*23*2 3*2=*(3)(2)3*2=*(3)(2)=x.y.(y x)(3)(2)x.y.(y x)(3)(2)(y.(y 3)(2)(y.(y 3)(2)(2)3)(2)3)=(f.c.f(f c)(3)(f.c.f(f c)(3)c.(3(3 c)c.(3(3 c)=c.(f

17、.c.(f(f(f(c)(3 c)c.(f.c.(f(f(f(c)(3 c)/有有c c不能置换不能置换c c c.(f.z.(f(f(f(z)(3 c)c.(f.z.(f(f(f(z)(3 c)c.(z.(3 c)(3 c)(3 c)(z)c.(z.(3 c)(3 c)(3 c)(z)/再展再展3 3=c.z.(f.c.(f(f(f(c)c)(3c)(3c)(z)c.z.(f.c.(f(f(f(c)c)(3c)(3c)(z)c.z.(c.z.(f.w.(f(f(f(w)c)(3c)(3c)(z)f.w.(f(f(f(w)c)(3c)(3c)(z)c.z.(w.(c(c(c(w)(3c)(3c

18、)(z)c.z.(w.(c(c(c(w)(3c)(3c)(z)/同理展开第二个同理展开第二个c,c,第三个第三个c c=c.z.(w.(c(c(c(w)(p.(c(c(c(p)(c.z.(w.(c(c(c(w)(p.(c(c(c(p)(q.(c(c(c(q)(z)q.(c(c(c(q)(z)c.z.(w.(c(c(c(w)(c.z.(w.(c(c(c(w)(p.(c(c(c(p)(c(c(c(z)p.(c(c(c(p)(c(c(c(z)c.z.(w.(c(c(c(w)(c.z.(w.(c(c(c(w)(c(c(c(c(c(c(z)(c(c(c(c(c(c(z)c.z.(c(c(c(c(c(c(

19、c(c(c(z)=9 c.z.(c(c(c(c(c(c(c(c(c(z)=9增强增强演算演算只用最底层只用最底层演算是极其复杂的。用高层命名函数，语义演算是极其复杂的。用高层命名函数，语义清晰。不仅如此，保留一些常见关键字，语义更清晰。例清晰。不仅如此，保留一些常见关键字，语义更清晰。例如，我们可以定义一个如，我们可以定义一个if_then_elseif_then_else为名的函数：为名的函数：if_then_else=p.m.n.p m nif_then_else=p.m.n.p m n，当当p p为为 真真 时，时，执执行行m m否则为否则为n n。我们先验证其真伪。我们先验证其真伪。例

20、例：当条件表达式为真时当条件表达式为真时if_then_elseif_then_else函数的归约函数的归约(if_then_else)T M Nif_then_else)T M N=(p.m.n.p m n)T M N=(p.m.n.p m n)T M N=(m.n.(T m n)M N=(m.n.(T m n)M N=(m.n.(x.y.x)m n)M N=(m.n.(x.y.x)m n)M N=(m.n.(y.m)n)M N=(m.n.(y.m)n)M N=(m.n.m)M N=(m.n.m)M N=(n.M)N=(n.M)N=M=Mifif表达式表达式 可保留显式if-then-els

21、e形式：(if_then_else)E1 E2 E3=if E1 then E2 else E3 其中E1，E2，E3为表达式。Let/whereLet/where表达式表达式 如果有高阶函数：如果有高阶函数：(n.multiply n(n.multiply n(succsucc n)(add i 2)n)(add i 2)=multiply(add i 2)(multiply(add i 2)(succsucc(add i 2)(add i 2)/n n 和和 add i 2add i 2置换变元得置换变元得=multiply n(multiply n(succsucc n)/let n=a

22、dd i 2 in n)/let n=add i 2 in let a=b in E (a.E)b E where a=b let a=b in E (a.E)b E where a=b (f.E2)(x.E1)=let f=x.E1 in E2f.E2)(x.E1)=let f=x.E1 in E2 =let f x=E1 in E2 =let f x=E1 in E2其中形如其中形如f=x.E1f=x.E1的的x.x.可移向左边为可移向左边为f x=E1 f x=E1。如如:sqrsqr=n.multiply n n /=n.multiply n n /整个是整个是函数表达式函数表达式 s

23、qrsqr n=multiply n n /n=multiply n n /两应用表达式也相等两应用表达式也相等 letlet表达式在表达式在ML.LISPML.LISP中直接采用，中直接采用，MirandaMiranda用用wherewhere关键字使程序更好读，关键字使程序更好读，letlet直到直到E E完结构成一个程序块。完结构成一个程序块。MirandaMiranda只不过把只不过把wherewhere块放在块放在E E之后之后.元组表达式元组表达式一般情况下一般情况下n n元组是元组是p=(xp=(x1 1,x,x2 2,x xn n),),建立在建立在p p上上函数有：函数有：l

24、et f(xlet f(x1 1,x,x2 2,x xn n)=E1 in E2)=E1 in E2 let let fpfp=E1 in=E1 in let x let x1 1=first p in=first p in let x let x2 2=second p in=second p in .let let x xn n=n_thn_th p in E2 p in E2LambdaLambda演算演算关于关于LambdaLambda演算演算l 表达式表达式l自由变量（计算一个自由变量（计算一个 表达式的自由变量表达式的自由变量集合集合）l替换（计算）替换（计算）l变换规则变换规则

25、（三种变换）（三种变换）l归约归约 l范式（性质及其计算）范式（性质及其计算）关于关于LambdaLambda演算演算l 表达式表达式 一个一个 表达式表达式由变量名、抽象符号由变量名、抽象符号，.以及括号等符号以及括号等符号构成，构成，其语法为：其语法为：:=|.|()关于关于LambdaLambda演算演算l变换规则变换规则 （三种变换）（三种变换）l 变换：设变换：设E是是 表达式，表达式，x是变量，则称下面变换为是变量，则称下面变换为变换变换（其中（其中y不在不在 FV(x.E)中）中）x.E-y.y/x E l 变换：设变换：设(x.E)和和E0为为 表达式，则称下面变换为表达式，则

26、称下面变换为变换变换（称（称变换规则的左部表达式为变换规则的左部表达式为基）基）(x.E)E0 EE0/xl 变换：假设变换：假设 x.Mx是一个表达式，且满足条件是一个表达式，且满足条件x FV(M)，则称下面变换为则称下面变换为变换变换:(x.M x)M 关于关于LambdaLambda演算演算l自由变量（计算一个自由变量（计算一个 表达式的自由变量集合表达式的自由变量集合）l表达式表达式E中变量名中变量名x的一次出现称为的一次出现称为自由出现自由出现，如果，如果E中任何一个形如中任何一个形如 x.E的子表达式包含该出现；的子表达式包含该出现；ly(x y.y(x.x y)(z(x.x x

27、)的自由变量集合的自由变量集合y,zl替换（计算）替换（计算）设设E和和E0是表达式，是表达式，x是变量名，是变量名，替换替换EE0/x是表示是表示 把把E中的所有中的所有x的自由出现替换成的自由出现替换成E0。l需要明确变量的自由出现需要明确变量的自由出现l计算规则计算规则l(y.x+y)y/x=z.y+z关于关于LambdaLambda演算演算l范式（性质及其计算）范式（性质及其计算）l假设假设E是一个表达式，且其中没有任何一个是一个表达式，且其中没有任何一个归约基，则称该表达式为归约基，则称该表达式为范式范式。l范式范式的存在性：如的存在性：如果有范式，则最左归约法果有范式，则最左归约法

28、一定能求出范式。一定能求出范式。l范式范式的唯一性：如的唯一性：如果有范式则在果有范式则在 变换下一变换下一定唯一。定唯一。函数式描述方法函数式描述方法关于函数式描述方法关于函数式描述方法函数式语言的特点函数式语言的特点引用透明性；高阶性；模式匹配；并行性；引用透明性；高阶性；模式匹配；并行性；函数式语言的组成部分函数式语言的组成部分程序结构程序结构类型及其操作类型及其操作表达式表达式用函数式语言来描述算法（解释器）用函数式语言来描述算法（解释器）函数空间函数空间函数定义（方程）函数定义（方程）关于函数式描述方法关于函数式描述方法函数式语言的组成部分函数式语言的组成部分程序结构程序结构函数定义

29、函数定义目标表达式目标表达式类型及其操作类型及其操作标准类型标准类型 -集合类型集合类型幂集类型幂集类型 -元组类型元组类型联合类型联合类型 -序列类型序列类型函数类型函数类型 -递归类型递归类型抽象类型抽象类型关于函数式描述方法关于函数式描述方法函数式语言的组成部分函数式语言的组成部分表达式表达式非非letlet表达式（常量，变量，表达式（常量，变量，表达式，条件表达表达式，条件表达式，式，以及各种操作）以及各种操作）letlet表达式表达式 letlet x=E x=E inin E E letrecletrec表达式表达式 letrecletrec x=E x=E1 1 inin E E

30、在表达式中增加类型说明在表达式中增加类型说明 关于函数式描述方法关于函数式描述方法用函数式语言来描述算法用函数式语言来描述算法函数空间：函数空间：INT*INT BOOL函数定义（方程）函数定义（方程）lookup L a=(null LFALSE，a=hd LTRUE，lookup(tl L)a)5.3 5.3 函数式语言怎样克服命令函数式语言怎样克服命令式语言的缺点式语言的缺点5.3.1 5.3.1 消除赋值消除赋值赋值语句在过程语言中起什么作用。在函数式语言中取消会有什么问题：1 存储计算子表达式的中间结果。2 条件语句的重要组成。3 用于循环控制变量。4 处理复杂数据结构(增删改某个成

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

32、循环要用递归。其它显式循环要用递归。4:4:禁止赋值意味着数据结构一旦创建不得修禁止赋值意味着数据结构一旦创建不得修改改,故采用如下函数式语言结构数据修改方式故采用如下函数式语言结构数据修改方式ABCEHGDFBCAFJI5.3.2 5.3.2 以递归代替以递归代替while_dowhile_do 组织仿真的要点是把递归函数体写入条件表达组织仿真的要点是把递归函数体写入条件表达式。式。循环终止条件是条件测试部分，循环终止条件是条件测试部分，函数如函数如有返回值放在有返回值放在thenthen部分，部分，递归函数体放在递归函数体放在elseelse部分，部分，如果不需返回值则取消一部分如果不需返

33、回值则取消一部分(else)else)。5.3.3 5.3.3 消除顺序消除顺序一旦语义相关无法传递数据，一旦语义相关无法传递数据，非得写成嵌套函非得写成嵌套函数不可数不可(返回值自动束定到外套函数的变元上返回值自动束定到外套函数的变元上)例例:pascalpascal实现：实现：c c：=a+b=a+b；s s：=sin(c*c)=sin(c*c)；。write(a write(a，b b，c c，s)s)；/上面计算不进行是无法打印/的逻辑上要有顺序。LISP LISP 实现实现：(print(let(c(+a b)print(let(c(+a b)let(s(sin(*c c)let(s

34、(sin(*c c)list a b c s)list a b c s)/仍有顺序但在一个 /表达式内。自左至右处理即隐式顺序。MirandaMiranda实现：实现：Answere a b=(a b c s)Answere a b=(a b c s)where where s=sin(c*c)s=sin(c*c)c=a+b c=a+b /多么清晰，全然没有顺序用嵌套代替语义相关的顺用嵌套代替语义相关的顺序 用懒求值代替顺序用懒求值代替顺序 利用卫式进一步消除顺序性利用卫式进一步消除顺序性MirandaMiranda的卫式表达式的卫式表达式 gcd a b=gcd(a-b)bgcd a b=g

35、cd(a-b)b，ab ab =gcd a(b-a)=gcd a(b-a)，ab a max2 2 max1 max2 2 =max2 =max2，max2 max1 3 max2 max1 3 =max1=max1，otherwise otherwise where where max1=(max_tree n1)4 max1=(max_tree n1)4 max2=(max_tree n2)5 max2=(max_tree n2)5如有应用：如有应用：(max_tree leaf1)max_tree leaf1)/结果值为结果值为3 3，leaf1leaf1用上例用上例(max_tree

36、tree1)max_tree tree1)/结果值为结果值为4949，tree1tree1用上例用上例 表表(list)list)MirandaMiranda表的表示法表的表示法 /空表空表1.1.nn /1 /1到到n,n,域表示域表示odd_number=1odd_number=1，3 3，.100.100 /1 /1到到100100内奇数表，头两项及最后项必写内奇数表，头两项及最后项必写eleven_up=11.eleven_up=11./10 /10以上，以上，无限表表示无限表表示evens=10evens=10，12.10012.100 /10 /10以上偶数表至以上偶数表至1001

37、00，头两项及最后项必写，头两项及最后项必写evens_up=12evens_up=12，14.14./10 /10以上偶数无限表，以上偶数无限表，week _days=“Mon”week _days=“Mon”，“Tue”“Tue”，“Wed”“Wed”，“Thur”“Thur”，“Fri”“Fri”/五个串值的表五个串值的表5.4.2 5.4.2 内定义操作内定义操作MirandaMiranda定义了常规的算术运算符定义了常规的算术运算符(+(+、-、*、/、divdiv、mod)mod)并按中缀表示使用。故内定义了一些并按中缀表示使用。故内定义了一些有用的表操作：有用的表操作：L1+L2

38、 /L1+L2 /表表L2L2并接到表并接到表L1L1的末尾的末尾 item:List /item:List /将项将项itemitem加到表加到表ListList的头前的头前 List List！n /n /从表从表ListList中选取第中选取第n n项项 L1-L2 /L1-L2 /从表从表L1L1中剔出中剔出L2L2的值的值#List /List /返回表返回表ListList的项的项(基基)数数5.4.3 5.4.3 定义函数定义函数MirandaMiranda把函数定义叫方程把函数定义叫方程(equation)equation)。例例：斐波那契数的函数定义，斐波那契数的函数定义，用

39、卫式表达式实现递归用卫式表达式实现递归Fibonacci n=1Fibonacci n=1，n=0 n=0 =1 =1，n=1 n=1 =Fibonacci(n-1)+Fibonacci(n-2)n1 =Fibonacci(n-1)+Fibonacci(n-2)n1 卫式表达式的值集应复盖所有的可能，卫式表达式的值集应复盖所有的可能，否则用否则用otherwiseotherwise。例例：利用利用wherewhere解二次方程解二次方程quadroot a b c=error“complex roots”quadroot a b c=error“complex roots”，delta del

40、ta 0 delta 0 where where delta=b*b-4*a*c delta=b*b-4*a*c radix=sqrt delta radix=sqrt delta term1=-b/(2*a)term1=-b/(2*a)term2=radix/(2*a)term2=radix/(2*a)MirandaMiranda完全按完全按演算模型，每个函数都是一元运算，当演算模型，每个函数都是一元运算，当有多个变元时，有多个变元时，函数名也是第一类对象，函数名也是第一类对象，它逐一应用到它逐一应用到各个参数，各个参数，中间返回函数可以任意取名，中间返回函数可以任意取名，这种中间函数这种中

41、间函数称称CurryCurry函数函数。例例：直角三角形求斜边长函数直角三角形求斜边长函数 hypotenuse a b=sqrt(a*a+b*b)hypotenuse a b=sqrt(a*a+b*b)调用时调用时 hypotenuse 3 4 /=5hypotenuse 3 4 /=5也可写作：也可写作：(hypotenuse 3)4 hypotenuse 3)4 f 4 f 4 Miranda Miranda则写作为：则写作为：f 4 where f=hypotenuse 3 f 4 where f=hypotenuse 3 /f=sqrt(9+b*b)/f=sqrt(9+b*b)即即

42、Curry Curry 函数。函数。例例:MirandaMiranda用变阶函数实现类型参数化。用变阶函数实现类型参数化。type row_type=array0.9 of Integer;type row_type=array0.9 of Integer;function Reduce(functionf(x:Integer,y:Integer):Integer;function Reduce(functionf(x:Integer,y:Integer):Integer;ar:row_type):Integer;/ar:row_type):Integer;/函数函数f f是参数化的。是参数化

43、的。var sum,k:Integer;var sum,k:Integer;beginbegin sum:=ar0;sum:=ar0;for k=1 to 9 do for k=1 to 9 do sum:=f(sum,ark);sum:=f(sum,ark);reduce:=sum reduce:=sumend;end;function MyOp(s:Integer,y:Integer):Integer;/function MyOp(s:Integer,y:Integer):Integer;/此处定此处定义一实例函数。义一实例函数。beginbegin MyOp:=abs(x)+abs(y)

44、MyOp:=abs(x)+abs(y)end;end;function MySum(ar:row_type):Integer;function MySum(ar:row_type):Integer;begin MySum:=Reduce(MyOp,ar)end;begin MySum:=Reduce(MyOp,ar)end;上上程序仅将程序仅将 ReduceReduce函数操作参数化。数组元素类型、长度还是固函数操作参数化。数组元素类型、长度还是固定的。定的。MirandaMiranda都可以，它设都可以，它设3 3个参数：操作、表、单位元。单位个参数：操作、表、单位元。单位元的值可用于归约过

45、程的初始化值，也是空表时的返回值：元的值可用于归约过程的初始化值，也是空表时的返回值：reduce f n=n 1reduce f n=n 1reduce f(a:x)n=f a(reduce x n)2reduce f(a:x)n=f a(reduce x n)2为了理解上不引起岐意，写明为了理解上不引起岐意，写明reducereduce的类型：的类型：reduce:(numreduce:(numnumnumnum)/num)/第一变元第一变元f f是函数类型（有是函数类型（有 括号）括号）,它是二元算子它是二元算子 num /num /返回值是表，表元素是返回值是表，表元素是numnum类

46、型类型 num /num /若空表映射为数，类型是若空表映射为数，类型是num.num.num /num /最后映射返回值是最后映射返回值是numnum类型。类型。22行中（行中（a:xa:x）是表头是表头a a和表尾和表尾x x，右边函数体是表尾归约后与表右边函数体是表尾归约后与表头归约。头归约。11行指明空表规约行指明空表规约 n n 次是单位元的次是单位元的 n n 次复合。次复合。5.4.4 5.4.4 表闭包表闭包表闭包是一个任意复杂结构的表闭包是一个任意复杂结构的(无限无限)表。其语法是：表。其语法是：:=:=|:=:=；|:=:=:=:=:=:=表闭包示例表闭包示例：ZF ZF

47、表达式表达式 解释解释 n*2|n2n*2|n2，4 4，6 6，8 8，10 10 44，8 8，1212，1616，2020 1 1n*n|n 1n*n|n 1，2 2，.11，4 4，9 9，.2 2x+y|x 1.3x+y|x 1.3；y3 y3，7 7 44，5 5，6 6，8 8，9 9，1010 3 3x*y|x 1.3x*y|x 1.3；y1.3 y1.3；x=yx=y11，2 2，4 4，3 3，6 6，99 4 411行只有一个生成器，行只有一个生成器，表值表值2 2，4 4，6 6，8 8，1010束定于束定于n n得出得出2 2倍表。倍表。22行是无限表也只有一产生器，

48、行是无限表也只有一产生器，33行行44行有两个产生器，行有两个产生器，4 4行还有一过滤器，行还有一过滤器，否则要对称出否则要对称出9 9个数。个数。例例：用用MirandaMiranda编写快速分类编写快速分类 sort =1sort =1sort(pivotsort(pivot：rest)=sort y|y restrest)=sort y|y rest；y=pivot 2 ypivot 4 ypivot 4 1 1行定义函数行定义函数sortsort的变元是空表它返回一空表的变元是空表它返回一空表(调用同一函调用同一函数数)，一般定义递归它都有一般定义递归它都有11行。行。它同时指出它同

49、时指出sortsort是表变元。是表变元。22行的圆括号不是表，行的圆括号不是表，而是说明变元一个表，而是说明变元一个表，它由元组它由元组pivotpivot和和restrest组成，即表头、表尾。组成，即表头、表尾。以局部的名字给出了与之结合的实参以局部的名字给出了与之结合的实参表表头、表尾。表表头、表尾。5.4.5 5.4.5 无限表无限表可以把无限表看作两部分：有限的头部，它放已经算好了的值，和一个无限的尾，它由生成新表尾的代码组成。这相当于一个函数，也采用懒求值，即不到表不够时不计算它。5.5 5.5 问题与讨论问题与讨论(1)(1)模拟状态不易模拟状态不易(2)(2)效率还是问题效率

50、还是问题从过去比顺序的命令式语言慢从过去比顺序的命令式语言慢200-1000200-1000倍到近来的倍到近来的3-53-5倍，倍，其原因是：其原因是：函数是第一类对象，函数是第一类对象，局部于它的数据一般要在堆局部于它的数据一般要在堆(heap)heap)上分上分配，配，为了避免悬挂引用，为了避免悬挂引用，要有自动重配的检查。要有自动重配的检查。无类型无类型(如如LISP)LISP)要在运行中检查类型，即使是强类型的要在运行中检查类型，即使是强类型的(如如MLML，Miranda)Miranda)减少了类型动态检查，减少了类型动态检查，但函数式语言天然匹配但函数式语言天然匹配选择模式的途径也