数据类型检查基础知识

June5,2000本资料来源June5,,2000第六章类类型检检查基础知识识类型体制制简单类型型检查器器的说明明类型表达达式的等等价多态函数数June5,,2000类型检查查基础（（1）类型检查查是编译译器的主主要任务务之一数据类型型信息的的计算和和维护程序的语语法结构构的类型型是否和和它的上上下文所所期望的的一致数据类型型是一个数数据对象象以及创创建和操操纵它们们的操作作集合所所组成的的类是数据对对象的一一个重要要属性类型位置值名组件：用用指针值值表示，，并通过过指针的的改变来来修改……June5,,2000类型检查查基础（（2）数据类型型规范的的基本内内容包括括：属性：区区别这个个类型的的数据对对象的属属性值：这个个类型的的数据对对象可能能取的值值操作：定定义对这这个类型型的数据据对象可可能的操操纵的操操作集合合数据类型型的实现现存储：表表示程序序执行过过程中在在计算机机存储器器中的数数据类型型的数据据对象的的存储表表示操作的实实现：根根据操纵纵数据对对象的存存储表示示的特定定算法或或过程来来表示数数据类型型所定义义的操作作的方式式数据类型型的语法法表示属性：通通过声明明或类型型定义来来体现值：表示示成文字字或已定定义的常常量操作：可可以通过过特殊符符号或内内部过程程（函数数）实现现，也可可以隐式式地通过过其它语语言元素素的组合合实现June5,,2000类型检查查基础（（3）基本数据据类型基本知识识：基本数据据对象只只有单一一的数据据值，这这种数据据对象以以及定义义在其上上的不同同操作组组成的类类称为基基本数据据类型种类：整整型、实实型、字字符型、、布尔型型等不同的语语言对上上述基本本类型的的表示可可能是截截然不同同的基本数据据类型的的规范：：属性：数数据对象象的基本本属性（（如类型型和名字字等）在在其生存存期中通通常是不不变的值：类型型决定了了它可取取的可能能值的集集合，基本数据据类型定定义的值值的集合合通常是是一个有有界的有有序集，，对任意意两个不不同的值值都可以以比较它它们的大大小June5,,2000类型检查查基础（（4）操作：种类：基本操作作：作为为语言定定义的一一部分程序员定定义的操操作：作作为类定定义的一一部分以以子程序序或方法法声明的的操作基本数据据对象的的实现存储表示示：通常用所所需的存存储块的的大小、、块内属属性和数数据值的的布局来来描述数据对象象的表示示一般和和它在内内存中的的位置是是无关的的数据对象象的地址址是指他他们所占占用的存存储块的的第一个个字或字字节的地地址从效率考考虑：由由编译器器决定数数据属性性，如C语言从灵活性性考虑：：数据对对象的属属性可以以作为运运行时该该数据对对象的一一部分以以描述符符的形式式存储，，通过软软件模拟拟June5,,2000类型检查查基础（（5）操作的实实现：直接实现现成硬件件操作如整型的的加、减减法等软件的实实现：作为函数数或过程程子程序序，如平平方根作为嵌入入代码序序列这两种实实现的不不同复合数据据类型字符串指针文件顺序文件件文本文件件直接访问问文件索引文件件June5,,2000类型检查查基础（（6）用户定义义的数据据类型结构化的的数据规范：成员的数数目每个成员员的类型型用来选择择成员的的名字最多成员员数目成员的组组织操作对数据结结构类型型上的定定义域和和值域的的规定和和基本类类型的方方法差不不多要增加一一些新的的重要操操作：成员选择择操作全数据结结构操作作成员的插插入和删删除建立和消消除数据据结构June5,,2000类型检查查基础（（7）抽象数据据类型数据抽象象，把封封装的概概念推广广到程序序员自定定义的数数据，抽抽象的数数据类型型是数据对象象的集合合，一般般使用一一个或多多个类型型定义在所定义义的数据据对象上上的抽象象操作的的集合将上述两两个集合合封装：：新的数据据类型的的使用者者不能直直接操作作这个类类型的数数据对象象，只能能通过已已定义的的操作来来使用和和操作数数据对象象信息隐藏藏继承多态June5,,2000类型检查查基础（（8）声明将程序执执行时所所需的数数据对象象的名字字和类型型的信息息传给语语言翻译译器的程程序语句句声明可以以表明数数据对象象的生存存期声明的种种类显式声明明隐式声明明如果数据据对象是是常量，，声明可可以指定定它的值值，变量量可以指指定初始始值声明也可可以指明明具体存存储的一一些信息息等，如如cobol中存储形形式的声声明操作的声声明：操操作形式式声明的目目的存储表示示的选择择存储管理理多态操作作类型检查查June5,,2000类型体制制（1））类型表达达式：语言结构构的类型型可以用用类型表表达式指指称类型构造造器在一个已已经说明明类型的的集合上上创建新新的类型型数组、记记录、指指针等类型表达达式的形形式定义义基本类型型是类型型表达式式一般有boolean,char,integer,real,type_error,void其中type_error表示类型型检查期期间的错错误void表示没有有值，用用于语句句的检查查June5,,2000类型体制制（2））类型表达达式可以以命名，，类型名名是类型型表达式式如记录名名或结构构名可以以作为类类型表示示用于变变量的类类型声明明1)名字直接接用struct或union等构造器器关联structHchain{intobjp;intnext;};structHchaindimchain[100]];2)类型说明明（typedeclaration），用typedef机制等typedefstruct{{intobjp;intnext;}Hchain;Hchaindimchain[100];;June5,,2000类型体制制（3））类型名的的管理：：类型表的的构造是一种特特定的符符号表类型的作作用域类似于变变量的作作用域类型名与与类型表表达式的的关联类型名可可以出现现在类型型表达式式中类型的递递归定义义如下的定定义在C语言中是是不合法法的，因因为在递递归使用用类型名名intBST时，没有有确定所所需要的的存储空空间大小小structintBST{intisNull;intval;structintBST left,,right; }但通过指指针是可可以解决决上述问问题的：：structintBST *left,**right;June5,,2000类型体制制（4））类型构造造器作用用于类型型表达式式的结果果仍是类类型表达达式，类类型构造造器包括括：数组：如果T是类型表表达式，，则array（I，T））是成分类类型为T和下标集集合为I的数组的的类型表表达式索引类型型是有限限制的，，可以决决定索引引的前后后次序，，I通常是一一个整数数区间数组通常常根据索索引从小小到大分分配连续续的存储储空间1）一维维数组2）多维维数组typedefenum{{red,green,,blue}}color;array[0...9,color]]ofinteger如何存放放？a)行主序（（行优先先等）：：在内存存中的存存放次序序是a[0,red]],a[0,green],,a[[0,,blud]],a[1,red]],a[1,green],,…b)列主序（（列优先先等）：：在内存存中的存存放次序序是a[0,red]],a[1,red]],……,a[9,red],a[0,green]],……开放索引引数组：：在声明明时没有有说明索索引区间间，常见见于参数数June5,,2000类型体制制（5））积：如果T1和T2是类型表表达式，，则它们们的笛卡卡儿积T1×T2也是类型型表达式式，假定定×是左左结合的的ML语言中的的类型定定义记录（结结构）：：从某种意意义上说说是它各各域类型型的积记录的各各个域是是有名字字的（与与积的区区别）对记录中中某个域域的引用用必须与与记录关关联记录类型型构造器器record作用于域域名和它它们的类类型组成成的元组组，形成成类型表表达式，，进而可可以完成成记录的的类型检检查typerow==recordaddress:integer;lexeme:: array[1...15]ofcharend;;vartable::array[1...101]]ofrow;;声明类型型名row代表类型型表达式式：record((address×integer)×(lexeme×array(1...15,,char))))))June5,,2000类型体制制（6））指针：如果T是类型表表达式，，则pointer（T）是表示类类型“指指向类型型T的对象的的指针””的类型型表达式式指针的值值是一个个存储器器地址，，其中保保存着其其基类型型的值通常指针针被看成成是数字字类型，，可以对对其进行行算术运运算指针的解解除引用用(dereference)操作符：：在C语言中，，如果有有int**p，则p表示对指指针的引引用，**p表示对指指针指向向变量的的引用，，此时**解除指指针变量量的引用用函数：定义域类类型D到值域类类型R的映射，，这样的的函数的的类型表表达式是是D→R1）mod函数，int×int→→int2）在pascal中的声明明：functionf(a,b:char)::↑integerchar×char→pointer(integer)函数的返返回值：：一般受受到限制制，但在在一些语语言中（（如ML），，函数的返返回值可可以式任任意类型型的对象象June5,,2000类型体制制（7））类型表达达式可以以包含变变量，变变量的值值是类型型表达式式利于讨论论未知类类型类型表达达式的表表示可以简便便地用图图表示内部结点点表示类类型构造造器叶结点表表示基本本类型、、类型名名或类型型变量June5,,2000类型体制制（8））类型体制制：定义：把把类型表表达式指指派到各各个部分分的一组组规则类型检查查器实现现类型体体制同一个语语言的不不同编译译器或处处理器可可能使用用不同的的类型体体制数组参数数是否作作为变元元某些数据据类型的的存储方方式June5,,2000类型体制制（9））静态和动动态的类类型检查查：由编译器器完成的的检查是是静态检检查所需要的的信息通通常由程程序员提提供的声声明和其其它语言言结构提提供每个操作作的参数数和结果果的数目目、顺序序和数据据类型每个变量量所命名名的数据据对象的的类型：：和变量量名相关关联的数数据对象象的类型型在程序序执行过过程中必必须是不不变的每个常数数数据对对象的类类型静态类型型检查的的特点对所有程程序语句句中的所所有操作作和所有有执行路路径不再需要要对类型型错误进进一步测测试不需要数数据对象象的类型型标签和和动态类类型检查查程序运行行速度和和存储使使用效率率得到很很大的改改善June5,,2000类型体制制（10）可以由硬硬件提供供支持程序易于于调试影响语言言的很多多特性：：声明、数数据控制制结构以以及子程程序的单单独编译译静态类型型检查的的缺点在某些情情况下，，不能进进行静态态类型检检查如数组访访问越界界的检查查解决方法法：借助动态态类型检检查，代代价太高高，可能能很少检检查到的的类型标标签也要要存储在在数据对对象中对未检查查的操作作听其自自然，可可能引起起错误June5,,2000类型体制制（11）目标程序序运行时时完成的的类型检检查是动动态检查查实现的基基础：在在每个数数据对象象中保存存一个表表明该对对象数据据类型的的类型标标签动态类型型检查的的优点程序设计计灵活不需要声声明和一个变变量名绑绑定的数数据对象象的类型型在程序序执行时时可以按按需改变变动态类型型检查的的缺点程序难于于调试动态执行行的路径径不能覆覆盖所有有的程序序路径，，所以测测试不完完全需要在程程序执行行过程中中保存类类型信息息很少有底底层硬件件的支持持，通过过软件实实现，程程序的执执行速度度降低不不少June5,,2000类型体制制（12）健全的类型体体制由于允许许静态地地确定这这些错误误是否在在程序运运行时发发生，不不需要动动态检查查类型错错误，称称为健全的类型体体制强类型化化如果一个个语言的的编译器器可以保保证它所所接受的的程序不不会有运运行时的的类型错错误，则则称这个个语言是是强类型型的很少有语语言是强强类型的的如C语言，数数组的引引用、两两个short型变量操操作的结结果可能能不是short型的等可以通过过限制类类型之间间的转换换，近似似地认为为是强类类型的，，如C语言June5,,2000类型体制制（13）错误恢复复：不如语法法错误直直观错误的报报告：至少要有有错误的的性质和和位置类型错误误的抑制制错误的恢恢复与类型体体制息息息相关强制类型型转换June5,,2000简单类型型检查器器的说明明（1））一个简单单语言每个标识识符的类类型必须须在它使使用前先先声明语言的定定义：P→D;;ED→D;;D||id::TT→char||integer||array[[num]]ofT||↑↑TE→literal||num||id||EmodE||E[[E]]||E↑这个语言言产生的的一个程程序：key::integer;keymod19999June5,,2000简单类型型检查器器的说明明（2））语言的简简单分析析两个基本本类型charinteger数组类型型的下标标都从1开始array[256]ofchar的类型表表达式是是array(1...256,,char))指针类型型↑integer的类型表表达式是是pointer(integer)id↑中的↑↑表示解解除指针针引用引入一个个新的基基本类型型：type_error，用于报告告错误June5,,2000简单类型型检查器器的说明明（3））语言的声声明部分分的翻译译方案P→D;;ED→D;;DD→id:T{{addtype(id.entry,T.type)}}T→char{{T.type:==char}}T→integer{{T.type:==integer}}T→array[num]ofT1{T..type::=array(num..val,T1.type)}}T→↑T1{T..type::=pointer(T1.type)}}在P→D;;E中,D出现在E之前，可可以保证证所有已已声明的的标识符符的类型型在由E产生的表表达式检检查之前前就已保保存下来来这个翻译译方案可可以方便便地实现现June5,,2000简单类型型检查器器的说明明（4））表达式的的类型检检查E的综合属属性type给出了E产生的表表达式的的类型表表达式表达式类类型检查查的翻译译方案：：E→literal{{E.type:==char}}E→num{{E.type::=integer}}E→id{{E..type::=loopup((id.entry)}}E→E1modE2{E..type::=ifE1.type==integerandE2.type==integerthenintegerelsetype__error}}E→E1[E2]{{E.type:==ifE2.type==integerandE1.type==array(s,,t)thentelsetype__error}}E→E1↑{{E..type::=ifE1.type==pointer((t))thentelsetype__error}}June5,,2000简单类型型检查器器的说明明（5））语句的类类型检查查增加一个个特殊的的类型void用于语句句检查由于语句句没有类类型，所所以如果果检查正正确，指指派语句句的类型型为void否则，指指派语句句的类型型为type_error对简单的的语言的的修改：：P→D;;SD→D;;D||id::TT→char||integer||array[[num]]ofT||↑↑TS→id:==E||ifEthenS||whileEdoS||S;SE→literal||num||id||EmodE||E[[E]]||E↑June5,,2000简单类型型检查器器的说明明（6））关于语句句的类型型检查的的翻译方方案：S→id:==E{{S.type::=ifid.type==E.typethenvoidelsetype__error}}S→ifEthenS1{S..type::=ifE.type=booleanthenS1.typeelsetype__error}}S→whileEdoS1{S..type::=ifE.type=booleanthenS1.typeelsetype__error}}S→S1;S2{S..type::=ifS1.type==voidandS2.type==voidthenvoidelsetype__error}}type_error的给出可可能仍然然不足够够，可以以进一步步报告类类型不匹匹配的性性质和位位置June5,,2000简单类型型检查器器的说明明（7））函数的类类型检查查函数类型型声明T→T1’→’T2{T..type::=T1.type→T2.type}}函数声明明E→E1(E2){E..type::=ifE2.type==sandE1.type==s→→tthentelsetype_error}上述简单单的文法法可以推推广到更更复杂的的情况多个变元元函数做变变元June5,,2000简单类型型检查器器的说明明（8））类型转换换语言类型型规则的的一个常常用扩充充是允许许混合类类型的算算术表达达式，如如表达式式3+2.5此时，如如果类型型规则不不做扩充充，对不不匹配的的类型进进行操作作时，要要报错上述扩充充允许强强制类型型转换：：(float)3+2..5类型转换换的种类类：不同同的语言言使用不不同的类类型转换换方式显式类型型转换：：由程序员员显式地地调用内内置的转转换函数数隐式类型型转换当类型不不匹配时时自动调调用强制制类型转转换June5,,2000简单类型型检查器器的说明明（9））类型转换换的基本本原则：：不丢失信信息类型的提提升一般般不会丢丢失信息息，如short转换为int，，或int转换为float等float转换为int可能会丢丢失信息息一个语言言是否使使用强制制类型转转换？不允许强强制类型型转换任何类型型失配都都是错误误，如Ada、、Pascal允许强制制类型转转换类型失配配时寻找找合适的的类型转转换找不到合合适的类类型转换换时，再再报错强制类型型转换可可能隐藏藏了原本本在编译译时刻可可以知道道的程序序设计错错误June5,,2000简单类型型检查器器的说明明（10）从整型到到实型的的类型检检查规则则：E→num{{E.type:=integer}E→num.num{{E.type:=real}E→id {E.type:=lookup(id..entry)}E→E1opE2{E.type:=ifE1.type=integerandE1.type=integerthenintegerelseifE1.type=integerandE1.type=realthenrealelseifE1.type=realandE1.type=integerthenrealelseifE1.type=realandE1.type=realthenrealelsetype_error}June5,,2000类型表达达式的等等价（1）类型等价价类型检查查经常要要面临的的问题：：两个类型型表达式式是否表表示相同同的类型型structt1{{structt2{{intx;intx1;inty[100]];inty1[[100];};}};类型等价价和类型型表示是是相互影影响的类型等价价的常用用形式结构等价价名字等价价在类型等等价中，，递归定定义如何何处理June5,,2000类型表达达式的等等价（2）类型表达达式的结结构等价价结构等价价的定义义两个类型型表达式式是同样样的基本本类型或两个类类型表达达式是同同样的类类型构造造器作用用于结构构等价的的类型即两个类类型表达达式是完完全相同同的如integer只等价于于integer，pointer((integer)只等价于于pointer(integer))等当类型表表达式仅仅由类型型构造器器作用于于基本类类型组成成时，可可以使用用这种等等价的概概念在实际实实现时可可能要放放宽限制制，如参参数数组组的界可可以不考考虑June5,,2000类型表达达式的等等价（3）结构等价价的测试试，两个个类型表表达式s和tfunctionsequiv((s,,t)::boolean;beginifs和t是相同的的基本类类型thenreturntrueelseifs==array(s1,s2)andt=array(t1,t2)thenreturnsequiv(s1,t1)andsequiv((s2,t2)elseifs==s1×s2andt==t1×t2thenreturnsequiv(s1,t1)andsequiv((s2,t2)elseifs==pointer(s1)andt=pointer(t1)thenreturnsequiv(s1,t1)elseifs==s1→s2andt==t1→t2thenreturnsequiv(s1,t1)andsequiv((s2,t2)elsereturnfalseendJune5,,2000类型表达达式的等等价（4）数据类型型结构等等价的例例子两个数组组是等价价的当且且仅当它它们有相相同的大大小和元元素类型型两个结构构是等价价的当且且仅当它它们有相相同的元元素，并并且元素素有相同同的名字字和顺序序结构中，，元素的的顺序是是重要的的如果不考考虑数组组的界，，则数组组等价的的测试可可以重写写为：如果有：：s=array((s1,s2)t=array((t1,t2)测试算法法中的第第4和第第5行改改写为：：elseifs==array(s1,s2)andt=array(t1,t2)thenreturnsequiv(s2,t2)June5,,2000类型表达达式的等等价（5）类型表达达式的名名字等价价类型表达达式的名名字在某些语语言中类类型是可可以命名名的如果有下下述的Pascal的声明typelink==↑↑cell;varnext:link;last:link;p:↑↑cell;q,r:↑↑cell;next,last,p,q,r是否有相相同的类类型？这依赖于于实现，，因为Pascal中没有定定义术语语“相同同的类型型”类型名可可以出现现在类型型表达式式中只有有基本类类型可以以出现的的地方June5,,2000类型表达达式的等等价（6）类型表达达式的名名字等价价把类型名名看成一一个可区区别的类类型两个类型型表达式式名字等等价当且且仅当这这两个类类型表达达式的名名字完全全相同在名字等等价下，，上例中中，next和last有相同的的类型（（link），而p,q,r有相同的的类型（（pointer(cell))）与结构等价价的不同同在结构等等价中，，类型名名字由它它们定义义的类型型表达式式代替，，当所有有的名字字替换后后，两个个类型表表达式变变成结构构等价的的类型表表达式，，则它们们结构等等价如果类型型没有显显式地与与一个名名字关联联为这类类类型每个个隐式地地建立一一个唯一一的类型型名此时，上上例中，，q,r有相同的的类型（（nqr）），而p与q有不同的的类型（（np）June5,,2000类型表达达式的等等价（7）类型表达达式的两两种等价价的比较较名字等价价的缺点点每个赋值值语句中中的每个个对象必必须有一一个类型型名，不不允许有有匿名类类型作为参数数传递的的数据对对象类型型，不允允许在子子程序中中再次定定义，需需要全局局类型定定义结构等价价的缺点点两个类型型结构等等价的确确切定义义：如果果两个结结构等价价的结构构类型中中各个域域的名字字必须相相同吗？？域的顺顺序？程序员声声明的两两个变量量有不同同的类型型，但它它们可能能在结构构上是等等价的，，静态检检查可能能无法发发现一些些类型不不相容的的操作等等错误判断算法法开销比比较大June5,,2000类型表达达式的等等价（8）名字等价价的测试试，两个个类型表表达式s和tfunctionsequiv((s,,t)::boolean;beginifs和t是相同的的基本类类型thenreturntrueelseifs和t是类型名名thenreturns==telsereturnfalseend名字等价价的测试试也可以以通过构构造类型型图来实实现每当看见见类型构构造器或或基本类类型对应应，构造造一个新新的结点点每看见一一个新的的类型名名，就构构造一个个叶结点点记录名字字引用的的是哪个个类型表表达式June5,,2000类型表达达式的等等价（9）类型表示示中的环环类型的递递归定义义如链表、、树等，，在类型型定义中中要引用用自身类型名起起重要的的作用例子：structcell{{intinfo;structcell**next;}June5,,2000类型表达达式的等等价（10）当碰到记记录构造造器时，，结构等等价的测测试停止止，被比比较的类类型或者者由于它它们有同同样的命命名记录录类型而而等价，，或者不不等价June5,,2000函数和算算符的重重载（1）重载符号号含义的确确定：依依赖于上上下文算术算符符的重载载：大多多数语言言中算术术算符是是重载的的2+3，，整型加加法2+3..65，，实型加加法在FORTRAN90中，如果果有realA((100),B(100))，则A+B是合法的的，向量量加法，，表示两两个数组组的对应应元素间间分别进进行加法法在FORTRAN语言中，，“（））”是是重载的的如果有realA((100)和integeri的声明，，则A(i)表示数组组元素的的引用如果有functionA(……)的声明，，则A(i)表示函数数的调用用，i是实在参参数June5,,2000函数和算算符的重重载（2）重载的消消除，也也称为算算符的鉴鉴别如果重载载的符号号在引用用点的含含义可以以唯一确确定，则则称为““重载的的消除””2+3+3.65因为是左左结合的的，先完完成第一一个加法法“+”，此时时是一个个整型加加法，在在完成第第二个加加法“+”，此时时是一个个实型加加法在C语言中，，要对第第一个加加法的类类型进行行提升June5,,2000函数和算算符的重重载（3）子表达式式的可能能类型集集合仅看函数数的变元元无法完完全消除除重载单看一个个子表达达式，可可能得到到的是一一个可能能类型的的集合例：在Ada中，算符符*的标标准解释释是：integer×integer→integer如果加入入如下的的声明：：function““*”((i,,j::integer)returncomplex;;function““*”((i,,j::complex)returncomplex;;此时，**的可能能类型包包括：integer×integer→integerinteger×integer→complexcomplex×complex→complex对于表达达式2**(3**5)，，子表达达式3**5的类类型是整整型，而而对于表表达式((3*5)*z，如果z是复型，，则3**5的类类型是复复型June5,,2000函数和算算符的重重载（4）表达式类类型检查查规则的的修改幻灯片32中，，一个表表达式只只能有唯唯一的类类型修改：允允许一个个表达式式对应一一个类型型集合以函数为为例：产生式语语义义规则E’→EE’.types:=E.typesE→idE.types:=lookup(id..entry)E→E1(E2)E.types:={{t|E2.types中存在一一个s，使得s→t属于E1.types}如果函数数的可能能类型集集合为空空，则可可以作为为通知类类型错误误的条件件June5,,2000函数和算算符的重重载（5）此时，子子表达式式的可能能类型集集合是{{integer,complex}，它的唯一一类型的的确定要要考虑其其出现的的上下文文环境June5,,2000函数和算算符的重重载（6）缩小可能能类型的的集合在一些情情况下，，完整的的表达式式要求有有唯一的的类型根据上下下文，缩缩小每个个表达式式的类型型选择，，直至唯唯一如果最终终仍然不不能得到到唯一的的类型，，则报告告类型错错误修改幻灯灯片46的语法法制导定定义，增增加继承承属性unique产生式语语义义规则E’→EE’.types:=E.typesE.unique:=ifE’.types={t}thentelsetype_errorE’.code:=E.codeE→idE.types:=lookup(id..entry)E.code:=gen(id.lexeme‘:’E.unique)E→E1(E2)E.types:={{t|E2.types中存在一一个s，使得s→t属于E1.types}t:=E.uniqueS:={{s|s∈E2.typesands→t∈E1.types}E2.unique:=ifS={s}thenselsetype_errorE1.unique:=ifS={s}thens→telsetype_errorE.code:=E1.code|||E2.code|||gen(‘apply’‘‘:’E.unique)June5,,2000函数和算算符的重重载（7）上述语法法制导定定义的解解释如果函数数E1(E2)返回类型型t，那么可以以找到类类型s，它对变元元E2是可行的的，同时时s→t对该函数数是可行行的对语法树树的两次次深度优优先遍历历实现上上述语法法制导定定义第一遍，，属性types的自下而而上综合合第二遍，，属性unique的自上而而下传播播code在从结点点返回时时进行综综合属性性计算June5,,2000多态函数数（1））变元类型型的多样样性普通函数数的一个个变元只只能有唯唯一的类类型函数体中中的语句句在固定定类型的的变元下下执行多态函数数允许一一个变元元有不同同的类型型函数体中中的语句句可以在在不同类类型的变变元下执执行算符也可可以是多多态的例：内部定义义的算符符通常是是多态的的数组索引引、函数数作用、、指针操操作等算术运算算Ada中的类属属函数是是多态的的在很多语语言中可可以定义义多态函函数June5,,2000多态函数数（2））为什么要要使用多多态函数数一些算法法便于实实现操作于某某种数据据结构，，但不必必顾及其其成分类类型在Pascal中实现链链表长度度的计算算：必须须声明info域的类型型type link==↑cell;cell=recordinfo:integer;next:linkend;;functionlength((lptr::link)::integer;varlen:integer;beginlen::=0;whildlptr<>>nildobeginlen::=len+1;lptr:==lptr↑↑.nextend;;length::=lenEnd;;June5,,2000多态函数数（3））利用多态态函数实实现上述述算法不必考虑虑info域的类型型，算法法只关心心该关心心的在ML中实现链链表长度度的计算算：Funlength(lptr))=typeifnull(lptr))then0elselength(tl((lptr))))+1;考虑下面面的两个个例子：：Length(([““sun”,,“mon””,““tue”]]);;Length(([10,,9,8]])ML的算法对对这两个个例子都都可以直直接进行行计算Pascal的算法对对第二个个例子可可以直接接进行计计算，而而对一个个例子要要修改算算法June5,,2000多态函数数（4））类型变量量：用变变量表示示类型在不要求求先声明明后使用用的语言言中，类类型变量量可以检检查标识识符使用用的一致致性如果同一一个未声声明的程程序变量量的不同同出现作作为不同同的类型型属性的的变量使使用，则则可以报报告使用用不一致致的错误误如果同一一个未声声明的程程序变量量的不同同出现使使用的类类型属性性的是唯唯一的，，则可以以保证使使用的一一致性，，并由此此得到变变量的类类型属性性类型推导导：从语言结结构的使使用方式式推导其其类型June5,,2000多态函数数（5））例：类型型推导技技术在Pascal和C语言中的的应用：：typelink==↑↑cell;proceduremlist((lptr::link;procedurep);;beginwhilelptr<>>nildobeginp(lptr);;lptr:==lptr↑↑.nextendend参数p是一个过过程，在在第一次次出现时时没有给给定参数数，所以以不知道道参数的的个数和和类型在p第二次出出现时，，从表达达式p(lptr)中可以推推导出p的类型必必须是：：link→void对于过程程mlist的调用，，如果对对应于p的实参的的类型不不满足上上述要求求，则是是一个错错误June5,,2000多态函数数（6））类型推导导技术与与类型检检查的关关系：有很多共共同的地地方，都都要处理理包含变变量的类类型表达达式例：多态态函数deref的类型functionderef(p));beginreturnp↑end;;在p的第一次次出现，，由于对对p的类型不不知道，，因而用用类型变变量β代表它的的类型在p的第二次次出现，，由于↑的出现，，知道p必是指向向某个未未知类型型α的指针，，所以β=pointer(α)，所以p↑的类型是是α所以函数数deref的类型表表达式是是：对于任意意类型α，pointer(α)→αJune5,,2000多态函数数（7））一个含多多态函数数的语言言全称量词词的引入入为了描述述“不同同类型””，引入入全称量量词前面的deref类型表达达式：全称量词词所作用用的类型型变量称称为由它它约束检查多态态函数的的语言的的文法P→D;;ED→D;;D||id::QQ→T→T’’→’’T|T×T|unary_constructor(T)|basic_type|(T))E→E((E))||E,,E||idJune5,,2000多态函数数（8））多态函数数的类型型检查与与普通函函数的类类型检查查的区别别同一表达达式中的的多态函函数的不不同出现现不需要要变元有有相同的的类型类型等价价概念的的不同，，通过““合一””判定类类型是否否等价下图中，，如果用用pointer(integer))代替αi，则pointer(αi)和pointer(pointer((integer)))结构等价价两个子表表达式合合一的结结果的记记录通常，类类型变量量可以出出现在几几个类型型表达式式中，如如果s和s’的合一使使得变量量α代表类型型t，则在类型型检查的的过程中中α必须继续续代表tJune5,,2000多态函数数（9））代换、实实例和合合一代换：将类型表表达式中中的类型型变量用用其所代代表的类类型表达达式去替替换用代换S去替换表表达式t中所有类类型变量量的函数数：functionsubst(t::type__expression)):type_expressionbeginift是基本类类型thenreturntelseift是变量thenreturnS(t))elseift是t1→t2thensubst(t1)→subst(t2)end为了方便便，用S(t))表示subst作用于t后所得的的类型表表达式，，这个结结果S(t))叫做t的实例June5,,2000多态函数数（10）如果代换换S对变量α没有指定定表达式式，则假假定S(α)是α，即S是这种变变量的恒恒等映射射例：用s<t表示s是t的实例pointer(integer))<pointer(α)pointer(real))<pointer(α)integer→integer<<α→αpointer(α)<βα<β下面左边边的类型型表达式式不是右右边的实实例integerreal (代换不能能用于基基本类型型)integer→realα→α(α的代换不不一致))integer→αα→α(α的所有