第5章函数式程序设计语言上课讲义

《第5章函数式程序设计语言上课讲义》由会员分享，可在线阅读，更多相关《第5章函数式程序设计语言上课讲义（50页珍藏版）》请在金锄头文库上搜索。

1、第5章 函数式程序设计语言,过程式程序设计语言由于数据的名值分离， 变量的时空特性导致程序难于查错、难于修改 命令式语言天生带来的三个问题只解决了一半 滥用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 /随调用次数而异，不是数学意义的确定函数。,5.2 演算,演算是符号的逻辑演算系统， 它正好只有这三种机制， 它就成为函数式程序设计语言的模型 演算是一个符号、逻辑系统，其公式就是符号串并按逻辑规则操纵 Church的理论证明， 演算是个完备的系统， 可以表示任何计算函数， 所以任何可用演算仿真实现的语言也是完备的。,演算使函数概念形式化，是涉及变量、函数、

3、函数组合规则的演算。 演算基于最简单的定义函数的思想： 一为函数抽象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 =

4、 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.(zx.y.y)(x.y.x) and=a.b.(ab)F) = a.b.(ab)x.y.y) or =

5、 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)(

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

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

8、注：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)归约约定 顺序:每次

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

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

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

12、) 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

13、. 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上函数有： l

14、et 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

15、:函数式语言都要定义表数据结构， 因为归约 和递归计算在表上很方便。 对整个表操作实 则是隐式迭代。 不用循环控制变量。 对于 顺序值也都用表写个映射函数即可隐式迭代。 部分达到作用3， 其它显式循环要用递归。,4:禁止赋值意味着数据结构一旦创建不得修改,故采用如下函数式语言结构数据修改方式,A,B,C,E,H,G,D,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)； /上面计算不进行是无法打印