第五章函数式程序设计语言.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)。 一切变量、标识符、表达式都是函数或(
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表达式(常量,变量,表达式,条件表达式
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五 函数 程序设计语言
链接地址:https://www.31doc.com/p-3117216.html