函数式程序设计语言

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

1、第五章函数式程序设计语言过程式程序设计语言由于数据的名值分离，变量的时空特性导致程序难于查错、难于修改命令式语言天生带来的三个问题只解决了一半滥用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的理论证明，λ演算是个完备的系统，可以表示任何计算函数，所以任何可用λ演算仿真实现的语言也是完备的。λ演算使函数概念形式化，是涉

8、及变量、函数、函数组合规则的演算。λ演算基于最简单的定义函数的思想：一为函数抽象λx.E，一为函数应用(λx.E)(a)。一切变量、标识符、表达式都是函数或(复合)高阶函数。如λx.C(C为常量)是常函数。5.2.1术语和表示法(1)λ演算有两类符号：小写单字符用以命名参数，也叫变量。外加四个符号：(、)、。、λ。大写单字符、特殊字符（如+、-、*、/）、大小写组成的标识符代替一个λ表达式。（2）公式变量是公式，如y。如y是变量F是公式，则λy.F也是公式。如F和G都是公式，则(FG)也是公式。（3）λ表达

9、式形如λy.F为λ函数表达式，以关键字λ开始，变量y为参数。形如(FG)为λ应用表达式为了清晰，λ表达式可以任加成对括号。λ演算公式举例x变量、公式、表达式。(λx.((y)x))函数，体内嵌入应用。(λz.(y(λz.x)))函数，体内嵌入应用，再次嵌入函数。((λz.(zy))x)应用表达式。λx.λy.λz.(xλx.(uv)w)复杂表达式(4)简略表示缩写与变形表达下例各表达均等效：λa.λb.λc.λz.E=λabcz.E=λ(abcz).E=λ(a，b，c，z).E=λa.(λb.(λc.(λz

10、.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可以用λ表达式展开形式语法核心的λ演算没有类型，没有顺序控制等概念，程序和数据没有区分。语法极简单：<

11、λ-表达式>::=<变量>

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

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

14、(<λ-表达式>)<变量>::=<字母>5.2.2约束变量和自由变量(λx.((bx)x))自由变量约束变量（λx.λy.(axy)(b(λy.(xy))))λ表达式中的作用域复盖（λx.(λx.(xa))(xb)(xc)）PMNROQ第1个x约束于P第2个x约束于O第3个x在M中自由，约束于O，P第4个x在N中自由，约束于P第5个x在R中自由，在Q中这5个x均约束出现,b，c自由出现。基本函数TRUE和FALSE的λ

15、表达式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)以下是算术操作函