第五章类型检查内容摘要：
{ = if == boolean then S1. type else type_error } S S1。 S2 {S. type = if S1. type == void and S2. type == void then void else type_error } 简单类型检查器的说明 类型检查 ——程序 P D。 S {P. type = if S. type == void then void else type_error } 简单类型检查器的说明 类型转换 E E1 op E2 { = if == integer and == integer then integer else if == integer and == real then real else if == real and == integer then real else if == real and == real then real else type_error } 多 态 函 数 为什么要使用多态函数 例：用 Pascal语言写不出求表长度的通用程序 若有下面的类型 type link = cell。 cell = record info : integer。 next : link end。 针对这个类型，可以写出下页的表长函数 多 态 函 数 function length(lptr : link) : integer。 var len : integer。 begin len := 0。 while lptr nil do begin len := len + 1。 lptr := lptr. next end。 length := len end。 计算过程并不涉及 表元的数据类型 但语言的类型系统 使得该函数不能通用 多 态 函 数 例：用 ML语言很容易写出求表长度的程序而不必管表元的类型 fun length (lptr) = if null (lptr) then 0 else length (tl (lptr)) + 1。 多 态 函 数 例：用 ML语言很容易写出求表长度的程序而不必管表元的类型 fun length (lptr) = if null (lptr) then 0 else length (tl (lptr)) + 1。 length ( [―sun‖, ―mon‖, ―tue‖] ) length ( [10, 9, 8 ] ) 都等于 3 多 态 函 数 • 多态函数 – 允许变元的类型有多种不同的情况 – 函数体中的语句的执行能适应变元类型有多种不同的情况（区别于重载的特征） • 多态算符 – 例如： 数组索引 、 函数应用、通过指针间接访问 – 相应操作的代码段接受不同类型的数组、函数等 – C语言手册中关于取地址算符 amp。 的论述是： 如果运算对象的类型是 ‘ … ’ ，那么结果类型是指向 ‘ … ’ 的指针 ” 多 态 函 数 类型变量 length的类型可以写成 .list() integer 允许使用类型变量，还便于讨论未知类型 – 在不要求标识符的声明先于使用的语言中，通过类型变量的使用去确定程序变量的类型 多 态 函 数 • 例 function deref (p)。 begin return p end。 多 态 函 数 • 例 function deref (p)。 对 p的类型一无所知： begin return p end。 多 态 函 数 • 例 function deref (p)。 对 p的类型一无所知： begin return p = pointer( ) end。 多 态 函 数 • 例 function deref (p)。 对 p的类型一无所知： begin return p = pointer( ) end。 deref的类型是 . pointer( ) 多 态 函 数 一个含多态函数的语言 P D。 E 引入类型变量、笛卡 D D。 D | id : Q 儿积类型、多态函数 Q typevariable. Q | T T T ‗‘T | T T | unaryconstructor ( T ) | basictype | typevariable | ( T ) E E (E ) | E, E | id 多 态 函 数 一个含多态函数的语言 P D。 E 引入类型变量、笛卡 D D。 D | id : Q 儿积类型、多态函数 Q typevariable. Q | T T T ‗‘T | T T 这是一个抽象语言 , | unaryconstructor ( T ) 忽略了函数定义的 | basictype 函数体 | typevariable | ( T ) E E (E ) | E, E | id 多 态 函 数 一个含多态函数的语言 P D。 E D D。 D | id : Q Q typevariable. Q | T T T ‗‘T | T T | unaryconstructor ( T ) 一个程序： | basictype deref : . pointer( ) 。 | typevariable q : pointer (pointer (integer))。 | ( T ) deref (deref (q)) E E (E ) | E, E | id 多 态 函 数 类型系统中增加的推理规则 • 环境规则 (Env Var) • 语法规则 (Type Var) (Type Product) | , dom () , | 1, , 2 | 1, , 2 | | T1, | T2 | T1 T2 多 态 函 数 类型系统中增加的推理规则 • 语法规则 (Type Parenthesis) (Type Forall) (Type Fresh) | T | (T ) , | T | .T | .T , , i | , i | [i /] T 多 态 函 数 类型系统中增加的推理规则 • 定型规则 (Exp Pair) (Exp FunCall) (其中 S是 T1和 T3的最一般的合一代换 ) | E1: T1， | E2: T2 | E1, E2: T1 T2 | E1: T1 T2, | E2: T3 | E1 (E2) : S(T2) 多 态 函 数 代换、实例和合一 代换 : 类型表达式中的类型变量用其所代表的类型表达式去替换 多 态 函 数 代换、实例和合一 代换 : 类型表达式中的类型变量用其所代表的类型表达式去替换 function subst (t : type_expression ) : type_expression。 begin if t是基本类型 then return t else if t是类型变量 then return S(t) else if t 是 t1 t2 then return subst(t1) subst(t2) end 多 态 函 数 实例 把 subst函数 用于 t后所得的类型表达式是 t的一个实例，用 S (t)表示。 例子（ s t 表示 s是 t 的实例 ） pointer( integer ) pointer( ) pointer( real ) pointer( ) integer integer pointer( ) 多 态 函 数 下面左边的类型表达式不是右边的实例 integer real 代换不能用于基本类型 integer real 的代换不一致 integer 的所有出现都应该代换 多 态 函 数 合一 如果存在某个代换 S使得 S(t1) = S(t2)， 那么这两个表达式 t1和 t2能够 合一 最一般的合一代换 S • S(t1) = S(t2)； • 对任何其它满足 S(t1) = S(t2)的代换 S， 代换S(t1)是 S(t1)的实例 多 态 函 数 多态函数的类型检查 多态函数和普通函数在类型检查上的区别 (1)同一多态函数的不同出现无须变元有相同类型 apply: o derefo:pointer(o) o apply : i derefi : pointer(i) i q: pointer(pointer(integer)) deref(deref (q ))的带标记的语法树 多 态 函 数 (2)必须把类型相同的概念推广到类型合一 apply: o derefo:pointer(o) o apply : i derefi : pointer(i) i q: pointer(pointer(integer)) deref(deref (q ))的带标记的语法树 多 态 函 数 (2)必须把类型相同的概念推广到类型合一 (3)要记录类型表达式合一的结果 apply: o derefo:pointer(o) o apply : i derefi : pointer(i。阅读剩余 0%
本站所有文章资讯、展示的图片素材等内容均为注册用户上传(部分报媒/平媒内容转载自网络合作媒体)，仅供学习参考。
用户通过本站上传、发布的任何内容的知识产权归属用户或原始著作权人所有。如有侵犯您的版权，请联系我们反馈本站将在三个工作日内改正。