上次课程小结电子教案

资源描述

《上次课程小结电子教案》由会员分享，可在线阅读，更多相关《上次课程小结电子教案（36页珍藏版）》请在金锄头文库上搜索。

1、上次课程小结,类型系统：赋给程序各部分的一组规则类型表达式：由类型构造符作用与基本类型表达式。基本的类型表达式：基本类型、类型名、类型变量的值类型构造符：、array(I, T)、pointer(T)、 record（F1F2.)、DR 简单的类型检查：语法制导翻译声明时构造类型表达式引用时计算类型表达式（类型检查）,4.4 类型表达式的等价,在简单的类型检查中，通过判定所给的两个类型表达式是否相等来进行类型检查。对于单态的类型，我们引入一个更专业的术语，类型等价来描述类型检查。类型的等价与类型的表示有关，表示不同，等价的概念也不同。本节讨论三个重要问题：有哪些类型等价程序

2、设计语言规定什么样的等价以及等价的判别,4.4.1 结构等价与等价的判别,若两个仅由类型构造符作用于基本类型组成的类型表达式完全相同，则称两个类型表达式结构等价。换句话说，类型表达式结构等价当且仅当二者完全相等。若类型表达式中没有名字，则结构等价就是类型等价。例如int与int结构等价，array(1.10, real)与array(1.10, real)结构等价。反映在类型表达式的语法树上，就是两棵语法树完全相同。, 结构等价的判别,算法4.1 判别类型是否结构等价输入两个类型表达式输出若两个类型表达式结构等价则返回true否则false 方法用下述递归函数进行判别：,fu

3、nction sequiv(s, t) return boolean is begin end sequiv;,if s and t are the same type then return true; elsif s=array(s1, s2) and t=array(t1, t2) then return sequiv(s1, t1) and sequiv(s2, t2); elsif s=s1s2 and t=t1t2 then return sequiv(s1, t1) and sequiv(s2, t2); elsif s=pointer(s1) and t=pointer(t1)

4、 then return sequiv(s1, t1); elsif s=s1s2 and t=t1t2 then return sequiv(s1, t1) and sequiv(s2, t2); else return false; end if;, 类型表达式的优化表示,sequiv(s, t)算法的弱点：需要对两棵语法树完全遍历后才能确定它们是否等价。当类型构造符层次很多并且仅在最底层不等价时，算法的效率较低。改进的思路：在调用sequiv之前，先用一种简单的方法将明确可以确定不等价的情况排除。即为了提高效率，牺牲一些次要信息，只有当两个类型表达式的主要信息相等时才判定次要信息是否也

5、相等。具体方法：对类型表达式的主要信息进行编码。将类型构造符表示的每个内部节点的多于一个的孩子分支剪去，仅保留一个重要的分支，类型表达式的语法树就退化为一个链，即一条从根到叶子的路径。对链上每个节点编码，形成一个类型编码的字符串或者整型数。由于类型编码仅反映了类型表达式的主要成份，因此两个编码不同，则类型表达式一定不等价（从而起到过滤的作用），反之不一定。, 类型表达式的优化表示（续1）,数组的类型表达式array(s, t) 简化为array(t)，即忽略下标类型保留数组元素类型。函数的类型表达式st简化为freturns(t)，即忽略参数类型保留返回值的类型。指针的类型表达式poi

