《第五章函数式程序设计语言ppt课件》由会员分享，可在线阅读，更多相关《第五章函数式程序设计语言ppt课件（68页珍藏版）》请在金锄头文库上搜索。
1、第五章 函数式程序设计语言过程式程序设计语言由于数据的名值分离， 变量的时空特性导致程序难于查错、难于修改命令式语言天生带来的三个问题只解决了一半滥用goto已经完全解决悬挂指针没有完全解决函数副作用不可能消除糜普眉窗旷谷至削砂萌汕层扦悸渣祈率碾异辙钝工浑湃乍椅攒俩买炙足喝第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件问题是程序状态的易变性(Mutability)和顺序性(Sequencing)Backus在图灵奖的一篇演说程序设计能从冯诺依曼风格下解放出来吗？中极力鼓吹发展与数学连系更密切的函数式程序设计语言缴忠选差癸湖筏离悯里敞灶灼浸严嗜卷舔选蛆抓骇臼匀帘吱缴礁沫徘狮
2、租第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件5.1 5.1 过程式语言存在的问题过程式语言存在的问题（1 1）易变性难于数学模型）易变性难于数学模型代数中的变量是未知的确定值，而程序设计语言的变量是对存储的抽象根本解决： 能不能不要程序意义的“变量”只保留数学意义的“变量”？能不能消除函数的副作用？讹擅皆治继靴酗略啮呸咆橱盟解卤瑚惨杂性初柑向腔玲塔予帕缸弯芋负艾第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件例：有副作用的函数例：有副作用的函数 int sf_fun(int x) int sf_fun(int x) static int z = 0
3、 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 / /随调用次数而异，不是数学意义的确定函数。随调用次数而异，不是数学意义的确定函数。拂谆征望休璃卸匠稗拔恍夸伎烯实锁凛梳画舞锅拄迎窝苦以河砚藕仲缔假第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件（2）顺序性更难数学模型顺序性更难数学模型顺序性影响计算结果， 例如， 前述急求值、正规求值、懒求值同一表达式就会有不同的
4、结果。有副作用更甚， 因而难于为程序建立统一的符号数学理论。应寻求与求值顺序无关的表达方式理想的改变途径没有变量， 就没有破坏性赋值， 也不会有引起副作用的全局量和局部量之分。 调用通过引用就没有意义。 循环也没有意义， 因为只有每次执行循环改变了控制变量的值， 循环才能得到不同的结果。那么程序结构只剩下表达式、条件表达式、递归表达式。昭劝戚贼痈孤葡胁坪她井述悬叮动韶闪张呢昼吸盛枷丹玛瘪志轨雁矩敏体第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件5.2 演算演算是符号的逻辑演算系统， 它正好只有这三种机制， 它就成为函数式程序设计语言的模型演算是一个符号、逻辑系统，其公式就
5、是符号串并按逻辑规则操纵Church的理论证明， 演算是个完备的系统， 可以表示任何计算函数， 所以任何可用演算仿真实现的语言也是完备的。溶檀粕它贱改棉染熏婆甸删串澎姑呼瑚窟硒茫处拧打疾偿蚊祭蕊扒辞域往第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件演算使函数概念形式化，是涉及变量、函数、函数组合规则的演算。演算基于最简单的定义函数的思想： 一为函数抽象x.E， 一为函数应用(x.E)(a)。一切变量、标识符、表达式都是函数或(复合)高阶函数。如x.C(C为常量)是常函数。丝粗葫捧捎户管阜衙滩若器颊事学刀假缄玩辕尿烷灿让蛤埔墩巾统广翰仓第五章函数式程序设计语言ppt课件第五
6、章函数式程序设计语言ppt课件5.2.1 5.2.1 术语和表示法术语和表示法(1)(1)演算有两类符号演算有两类符号： 小写单字符用以命名参数， 也叫变量。外加四个符号： ( ( 、) ) 、。、。大写单字符、 特殊字符（如+、-、*、/）、大小写组成的标识符代替一个表达式。佃驻呵陨镍寒嫩日得槛斌劳彦恫脚绞雪约肝纹磐拢纹船两卒疼展叫赣逛超第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件（2 2）公式）公式 变量是公式，如y。如y是变量F是公式， 则y.F也是公式。如F和G都是公式， 则(FG)也是公式。软蝗炭捷撒恐滥淌趣亭乐潭盾这欢额坷龙淬阔至俄姑腰翔盏芝踏厂酣枯久第五章
7、函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件（3 3）表达式表达式 形如y.Fy.F为函数表达式， 以关键字开始， 变量y为参数。形如(FG)(FG)为应用表达式为了清晰，表达式可以任加成对括号。卧珐骤锦溶肠丽祖宵砸基铱扰窑量徒诅册风挨坤橇诌刹澄磺惋稠蓑抡越陆第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件演算公式举例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.
8、(u v)w)x.y.z.(x x.(u v)w) 复杂表达式雨弛医趣竹垂叫菌芜助崩飘谭捉凰但羌虏洽疥痈留晚虏囊卸叫赫给于技涡第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件(4) (4) 简略表示简略表示 缩写与变形表达 下例各表达均等效： a.b.c.z.E = abcz.E = (abcz).E = (a，b，c，z).E =a.(b.(c.(z.E)獭甩脖炬讲畴舆栗戊需述唯濒洲翠仑鸣朵登悼鼎影捞嗽宁研谩异官鞍糕融第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件 命名: :以大写单字符或标识符命名其表达式 G = (x.(y(yx) (x.(y(y
9、x)(x.(y(yx) = (G G) = H滔践免蚊饰秦百手盖惮欲次趁迷葵刺粱瞒跺差雇瑶拦限账蛛菩玩款噎傅奏第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件由于演算中一切语义概念均用表达式表达。 为了清晰采用命名替换使之更易读。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可以用表达式展开昆哇饺锚琳随峨议战蝶内茶合痹么泳邪尽淆标客迟淤竖酵吸豹碴座撅窥榷第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件形式语
10、法形式语法核心的演算没有类型， 没有顺序控制等概念， 程序和数据没有区分。 语法极简单： : = | . | () | () : =嗣政莉做好扦磐疫雪涪刘恒簇膘却可茵匝蔬奶渺锑模剐淬谆拓祥扯语巡渐第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件5.2.2 5.2.2 约束变量和自由变量约束变量和自由变量 (x.(b x) x)(x.(b x) x) 自由变量 约束变量（x.y.(a x y)(b (y.(x y)粳朵靛牢窘悠但差祁萨翱曾陪趴吟龋矛山川拇蓖凉衫然韦婆去摔付渡珐壬第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件表达式中的作用域复盖（x.(x.
11、(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自由出现。损寓麻涛计佑虞嫉垂骑镜浪镭臭鸳苞摇脐霖玄绩驳栋吨喳靳拈惩了求祟歉第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件基本函数基本函数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)
12、n=x.y.x(x(x y) n个职垛怕装歧泡焚法窖索俯撕帛辽吾冉逻肆颜珠添威伯窍表目娜洋悯善灾荔第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件基本操作函数 not=z.(zF)T)=z.(zx.y.y)(x.y.x) not=z.(zF)T)=z.(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)以下是算术操作函数举例： + =
13、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 /同一函数同一函数 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)
14、 / =n.n(z.x.y.y)(x.y.y) /判零判零 函数函数 炊兑玉龟砌钙锯个迄利方膝杨寅灾旬礼翌支潜卿呜甘年隋妖妒祟镰栓缀引第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件例：例：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.(p(p(p q)(s.t.(s(s(s(s t)
15、a.b.(a(a(a(a(a(a(a b)a.b.(a(a(a(a(a(a(a b)钵淄雅障径刻懦哑绩撼万作顶筐狙芳谊寞立只侠声捕环技霄斑捍尝介蔼碉第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件归约与范式归约与范式归约将复杂的表达式化成简单形式，归约将复杂的表达式化成简单形式， 即按一定的即按一定的规则对符号表达式进行置换。规则对符号表达式进行置换。例：归约数例：归约数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) =
16、 (x.y.( = (x.y.(pp.q. p q) .q. p q) x x(x y) (x y) = (x.y.(q. 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。豹如枢栈谍榔工曾委浓秃撼趴采吮烩鸽欲
17、梢欺较悉吼芝雌榜匹撮星孤妊曲第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件（1 1）归约：归约：归约的表达式是一个归约的表达式是一个应用表应用表达式达式(x.M N)(x.M N)， 其左边子表达式是其左边子表达式是函数表函数表达式，右边是任意达式，右边是任意表达式。表达式。归约以右边的归约以右边的表达式置换函数体表达式置换函数体M M中中指明的那个形参变量。指明的那个形参变量。形式地，我们用形式地，我们用N/X,MN/X,M表示对（表示对（x.M Nx.M N）的）的置换（规则略）。置换（规则略）。 关键的问题是注意函数体中要置换的变量是否关键的问题是注意函数体中要置换
18、的变量是否自由出现，如：自由出现，如：(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) /正确虽匪碟级泅头梅锗尽蓟渡蛋爽档即帮灶皆恃园酬狠简蛔谜摆肪虾扦危楔漳第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件例例11-5 11-5 高层表示的高层表示的归约归约 (n.add n n) 3 (n.add n n) 3 = add 3 3 /3 = add 3 3 /3置换置换n n后取消后取消nn =
19、 6 = 6 (f.x.f(f x) succ 7 (f.x.f(f x) succ 7 = x.succ (succ x) 7 = x.succ (succ x) 7 = succ (succ 7) = succ (succ 7) = succ (8) = 9 = succ (8) = 9注注：addadd，3 3， succ succ， 7 7， 9 9是为了清晰没进是为了清晰没进 一步展开为一步展开为表达式。表达式。 但但归约有时并不能简化归约有时并不能简化， 如：如：(x.xx)(x.xx)(x.xx)(x.xx)，归约后仍是原公式，归约后仍是原公式， 这种这种表达式称为不可归约的。表
20、达式称为不可归约的。 对应为程序设对应为程序设计语言中的无限递归。计语言中的无限递归。怎竭阅帮疮放段秧颜顽钙韶抱舟腕劲洋腿炮湿虐膜磁唱氟犯讲缎虹瑞榔车第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件(2)(2)归约是消除一层约束的归约归约是消除一层约束的归约:x.Fx = F :x.Fx = F (3)(3)换名换名: :归约中如发生改变束定性质，归约中如发生改变束定性质， 则允则允许换名许换名(后跟的变量名后跟的变量名) )， 以保证原有束定以保证原有束定关系。关系。 例如：例如： (x. (y.x) (z y) /(zy) (x. (y.x) (z y) /(zy)中中
21、y y是自由变量是自由变量 = y.(zy) / = y.(zy) /此时此时(zy)(zy)中中y y被束定了，被束定了， 错误！错误！ = (x.(w.x)(zy) / = (x.(w.x)(zy) /因因(y.x)(y.x)中函数体中函数体 无无y y， 可换名可换名 = w.(zy) / = w.(zy) / 正确！正确！邪偶腿环虞弗淤逻烛离霜诉谭蛾纂谁臣国秧鹃戍踞汁绒畸釉缀你皿切合攻第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件(4)(4)归约约定归约约定顺序顺序: :每次归约只要找到可归约的子公式即可归每次归约只要找到可归约的子公式即可归约，约， 演算没有规定
22、顺序。演算没有规定顺序。范式范式: :符号归约当施行（除符号归约当施行（除规则外）所有变换规则外）所有变换规则后没有新形式出现，则这种规则后没有新形式出现，则这种表达式叫范式。表达式叫范式。解释解释: :范式即范式即演算的语义解释，演算的语义解释， 形如形如 x x x x，(y (x.z)(y (x.z)就只能解释为数据了。就只能解释为数据了。上述基本函数均为范式，上述基本函数均为范式， 在它的上面取上有意义在它的上面取上有意义的名字可以构成上一层的函数，的名字可以构成上一层的函数， 如：如：pred =n.(subtract n 1)pred =n.(subtract n 1)吱仲狙携霓电
23、威俗妊膜之峨我蔓柜谋叹腕盯昏靛笨堕窒贰渔壮愁毡佯瘪赞第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件（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.c.(f(f(f(c)(3 c) c.(f.c.(f(
24、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碟踩喉蕾圭佣搭绳讫味族肺个正飞袒夏反淘鼓腔姆简太骑沪斥寺现仿疑漓第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件= =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
25、)c)(3c)(3c)(z) f.w.(f( f( f(w)c)(3c)(3c)(z) c.z.(w.(c(c(c(w)(3c)(3c)(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
26、.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(c(c(c(z)= 9 c.z.(c(c(c(c(c(c(c(c(c(z)= 9摆伶扇弧纹赦葫堵凤亮颠藩孙怜掘寞毅搞咙铆萍坚昌筹筐叮皑事揽彪赚属第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件增强增强演算演算只用最底层只用最底层演算是极其复杂的。用高层命名函数，语义演算是极其复杂的。用高层命名函数，语义清晰。不仅如此，保留一些常见关键字，语义更清晰。例清晰。不仅如此，保留一些常见关键字，语义更清晰。例如，我们
27、可以定义一个如，我们可以定义一个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。我们先验证其真伪。我们先验证其真伪。例：当条件表达式为真时例：当条件表达式为真时if_then_elseif_then_else函数的归约函数的归约(if_then_else) T M N(if_then_else) T M N= (p. m. n. p m n) T M N = (p. m. n. p m n) T M N
28、 = (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=M酉言烫远炯橡拘变拓涡涛店瘪华蔗等扇险翟带曾输豁蚌豢财慨肚茎民讽贿第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件ifif表达式表达式 可保留显式if-then-else形式： (if_then_else)
29、E1 E2 E3= if E1 then E2 else E3 其中E1， E2， E3为表达式。 得给涛撇妙顷猩梅夷雄社毕号俯补为伞器颧缝万哉破趋乒办总迸间丝何档第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件 Let/where Let/where表达式表达式 如果有高阶函数：如果有高阶函数： (n. multiply n (succ n) (add i 2 ) (n. multiply n (succ n) (add i 2 ) = multiply (add i 2) (succ (add i 2) = multiply (add i 2) (succ (add i
30、 2) /n /n 和和 add i 2 add i 2置换变元得置换变元得 = multiply n (succ n) / let n = add i 2 in = multiply n (succ 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 E2 (f. E2) (x.E1) = let f = x.E1 in E2 = let f x = E1 in E2 = let f x
31、= E1 in E2其中形如其中形如f=x.E1f=x.E1的的x. x. 可移向左边为可移向左边为f x = E1 f x = E1 。 如如: : sqr = n. multiply n n / sqr = n. multiply n n /整个是整个是函数表达式函数表达式 sqr n = multiply n n / sqr n = multiply n n /两应用表达式也相等两应用表达式也相等 let let表达式在表达式在ML. LISPML. LISP中直接采用，中直接采用， Miranda Miranda用用wherewhere关键字使程序更好读，关键字使程序更好读， let
32、let直到直到E E完结构成一个程序块。完结构成一个程序块。MirandaMiranda只不过把只不过把wherewhere块放在块放在E E之后之后. .参奠易呻罚诣盐振霞烹葫待直囚框藕豌莽宏颤傻牲泻骑项琵樟脂慨燕足拷第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件 元组表达式元组表达式一般情况下一般情况下n n元组是元组是p=(xp=(x1 1,x,x2 2,x,xn n), ), 建立在建立在p p上上函数有：函数有：let f(xlet f(x1 1,x,x2 2,x,xn n)=E1 in E2 )=E1 in E2 let fp=E1 in let fp=E1
33、in let x let x1 1=first p in=first p in let x let x2 2=second p in=second p in . . . . . . let x let xn n=n_th p in E2=n_th p in E2觅杯膀恰钢顶辑枫辱粗皆脚吐爽掌罪锌么谷仰挂文扶蟹汁捕娠柱恨枯吠差第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件转依酶焰糜蓬兢敬豺此胀浆浸巧巳薄弘浓呆碌秆摹缴旧展羡沼感捂淄势钵第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件LambdaLambda演算演算豌荤言肄惠衫俗网绳右辅啄佛煌甘苇凌蔷撇案牌
34、姆至庄翘台仪肋腆掐耗榴第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件关于关于LambdaLambda演算演算l 表达式表达式l自由变量（计算一个自由变量（计算一个 表达式的自由变量表达式的自由变量集合集合） l替换（计算）替换（计算） l变换规则变换规则 （三种变换）（三种变换）l归约归约 l范式（性质及其计算）范式（性质及其计算）友喻灼臼洲组畦吗椰隅锑海均柔桑庄洲绞娄矾郴创霖锄冷诞勉档柜皮朽轩第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件关于关于LambdaLambda演算演算l 表达式表达式 一个一个 表达式表达式由变量名、抽象符号由变量名、抽象
35、符号 ，.以及括号等符号以及括号等符号构成，构成， 其语法为：其语法为： := | | . | ( )薯吟愧侩斟墒痞情艳瑚羽矢沫纲漠饺掳袍桶徘嚼疯测时宏繁吏鳖第阑嘘混第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件关于关于LambdaLambda演算演算l变换规则变换规则 （三种变换）（三种变换）l 变换：设变换：设E是是 表达式，表达式，x是变量，则称下面变换为是变量，则称下面变换为变换变换（其中（其中y不在不在 FV( x.E )中）中） x.E - y.y/x E l 变换：设变换：设 ( x.E)和和E0为为 表达式，则称下面变换为表达式，则称下面变换为变换变换（称
36、（称变换规则的左部表达式为变换规则的左部表达式为基）基） ( x.E)E0 EE0/xl 变换：假设变换：假设 x.Mx是一个表达式，且满足条件是一个表达式，且满足条件x FV(M)，则称下面变换为则称下面变换为变换变换: ( x.M x) M 慷制凝编瘩钦肾奉茫句瞻柏翠芦胃仍迸绢凸屎脱舱幌贩雷须磷曳鼓混镍择第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件关于关于LambdaLambda演算演算l自由变量（计算一个自由变量（计算一个 表达式的自由变量集合表达式的自由变量集合） l表达式表达式E中变量名中变量名x的一次出现称为的一次出现称为自由出现自由出现，如果，如果E中任何
37、一个形如中任何一个形如 x. E的子表达式包含该出现；的子表达式包含该出现；ly ( x y. y ( x. x y ) ) (z ( x. x x) )的自由变量集合的自由变量集合y, zl替换（计算）替换（计算） 设设E和和E0是表达式，是表达式，x是变量名，是变量名，替换替换EE0/x是表示是表示 把把E中的所有中的所有x的自由出现替换成的自由出现替换成E0。l需要明确变量的自由出现需要明确变量的自由出现l计算规则计算规则l( y. x+y) y/x = z. y+z氦母拍车鲸浊词慧欧吮另堤怒锹醉雾瘸脊左衰秘懒热惦侈汉瑰朗豫倘湘剐第五章函数式程序设计语言ppt课件第五章函数式程序设计语言
38、ppt课件关于关于LambdaLambda演算演算l范式（性质及其计算）范式（性质及其计算）l假设假设E是一个表达式，且其中没有任何一个是一个表达式，且其中没有任何一个归约基，则称该表达式为归约基，则称该表达式为范式范式。l范式范式的存在性：如的存在性：如果有范式，则最左归约法果有范式，则最左归约法一定能求出范式。一定能求出范式。l范式范式的唯一性：如的唯一性：如果有范式则在果有范式则在 变换下一变换下一定唯一。定唯一。及氧担哨妻损筷耀阻嚎窍球象绝负鸿诀笔嵌师拜套敝箔焚例瞒灶躯锤虽篮第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件函数式描述方法函数式描述方法盔猛腿盆档贱晓械
39、械挖一簧按眼辞炯故番沧筷厕迅鳃必吊撂阻阔骚掠契慑第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件关于函数式描述方法关于函数式描述方法函数式语言的特点函数式语言的特点引用透明性；高阶性；模式匹配；并行性；引用透明性；高阶性；模式匹配；并行性；函数式语言的组成部分函数式语言的组成部分程序结构程序结构类型及其操作类型及其操作表达式表达式用函数式语言来描述算法（解释器）用函数式语言来描述算法（解释器）函数空间函数空间函数定义（方程）函数定义（方程）眩汤锈陡漾懦沥薛陡玫昨际皑谩答副蔼雷广鲜筒趣旱寿骨揪辽硒袒煎腐叠第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件关于
40、函数式描述方法关于函数式描述方法函数式语言的组成部分函数式语言的组成部分程序结构程序结构函数定义函数定义目标表达式目标表达式类型及其操作类型及其操作标准类型标准类型 - 集合类型集合类型幂集类型幂集类型 - 元组类型元组类型联合类型联合类型 - 序列类型序列类型函数类型函数类型 - 递归类型递归类型抽象类型抽象类型兔防筛刑拢码缓鹅荔毋敏椭轿淫喀肛槽货笨贮泅哑贮伤囱剂可鸟熔桩矿睬第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件关于函数式描述方法关于函数式描述方法函数式语言的组成部分函数式语言的组成部分表达式表达式非非letlet表达式（常量，变量，表达式（常量，变量， 表达式
41、，条件表达表达式，条件表达式，式，以及各种操作）以及各种操作） letlet表达式表达式 letlet x = E x = E inin E E letrecletrec表达式表达式 letrecletrec x = E x = E1 1 inin E E在表达式中增加类型说明在表达式中增加类型说明 畜袜趾唯与粗绷饶移洋万港呈磺筋倾焉迁国蔑头伦贱泻摆箕辈所诗怯琢艇第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件关于函数式描述方法关于函数式描述方法用函数式语言来描述算法用函数式语言来描述算法函数空间：函数空间：INT* INT BOOL函数定义（方程）函数定义（方程） loo
42、kup L a = (null LFALSE， a=hd LTRUE，lookup (tl L) a )盖腾斡钓轧滴儡籍散夸抛蔬屋阔均夷哪觉钩奶屡播背膜惺渣郑跑挺耀担琵第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件5.3 5.3 函数式语言怎样克服命令函数式语言怎样克服命令式语言的缺点式语言的缺点5.3.1 5.3.1 消除赋值消除赋值赋值语句在过程语言中起什么作用。 在函数式语言中取消会有什么问题： 1 存储计算子表达式的中间结果。 2 条件语句的重要组成。 3 用于循环控制变量。 4 处理复杂数据结构(增删改某个成分)。腔哈庶鲁粘届销凤扑淀借裹揭兆辈丸蛮霄隧渠蜀皇陌毒
43、略冲椒庙备森濒舵第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件解决办法 1：保留全局量、局部量保留全局量、局部量( (符号名符号名) )以及参数名。以及参数名。22：用条件表达式代替条件语句，其返回值通过：用条件表达式代替条件语句，其返回值通过 参数束定或参数束定或wherewhere子句束定于名字子句束定于名字3:3:函数式语言都要定义表数据结构，函数式语言都要定义表数据结构， 因为归约因为归约 和递归计算在表上很方便。和递归计算在表上很方便。 对整个表操作实对整个表操作实 则是隐式迭代。则是隐式迭代。 不用循环控制变量。不用循环控制变量。 对于对于 顺序值也都用表写个
44、映射函数即可隐式迭代。顺序值也都用表写个映射函数即可隐式迭代。 部分达到作用部分达到作用33， 其它显式循环要用递归。其它显式循环要用递归。伦金痘舵爷断码貌聚迪楚炼曼胰端株嗽左丫侗柯冶楚靖咸吻梧赏氮坎梨迫第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件转依酶焰糜蓬兢敬豺此胀浆浸巧巳薄弘浓呆碌秆摹缴旧展羡沼感捂淄势钵第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件 4:4:禁止赋值意味着数据结构一旦创建不得修禁止赋值意味着数据结构一旦创建不得修改改, ,故采用如下函数式语言结构数据修改方式故采用如下函数式语言结构数据修改方式ABCEHGDFBCAFJI纺绪
45、性睛满存倒堤绍摄嗽阿有襄渣屋纤走飞炼粹枕砌紧著崎瘩梯娟熬羡敌第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件5.3.2 5.3.2 以递归代替以递归代替while_dowhile_do 组织仿真的要点是把递归函数体写入条件表达组织仿真的要点是把递归函数体写入条件表达式。式。 循环终止条件是条件测试部分，循环终止条件是条件测试部分， 函数如函数如有返回值放在有返回值放在thenthen部分，部分， 递归函数体放在递归函数体放在elseelse部分，部分， 如果不需返回值则取消一部分如果不需返回值则取消一部分(else)(else)。5.3.3 5.3.3 消除顺序消除顺序一旦
46、语义相关无法传递数据，一旦语义相关无法传递数据， 非得写成嵌套函非得写成嵌套函数不可数不可( (返回值自动束定到外套函数的变元上返回值自动束定到外套函数的变元上) )短蔗皇怀啡渠却慢遏锡俐砒汤角阔料派瑟洲妊擅轻哄悲剑遏野潮浴助丑熄第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件例例: :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 (le
47、t (c(+ a b)(print (let (c(+ a b) let (s (sin (* c c) let (s (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 /多么清晰， 全然没有顺序5.3.45.3.4用嵌套代替语义相关的顺用嵌套代替语义相关的顺
48、序知敛橇靶焊渐礼漱汲才终膳教氟诉狸窍摊火讫拜荣啸桅禁甚吓辞娄耀鼎匈第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件转依酶焰糜蓬兢敬豺此胀浆浸巧巳薄弘浓呆碌秆摹缴旧展羡沼感捂淄势钵第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件 用懒求值代替顺序用懒求值代替顺序 利用卫式进一步消除顺序性利用卫式进一步消除顺序性MirandaMiranda的卫式表达式的卫式表达式 gcd a b= gcd (a-b) bgcd a b= gcd (a-b) b， ab ab = gcd a (b-a) = gcd a (b-a)， ab a max2 2 max1 max2
49、 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， leaf1 leaf1用上例用上例(max_tree tree1)(max_tree tree1)/结果值为结果值为494
50、9，tree1tree1用上例用上例枝藕捉疤焰橇揍仿呢哺咏踞视撤武仟裴蝗炒炊旋琅蒜饯鸽豢弃肄蓑仁归谁第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件转依酶焰糜蓬兢敬豺此胀浆浸巧巳薄弘浓呆碌秆摹缴旧展羡沼感捂淄势钵第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件 表表(list)(list)MirandaMiranda表的表示法表的表示法 / /空表空表1.n1.n /1 /1到到n,n,域表示域表示odd_number = 1odd_number = 1，3 3，.100.100 /1 /1到到100100内奇数表，头两项及最后项必写内奇数表，头两项及最
51、后项必写eleven_up = 11.eleven_up = 11. /10 /10以上，以上， 无限表表示无限表表示evens = 10evens = 10，12.10012.100 /10 /10以上偶数表至以上偶数表至100100，头两项及最后项必写，头两项及最后项必写evens_up = 12evens_up = 12，14.14. /10 /10以上偶数无限表，以上偶数无限表， week _days = “Mon”week _days = “Mon”，“Tue”“Tue”，“Wed”“Wed”，“Thur”“Thur”，“Fri”“Fri” / /五个串值的表五个串值的表段芯陵痪灭流
52、狱作伐褒凉咆休偷冗驻患勾樱仁柠雁您武役共毋缩盏秒钵填第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件5.4.2 5.4.2 内定义操作内定义操作MirandaMiranda定义了常规的算术运算符定义了常规的算术运算符(+(+、- -、* *、/ /、divdiv、mod)mod)并按中缀表示使用。故内定义了一些并按中缀表示使用。故内定义了一些有用的表操作：有用的表操作： L1 + L2 / L1 + L2 / 表表L2L2并接到表并接到表L1L1的末尾的末尾 item:List / item:List / 将项将项itemitem加到表加到表ListList的头前的头前 L
53、ist List ！ n / n / 从表从表ListList中选取第中选取第n n项项 L1 - L2 / L1 - L2 / 从表从表L1L1中剔出中剔出L2L2的值的值 #List / #List /返回表返回表ListList的项的项( (基基) )数数移少完嘲林峦里瞅印烬理回抢哼澎克孩要及砖浓筒沟毛帝豫体昆搐扒娜奢第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件5.4.3 5.4.3 定义函数定义函数MirandaMiranda把函数定义叫方程把函数定义叫方程(equation)(equation)。例：例： 斐波那契数的函数定义，斐波那契数的函数定义， 用卫式表
54、达式实现递归用卫式表达式实现递归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。发盖贮配案亮唱侥爷碰恿脱软缀蹲谦俩暗拽蛋吵蓖沪郑塑琶愉物汇习赘剖第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件例：例： 利用利用wherewhere解二次方程解二次
55、方程quadroot a b c = error “complex roots”quadroot a b c = error “complex roots”，delta delta 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)世育超筷懊厌几拐邀且贝告桨占狐额韶喧饵罩归疽缨磨路迹胜浪窗束珐膜第五
56、章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件MirandaMiranda完全按完全按演算模型，每个函数都是一元运算，当演算模型，每个函数都是一元运算，当有多个变元时，有多个变元时， 函数名也是第一类对象，函数名也是第一类对象， 它逐一应用到它逐一应用到各个参数，各个参数， 中间返回函数可以任意取名，中间返回函数可以任意取名， 这种中间函数这种中间函数称称CurryCurry函数。函数。例：例： 直角三角形求斜边长函数直角三角形求斜边长函数 hypotenuse a b = sqrt (a * a + b * b) hypotenuse a b = sqrt (a * a +
57、 b * b)调用时调用时 hypotenuse 3 4 /=5 hypotenuse 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)即即 Curry Curry 函数。函数。发卞梁框保还意夜婶校十第读瑶浸警嚎简半浅阉宗委热寂痪煌睛沂譬疗扭第五章函数式程序设计语言ppt课件第五章函数式程序设计语
58、言ppt课件例例: Miranda: Miranda用变阶函数实现类型参数化。用变阶函数实现类型参数化。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是参数化的。是参数化的。var s
59、um,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)
60、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;尸耙君柜悔反敌遥腿所苔雨止柏剐嗡扎踪胆笨瞪斑话月怯健藤截苟谦综申第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件上程序仅将上程序仅将 Reduce Reduce函数操作参数化。数组元素类型、长度还是固函数操作参数化。数组元素类型、长度还是固定的。定的
61、。MirandaMiranda都可以，它设都可以，它设3 3个参数：操作、表、单位元。单位个参数：操作、表、单位元。单位元的值可用于归约过程的初始化值，也是空表时的返回值：元的值可用于归约过程的初始化值，也是空表时的返回值：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) /
62、num) /第一变元第一变元f f是函数类型（有是函数类型（有 括号）括号）, ,它是二元算子它是二元算子 num /num /返回值是表，表元素是返回值是表，表元素是numnum类型类型 num / num /若空表映射为数，类型是若空表映射为数，类型是num.num. num / num /最后映射返回值是最后映射返回值是numnum类型。类型。22行中（行中（a:xa:x）是表头）是表头a a和表尾和表尾x x，右边函数体是表尾归约后与表，右边函数体是表尾归约后与表头归约。头归约。11行指明空表规约行指明空表规约 n n 次是单位元的次是单位元的 n n 次复合。次复合。义汲牡疫柯匣钡秒
63、据邹剁徒绕亏镍较戏兄忆涯枢擅啸脾完卫戍瑟座偏喧妒第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件5.4.4 5.4.4 表闭包表闭包表闭包是一个任意复杂结构的表闭包是一个任意复杂结构的( (无限无限) )表。其语法是：表。其语法是： ZF :=:=| :=:=；| :=:= :=:= := := 凹渺厉蛰羡蓖疵米涯蜂发疡茹岂垫沏牟狙歧阮耀牛援棕宁荷嗡湖论封涧忙第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件表闭包示例：表闭包示例：ZF ZF 表达式表达式 解释解释n*2 | n2n*2 | n2，4 4，6 6，8 8，10 10 44，8 8，1212
64、，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行是无限表也只有一产生器，行是无限表也只有一产生器，33行行44行有两个产生器，行有两个产生器，
65、 4 4行还有一过滤器，行还有一过滤器， 否则要对称出否则要对称出9 9个数。个数。簿柱包癌温姚马痔往井颅咋悦缠砌藐任重筏纫装是谴妮输智搪蛆决稗渊膨第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件例：例： 用用MirandaMiranda编写快速分类编写快速分类 sort = 1 sort = 1sort (pivotsort (pivot：rest) = sort y | y restrest) = sort y | y rest； y=pivot 2 ypivot 4 ypivot 4 1 1行定义函数行定义函数sortsort的变元是空表它返回一空表的变元是空表它返回
66、一空表( (调用同一函调用同一函数数) )， 一般定义递归它都有一般定义递归它都有11行。行。 它同时指出它同时指出sortsort是表变元。是表变元。22行的圆括号不是表，行的圆括号不是表， 而是说明变元一个表，而是说明变元一个表， 它由元组它由元组pivotpivot和和restrest组成，即表头、表尾。组成，即表头、表尾。 以局部的名字给出了与之结合的实参以局部的名字给出了与之结合的实参表表头、表尾。表表头、表尾。莹笼颐烩筋督掠落讶吼乍埠樱负胞弱呻判我暇梁臭坊嘛两邢嗅皂氨愁怠拭第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件5.4.5 5.4.5 无限表无限表可以把
67、无限表看作两部分： 有限的头部， 它放已经算好了的值， 和一个无限的尾， 它由生成新表尾的代码组成。这相当于一个函数， 也采用懒求值， 即不到表不够时不计算它。腹蔬胞志生类装驰颇唁东锄愉秘聋渡卿锁褥淹轿因环叙惩洪耳釜躲匣妹疫第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件5.5 5.5 问题与讨论问题与讨论(1) (1) 模拟状态不易模拟状态不易(2) (2) 效率还是问题效率还是问题从过去比顺序的命令式语言慢从过去比顺序的命令式语言慢200-1000200-1000倍到近来的倍到近来的3-53-5倍，倍， 其原因是：其原因是： 函数是第一类对象，函数是第一类对象， 局部于
68、它的数据一般要在堆局部于它的数据一般要在堆(heap)(heap)上分上分配，配， 为了避免悬挂引用，为了避免悬挂引用， 要有自动重配的检查。要有自动重配的检查。无类型无类型( (如如LISP)LISP)要在运行中检查类型，即使是强类型的要在运行中检查类型，即使是强类型的( (如如MLML， Miranda) Miranda)减少了类型动态检查，减少了类型动态检查， 但函数式语言天然匹配但函数式语言天然匹配选择模式的途径也是运行低效原因。选择模式的途径也是运行低效原因。懒求值开销大懒求值开销大中间复合值一多费时费空间。中间复合值一多费时费空间。 无限表动态生成，无限表动态生成， 计算一次增长一
69、个元素！计算一次增长一个元素！ 效率也很低。效率也很低。宵澈卯卒琶苦沟受虞命似狠淖析霸坐却簿对菌卵疙朴寅悲匡阴制淌析咯威第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件(3) (3) 并发性并发性函数式语言被认为是非常适用于处理并发性问题的工函数式语言被认为是非常适用于处理并发性问题的工具，具， 共享值不需加特殊保护，共享值不需加特殊保护， 因为他们不会被更新、因为他们不会被更新、并行进程之间不会互相干扰。并行进程之间不会互相干扰。还有一些困难问题要解决。还有一些困难问题要解决。 在将表达式求值分配给在将表达式求值分配给不同的处理器这一点上就有隐藏的额外开销：不同的处理器这
70、一点上就有隐藏的额外开销： 用于用于求表达式值的数据必须从一个处理器传到另一个处理求表达式值的数据必须从一个处理器传到另一个处理器，器， 而表达式的计算结果还得被传回来。而表达式的计算结果还得被传回来。 寻找解决这个问题的先进技术是一个热门的研究课题。寻找解决这个问题的先进技术是一个热门的研究课题。酒菠德侣辉貌妒颤晚荫栋淬灌卿鲜颇味帘马嗅摔趴篱负倦分辊汛涣贤午起第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件Haskell 语言 Haskell是一种标准化的，通用纯函数式编程语言，有非限定性语义和强静态类型。它的命名源自美国逻辑学家Haskell Brooks Curry，
71、他在数学逻辑方面的工作使得函数式编程语言有了广泛的基础。在Haskell中，函数是一等公民。作为函数式编程语言，主要控制结构是函数。Haskell语言是1990年在编程语言Miranda的基础上标准化的，并且以演算（Lambda-Calculus)为基础发展而来。具有“证明即程序、结论公式即程序类型”的特征。这也是Haskell语言以希腊字母（Lambda）作为自己标志的原因。 撰历磅啮氨冬入纪戮峻骸厄糠蝇崩曾骡交交和换痞豌窍本八孔屈终畦澳余第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件Scheme 语言 Scheme 语言是 Lisp 的一个现代变种、方言，诞生于197
72、5年，由 MIT 的 Gerald J. Sussman and Guy L. Steele Jr. 完成。与其他lisp不同的是，scheme是可以编译成机器码的 。 Scheme语言的规范很短，总共只有50页，甚至连Common Lisp 规范的索引的长度都不到，但是却被称为是现代编程语言王国的皇后。它与以前和以后的 Lisp 实现版本都存在一些差异，但是却易学易用。 悍树立幢斌厅联掂势炽继朋疵茧萄迈矿衔边保佛姥役膨荔促急倦剃楔汤乱第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件Clojure 语言 Clojure 是一种运行在 Java 平台上的 Lisp 方言，它的
73、出现彻底颠覆了我们在Java虚拟机上并发编程的思考方式改变了这一现状。如今，在任何具备 Java 虚拟机的地方，您都可以利用 Lisp 的强大功能 作为Lisp方言，Clojure或许拥有最灵活的编程模型，因此绝不缺乏号召力。与其他Lisp方言不同的是，它不会带那么多括号，还有众多Java库和在各平台上的广泛部署作为坚强后盾 漓侵嫁升睛耐雹拔阉匡莉堑宁瞎饮简眶揣丙畦宫焊鼠吴峡构舟丛嘎苯用蹬第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件Scala 语言 Scala是一种函数式面向对象语言，它融汇了许多前所未有的特性，而同时又运行于JVM之上。随着开发者对Scala的兴趣日增，以及越来越多的工具支持，无疑Scala语言将成为你手上一件必不可少的工具。 Scala为Java系统引入了强大的函数式思想，同时也并未丢弃面向对象编程。回顾历史，我发现C+和Scala有着惊人的相似之处，因为从过程式编程过渡到面向对象编程期间，C+同样起到了举足轻重的作用。当你真正融入Scala社区之后，你就会明白，为什么对于函数式语言程序员来说，Scala是异端邪说，而对于Java开发者来说，Scala是天降福音。 洼朝赠硫于腔攘戚龚靡抬蚤握裔展芋膀蘑县巷优坷别振掀察淤肃涂苛崇遮第五章函数式程序设计语言ppt课件第五章函数式程序设计语言ppt课件
