第5章函数式程序设计语言 过程式程序设计语言由于数据的名值分离,变 量的时空特性导致程序难于查错、难于修改 命令式语言天生带来的三个问题只解决了一半 滥用goto已经完全解决 悬挂指针没有完全解决 函数副作用不可能消除
第5章 函数式程序设计语言 • 过程式程序设计语言由于数据的名值分离， 变 量的时空特性导致程序难于查错、难于修改 • 命令式语言天生带来的三个问题只解决了一半 • 滥用goto已经完全解决 • 悬挂指针没有完全解决 • 函数副作用不可能消除
°问题是程序状态的易变性( Mutability) 和顺序性( Sequencing Backus在图灵奖的一篇演说《程序设计 能从冯·诺依曼风格下解放出来吗?》中 极力鼓吹发展与数学连系更密切的函数 式程序设计语言
• 问题是程序状态的易变性(Mutability) 和顺序性(Sequencing) • Backus在图灵奖的一篇演说《程序设计 能从冯·诺依曼风格下解放出来吗？》中 极力鼓吹发展与数学连系更密切的函数 式程序设计语言
5.1过程式语言存在的问题 (1)易变性难于数学模型 ·代数中的变量是未知的确定值,而程序 设计语言的变量是对存储的抽象 根本解决:能不能不要程序意义的“变 量”只保留数学意义的“变量”? 能不能消除函数的副作用?
5.1 过程式语言存在的问题 （1）易变性难于数学模型 • 代数中的变量是未知的确定值，而程序 设计语言的变量是对存储的抽象 • 根本解决： 能不能不要程序意义的“变 量”只保留数学意义的“变量”？ • 能不能消除函数的副作用？
例:有副作用的函数 int sf fun(int x) static int z=0;//第一次装入赋初值 return x+(z++ sf fun(③3)={3|4|5|6|7. //随调用次数而异,不是数学意义的确定函数
例：有副作用的函数 int sf_fun(int x) static int z = 0； //第一次装入赋初值 return x + (z++)； sf_fun(3) = {3 |4 | 5 | 6 | 7 …} //随调用次数而异，不是数学意义的确定函数
(2)顺序性更难数学模型 ·顺序性影响计算结果,例如,前述急求值、正规求 值、懒求值同一表达式就会有不同的结果。有副作用 更甚,因而难于为程序建立统一的符号数学理论 应寻求与求值顺序无关的表达方式 理想的改变途径 ·没有变量,就没有破坏性赋值,也不会有引起副作 用的全局量和局部量之分。调用通过引用就没有意义 循环也没有意义,因为只有每次执行循环改变了控制 变量的值,循环才能得到不同的结果 那么程序结构只剩下表达式、条件表达式、递归表达 式
（2）顺序性更难数学模型 • 顺序性影响计算结果， 例如， 前述急求值、正规求 值、懒求值同一表达式就会有不同的结果。有副作用 更甚， 因而难于为程序建立统一的符号数学理论。 • 应寻求与求值顺序无关的表达方式 • 理想的改变途径 • 没有变量， 就没有破坏性赋值， 也不会有引起副作 用的全局量和局部量之分。 调用通过引用就没有意义。 循环也没有意义， 因为只有每次执行循环改变了控制 变量的值， 循环才能得到不同的结果。 • 那么程序结构只剩下表达式、条件表达式、递归表达 式
52λ演算 λ演算是符号的逻辑演算系统,它正好只有这 三种机制,它就成为函数式程序设计语言的模 型 λ演算是一个符号、逻辑系统,其公式就是符。 号串并按逻辑规则操纵 Church的理论证明,λ演算是个完备的系统 可以表示任何计算函数,所以任何可用λ演算 仿真实现的语言也是完备的
5.2 λ演算 • λ演算是符号的逻辑演算系统，它正好只有这 三种机制， 它就成为函数式程序设计语言的模 型 • λ演算是一个符号、逻辑系统，其公式就是符 号串并按逻辑规则操纵 • Church的理论证明， λ演算是个完备的系统， 可以表示任何计算函数， 所以任何可用λ演算 仿真实现的语言也是完备的
λ演算使函数概念形式化,是涉及变量、函 数、函数组合规则的演算。 入演算基于最简单的定义函数的思想:一为 函数抽象λX.E,一为函数应用(λxE)(a)。 高阶函数。如入xC(为常量)是常函Q合 切变量、标识符、表达式都是函数或(
• λ演算使函数概念形式化，是涉及变量、函 数、函数组合规则的演算。 • λ演算基于最简单的定义函数的思想： 一为 函数抽象λx.E， 一为函数应用(λx.E)(a)。 • 一切变量、标识符、表达式都是函数或(复合) 高阶函数。如λx.C(C为常量)是常函数
λ演算公式举例 变量、公式、表达式 (λx.((y)x)) 函数,体内嵌入应用。 (λz.(y(λz.x))函数,体内嵌入应用 再次嵌入函数。 ((λz.(zy)x)应用表达式。 λx.Ay.λz.(xλx.(uv)w)复杂表达式
λ演算公式举例 x 变量、公式、表达式。 (λx.((y)x)) 函数， 体内嵌入应用。 (λz.(y(λz.x))) 函数， 体内嵌入应用， 再次嵌入函数。 ((λz.(z y))x) 应用表达式。 λx.λy.λz.(x λx.(u v)w) 复杂表达式
由于λ演算中一切语义概念均用λ表达式表 达。为了清晰采用命名替换使之更易读。 λx.Ay.x //逻辑真值 TF12 入 Ⅹ.Ny.y //逻辑假值 λx.y.xy //数1 入x.y.x(xy //数2 zerop=n.n(λx.F)T/判零函数 注: zerop中的F、T可以用λ表达式展开
由于λ演算中一切语义概念均用λ表达式表 达。 为了清晰采用命名替换使之更易读。 T = λx.λy.x //逻辑真值 F = λx.λy.y //逻辑假值 1 = λx.λy.x y //数1 2 = λx.λy.x(x y) //数2 zerop = λn.n(λx.F)T //判零函数 注：zerop中的F、T可以用λ表达式展开
形式语法 核心的λ演算没有类型,没有顺序控制等概念 程序和数据没有区分。语法极简单 λ-表达式〉:∴:= λ.〈λ-表达式> () () 变量〉 <字母
形式语法 核心的λ演算没有类型， 没有顺序控制等概念 ， 程序和数据没有区分。 语法极简单： :: = | λ. | () | () :: =