6、nter(t)本身就是一个一元的构造符，因此无需简化。问题：与record的简化如何处理？简化类型表达式的编码：,类型表达式的化简：, 类型表达式的优化表示（续2）,例4.14 考虑类型表达式 array(1.10, pointer(intchar)：,简化后的类型表达式为array( pointer(freturns(char)。将其从左到右转换为编码，得到1001110001。,4.4.2 引入类型名的等价判别,若每个类型名作为一个可区分的类型出现在表达式中并且使得两个类型表达式完全相同，则称它们名字等价。若将类型表达式中的所有名字均用其定义的类型表达式替换后两个类型表达式完全相同，

7、则称它们结构等价。,例4.15 对于下述Pascal程序段：,type cell = array1.10, int; type link = cell; varnext : link; last : link; p: cell; q,r: cell;,采用名字等价，则变量next和last的类型表达式为link，变量p、q、r的类型表达式为pointer(cell)，显然next和last名字等价，p、q、r名字等价。,若将名字用它们所代表的结构代替，则5个变量的类型表达式均为pointer(array(1.10, int)。因此它们全部结构等价。,4.4.2 引入类型名的等价判别（续1）,名

8、字等价通过对取值范围相同但是代表不同意义的对象取不同的类型名，使得它们具有不同的类型。不同类型的对象不能进行运算，从而避免了潜在的错误；名字等价提高了程序的可靠性，但是降低了程序的灵活性；程序设计语言可以根据不同的需求采用不同的等价策略。例如Algol 68采用结构等价，而Ada采用名字等价。,例4.16 下述Ada类型定义语句将完全相同的结构定义为不同的名字： type male_type is node_array; type female_type is node_array; male : male_type; female : female_type; 在名字等价下，变量male

9、和female的类型不同，使得这两个变量之间不能运算。,为什么规定采用何种类型等价,Pascal没有规定采用何种等价，其等价问题依赖于实现，给熟悉名字等价或结构等价的程序员带来不必要的使用上的混乱。 Pascal关于类型等价的一种解决方案是：变量声明时对类型的每次引用，均隐含地为它构造一个类型名，然后采用名字等价。,typecell = array1.10, int; typelink = cell; np = cell; nqr = cell; varnext : link; last : link; p : np; q,r : nqr;,type cell = array1.10, int

10、; type link = cell; varnext : link; last : link; p: cell; q,r: cell;,在名字等价的定义下，原来与q和r类型等价的p现在被认为不与任何变量的类型等价。,为什么规定采用何种类型等价（续）,Pascal的这种类型等价的实现方法，似乎比名字等价更为严格。程序员可以采用一种变通的方法将Pascal程序转换为名字等价，若有不同的变量声明具有结构等价的类型时，一定要先定义此类型，即为此类型命名。例4.17 定义下述两个声明语句，变量a和参数x实质上结构等价： var a : array 1.10 of integer; function

11、 test ( x : array 1.10 of integer) : integer; 根据Pascal的等价策略，a与x类型不等价，因此a不能作为函数test的实参。若希望a作为test的实参，则必须首先为它们共同的类型命名，然后a和x均被声明为此类型名所定义的类型： type arr_type = array 1.10 of integer; var a : arr_type; function test (x : arr_type ) : integer; 从而使得a与x类型等价。,单态类型检查的一般过程,确定一种类型等价方式：没有类型名的情况下所有等价问题均是结构等价；名字可以作

12、为类型表达式时，就需要确定等价策略，是采用名字等价还是采用结构等价；根据类型信息构造类型表达式，名字等价与结构等价的唯一区别就是类型名是否可以出现在类型表达式中；判定表达式的类型等价就是判定它们的类型表达式是否相等。,4.5 多态函数的类型检查,通俗的讲，程序设计语言中的多态就是一个符号可以有多种意思。多态与强类型是密不可分的，虽然一个符号可以有多种意思，但是编译器必须保证它的每次使用是确定的并且是类型正确的，否则并不是多态而是弱类型。弱类型的典型例子是C，例如在C程序中char类型的变量和int类型的变量可以运算，但是运算结果的正确性由程序员负责。,4.5.1 多态函数与类型变量的表

13、示,通用多态中的参数多态被称为多态函数。多态函数的基本特征是参数的类型是类型变量且该变量可以取无穷多个值，但是所有类型均对应同一代码序列。多态函数中形参的类型是变量，称为类型变量，用、等表示。从语言结构的使用方式推断其类型，被称为类型推断（type inference）。例如从函数体推断函数的类型。,例4.18 对于函数定义： function deref(p); begin return p end；从函数体中可以看出，p的类型应该是指向某对象的指针，而p返回它所指向的对象。设该对象的类型为，则p的类型是pointer()，因此函数deref(p)的类型应该是： .pointer() (

展开阅读全文