【教学课件】第五章函数式程序设计语言.ppt

《【教学课件】第五章函数式程序设计语言.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第五章函数式程序设计语言.ppt（68页珍藏版）》请在三一办公上搜索。

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

2、函数的副作用？,例：有副作用的函数 int sf_fun(int x)static int z=0；/第一次装入赋初值 return x+(z+)；sf_fun(3)=3|4|5|6|7/随调用次数而异，不是数学意义的确定函数。,（2）顺序性更难数学模型,顺序性影响计算结果，例如，前述急求值、正规求值、懒求值同一表达式就会有不同的结果。有副作用更甚，因而难于为程序建立统一的符号数学理论。应寻求与求值顺序无关的表达方式理想的改变途径没有变量，就没有破坏性赋值，也不会有引起副作用的全局量和局部量之分。调用通过引用就没有意义。循环也没有意义，因为只有每次执行循环改变了控制变量的值，循环才能得到不同的

3、结果。那么程序结构只剩下表达式、条件表达式、递归表达式。,5.2 演算,演算是符号的逻辑演算系统，它正好只有这三种机制，它就成为函数式程序设计语言的模型演算是一个符号、逻辑系统，其公式就是符号串并按逻辑规则操纵Church的理论证明，演算是个完备的系统，可以表示任何计算函数，所以任何可用演算仿真实现的语言也是完备的。,演算使函数概念形式化，是涉及变量、函数、函数组合规则的演算。演算基于最简单的定义函数的思想：一为函数抽象x.E，一为函数应用(x.E)(a)。一切变量、标识符、表达式都是函数或(复合)高阶函数。如x.C(C为常量)是常函数。,5.2.1 术语和表示法,(1)演算有两类符号：小写单

