关于 Lambda演算 ●自由变量(计算一个表达式的自由变量集合) 表达式E中变量名x的一次出现称为由出现,如果E 中任何一个形如xE的子表达式包含该出现; ●y(x∴y(Axxy)(z(λxxx))的自由变量集合{y功 ●替换(计算) 设E和E0是表达式,x是变量名,替换EE0/x是表示 把E中的所有x的自由出现替换成E0 ●需要明确变量的自由出现 ●计算规则 (yx+y)yx]=λzy+z 2021/2/5
2021/2/5 11 关于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是一个表达式,且其中没有任何一个 归约基,则称该表达式为范式。 范式的存在性:如果有范式,则最左归约法 定能求出范式。 范式的唯一性:如果有范式则在a变换下 定唯 2021/2/5
2021/2/5 12 关于Lambda演算 ⚫ 范式（性质及其计算） ⚫ 假设E是一个表达式，且其中没有任何一个 归约基，则称该表达式为范式。 ⚫ 范式的存在性：如果有范式，则最左归约法 一定能求出范式。 ⚫ 范式的唯一性：如果有范式则在变换下一 定唯一
函数式描述方法 2021/2/5
2021/2/5 13 函数式描述方法
关于函数式描述方法 ●函数式语言的特点 引用透明性;高阶性;模式匹配;并行性; ●函数式语言的组成部分 程序结构 类型及其操作 表达式 用函数式语言来描述算法(解释器) 函数空间 函数定义(方程) 2021/2/5
2021/2/5 14 关于函数式描述方法 ⚫ 函数式语言的特点 – 引用透明性；高阶性；模式匹配；并行性； ⚫ 函数式语言的组成部分 – 程序结构 – 类型及其操作 – 表达式 ⚫ 用函数式语言来描述算法（解释器） – 函数空间 – 函数定义（方程）
关于函数式描述方法 函数式语言的组成部分 程序结构 函数定义 目标表达式 类型及其操作 标准类型 集合类型 幂集类型 元组类型 联合类型 序列类型 函数类型 递归类型 抽象类型 2021/2/5
2021/2/5 15 关于函数式描述方法 ⚫ 函数式语言的组成部分 – 程序结构 ⚫ 函数定义 ⚫ 目标表达式 – 类型及其操作 – 标准类型 - 集合类型 – 幂集类型 - 元组类型 – 联合类型 - 序列类型 – 函数类型 - 递归类型 – 抽象类型