函数式程序设计语言

《函数式程序设计语言》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章函数式程序设计语言过程式程序设计语言由于数据的名值分离，变量的时空特性导致程序难于查错、难于修改命令式语言天生带来的三个问题只解决了一半滥用goto已经完全解决悬挂指针没有完全解决函数副作用不可能消除问题是程序状态的易变性(Mutability)和顺序性(Sequencing)Backus在图灵奖的一篇演说《程序设计能从冯·诺依曼风格下解放出来吗？》中极力鼓吹发展与数学连系更密切的函数式程序设计语言5.1过程式语言存在的问题（1）易变性难于数学模型代数中的变量是未知的确定值，而程序设计语言的变量是对存储的抽象根本解决：能不能不要程序意义的“变量”只保留数学意义的“变量”？能不

2、能消除函数的副作用？例：有副作用的函数intsf_fun(intx)staticintz=0；//第一次装入赋初值returnx+(z++)；sf_fun(3)={3

3、4

4、5

5、6

6、7…}//随调用次数而异，不是数学意义的确定函数。（2）顺序性更难数学模型顺序性影响计算结果，例如，前述急求值、正规求值、懒求值同一表达式就会有不同的结果。有副作用更甚，因而难于为程序建立统一的符号数学理论。应寻求与求值顺序无关的表达方式理想的改变途径没有变量，就没有破坏性赋值，也不会有引起副作用的全局量和局部量之分。调用通过引用就没有意义。循环也没有意义，因为只有每次执行循环改变了控制变量的值，循环才能

7、得到不同的结果。那么程序结构只剩下表达式、条件表达式、递归表达式。5.2λ演算λ演算是符号的逻辑演算系统，它正好只有这三种机制，它就成为函数式程序设计语言的模型λ演算是一个符号、逻辑系统，其公式就是符号串并按逻辑规则操纵Church的理论证明，λ演算是个完备的系统，可以表示任何计算函数，所以任何可用λ演算仿真实现的语言也是完备的。λ演算使函数概念形式化，是涉及变量、函数、函数组合规则的演算。λ演算基于最简单的定义函数的思想：一为函数抽象λx.E，一为函数应用(λx.E)(a)。一切变量、标识符、表达式都是函数或(复合)高阶函数。如λx.C(C为常量)是常函数。λ演算公式举例x变量、

8、公式、表达式。(λx.((y)x))函数，体内嵌入应用。(λz.(y(λz.x)))函数，体内嵌入应用，再次嵌入函数。((λz.(zy))x)应用表达式。λx.λy.λz.(xλx.(uv)w)复杂表达式由于λ演算中一切语义概念均用λ表达式表达。为了清晰采用命名替换使之更易读。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可以用λ表达式展开形式语法核心的λ演算没有类型，没有顺序控制等概念，程序和数据没有区分。语法极简单：<λ-表达式>::

9、=<变量>

10、λ<变量>.<λ-表达式>

11、(<λ-表达式><λ-表达式>)

12、(<λ-表达式>)<变量>::=<字母>基本函数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.((zλx.λ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.

13、λ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)))))))归

14、约与范式归约将复杂的表达式化成简单形式，即按一定的规则对符号表达式进行置换。例：归约数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）β归约：