第五章函数式程序设计语言

第五章函数式程序设计语言内容摘要：

)=E1 in E2 ≡ let fp=E1 in let x1=first p in let x2=second p in . . . let xn=n_th p in E2 Lambda演算 关于 Lambda演算  表达式  自由变量（计算一个 表达式的自由变量集合 ）  替换（计算）  变换规则 （三种变换）  归约  范式（性质及其计算） 关于 Lambda演算  表达式 一个 表达式 由变量名、抽象符号 ， .以及括号等符号构成， 其语法为： 表达式 ::= 变量名 | 表达式 表达式 |  变量名 . 表达式 | ( 表达式 ) 关于 Lambda演算  变换规则 （三种变换）  变换：设 E是 表达式， x是变量，则称下面变换为 α变换（其中 y不在 FV(  )中）  〉 y.[y/x] E  变换：设 ()和 E0为 表达式，则称下面变换为 β变换（称 β变换规则的左部表达式为 β基） ()E0 E[E0/x]  变换：假设 ，且满足条件 xFV(M)，则称下面变换为 η变换 : ( x) M    关于 Lambda演算  自由变量（计算一个 表达式的自由变量集合 ）  表达式 E中变量名 x的一次出现称为 自由出现 ，如果 E中任何一个形如 x. E’的子表达式包含该出现；  y (x y. y (x. x y ) ) (z (x. x x) )的自由变量集合 {y, z}  替换（计算） 设 E和 E0是表达式， x是变量名， 替换 E[E0/x]是表示 把 E中的所有 x的自由出现替换成 E0。  需要明确变量的自由出现  计算规则  ( y. x+y) [y/x] = z. y+z 关于 Lambda演算  范式（性质及其计算）  假设 E是一个表达式，且其中没有任何一个归约基，则称该表达式为 范式。  范式 的存在性：如 果有范式，则最左归约法一定能求出范式。  范式 的唯一性：如 果有范式则在 变换下一定唯一。 函数式描述方法 关于函数式描述方法 • 函数式语言的特点 – 引用透明性；高阶性；模式匹配；并行性； • 函数式语言的组成部分 – 程序结构 – 类型及其操作 – 表达式 • 用函数式语言来描述算法（解释器） – 函数空间 – 函数定义（方程） 关于函数式描述方法 • 函数式语言的组成部分 – 程序结构 • 函数定义 • 目标表达式 – 类型及其操作 – 标准类型 集合类型 – 幂集类型 元组类型 – 联合类型 序列类型 – 函数类型 递归类型 – 抽象类型 关于函数式描述方法 • 函数式语言的组成部分 – 表达式 •非 let表达式（常量，变量， 表达式，条件表达式， 以及各种操作） •let表达式 let x = E’ in E •letrec表达式 letrec x = E1 in E •在表达式中增加类型说明 关于函数式描述方法 • 用函数式语言来描述算法 – 函数空间： INT*  INT  BOOL – 函数定义（方程） lookup L a = (null L→FALSE ， a=hd L→TRUE ， lookup (tl L) a ) 函数式语言怎样克服命令式语言的缺点 • 消除赋值 赋值语句在过程语言中起什么作用。 在函数式 语言中取消会有什么问题： [1] 存储计算子表达式的中间结果。 [2] 条件语句的重要组成。 [3] 用于循环控制变量。 [4] 处理复杂数据结构 (增删改某个成分 )。 解决办法 [1]： 保留全局量、局部量 (符号名 )以及参数名。 [2]： 用条件表达式代替条件语句，其返回值通过 参数束定或 where子句束定于名字 [3]:函数式语言都要定义表数据结构， 因为归约 和递归计算在表上很方便。 对整个表操作实 则是隐式迭代。 不用循环控制变量。 对于 顺序值也都用表写个映射函数即可隐式迭代。 部分达到作用 [3]， 其它显式循环要用递归。 [4]:禁止赋值意味着数据结构一旦创建不得修改 ,故采用如下函数式语言结构数据修改方式 A B C E H G D F’ B’ C A F J I 以递归代替 while_do 组织仿真的要点是把递归函数体写入条件表达式。 循环终止条件是条件测试部分， 函数如有返回值放在 then部分， 递归函数体放在else部分， 如果不需返回值则取消一部分(else)。 消除顺序 一旦语义相关无法传递数据， 非得写成嵌套函数不可 (返回值自动束定到外套函数的变元上 ) 例 :pascal实现： c： =a+b； s： =sin(c * c)；。 write(a， b， c， s)； //上面计算不进行是无法打印 //的逻辑上要有顺序。 LISP 实现 ： (print (let ((c(+ a b))) let ((s (sin (* c c)))) list a b c s )))) //仍有顺序但在一个 //表达式内。 自左至右处理即隐式顺序。 Miranda实现： Answere a b = (a b c s ) where s= sin (c* c) c= a+b //多么清晰， 全然没有顺序 序 • 用懒求值代替顺序 • 利用卫式进一步消除顺序性 Miranda的卫式表达式 gcd a b= gcd (ab) b， ab = gcd a (ba)， ab = a， a=b LISP的条件选择 （ define GCD (a b) （ cond (( greaterp a b) (GCD ((diference a b ) b))) ((Lessp a b) (GCD (a (。