四章类型检查

第四章 类型检查 类型检查属于语义的范畴，根据程序设计语言的要求，类型检查可以在编译时进行（静态语义），也可以在程序运行时进行（动态语义）。本章仅涉及静态语义。静态语义检查：1.类型检查：算符是否作用于类型不一致的运算对象；2.作用域检查：确定的名字是否在确定的范围内起作用（包括唯一性检查）；3.控制流检查：控制是否合法地进入和离开（特别是离开）一个结构，如C语言中的break应该出现在while、for、switch等语句中，goto应转向合法的标号等；4.关联名字检查：相同的名字出现在不同的地方是否相关联，如function checker()is.begin.end checker;类型检查的复杂性：随着程序设计语言的发展，类型变得越来越丰富，从而使得类型检查越来越复杂。本章的目的：将类型检查的相关联问题，从静态语义中抽取出来，进行专门的讨论，重点讨论类型检查的基本原理和一般方法。类型检查的基本思想：类型系统（立法）类型检查器（执法）41 类型简介 类型的发展是程序设计语言发展的重要因素之一，程序设计语言提供的强类型的保障机制，将程序中的类型错误降到最低,从而提高软件的可靠性。面向对象技术是类型发展的结果，为软件的重用提供了支持，并在提高软件可靠性的基础上提高了软件的可维护性。参考文献：1.Luca Cardelli&Peter Wegner,On Understanding Types,Data Abstruction,and Polymorphism,Computing Surveys,Vol.17,No.4.Dec.1985.2.Luca Cardelli,Type Systems,CRC press,Feb.20044.1.1 从不分类到类型 不分类：1.无论是代码还是数据，均被认为是具有固定大小的bit string，即memory byte or word。2.代表代码还是数据？是整型数还是字符串？正确使用这些字或字节是程序设计人员的责任。3.根据字或字节所表示信息的用途和特性进行分类和管理，于是就有了类型的概念。类型是由一个值的集合与值集合上的操作集合组成的系统（value-set,operator-set）。例如integer 是一个类型，在特定程序语言中可如下规定：（-32768，32767，+、-、*、/、.）因此，3.5、8.2、7/3、10000000等不是integer。引入类型的目的，是让程序设计语言（编译器）承担起对类型检查的责任。4.1.2 静态类型与强类型类型检查一般在编译时进行，但也有一些需要在运行时进行。编译时类型检查：var x:integer;y:boolean;y:=x;可以对赋值句 y:=x;进行静态类型检查：A id:=E if id.typeE.type then A.type:=type_error;else.因为x和y的类型在编译时是确定的。4.1.2 静态类型与强类型（续1）若程序设计语言中允许动态数组，则下述源程序段是合法的：var x,y:integer;.procedure sort(left,right:integer)is A:arrayleft.right of objects;.end sort;.sort(x,y);x和y是整型值，可以作为数组的下界和上界。x和y的值只能在运行时才能确定，而当xy时，sort(x,y)不能正确运行。运行时类型检查：4.1.2 静态类型与强类型（续2）每个表达式的类型均可以通过静态程序分析来确定的程序设计语言被称为是静态类型的。若程序设计语言的所有表达式在任何时刻均是类型一致的，则称该语言是强类型的。1.强类型语言提高了对编译器的要求，因为它要求无论是编译阶段还是运行阶段，表达式的运算均要保证类型的一致性；2.OOPL不是静态类型语言，因为方法的重置（override）是静态不可确定的；3.为使OOPL保持类型的一致性，它应是强类型的。4.1.3 多态（Polymorphism）强类型和静态类型提高了程序的可靠性，但是限制了程序设计的灵活性。多态 允许操作或操作对象取多于一种的类型的机制被称为多态。一般来讲，操作对象（实参）可以具有多于一种类型的函数被称为多态函数，这类多态属于通用多态；操作可以施加于多于一种类型的操作对象被称为多态类型，这类多态属于特定多态。例4.1 若x:integer;y:real;则x+y是否合法？例4.2 对一ADT：stack(object);操作push(object)、pop(object)中的参数object可以取什么类型？多态的分类多态（polymorphism）重载(overloading)通用(universal)特定(ad-hoc)参数(parametric)包含(inclusion)强制(coercion)通用多态:实例可以有无穷多个a.参数多态：过程式程序设计语言中最具代表性的通用多态，它很象宏(macro)，即参数的类型可以有无穷多个，而对所有的类型参数，均执行同一代码序列。C语言的源程序中，可以通过#define定义如下：#define enter(x)printf(enter in);printf(x);printf(n)对enter(ForStatement)和enter(Expression)的调用得到不同的结果：enter in ForStatemententer in Expression 通用多态:实例可以有无穷多个（续1）参数多态与宏的区别：宏的参数是变量，而参数多态的参数是类型，即确定的类型（可以认为类型是常量）成为可变的。例如可以通过类属(generic)机制在Ada源程序中定义generic的stack程序包，使得操作对象object可以取不同类型：定义：generic type object is private;package stack is procedure push(element:in object);procedure pop(element:out object);.end stack;声明与引用：package int_stack is new stack(integer);package str_stack is new stack(string);int_stack.push(3);str_stack.push(hello);通用多态:实例可以有无穷多个（续2）b.包含多态：包含多态是另一种形式的通用多态。子类型、派生类型、子类（派生类）均属于包含多态。不同的是：子类型和派生类型的基类型是程序设计语言提供的，而子类的基类是程序设计者自己定义的。Ada语言的源程序中可以定义整型数的子类型和派生类型height和weight如下：subtype height is integer range 1.200;-身高subtype weight is integer range 1.200;-体重type height is range 1.200;-身高type weight is range 1.200;-体重 integer上的所有运算均适用于height和weight，但是它们的值集合均是integer的子集1,200。派生类型被认为是新的类型，并且不在同一类型中的变量不能一起运算。特定多态：有限个不同的、且不关联的类型b.强制（coercion）：强制是根据应用需求对类型进行内部转换，以减少重载的类型。例如：表达式3+4、3.0+4、3+4.0和3.0+4.0中+可以是：1.4种重载类型，对应四种形式的运算；2.1种重载类型，所有形式的运算均强制为real+real；3.两种重载类型：int+int和real+real。int+real和real+int均强制为real+real。a.重载（overload）：相同的操作符施加于不同的操作对象，根据上下文确定操作的具体类型，即采用哪段代码序列实现此操作。例如：表达式x+y中的+可以是数的加、字符串的联接和集合的并。几乎多态的语言 多态既保持了强类型，又增加了程序设计语言的灵活性和功能。但是，传统的程序设计语言如Pascal、Ada83、C等，并不是真正的多态语言，因为它们仅支持部分的多态，即将多态看作为exception而不是rule。4.1.4 面向对象程序设计语言（OOPL）Object-Oriented=data abstractions+object types+type inheritance1.从类型发展的观点看，OOPL应该是强类型的、多态的、且对象类型化的。2.它与过程式程序设计语言的最大区别在于，OOPL引入了类与类的继承。OOPL是程序设计语言的一个重要发展，它的最重要特征之一就是将对象类型化，即将构造新的类型的权利交给了程序设计语言的使用者。换句话说，传统的PL为我们提供了类型（仅提供了简单类型），而OOPL为我们提供了构造（定义）类型的方法。Ada83支持data abstractions1.基于对象的程序设计语言，源程序重要组成：package；2.package组成：规格说明(specification)与体(body)。package stack is-规格说明 procedure push(x:in object);procedure pop(x:out object);.end stack;package body stack is -体 procedure push(x:in object)is .end push;.end stack;使用：with stack;use stack;.push(x);或者with stack;.stack.push(x);Ada83程序包不是类型Ada的记录类型：const max_students=200;-学生人数最大值const max_teachers=20;-教师人数最大值type name_str is array(1.10)of character;-姓名type student_type is record-学生记录id_no:student_id_no;name:name_str;end record;type teacher_type is record-教师记录 id_no:teacher_id_no;name :name_str;end record;type class is record-班级记录students:array(1.max_students)of student_type;teachers:array(1.max_teachers)of teacher_type;end record;Ada83程序包不是类型（续）问题：是否可以象声明记录类型的变量那样声明package的实例？但是不可以为package声明对象，例如：stack1,stack2:stack;-?stack1.push(x);-?因为package不是类型！可以为记录类型声明对象并使用它们，例如:C0014,S00:class;S00.studentsi.name:=张三;C0014.teachersj.name:=李四;面向对象机制的两种实现方法过程式程序设计语言实现类型化与继承机制的两条途径：1.记录类型中扩充操作2.扩充抽象数据类型（ADT或程序包）为类型1.ADT类型化Ada95 的标签类型a.类的定义package class_account is privateend class_account;b.对象的声明与引用Mike:account;deposit(Mike,50.00);type account is tagged private;subtype Money is float;procedure deposit(the:in out account;amount:in Money);function balance(the:in account)return Money;type account is tagged recordbalance_of:Money:=0.00;end record;1.ADT类型化（续1）with class_account;use class_account;package class_interest_account isprivate end class_interest_account;d.继承机制下对象的声明与引用corinna:interest_account;deposit(corinna,500.00);calc_interest(corinna);type interest_account is new account with private;procedure calc_interest(the:in out interest_account);.type interest_account is new account with record accumulated_interest:Money:=0.00;end record;.c.类的继承（派生类）2.C+结构的扩充 C+通过对C的struct进行扩充，使得结构中既含有操作对象，又含有操作。a.struct及其上的操作typedef struct int year,month,day;date_struct;void add_year(date_struct&day,int n);/增加年份void add_month(date_struct&day,int n);/增加月份void add_day (date_struct&day,int n);/增加天数const void out_date(char*x,date_struct&day);b.C+对struct的扩展：操作作为struct的成员typedef struct int year,month,day;/数据成员void add_year(int n);/函数成员：增加年份void add_month(int n);/函数成员：增加月份void add_day(int n);/函数成员：增加天数const void out_date(char*x);/函数成员：显示日期 date_type;3.C+的classclass date_class private:int year,month,day;/数据成员 public:void add_year(int n);/函数成员：增加年份 void add_month(int n);/函数成员：增加月份 void add_day (int n);/函数成员：增加天数 const void out_date(char*x);/函数成员：显示日期 date_class()year=2001;month=1;day=1;date_class();问题：1.由struct扩充的类中如何实现信息隐藏和继承？2.struct 中的内容隐藏后，给初始化带来困难。4.Ada95中类与继承的实现方法1.类的基本实现方法记录（record）扩充与程序包（package）扩充的结合以package为类的基本框架，引入一个带标签的recordrecord中声明操作对象，package中声明施加于对象的操作2.继承的基本实现方法在基类标签record基础上声明一个派生类的标签record派生类继承基类的所有操作对象（record）和所有的操作（在package中）分别在派生类的record和package中增加操作对象和操作（问题：重置应如何实现？）3.核心思想明确区分类型中值的集合与值上操作的集合。充分利用Ada83的信息隐藏机制。OOPL与OOP范型（paradigm）程序设计语言与它所支持的范型是两个独立的概念。OOPL支持OOP范型，但是由于OOPL的基础是过程式程序设计语言，如C+、Ada95等均从过程式程序设计语言演变而来，因此绝大多数OOPL也支持过程式程序设计范型。编译系统需要考虑和解决的问题：1.定义类与声明实例的机制2.对象的建立与初始化（撤消）3.继承与动态分派（dispatch）（override）4.子类型与继承的区别5.运行时对象与方法的表示6.OO机制的类型系统同样：过程式程序设计语言也可以支持OOP程序设计。问题：Java是否支持过程式程序设计？本章主要内容1.类型与类型系统2.单态的类型检查3.参数多态的类型检查4.特定多态（重载）的类型检查5.类型系统形式化方法简介结 束（2005年4月22日）4.2 类型系统4.2.1 类型表达式 与语法分析首先描述（文法），然后分析（自动机）类似，类型检查也沿用同样的思路：类型系统：描述什么样的类型关系在句子上是合法的；类型检查器：根据类型系统的规定，检查句子的类型。赋给程序各部分的一组规则构成了程序设计语言（编译器）的类型系统。本节的讨论中，类型表达式就是规则的具体表示。基本思想：用类型表达式规定语言结构的类型，并通过表达式的计算确定所有语言结构的类型。4.2.1.1 类型表达式的递归定义 类型表达式可递归定义如下：1.基本类型是类型表达式；2.类型名是类型表达式；3.类型变量的值是类型表达式；4.类型构造器作用于类型表达式的结果是一个类型表达式。程序设计语言的基本类型作为类型表达式 基本类型(简单类型)是类型表达式，例如boolean，character，integer(包括子范围，如1.15、15)，real等等。需要注意类型表达式与程序设计语言中类型声明的区别，例如integer和character类型在C+中分别被声明为int和char。二者的区别可以根据上下文进行区分。void是一个类型表达式，它表示对类型的不关心，或习惯上也称为无类型。type_error是一个类型表达式，它表示类型错，与error在Yacc中的作用十分相似。但是error表示一个语法错误，type_error表示一个语义错误。4.2.1.1 类型表达式的递归定义（续1）类型名与类型变量的值作为类型表达式 类型名是一个类型表达式，例如：type student is record.中student是一个类型表达式。类型变量是一个类型表达式，例如：generictype object is private;package stack is.package int_stack is new stack(integer);object是一个类型变量，不是类型表达式 integer是类型变量的值，是类型表达式。类型构造符 程序设计语言中提供了基本的类型组合方法，可以将简单类型组合为复杂类型，这些类型的组合方法在类型系统中被称为类型构造符，即利用类型构造符构造出复杂的类型表达式。程序设计语言中常见的组合方法有数组、记录、指针等等，它们均可以作为类型表达式中的类型构造符。数组（array）array是一个类型构造符。由于数组有两个基本成分：数组元素的类型T和数组下标的类型I，所以数组的类型可以表示为array(I,T)，即类型构造符array作用于类型表达式I和T的结果是一个类型表达式。积（，Cartesion Products）是一个类型表达式，用于表示若干个类型的并列关系，如参数列表、记录或程序包的分量等。若T1，T2分别是类型表达式，则T1和T2的积T1T2也是一个类型表达式。可以规定具有左结合性质，T1T2T3=(T1T2)T3。类型构造符（续1）记录（record）record是一个类型构造符。记录可以看作是各field（域或字段）的积，而每个字段由名字与类型共同确定，于是记录的类型可以表示为：record（F1F2.Fn），其中Fi=nameifieldi。即record作用于F1F2.Fn的结果是一个类型表达式。指针（pointer）pointer 是一个类型构造符。若T是类型表达式，则pointer(T)是表示类型“指向类型T的对象的指针”的类型表达式。函数（，function）是一个类型构造符。作为一个类型构造符具有特别重要的意义。这说明函数也被看作一个类型，它是定义域到值域的一个映射。设定义域类型为D，值域类型为R，则函数的类型表达式为DR。异或积（，disjunctive products）是一个类型表达式，用于表示若干个类型的其中之一，如记录中变体部分的各分量之间的关系。类型构造符（续2）var x:integer;a:array 1.10 of integer;type row=recordaddress:integer;lexeme:array 1.15 of char;end;var table:array 1.10 of row;var P:row;function max(x:integer,y:integer):integer;function f(a,b:char):integer;union Aint i;char c;double d;例4.11 对于下述Pascal和C+的类型定义语句和数据对象声明语句：类型构造符（续3）变量x是一个整型数，它的类型表达式可以表示为：int。变量a是一个数组，它的下标类型为1.10，数组元素的类型为int，a的类型表达式是类型构造符array作用于下标类型和数组元素类型形成的类型表达式：array(1.10,int)。var x:integer;a:array 1.10 of integer;类型构造符（续4）row是一个类型名，它代表的类型是一个具有两个域的记录，根据记录的类型表达式的构造方法：row=record(addressint)(lexemearray(1.15,char)row一旦被定义就是一个类型表达式，因此变量table的类型表达式可表示为：array(1.10,row)，即数组元素的类型为row。变量P是一个指针类型，它所指向的对象的类型是row，因此P的类型表达式为：pointer(row)。type row=recordaddress:integer;lexeme:array 1.15 of char;end;var table:array 1.10 of row;var P:row;类型构造符（续5）function max(x:integer,y:integer):integer;function f(a,b:char):integer;union A int i;char c;double d;函数的类型是定义域到值域的一个映射，因此函数max的类型表达式为：intintint。函数f的类型表达式为：charcharpointer(int)。若将void引入函数的类型表达式，则Dvoid是没有返回值的函数（在Pascal中被称为过程），voidR是没有参数的函数，而voidvoid是既无参数又无返回值的函数。C+的union结构A也是一个记录类型，但是其特征是三个分量只能取其一，因此A的类型表达式为：record（iintccharddouble）问题：类(class)是否一个类型构造符？如何构造类的类型表达式？4.2.2 类型表达式的图型表示 类型表达式与算术表达式或布尔表达式相似，均是由操作数与操作符（类型构造符）组成，所以用于表示算术表达式或布尔表达式的图型，均可表示类型表达式。如树、图（dag）等。其中叶子表示基本类型，内部节点（包括根）表示类型构造符。显然此树也可以被称为类型表达式的语法树。record address integer lexeme array1.15 char(b)row类型表达式的语法树char char integer pointer(a)f类型表达式的语法树4.3 简单的类型检查 编译时进行的类型检查被称为静态类型检查，它的基本思想是用类型表达式规定语言结构的类型，并通过类型表达式的计算确定所有语言结构的类型。通常的做法是声明时构造类型表达式，引用时检查类型表达式，因此一般的类型化程序设计语言均要求先声明后引用。4.3.1 一个简单的程序设计语言 文法P D;E D D;D|id:TT char|integer|arraynum of T|TE literal|num|id|E mod E|EE|E 其中arraynumof T中，简化了下标类型：1.num。基本类型与类型构造器 基本类型：char、integer、type_error 类型构造器：pointer()、array(array)声明时id类型的确定P D;ED D;DD id:T addtype(entry(id.name),T.type);T char T.type:=char;(AG4.1)|integer T.type:=integer;|T1 T.type:=pointer(T1.type);|arraynumof T1 T.type:=array(num.val,T1.type);4.3.2 表达式的类型检查 当声明语句确定了每个id的类型之后，表达式的类型可作如下检查：E literal E.type:=char;|num E.type:=integer;(AG4.2)|id E.type:=lookup(entry(id.name);|E1 mod E2 T.type:=if E1.type=integer and E2.type=integer then integer else type_error;|E1E2 E.type:=if E2.type=integer and E1.type=array(s,t)then t else type_error;|E1 E.type:=if E1.type=pointer(t)then t else type_error;4.3.3 语句的类型检查 语句的作用是执行一个（或一串）动作，语句本身没有值，也就没有类型。为此，引入void作为语句（statements）的类型，对上述简单的程序设计语言进行扩充，即可对下述语句进行类型检查。S id:=E S.type:=if compatible(id.type,E.type)then void else type_error;|if E then S1 S.type:=if E.type=boolean (AG4.3)then S1.type else type_error;|while E do S1 S.type:=if E.type=boolean then S1.type else type_error;|S1;S2 S.type:=if S1.type=void then S2.type else type_error;问题：if E then S1 else S2的类型检查如何设计？声明与语句类型检查举例：x:integer;if x5 then x:=5PD ;Sx :T if C then Sinteger x 5 x:=E5将将P D;E中的E修改为S.int(int)(int)(int).int.b.void.voidP D;ET integer T.type:=integer;D id:T addtype(entry(id.name),T.type);S id:=E S.type:=if compatible(id.type,E.type)then void else type_error;|if E then S1 S.type:=if E.type=boolean then S1.type else type_error;需要加入哪些产生式和语义规则？4.3.4 函数的类型检查 根据函数类型的定义可知，函数的类型是一个定义域到值域的映射，值域可以是一个类型T，也可以是void，当它是T时，函数调用是一个表达式，否则函数调用是一个语句。将函数的调用引入类型检查，需要做两件事情：如何定义函数，并在定义函数的时候确定其类型；如何调用函数，并在调用时检查函数的类型。函数声明的方法可以有两种形式：1.扩充类型T（教材，理论上）；2.扩充声明语句（程序设计语言，如Pascal等）。将函数作为类型函数作为类型在语法上的描述：D id:T addtype(entry(id.name),T.type);(AG4.4)T T1 T2 T.type:=T1.type T2.type;E E1(E2)E.type:=if E2.type=s and E1.type=st then t else type_error;上述D与T是对函数声明的扩充，E是对函数调用的扩充。T产生式中扩充了函数类型T1 T2，即定义域类型到值域类型的映射。当函数名在D产生式中象变量一样被声明为T类型时，函数的类型表达式就通过addtype被填写进了符号表中。E产生式中扩充了函数调用的语法，其中E1是函数名，E2是实参列表构成的表达式。函数调用时进行上述语义规则所规定的类型检查，若实参的类型为s，函数名的类型为s到t的映射，则显然函数返回值的类型是t，否则发现一个类型错误。Pascal的函数声明与调用 D function id(PS):T addtype(id.entry,PS.typeT.type);(AG4.5)PS id:T addtype(id.entry,T.type);PS.type:=T.type;|PS1;PS2 PS.type:=PS1.typePS2.type;E E1,E2 E.type:=E1.typeE2.type;|E1(E2)E.type:=if E2.type=s and E1.type=st then t else type_error;D产生式中扩充了函数声明，其中PS是形参列表，而T是返回值类型，因此函数名id的类型应该是PS.typeT.type，即形参类型到返回值类型的映射，因此在函数声明时将该类型填写进符号表中，使得id具有了该类型。函数调用时进行检查。注意，无论是形参列表还是实参列表（E1,E2），它们的类型均是所有参数的积。Pascal的函数声明与调用（续1）例4.12 对于的函数声明 function max(a:integer;b:integer):integer和函数调用max(5,8)，类型的确定与检查分别如下。D function id(PS):T addtype(id.entry,PS.typeT.type);PS id:T addtype(id.entry,T.type);PS.type:=T.type;|PS1;PS2 PS.type:=PS1.typePS2.type;声明时确定类型：Dfunction max(PS3 ):T3PS1 ;PS2 integera :T1 b :T2integer integerDfunction max (PS3 ):T3.t=intPS1.t=int;PS2.t=int integera :T1.t=int b :T2.t=intinteger integer.t =intintintintint Pascal的函数声明与调用（续2）被归约的产生式语义规则的计算计算结果T1integerT1.type:=intT1.type=intPS1id:T1PS1.type:=T1.typeaddtype(a,int)PS1.type=int(第一个参数类型是int)T2integerT2.type:=intT2.type=intPS2id:T2PS2.type:=T2.typeaddtype(b,int)PS2.type=int(第二个参数类型是int)PS3PS1;PS2P S 3.t y p e:=PS1.typePS2.typePS3.type=intintT3integerT3.type:=intT2.type=intD f u n c t i o n max(PS3):T3a d d t y p e(m a x,intintint)函数max的类型是intintint具体步骤：Pascal的函数声明与调用（续3）调用时检查类型：E E1,E2 E.type:=E1.typeE2.type;|E1(E2)E.type:=if E2.type=s and E1.type=st then t else type_error;|id E.type:=lookup(entry(id.name);E5E1 (E4 )max E2 ,E35 8E5E1 (E4 )max E2.t=int ,E3.t=int5 8.t=intintint.t=intintint Pascal的函数声明与调用（续4）产生式语义规则的计算计算结果E1maxE1.type:=lookup(entry(max)E1.type =intintintE2numE2.type:=intE2.type=intE3numE3.type:=intE3.type=intE4E2,E3E4.type:=E2.typeE3.typeE4.type=intintE5E1(E4)E5.type:=if E4.type=s and E1.type=st then t else type_error;E5.type=int具体步骤：结 束（2005年4月26日）