研究生课程_程序语言设计原理教程_第11章.ppt

第11章函数式程序设计语言,过程式程序设计语言由于数据的名值分离，变量的时空特性导致程序难于查错、难于修改命令式语言天生带来的三个问题只解决了一半滥用goto已经完全解决悬挂指针没有完全解决函数副作用不可能消除,问题是程序状态的易变性(Mutability)和顺序性(Sequencing)Backus在图灵奖的一篇演说程序设计能从冯诺依曼风格下解放出来吗？中极力鼓吹发展与数学连系更密切的函数式程序设计语言,11.1过程式语言存在的问题,（1）易变性难于数学模型代数中的变量是未知的确定值，而程序设计语言的变量是对存储的抽象根本解决：能不能不要程序意义的“变量”只保留数学意义的“变量”？能不能消除函数的副作用？,例：有副作用的函数intsf_fun(intx)staticintz=0；/第一次装入赋初值returnx+(z+)；sf_fun(3)=3|4|5|6|7/随调用次数而异，不是数学意义的确定函数。,（2）顺序性更难数学模型,顺序性影响计算结果，例如，前述急求值、正规求值、懒求值同一表达式就会有不同的结果。有副作用更甚，因而难于为程序建立统一的符号数学理论。应寻求与求值顺序无关的表达方式理想的改变途径没有变量，就没有破坏性赋值，也不会有引起副作用的全局量和局部量之分。调用通过引用就没有意义。循环也没有意义，因为只有每次执行循环改变了控制变量的值，循环才能得到不同的结果。那么程序结构只剩下表达式、条件表达式、递归表达式。,演算,演算是符号的逻辑演算系统，它正好只有这三种机制，它就成为函数式程序设计语言的模型演算是一个符号、逻辑系统，其公式就是符号串并按逻辑规则操纵Church的理论证明，演算是个完备的系统，可以表示任何计算函数，所以任何可用演算仿真实现的语言也是完备的。,演算使函数概念形式化，是涉及变量、函数、函数组合规则的演算。演算基于最简单的定义函数的思想：一为函数抽象x.E，一为函数应用(x.E)(a)。一切变量、标识符、表达式都是函数或(复合)高阶函数。如x.C(C为常量)是常函数。,11.2.1术语和表示法,(1)演算有两类符号：小写单字符用以命名参数，也叫变量。外加四个符号：(、)、。、。大写单字符、特殊字符（如+、-、*、/）、大小写组成的标识符代替一个表达式。,（2）公式变量是公式，如y。如y是变量F是公式，则y.F也是公式。如F和G都是公式，则(FG)也是公式。,（3）表达式形如y.F为函数表达式，以关键字开始，变量y为参数。形如(FG)为应用表达式为了清晰，表达式可以任加成对括号。,演算公式举例,x变量、公式、表达式。(x.(y)x)函数，体内嵌入应用。(z.(y(z.x)函数，体内嵌入应用，再次嵌入函数。(z.(zy)x)应用表达式。x.y.z.(xx.(uv)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)=(GG)=H,由于演算中一切语义概念均用表达式表达。为了清晰采用命名替换使之更易读。T=x.y.x/逻辑真值F=x.y.y/逻辑假值1=x.y.xy/数12=x.y.x(xy)/数2zerop=n.n(x.F)T/判零函数注：zerop中的F、T可以用表达式展开,(5)形式语法,核心的演算没有类型，没有顺序控制等概念，程序和数据没有区分。语法极简单：:=|.|()|():=,11.2.2约束变量和自由变量,(x.(bx)x)自由变量约束变量（x.y.(axy)(b(y.(xy),表达式中的作用域复盖,（x.(x.(xa)(xb)(xc)）,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自由出现。,11.2.3基本函数,TRUE和FALSE的表达式T=x.y.xF=x.y.y整数的表达式：0=x.y.y1=x.y.xy2=x.y.x(xy)n=x.y.x(x(xy)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.(ax.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(xy)/后继函数zerop=n.n(x.F)T=n.n(z.x.y.y)(x.y.y)/判零函数,例：3+4就写add34，add3返回“加3函数”应用到4上当然就是7。写全了是：（x.y.a.b.(xa)(ya)b)）(p.q.(p(p(pq)(s.t.(s(s(s(st)a.b.(a(a(a(a(a(a(ab),11.2.4归约与范式,归约将复杂的表达式化成简单形式，即按一定的规则对符号表达式进行置换。例：归约数1的后继(succ1)=(n.(x.y.nx(xy)1)=(x.y.1x(xy)=(x.y.(p.q.pq)x(xy)=(x.y.(q.xq)(xy)=(x.y.x(xy)=2注：succ和1都是函数(1是常函数)，第一步是n束定的n被1置换。展开后，x置换p，(xy)置换q，最后一行不能再置换了，它就是范式，语义为2。,（1）归约：归约的表达式是一个应用表达式(x.MN)，其左边子表达式是函数表达式，右边是任意表达式。归约以右边的表达式置换函数体M中指明的那个形参变量。形式地，我们用N/X,M表示对（x.MN）的置换（规则略）。关键的问题是注意函数体中要置换的变量是否自由出现，如：(x.x(x.(xy)(zz)=(zz)(x.(zz)y)/错误，第二x个非自由出现。=(zz)(x.(xy)/正确,例11-5高层表示的归约,(n.addnn)3=add33/3置换n后取消n=6(f.x.f(fx)succ7=x.succ(succx)7=succ(succ7)=succ(8)=9注：add，3，succ，7，9是为了清晰没进一步展开为表达式。,但归约有时并不能简化，如：(x.xx)(x.xx)，归约后仍是原公式，这种表达式称为不可归约的。对应为程序设计语言中的无限递归。,(2)归约是消除一层约束的归约:x.Fx=F(3)换名:归约中如发生改变束定性质，则允许换名(后跟的变量名)，以保证原有束定关系。例如：(x.(y.x)(zy)/(zy)中y是自由变量=y.(zy)/此时(zy)中y被束定了，错误！=(x.(w.x)(zy)/因(y.x)中函数体无y，可换名=w.(zy)/正确！,(4)归约约定顺序:每次归约只要找到可归约的子公式即可归约，演算没有规定顺序。范式:符号归约当施行（除规则外）所有变换规则后没有新形式出现，则这种表达式叫范式。解释:范式即演算的语义解释，形如xx，(y(x.z)就只能解释为数据了。上述基本函数均为范式，在它的上面取上有意义的名字可以构成上一层的函数，如：pred=n.(subtractn1),（5）综合规约例题：以演算规约3*23*2=*(3)(2)=x.y.(yx)(3)(2)(y.(y3)(2)(2)3)=(f.c.f(fc)(3)c.(3(3c)=c.(f.c.(f(f(f(c)(3c)/有c不能置换cc.(f.z.(f(f(f(z)(3c)c.(z.(3c)(3c)(3c)(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)c.z.(c(c(c(c(c(c(c(c(c(z)=9,11.2.5Church-Rosser定理,按照演算的运算规则，谁先归约最后归约出的结果是一样的。例:不同归约次序的正规演算得同一结果(x.(xy)(u.(uv)(p.(pq)r)(u.(uv)y)(p.(pq)r)（(x.(xy)(u.(uv)(rq)(yv)(p.(pq)r)(u.(uv)y)(rq)(u.(uv)y)(rq)(yu)(rq)(yu)(rq)(yu)(rq),(1)严格函数归约直到不可归约时正常终止，除开不可归约函数而外，有些函数尽管在符号上可归约，语义上无任何意义，到机器上不可执行的。这就是所谓停机问题，一般说来，停机问题是不可判定的，但我们在表示上给它以符号，例如：dividem0=表示该函数非正常终止，是一个不代表任何值的值。不终止的计算结果值为若f=则称f为严格函数若f=v,v为确定的值，则f为非严格函数正是由于有非严格函数的存在，就产生了求值次序的问题,非严格函数取决于次序的例子例：演算不同求值次序的归约(n.multiplynn)add34)/先做右端子表达式=(n.muliplynn)7/急求值=multiply77=49=mutiply(add34)(add34)/先做归约=mutiply7(add34)=mutiply77=49/正规求值若为mutiply(add34)(add34)/两个表达式一样，后一个不归约，取前一个的值。=mutiply77=49/懒求值,重述Church-Rosser定理如按正规求值次序对某表达式E求值结果为正常值v，则按其他求值次序可能是v也可能是。若按正规求值结果为即非正常终止，则按任何求值规则结果也为正规求值是由外向里Outside_in求值急求值是由里向外Inside_out求值,11.2.6增强演算,只用最底层演算是极其复杂的。用高层命名函数，语义清晰。不仅如此，保留一些常见关键字，语义更清晰。例如，我们可以定义一个if_then_else为名的函数：if_then_else=p.m.n.pmn，当p为真时，执行m否则为n。我们先验证其真伪。例：当条件表达式为真时if_then_else函数的归约(if_then_else)TMN=(p.m.n.pmn)TMN=(m.n.(Tmn)MN=(m.n.(x.y.x)mn)MN=(m.n.(y.m)n)MN=(m.n.m)MN=(n.M)N=M,if表达式可保留显式if-then-else形式：(if_then_else)E1E2E3=ifE1thenE2elseE3其中E1，E2，E3为表达式。,Let/where表达式如果有高阶函数：(n.multiplyn(succn)(addi2)=multiply(addi2)(succ(addi2)/n和addi2置换变元得=multiplyn(succn)/letn=addi2inleta=binE(a.E)bEwherea=b(f.E2)(x.E1)=letf=x.E1inE2=letfx=E1inE2其中形如f=x.E1的x.可移向左边为fx=E1。如:sqr=n.multiplynn/整个是函数表达式sqrn=multiplynn/两应用表达式也相等let表达式在ML.LISP中直接采用，Miranda用where关键字使程序更好读，let直到E完结构成一个程序块。Miranda只不过把where块放在E之后.,元组表达式一般情况下n元组是p=(x1,x2,xn),建立在p上函数有：letf(x1,x2,xn)=E1inE2letfp=E1inletx1=firstpinletx2=secondpin.letxn=n_thpinE2,11.3函数式语言怎样克服命令式语言的缺点,11.3.1消除赋值赋值语句在过程语言中起什么作用。在函数式语言中取消会有什么问题：1存储计算子表达式的中间结果。2条件语句的重要组成。3用于循环控制变量。4处理复杂数据结构(增删改某个成分)。,Miranda解决办法,1：保留全局量、局部量(符号名)以及参数名。2：用条件表达式代替条件语句，其返回值通过参数束定或where子句束定于名字3:函数式语言都要定义表数据结构，因为归约和递归计算在表上很方便。对整个表操作实则是隐式迭代。不用循环控制变量。对于顺序值也都用表写个映射函数即可隐式迭代。部分达到作用3，其它显式循环要用递归。,4:禁止赋值意味着数据结构一旦创建不得修改,故采用如下函数式语言结构数据修改方式,A,B,C,E,H,G,D,F,B,C,A,F,J,I,11.3.2以递归代替while_do,组织仿真的要点是把递归函数体写入条件表达式。循环终止条件是条件测试部分，函数如有返回值放在then部分，递归函数体放在else部分，如果不需返回值则取消一部分(else)。,11.3.3消除顺序,一旦语义相关无法传递数据，非得写成嵌套函数不可(返回值自动束定到外套函数的变元上),例:pascal实现：c：=a+b；s：=sin(c*c)；。write(a，b，c，s)；/上面计算不进行是无法打印/的逻辑上要有顺序。LISP实现：(print(let(c(+ab)let(s(sin(*cc)listabcs)/仍有顺序但在一个/表达式内。自左至右处理即隐式顺序。Miranda实现：Answereab=(abcs)wheres=sin(c*c)c=a+b/多么清晰，全然没有顺序,11.3.4用嵌套代替语义相关的顺序,用懒求值代替顺序,利用卫式进一步消除顺序性,Miranda的卫式表达式gcdab=gcd(a-b)b，ab=gcda(b-a)，amax22=max2，max2max13=max1，otherwisewheremax1=(max_treen1)4max2=(max_treen2)5,如有应用：(max_treeleaf1)/结果值为3，leaf1用上例(max_treetree1)/结果值为49，tree1用上例,表(list),Miranda表的表示法/空表1.n/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”/五个串值的表,11.4.2内定义操作Miranda定义了常规的算术运算符(+、-、*、/、div、mod)并按中缀表示使用。故内定义了一些有用的表操作：L1+L2/表L2并接到表L1的末尾item:List/将项item加到表List的头前List！n/从表List中选取第n项L1-L2/从表L1中剔出L2的值#List/返回表List的项(基)数,11.4.3定义函数,Miranda把函数定义叫方程(equation)。例：斐波那契数的函数定义，用卫式表达式实现递归Fibonaccin=1，n=0=1，n=1=Fibonacci(n-1)+Fibonacci(n-2)n1卫式表达式的值集应复盖所有的可能，否则用otherwise。,例：利用where解二次方程quadrootabc=error“complexroots”，delta0wheredelta=b*b-4*a*cradix=sqrtdeltaterm1=-b/(2*a)term2=radix/(2*a),Miranda完全按演算模型，每个函数都是一元运算，当有多个变元时，函数名也是第一类对象，它逐一应用到各个参数，中间返回函数可以任意取名，这种中间函数称Curry函数。例：直角三角形求斜边长函数hypotenuseab=sqrt(a*a+b*b)调用时hypotenuse34/=5也可写作：(hypotenuse3)4f4Miranda则写作为：f4wheref=hypotenuse3/f=sqrt(9+b*b)即Curry函数。,例:Miranda用变阶函数实现类型参数化。typerow_type=array0.9ofInteger;functionReduce(functionf(x:Integer,y:Integer):Integer;ar:row_type):Integer;/函数f是参数化的。varsum,k:Integer;beginsum:=ar0;fork=1to9dosum:=f(sum,ark);reduce:=sumend;functionMyOp(s:Integer,y:Integer):Integer;/此处定义一实例函数。beginMyOp:=abs(x)+abs(y)end;functionMySum(ar:row_type):Integer;beginMySum:=Reduce(MyOp,ar)end;,上程序仅将Reduce函数操作参数化。数组元素类型、长度还是固定的。Miranda都可以，它设3个参数：操作、表、单位元。单位元的值可用于归约过程的初始化值，也是空表时的返回值：reducefn=n1reducef(a:x)n=fa(reducexn)2为了理解上不引起岐意，写明reduce的类型：reduce:(numnumnum)/第一变元f是函数类型（有括号）,它是二元算子num/返回值是表，表元素是num类型num/若空表映射为数，类型是num.num/最后映射返回值是num类型。2行中（a:x）是表头a和表尾x，右边函数体是表尾归约后与表头归约。1行指明空表规约n次是单位元的n次复合。,11.4.4表闭包,表闭包是一个任意复杂结构的(无限)表。其语法是：:=|:=；|:=:=:=,表闭包示例：ZF表达式解释n*2|n2，4，6，8，104，8，12，16，2