《第五章函数式程序设计语言.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)。 一切变量、标识符、表达式都是函数或(
4、复合)高阶函数。如x.C(C为常量)是常函数。,5.2.1 术语和表示法,(1)演算有两类符号： 小写单字符用以命名参数， 也叫变量。 外加四个符号： ( 、) 、。、。 大写单字符、 特殊字符（如+、-、*、/）、大小写组成的标识符代替一个表达式。,（2）公式 变量是公式，如y。 如y是变量F是公式， 则y.F也是公式。 如F和G都是公式， 则(FG)也是公式。,（3）表达式 形如y.F为函数表达式， 以关键字开始， 变量y为参数。 形如(FG)为应用表达式 为了清晰，表达式可以任加成对括号。,演算公式举例,x 变量、公式、表达式。 (x.(y)x) 函数， 体内嵌入应用。 (z.(y(z.
5、x) 函数， 体内嵌入应用， 再次嵌入函数。 (z.(z y)x) 应用表达式。 x.y.z.(x x.(u v)w) 复杂表达式,(4) 简略表示,缩写与变形表达 下例各表达均等效： 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 /数
6、1 2 = x.y.x(x y) /数2 zerop = n.n(x.F)T /判零函数 注：zerop中的F、T可以用表达式展开,形式语法,核心的演算没有类型， 没有顺序控制等概念， 程序和数据没有区分。 语法极简单： : = | . | () | () : =,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中自由
7、，在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.(zx.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) * =
8、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.
9、(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）的置换（规则略）。 关键的问题是注意函数体中要置换的
10、变量是否自由出现，如： (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是为了清晰没进 一步展开为表达式。,但归约有时并不能简化， 如：(x.xx)(x.xx)，归约后仍是原公式， 这种表达式称为不可归约的。 对应为程序设计语言中的无限递归
11、。,(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)就只
12、能解释为数据了。 上述基本函数均为范式， 在它的上面取上有意义的名字可以构成上一层的函数， 如：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)
13、c.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.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_e
14、lse为名的函数：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 e
15、lse 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 = E
16、1 。 如: 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,Lam
17、bda演算,关于Lambda演算,表达式 自由变量（计算一个表达式的自由变量集合） 替换（计算） 变换规则 （三种变换） 归约 范式（性质及其计算）,关于Lambda演算,表达式 一个表达式由变量名、抽象符号，.以及括号等符号构成， 其语法为： := | | . | ( ),关于Lambda演算,变换规则 （三种变换） 变换：设E是表达式，x是变量，则称下面变换为变换（其中y不在 FV( x.E )中） x.E - y.y/x E 变换：设 (x.E)和E0为表达式，则称下面变换为变换（称变换规则的左部表达式为基） (x.E)E0 EE0/x 变换：假设x.Mx是一个表达式，且满足条件xFV(
18、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是变量名，替换EE0/x是表示 把E中的所有x的自由出现替换成E0。 需要明确变量的自由出现 计算规则 ( y. x+y) y/x = z. y+z,关于Lambda演算,范式（性质及其计算） 假设E是一个表达式，且其中没有任何一个归约基，则称该表达式为范式。 范
19、式的存在性：如果有范式，则最左归约法一定能求出范式。 范式的唯一性：如果有范式则在变换下一定唯一。,函数式描述方法,关于函数式描述方法,函数式语言的特点 引用透明性；高阶性；模式匹配；并行性； 函数式语言的组成部分 程序结构 类型及其操作 表达式 用函数式语言来描述算法（解释器） 函数空间 函数定义（方程）,关于函数式描述方法,函数式语言的组成部分 程序结构 函数定义 目标表达式 类型及其操作 标准类型 - 集合类型 幂集类型 - 元组类型 联合类型 - 序列类型 函数类型 - 递归类型 抽象类型,关于函数式描述方法,函数式语言的组成部分 表达式 非let表达式（常量，变量，表达式，条件表达式
20、，以及各种操作） 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 消除赋值 赋值语句在过程语言中起什么作用。 在函数式 语言中取消会有什么问题： 1 存储计算子表达式的中间结果。 2 条件语句的重要组成。 3 用于循环控制变量。 4 处理复杂数据结构(增
21、删改某个成分)。,解决办法,1：保留全局量、局部量(符号名)以及参数名。 2：用条件表达式代替条件语句，其返回值通过 参数束定或where子句束定于名字 3:函数式语言都要定义表数据结构， 因为归约 和递归计算在表上很方便。 对整个表操作实 则是隐式迭代。 不用循环控制变量。 对于 顺序值也都用表写个映射函数即可隐式迭代。 部分达到作用3， 其它显式循环要用递归。,4:禁止赋值意味着数据结构一旦创建不得修改,故采用如下函数式语言结构数据修改方式,A,B,C,E,H,G,D,F,B,C,A,F,J,I,5.3.2 以递归代替while_do,组织仿真的要点是把递归函数体写入条件表达式。 循环终止
22、条件是条件测试部分， 函数如有返回值放在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 ) /仍有顺序但在一个 /表达式内。自左至右处理即隐式顺序。 Miranda
23、实现： Answere a b = (a b c s ) where s= sin (c* c) c= a+b /多么清晰， 全然没有顺序,5.3.4用嵌套代替语义相关的顺序,用懒求值代替顺序,利用卫式进一步消除顺序性,Miranda的卫式表达式 gcd a b= gcd (a-b) b， ab = gcd a (b-a)， ab = 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.
24、5 输出问题,利用数据对象内部原有的顺序 结构对象是第一类对象， 语言支持的任何形式(交互、非交互)的输出都可以用在表和元组上。Miranda就是用无限表动态实现的 无限表尾不表示任何值， 它是函数对象， 每当调用到它时， 它按规定计算表头值， 并构造 一新的函数对象放在表尾， 以便再展其它项， 它就是新的无限表尾的头， 这个过程一直延续到需要的表长已达到。 输入输出流就是一个值的无限表， 每次处理输入流一个新值就附在表尾并为程序访问。同样， 也用无限表模型输出流。,5.4 函数式语言Miranda,简单的Miranda手本 Miranda 演算 sq n = n * n sq = n. *
25、n n z=sq x/sq y z=/(sq x)(sq y),Miranda的基本类型有字符(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行执行后,
26、第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用上例,表(list),Miranda表的表示法 /
27、空表 1n /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的
28、末尾 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) n1 卫式表达式的值集应复盖所有的可能， 否则用otherwise。,例： 利用where解二次方程 quadroot a b c = error
29、 “complex roots”，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
30、 Miranda则写作为： f 4 where f = hypotenuse 3 /f=sqrt(9 + b*b)即 Curry 函数。,例: Miranda用变阶函数实现类型参数化。 type row_type=array09 of Integer; function Reduce(functionf(x:Integer,y:Integer):Integer; ar:row_type):Integer;/函数f是参数化的。 var sum,k:Integer; begin sum:=ar0; for k=1 to 9 do sum:=f(sum,ark); reduce:=sum end;
31、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函数操作参数化。数组元素类型、长度还是固定的。Miranda都可以，它设3个参数：操作、表、单位元。单位元的值可用于归约过程的初始化值，也是空表时的返回值： reduce f n = n 1 reduce f(a : x) n = f a (reduce x
32、n) 2 为了理解上不引起岐意，写明reduce的类型： reduce:(numnumnum) /第一变元f是函数类型（有 括号）,它是二元算子 num /返回值是表，表元素是num类型 num /若空表映射为数，类型是num. num /最后映射返回值是num类型。 2行中（a:x）是表头a和表尾x，右边函数体是表尾归约后与表头归约。1行指明空表规约 n 次是单位元的 n 次复合。,5.4.4 表闭包,表闭包是一个任意复杂结构的(无限)表。其语法是： :=| :=；| := := := ,表闭包示例： ZF 表达式 解释 n*2 | n2，4，6，8，10 4，8，12，16，20 1 n*
33、n | n 1，2，. 1，4，9，. 2 x+y | x 13； y3，7 4，5，6，8，9，10 3 x*y | x 13； y13；x=y1，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； ypivot 4 1行定义函数sort的变元是空表它返回一空表(调用同一函数)， 一般定义递归它都有1行。 它同时指出sort是表变元。2
34、行的圆括号不是表， 而是说明变元一个表， 它由元组pivot和rest组成，即表头、表尾。 以局部的名字给出了与之结合的实参表表头、表尾。,5.4.5 无限表,可以把无限表看作两部分： 有限的头部， 它放已经算好了的值， 和一个无限的尾， 它由生成新表尾的代码组成。这相当于一个函数， 也采用懒求值， 即不到表不够时不计算它。,5.5 问题与讨论,(1) 模拟状态不易 (2) 效率还是问题 从过去比顺序的命令式语言慢200-1000倍到近来的3-5倍， 其原因是： 函数是第一类对象， 局部于它的数据一般要在堆(heap)上分配， 为了避免悬挂引用， 要有自动重配的检查。 无类型(如LISP)要在
35、运行中检查类型，即使是强类型的(如ML， Miranda)减少了类型动态检查， 但函数式语言天然匹配选择模式的途径也是运行低效原因。 懒求值开销大 中间复合值一多费时费空间。 无限表动态生成， 计算一次增长一个元素！ 效率也很低。,(3) 并发性 函数式语言被认为是非常适用于处理并发性问题的工具， 共享值不需加特殊保护， 因为他们不会被更新、并行进程之间不会互相干扰。 还有一些困难问题要解决。 在将表达式求值分配给不同的处理器这一点上就有隐藏的额外开销： 用于求表达式值的数据必须从一个处理器传到另一个处理器， 而表达式的计算结果还得被传回来。 寻找解决这个问题的先进技术是一个热门的研究课题。,
36、Haskell 语言,Haskell是一种标准化的，通用纯函数式编程语言，有非限定性语义和强静态类型。它的命名源自美国逻辑学家Haskell Brooks Curry，他在数学逻辑方面的工作使得函数式编程语言有了广泛的基础。在Haskell中，函数是一等公民。作为函数式编程语言，主要控制结构是函数。Haskell语言是1990年在编程语言Miranda的基础上标准化的，并且以演算（Lambda-Calculus)为基础发展而来。具有“证明即程序、结论公式即程序类型”的特征。这也是Haskell语言以希腊字母（Lambda）作为自己标志的原因。,Scheme 语言,Scheme 语言是 Lisp
37、 的一个现代变种、方言，诞生于1975年，由 MIT 的 Gerald J. Sussman and Guy L. Steele Jr. 完成。与其他lisp不同的是，scheme是可以编译成机器码的 。 Scheme语言的规范很短，总共只有50页，甚至连Common Lisp 规范的索引的长度都不到，但是却被称为是现代编程语言王国的皇后。它与以前和以后的 Lisp 实现版本都存在一些差异，但是却易学易用。,Clojure 语言,Clojure 是一种运行在 Java 平台上的 Lisp 方言，它的出现彻底颠覆了我们在Java虚拟机上并发编程的思考方式改变了这一现状。如今，在任何具备 Java
38、 虚拟机的地方，您都可以利用 Lisp 的强大功能 作为Lisp方言，Clojure或许拥有最灵活的编程模型，因此绝不缺乏号召力。与其他Lisp方言不同的是，它不会带那么多括号，还有众多Java库和在各平台上的广泛部署作为坚强后盾,Scala 语言,Scala是一种函数式面向对象语言，它融汇了许多前所未有的特性，而同时又运行于JVM之上。随着开发者对Scala的兴趣日增，以及越来越多的工具支持，无疑Scala语言将成为你手上一件必不可少的工具。 Scala为Java系统引入了强大的函数式思想，同时也并未丢弃面向对象编程。回顾历史，我发现C+和Scala有着惊人的相似之处，因为从过程式编程过渡到面向对象编程期间，C+同样起到了举足轻重的作用。当你真正融入Scala社区之后，你就会明白，为什么对于函数式语言程序员来说，Scala是异端邪说，而对于Java开发者来说，Scala是天降福音。,