函数式程序设计语言.ppt

* 程序设计语言范型程序设计语言范型 Programming Languages ParadigmsProgramming Languages Paradigms 教师： 张荣华 计算机科学与技术学院 华北电力大学 函数式程序设计语言 Scheme语言数据抽象 第二部分 第五章 函数程序设计语言 Scheme语言数据抽象第五章 - 3 回顾 n任何强有力的程序设计语言都必须能表述基本的数 据和过程，还需要提供对数据和过程进行组合和抽 象的方法摘自计算机程序的构造和解释 n 控制抽象（表达式层次、语句层次、程序单元层次） n 数据抽象（本章研究内容） 函数程序设计语言 Scheme语言数据抽象第五章 - 4 回顾 nScheme语言控制抽象（第五章 第二部分） n将一个过程的使用方式，与该过程究竟如何通过更基 本的过程实现的具体细节相互分离的一种技术。 n 基本数据（数）； n 基本过程（算数运算）； n 用复合、条件、参数将过程组合起来形成复合过程； n 通过define、lambda做过程抽象； n 过程的计算模式（递归计算和迭代计算过程） n 高阶过程 nScheme语言数据抽象（第五章 第三部分） n讨论程序设计语言提供的将数据对象组合起来形成复 合数据的方式。 函数程序设计语言 Scheme语言数据抽象第五章 - 5 内容 n 1. 数据抽象导引 n1.1 序对 n1.2 有理数包的抽象屏障 n 2. 表结构 n2.1 序列与闭包性质 n2.2 表操作 n2.3 表映射 n 3. 函数式语言高级抽象综合实例 函数程序设计语言 Scheme语言数据抽象第五章 - 6 1. 数据抽象导引 n数据抽象 n将程序中处理数据对象的表示的部分，与处理数据对 象的使用的部分相互隔离起来的一种技术。 n例如：考虑线性组合：ax + by (define (linear-combination a b x y) (+ (* a x) (* b y) (define (linear-combination a b x y) (add (mul a x) (mul b y) n数据抽象的关键： n构造函数（“粘合剂”）+ 选择函数（“分离剂”） 函数程序设计语言 Scheme语言数据抽象第五章 - 7 实例：有理数的算术运算 n假定： n存在一种方法可以从分子和分母构造出有理数； n存在一种方法可以从已经存在的有理数中分离它的 分子和分母。 n n n (make-rat ) (numer ) (denom ) /从分子n和分母d构造有理数并返回 /返回有理数x的分母 /返回有理数x的分子 构造函数 选择函数 函数程序设计语言 Scheme语言数据抽象第五章 - 8 实例：有理数的算术运算 n例如：实现两个有理数相加 n n 函数程序设计语言 Scheme语言数据抽象第五章 - 9 内容 n 1. 数据抽象导引 n1.1 序对 n1.2 有理数包的抽象屏障 n 2. 表结构 n2.1 序列与闭包性质 n2.2 表操作 n2.3 表映射 n 3. 函数式语言高级抽象综合实例 函数程序设计语言 Scheme语言数据抽象第五章 - 10 1.1 序对 nScheme语言提供的构造函数和选择函数 n 内部的基本过程：cons n模拟构造函数的功能，构造序对。 n表结构：由序对构造起来的复合数据对象。 n 内部基本过程：car和cdr n模拟选择函数的功能，实现对序对的操作。 函数程序设计语言 Scheme语言数据抽象第五章 - 11 内容 n 1. 数据抽象导引 n1.1 序对 n1.2 有理数包的抽象屏障 n 2. 表结构 n2.1 序列与闭包性质 n2.2 表操作 n2.3 表映射 n 3. 函数式语言高级抽象综合实例 函数程序设计语言 Scheme语言数据抽象第五章 - 12 1.2 有理数包的抽象屏障 使用有理数的程序 add-rat、sub-rat . make-rat 、numer、denom cons、car、cdr 抽 象 抽 象 12 函数程序设计语言 Scheme语言数据抽象第五章 - 13 内容 n 1. 数据抽象导引 n 2. 表结构 n2.1 序列与闭包性质 n2.2 表操作 n2.3 表映射 n 3. 函数式语言高级抽象综合实例 函数程序设计语言 Scheme语言数据抽象第五章 - 14 2.1 序列与闭包性质 n序对的“盒子和指针表示方式” n例如： n每个对象表示一个指向盒子的指针 n左边的方盒放着序对的car n右边的方盒放着序对的cdr ncons的闭包性质 n建立元素本身也是序对的序对，表结构 1 2 34 12 函数程序设计语言 Scheme语言数据抽象第五章 - 15 2.1 序列与闭包性质 n序列（Sequences）/ 表（list） n由序对构造出的一种数据结构。 n表示一批数据对象的有序集合。 1234 函数程序设计语言 Scheme语言数据抽象第五章 - 16 内容 n 1. 数据抽象导引 n 2. 表结构 n2.1 序列与闭包性质 n2.2 表操作 n2.3 表映射 n 3. 函数式语言高级抽象综合实例 函数程序设计语言 Scheme语言数据抽象第五章 - 17 2.2 表操作 n【例1】 函数程序设计语言 Scheme语言数据抽象第五章 - 18 2.2 表操作 n【例2】用迭代计算模型改写下面的过程。 函数程序设计语言 Scheme语言数据抽象第五章 - 19 2.2 表操作 n【例3】实现两个表的合并。 函数程序设计语言 Scheme语言数据抽象第五章 - 20 内容 n 1. 数据抽象导引 n 2. 表结构 n2.1 序列与闭包性质 n2.2 表操作 n2.3 表映射 n 3. 函数式语言高级抽象综合实例 函数程序设计语言 Scheme语言数据抽象第五章 - 21 2.3 表映射 n表映射 n将某种变换应用于一个表的所有元素，得到的结果构 成新的表。 n例如：将一个表中的元素按给定因子缩放。 函数程序设计语言 Scheme语言数据抽象第五章 - 22 2.3 表映射 n问题: n如何将表的映射这个一般性问题进行抽象？ n解决方法： n将其中的公共模式表述为一个高阶过程map n研究Scheme标准提供的内部map过程 函数程序设计语言 Scheme语言数据抽象第五章 - 23 2.3 表映射 n问题: n如何将表的映射这个一般性问题进行抽象？ n解决方法： n将其中的公共模式表述为一个高阶过程map n研究Scheme标准提供的内部map过程 函数程序设计语言 Scheme语言数据抽象第五章 - 24 使用map改进scale-list 函数程序设计语言 Scheme语言数据抽象第五章 - 25 内容 n 1. 数据抽象导引 n 2. 表结构 n2.1 序列与闭包性质 n2.2 表操作 n2.3 表映射 n 3. 函数式语言高级抽象综合实例 n【实例1】对于一棵树，计算值为奇数的叶子的平方和。 n【实例2】构造所有为偶数的斐波那契数Fib(k)的一个表，其中 的k小于等于某个给定的整数n。 (1 2) 3 4) (1 2) 1 2 3 4 n【实例1分析】 枚举一棵树的树叶 过滤它们，选出其中的奇数 对选出的每一个数求平方 从0开始，用+累积起得到的结果 函数程序设计语言 Scheme语言数据抽象第五章 - 28 3 函数式语言高级抽象综合实例 n实例1和实例2的信号流流水线处理模式 enumerate: tree leaves filter: odd? map: square accumulate: +，0 enumerate: integers map: fib filter: even? accumulate: cons，( ) 枚举 从0到n的整数 对每个整数计算 相应的斐波那契数 过滤它们 选出其中的偶数 从空表