4、字符用以命名参数，也叫变量。外加四个符号：(、)、。、。大写单字符、特殊字符（如+、-、*、/）、大小写组成的标识符代替一个表达式。,（2）公式 变量是公式，如y。如y是变量F是公式，则y.F也是公式。如F和G都是公式，则(FG)也是公式。,（3）表达式 形如y.F为函数表达式，以关键字开始，变量y为参数。形如(FG)为应用表达式为了清晰，表达式可以任加成对括号。,演算公式举例,x 变量、公式、表达式。(x.(y)x)函数，体内嵌入应用。(z.(y(z.x)函数，体内嵌入应用，再次嵌入函数。(z.(z y)x)应用表达式。x.y.z.(x x.(u v)w)复杂表达式,(4)简略表示,缩写与变

5、形表达 下例各表达均等效：a.b.c.z.E=abcz.E=(abcz).E=(a，b，c，z).E=a.(b.(c.(z.E),命名:以大写单字符或标识符命名其表达式 G=(x.(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可以用表达式展开,形式语法,核心的演算没有类型，没有顺序控制等概念，程序和数据没有区分。语法极简单：:=|.|()|(

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

7、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.

8、(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)，其左边子表达式是

9、函数表达式，右边是任意表达式。归约以右边的表达式置换函数体M中指明的那个形参变量。形式地，我们用N/X,M表示对（x.M N）的置换（规则略）。关键的问题是注意函数体中要置换的变量是否自由出现，如：(x.x(x.(xy)(zz)=(zz)(x.(zz)y)/错误，第二x个非自由出现。=(zz)(x.(xy)/正确,例11-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是为了清晰没进 一步展开为表达式。,但归约有时并不

10、能简化，如：(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)归约约定顺序:每次归约只要找到可归约的子公式即可归约，演算没有规定顺序。范式:符号归约当施行（除规则外）所有变换规则后没有新形式出现，则这种表达式叫范式。解释

11、:范式即演算的语义解释，形如 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)c.z.(f.

12、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.z.(w.(c(c(c(w)(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=

13、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

14、 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关键字使程序更好

15、读，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,Lambda演算,关于Lambda演算,表达式自由变量（计算一个表达式的自由变量集合）替换（计算）变换规则（三种变换）归约 范式（性质及其计算）,关于Lambda演算,表达式 一个表达式由变量名、抽象符号，.以及括号等符号构成，其语法为：:=|.|(),

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

17、是变量名，替换EE0/x是表示 把E中的所有x的自由出现替换成E0。需要明确变量的自由出现计算规则(y.x+y)y/x=z.y+z,关于Lambda演算,范式（性质及其计算）假设E是一个表达式，且其中没有任何一个归约基，则称该表达式为范式。范式的存在性：如果有范式，则最左归约法一定能求出范式。范式的唯一性：如果有范式则在变换下一定唯一。,函数式描述方法,关于函数式描述方法,函数式语言的特点引用透明性；高阶性；模式匹配；并行性；函数式语言的组成部分程序结构类型及其操作表达式用函数式语言来描述算法（解释器）函数空间函数定义（方程）,关于函数式描述方法,函数式语言的组成部分程序结构函数定义目标表达式

18、类型及其操作标准类型-集合类型幂集类型-元组类型联合类型-序列类型函数类型-递归类型抽象类型,关于函数式描述方法,函数式语言的组成部分表达式非let表达式（常量，变量，表达式，条件表达式，以及各种操作）let表达式 let x=E in E letrec表达式 letrec x=E1 in E在表达式中增加类型说明,关于函数式描述方法,用函数式语言来描述算法函数空间：INT*INT BOOL函数定义（方程）lookup L a=(null LFALSE，a=hd LTRUE，lookup(tl L)a),5.3 函数式语言怎样克服命令式语言的缺点,5.3.1 消除赋值赋值语句在过程语言中起什么

19、作用。在函数式语言中取消会有什么问题：1 存储计算子表达式的中间结果。2 条件语句的重要组成。3 用于循环控制变量。4 处理复杂数据结构(增删改某个成分)。,解决办法,1：保留全局量、局部量(符号名)以及参数名。2：用条件表达式代替条件语句，其返回值通过 参数束定或where子句束定于名字3:函数式语言都要定义表数据结构，因为归约 和递归计算在表上很方便。对整个表操作实 则是隐式迭代。不用循环控制变量。对于 顺序值也都用表写个映射函数即可隐式迭代。部分达到作用3，其它显式循环要用递归。,4:禁止赋值意味着数据结构一旦创建不得修改,故采用如下函数式语言结构数据修改方式,A,B,C,E,H,G,D

20、,F,B,C,A,F,J,I,5.3.2 以递归代替while_do,组织仿真的要点是把递归函数体写入条件表达式。循环终止条件是条件测试部分，函数如有返回值放在then部分，递归函数体放在else部分，如果不需返回值则取消一部分(else)。,5.3.3 消除顺序,一旦语义相关无法传递数据，非得写成嵌套函数不可(返回值自动束定到外套函数的变元上),例: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)/仍

21、有顺序但在一个/表达式内。自左至右处理即隐式顺序。Miranda实现：Answere a b=(a b c s)where s=sin(c*c)c=a+b/多么清晰，全然没有顺序,用嵌套代替语义相关的顺序,用懒求值代替顺序,利用卫式进一步消除顺序性,Miranda的卫式表达式 gcd a b=gcd(a-b)b，ab=gcd a(b-a)，ab=a，a=bLISP的条件选择（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 输出问题,利用数据对象内

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

23、iranda的基本类型有字符(char类型，加单引号的字母)，真值(bool类型，值为True和False)和数(num 类型，包括整数、实数)，数据结构只有表和元组，串是字符表,5.4.1 数据结构,元组(tuple)树类型定义 tree:=Leaf Integer|Node tree tree 1 leaf1=(Leaf 3)2 tree1=(Node leaf1(Node(Leaf 17)(Leaf 49)3,3,3,17,49,leaf 1,tree 1,leaf 1,第2行执行后,第3行执行后,多态函数定义及调用 设函数 max_tree 为求树中叶子值最大,max_tree(Lea

24、f 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用上例,表(list),Miranda表的表示法/空表1.n/1到n,域表示odd_number=1，3，.100/1到100内奇数表，头两项及最后项必写eleven_up=11./10以上，无限表表示e

25、vens=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 定义函数,Mirand

26、a把函数定义叫方程(equation)。例：斐波那契数的函数定义，用卫式表达式实现递归Fibonacci n=1，n=0=1，n=1=Fibonacci(n-1)+Fibonacci(n-2)n1 卫式表达式的值集应复盖所有的可能，否则用otherwise。,例：利用where解二次方程quadroot a b c=error“complex roots”，delta 0 where delta=b*b-4*a*c radix=sqrt delta term1=-b/(2*a)term2=radix/(2*a),Miranda完全按演算模型，每个函数都是一元运算，当有多个变元时，函数名也是第一

27、类对象，它逐一应用到各个参数，中间返回函数可以任意取名，这种中间函数称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=array0.9 of Integer;function Reduce(functionf(x:Integer,y:Integer):Inte

28、ger;ar:row_type):Integer;/函数f是参数化的。var sum,k:Integer;begin sum:=ar0;for k=1 to 9 do sum:=f(sum,ark);reduce:=sumend;function MyOp(s:Integer,y:Integer):Integer;/此处定义一实例函数。begin MyOp:=abs(x)+abs(y)end;function MySum(ar:row_type):Integer;begin MySum:=Reduce(MyOp,ar)end;,上程序仅将 Reduce函数操作参数化。数组元素类型、长度还是固定

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

30、任意复杂结构的(无限)表。其语法是：:=|:=；|:=:=:=,表闭包示例：ZF 表达式 解释n*2|n2，4，6，8，10 4，8，12，16，20 1n*n|n 1，2，.1，4，9，.2x+y|x 1.3；y3，7 4，5，6，8，9，10 3x*y|x 1.3；y1.3；x=y1，2，4，3，6，9 4,1行只有一个生成器，表值2，4，6，8，10束定于n得出2倍表。2行是无限表也只有一产生器，3行4行有两个产生器，4行还有一过滤器，否则要对称出9个数。,例：用Miranda编写快速分类 sort=1sort(pivot：rest)=sort y|y rest；ypivot 4 1行定

31、义函数sort的变元是空表它返回一空表(调用同一函数)，一般定义递归它都有1行。它同时指出sort是表变元。2行的圆括号不是表，而是说明变元一个表，它由元组pivot和rest组成，即表头、表尾。以局部的名字给出了与之结合的实参表表头、表尾。,5.4.5 无限表,可以把无限表看作两部分：有限的头部，它放已经算好了的值，和一个无限的尾，它由生成新表尾的代码组成。这相当于一个函数，也采用懒求值，即不到表不够时不计算它。,5.5 问题与讨论,(1)模拟状态不易(2)效率还是问题从过去比顺序的命令式语言慢200-1000倍到近来的3-5倍，其原因是：函数是第一类对象，局部于它的数据一般要在堆(heap

32、)上分配，为了避免悬挂引用，要有自动重配的检查。无类型(如LISP)要在运行中检查类型，即使是强类型的(如ML，Miranda)减少了类型动态检查，但函数式语言天然匹配选择模式的途径也是运行低效原因。懒求值开销大中间复合值一多费时费空间。无限表动态生成，计算一次增长一个元素！效率也很低。,(3)并发性函数式语言被认为是非常适用于处理并发性问题的工具，共享值不需加特殊保护，因为他们不会被更新、并行进程之间不会互相干扰。还有一些困难问题要解决。在将表达式求值分配给不同的处理器这一点上就有隐藏的额外开销：用于求表达式值的数据必须从一个处理器传到另一个处理器，而表达式的计算结果还得被传回来。寻找解决这

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

34、e 语言,Scheme 语言是 Lisp 的一个现代变种、方言，诞生于1975年，由 MIT 的 Gerald J.Sussman and Guy L.Steele Jr.完成。与其他lisp不同的是，scheme是可以编译成机器码的。Scheme语言的规范很短，总共只有50页，甚至连Common Lisp 规范的索引的长度都不到，但是却被称为是现代编程语言王国的皇后。它与以前和以后的 Lisp 实现版本都存在一些差异，但是却易学易用。,Clojure 语言,Clojure 是一种运行在 Java 平台上的 Lisp 方言，它的出现彻底颠覆了我们在Java虚拟机上并发编程的思考方式改变了这一现

35、状。如今，在任何具备 Java 虚拟机的地方，您都可以利用 Lisp 的强大功能 作为Lisp方言，Clojure或许拥有最灵活的编程模型，因此绝不缺乏号召力。与其他Lisp方言不同的是，它不会带那么多括号，还有众多Java库和在各平台上的广泛部署作为坚强后盾,Scala 语言,Scala是一种函数式面向对象语言，它融汇了许多前所未有的特性，而同时又运行于JVM之上。随着开发者对Scala的兴趣日增，以及越来越多的工具支持，无疑Scala语言将成为你手上一件必不可少的工具。Scala为Java系统引入了强大的函数式思想，同时也并未丢弃面向对象编程。回顾历史，我发现C+和Scala有着惊人的相似之处，因为从过程式编程过渡到面向对象编程期间，C+同样起到了举足轻重的作用。当你真正融入Scala社区之后，你就会明白，为什么对于函数式语言程序员来说，Scala是异端邪说，而对于Java开发者来说，Scala是天降福音。,