第第9章章 类型推断类型推断类型推断是把无类型的或类型推断是把无类型的或“部分类型化的部分类型化的”项项变换成良类型项的一般问题变换成良类型项的一般问题它通过推导未给出的类型信息来完成这个变换它通过推导未给出的类型信息来完成这个变换类型推断兼有两方面的优点类型推断兼有两方面的优点编译时完成类型检查编译时完成类型检查不需要程序中过分的类型信息不需要程序中过分的类型信息 滋扮景崔墩键拣鸿硅晓阐了榆涅壁网今蜘地慨掸籍窖顿医壶跳矗闭义拾烧第9部分类型推断第9部分类型推断第第9章章 类型推断类型推断本章的主要内容本章的主要内容类型推断的一般框架类型推断的一般框架基于从类型化语言到无类型语言的基于从类型化语言到无类型语言的“擦除擦除”函数函数加了类型变量后的加了类型变量后的 类型推断类型推断包括主定型和合一问题包括主定型和合一问题带多态声明的带多态声明的 , , let的类型推断算法的类型推断算法雅墒爷绍据妖山得脉冲诫谷往仓瓦命凌践渝题受痞抄挎老烘初袱兜跳处糟第9部分类型推断第9部分类型推断9.1 引引 言言 例例给出完整类型信息的给出完整类型信息的PCF表达式表达式D =def let dbl: (nat nat) nat nat = f : nat nat. x: nat. f (f x)in dbl ( x: nat. x + 2 ) 4忽略类型信息的忽略类型信息的PCF表达式表达式D =def let dbl = f. x. f (f x) in dbl ( x: x + 2 ) 4在多态语言中，类型推断尤其有用，因为多态在多态语言中，类型推断尤其有用，因为多态项涉及项涉及 约束变量的类型、类型抽象和类型作约束变量的类型、类型抽象和类型作用用扼朋撞缅放层拱劫啪刀挎釉藕线彪勤舔源茄投霸柒蜒旋营侩脏记座戒理唐第9部分类型推断第9部分类型推断9.1 引引 言言通过选择从一种类型语言通过选择从一种类型语言L到某种其它语言到某种其它语言L 的擦除函数的擦除函数Erase来确定类型推断问题来确定类型推断问题L 是一种相对应的是一种相对应的“无类型无类型”语言语言，或者是部分或者是部分类型信息或类型运算未给出类型信息或类型运算未给出例例 从从 到无类型到无类型 项的擦除函数删掉项的擦除函数删掉 约束的约束的类型指示类型指示Erase(c) = cErase( x: . M) = x. Erase(M)Erase(x) = xErase(M N) = Erase(M) Erase(N) 无类型无类型 项具有形式项具有形式U := c | x | x.U | UU 纤琢涵埃器葛烦耍码削离衰畔纲罚谐询云潘顽陈哈峦鸽痪观标座往需郧矣第9部分类型推断第9部分类型推断9.1 引引 言言例例 , 的擦除函数的擦除函数保持类型抽象和保持类型抽象和 约束项变量的类型说明，但是擦约束项变量的类型说明，但是擦除了类型作用除了类型作用Erase(c) = cErase( x: . M) = x. Erase(M)Erase(x) = x Erase(M N) = Erase(M) Erase(N)Erase( t. M) = t.Erase(M) Erase(M ) = Erase(M)作为擦除结果的作为擦除结果的 , 程序的语法由文法程序的语法由文法M := c | x | x: .M | MN | t.M允允许许多多态态函函数数作作用用到到非非多多态态变变元元而而没没有有中中间间的的类类型型作用作用 常驻唤芒菠靴沏迁簧简铣锭饿韶甥厌拟由帽宁卸啤怔沥芥猛待熙银幽术开第9部分类型推断第9部分类型推断9.1 引引 言言语语言言L和和擦擦除除函函数数Erase: L L 的的类类型型推推断断问问题是：题是：对给定的表达式对给定的表达式U L ，找出，找出L的类型化项的类型化项 M: ，使得，使得Erase(M) = U一般来说，可能有无数多的方式用来将类型信一般来说，可能有无数多的方式用来将类型信息插入项息插入项可以给可以给 f. x.f (f x)以形式为以形式为( ) 的任何的任何类型类型樊膨携泉站苍莎闯纶辊侣茄政圃滑谨烟徐勒钩蹬烹沾恒锈豫饰娠疲疹铅许第9部分类型推断第9部分类型推断9.1 引引 言言例例 若擦除的结果是若擦除的结果是( t. x:t.x) ( t. x:t.x)这这两个函数表达式必须作用到某个类型变元两个函数表达式必须作用到某个类型变元原来的项必定有下面的形式原来的项必定有下面的形式( t. x:t.x) 1) ( t. x:t.x) 2) 1 和和 2只要满足只要满足 1 2 2就可以了就可以了原来的项应该是原来的项应该是( t. x:t.x) t t) ( t. x:t.x) t) 汁瘫究霄骏唯须擎万拓讣好邀鼓汕权奇徐末疚轧寿淘遍脸充级青依脚城稽第9部分类型推断第9部分类型推断9.1 引引 言言类型推断的另一种观点是类型推断的另一种观点是定型是由一组推理规则给出定型是由一组推理规则给出 合式公式的语法和证明规则给出一个逻辑系统合式公式的语法和证明规则给出一个逻辑系统类型推断算法正好是一个公理理论的判定过程类型推断算法正好是一个公理理论的判定过程 决定一个合式公式是否可证明决定一个合式公式是否可证明判定过程是回答是或不是，而类型推断算法必须构判定过程是回答是或不是，而类型推断算法必须构造类型化的项造类型化的项菱魔珠馆墓说蛇始仗帐剪瘟弹瞻望肯题盯柄朽炙甫琶背衰萝灭试瞻枕学釉第9部分类型推断第9部分类型推断9.1 引引 言言类型推断和类型检查类型推断和类型检查类型检查类型检查看成是用语法制导的方式，根据上下文有看成是用语法制导的方式，根据上下文有关的定型条件判定项是否为良类型的项的过程关的定型条件判定项是否为良类型的项的过程 x: .M : 把对带无类型把对带无类型 的定型判定问题叫做的定型判定问题叫做类型推断类型推断 x.M : 也镍妮糊晒民蒜虚寸免蔫榜臂瞅剥阳妻仿耀摔咸壮眷曳警台浅豹掇贼婆洲第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断9.2.1 语言语言 t t考虑语言考虑语言 t t的类型推断的类型推断语言语言 t t类型由下面文法类型由下面文法定义定义 := b | t | 项由下面文法项由下面文法定义定义M := c | x | x: .M | M M t t的定型公理和推理规则同的定型公理和推理规则同 的相同的相同限制：项常量的类型一定不含类型变量限制：项常量的类型一定不含类型变量 蕾唬盟轧菜豫响梅物尿荤济醛烦胳们睦祥念亡广杯箕矫哆典营具圾榔轰细第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断命题命题 令令 M 是任意的良类型是任意的良类型 t t项。如果项。如果由类型化项上的由类型化项上的 和和 归约有归约有M N，那么由，那么由无类型项上的同样归约有无类型项上的同样归约有Erase(M) Erase(N)。反过来，如果由无类型的归约有。反过来，如果由无类型的归约有Erase(M) V，那么存在一个类型化，那么存在一个类型化 项项 N ，使得，使得M N且且Erase(N) V。M M1 . . . MkErase(M) Erase(M1) . . . Erase(Mk) 窒攀板网迟茸桶糙雾庇髓牌脂轮懒梢蚤鹅麦缴粘苫秒窄异伤烁频之悯函溺第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断事实事实 一个无类型项一个无类型项U，只有不存在从它开始，只有不存在从它开始的无类型归约的无穷序列时，它才可能被类型的无类型归约的无穷序列时，它才可能被类型化化例例( x.xx) ( x.xx)推论推论1 如果如果U不是强范式的，那么就不存在可推不是强范式的，那么就不存在可推导的定型导的定型 M: ，使得使得Erase(M) = U 推论推论2 如果如果U是不可类型化的，那么由是不可类型化的，那么由 t t的主语的主语归约性质，知道没有一个能归约到归约性质，知道没有一个能归约到U的项是可类型的项是可类型化的化的M M1 . . . MkErase(M) Erase(M1) . . . Erase(Mk)知竖肮遏沦任蹈员妨腾瘫堰跟丫浪烽梭寄谍促社拽嫂充附迢脉彪湖桅榴芒第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断9.2.2 代换、实例与合一代换、实例与合一事实事实 在在 t t的类型推断中，可推导的定型断的类型推断中，可推导的定型断言封闭于代换言封闭于代换类型代换类型代换类型代换类型代换S作用到类型表达式作用到类型表达式 S 是把是把 中的每个变量中的每个变量t用用S (t)代替代替类型代换类型代换S作用到类型指派作用到类型指派 S = x: S | x: 类型代换类型代换S作用到作用到 t t项项结果结果S M同同M的区别仅在的区别仅在 约束变元的类型约束变元的类型令懈赵背斧蛀烽矮耀唱凸奸岩淡功蛾蝴身伙相阂肆乍峭踪肪闻话膜狼厉职第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断实例实例定定型型断断言言 M : 是是 M: 的的实实例例，如如果果存存在在类类型代型代换换S使得使得 S , M = S M并且并且 = S 引引理理 如如果果定定型型断断言言 M: 是是可可推推导导的的，那那么么它的每个实例它的每个实例S SM:S 也是可推导的也是可推导的粘潭党眩饺汛驱殃辙敦茵膀宋挤聊豪埔挎久疥邪卓脓且港瞄蚊哗凤泡幼曲第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断合一算法合一算法合一合一如果如果E是类型表达式之间的一个等式集合，如果对每是类型表达式之间的一个等式集合，如果对每个等式个等式 = E都有都有S S ，那么类型代换，那么类型代换S合一合一E例例E = s = t v, t = v wS = t, v w , s, (v w) v 代换结果代换结果(v w) v = (v w) v, v w = v wS合一合一E缎丧签勒寄镶疫假与表游浅菇埔锈佣皮伐烙宅辐履琴剐涅桐抨侧运谢孽挖第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断最一般的合一代换最一般的合一代换如如果果存存在在某某个个代代换换T使使得得R = TS，那那么么S比比R更更一一般般如如果果不不存存在在比比S更更一一般般的的代代换换，则则称称S是是最最一一般般的的合一代换合一代换 最最一一般般代代换换是是使使E的的每每个个等等式式经经代代换换后后左左右右两两边边语语法上一样的最简单的方式法上一样的最简单的方式谜淀煤仿吟鳃背熔拨棒侦岁孜迭踢墙佛樱氯狈闻管丢叔殉竿羽梳衣腰荡沙第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断例例E = s = t v, t = v w最最一一般般的的合合一一代代换换S = t, v w , s, (v w) v 代换结果代换结果(v w) v = (v w) v, v w = v w另一个合一代换另一个合一代换S = t, (w w) w , s, (w w) w) (w w) , v, w w 代换结果代换结果(w w) w)(w w)=(w w) w(w w), (w w) w = (w w) w季伪回掇遍嫡匹闰移狄颅缆返东钎吃庭简酵炼闭联酞搭望寸铂筒悠专隶颤第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断引引理理 令令E是是类类型型表表达达式式之之间间的的任任意意等等式式集集合合。存存在在一一个个算算法法Unify，使使得得如如果果E是是可可合合一一的的，那那么么Unify(E)计计算算得得出出一一个个最最一一般般的的合合一一代代换换. .如果如果E不可合一，那么不可合一，那么Unify(E)失败失败如如果果 和和都都是是类类型型指指派派，那那么么合合一一可可以以用用来来找找出最一般的代换出最一般的代换S，使得，使得S S 是合式的是合式的直直接接合合一一所所有有等等式式 = 的的集集合合就就可可以以了了，其其中中x: 并且并且x: 俗醒顽哪主悯司嫂忱聚樟蜜棘柞昧淆锰喇悔场伶袭绅闹熙转怂绷巢岗巫榆第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断递归算法递归算法Unify1. Unify() = 2. Unify(E b1 = b2) = if b1 b2 then fail else Unify(E)3. Unify(E t = ) = if (t ) then Unify(E) else if t occurs in then fail else Unify( /tE) /t 4. Unify(E 1 2 = 1 2) = Unify(E 1 = 1 2 = 2)敌蓝游衔姑冻坡资惹敦洁讥括勃劳跪旬碍粱驶囱揖厚襄锋琢谰凰访蓄棱酬第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断9.2.3 主定型算法主定型算法显式定型显式定型如如果果U是是一一个个无无类类型型 项项，能能够够使使得得Erase(M) = U的的合合式的类型化项式的类型化项 M: 是是U的一个显式定型的一个显式定型主显式定型（简称主定型）主显式定型（简称主定型）如果如果U的每个显式定型都是的每个显式定型都是 M: 的一个实例，那么的一个实例，那么 M: 是是U的主定型的主定型 稻饺津崩汪蔑玄沃焕赞买掠艺炸吗仪俩符穆靠踢裳阉刹欠末先脊翼脐怔音第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断 t t主定型算法主定型算法PT1. PT(c) = c: , 其中其中 是是c的类型的类型, 它不含类型变量它不含类型变量2. PT(x) = x : t x : t3. PT( x.U) = let M: = PT(U) in if x: （对某个（对某个 ） then - x: x: . M: else x:s. M:s 其中其中s是新的类型变量是新的类型变量 抱垮徐缠兆枕郭糖甄枚介娶霄瘁汹篱湘描馋倦坟荡孟蚌串驯萝聘聊嘱嗣道第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断 t t主定型算法主定型算法PTPT(UV) = let M: = PT(U) N: = PT(V)其中类型变量重新命名以其中类型变量重新命名以区别于区别于PT(U)中的变量中的变量 S = Unify( = | x: 并且并且 x: = t)，其其中中t是是新新类类型型变变量量in S S S (MN) : St繁靶蛮荆库叉扇呕哟沁蔚及贩坚痔错蚂苯醚掳项祥琼龋燕拔咸弃荫即蛇谗第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断例例 计算计算 x. y.xy的主定型的主定型PT(xy) = letx:r x:r = PT(x)y:s y:s = PT(y)S = Unify(r = s t)inx : Sr y : Ss xy:StPT(xy) = x: s t, y:s xy: tPT( x. y.xy) = x: s t. y:s.xy: (s t ) s t 欠活慷夏腿御酪敲燃一论薄恭淋犯努昔妨澎少榆兔栖帕胡抢嘘蔓富蔷习沸第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断例例 算法算法PT为什么对为什么对 x.xx会失败会失败PT(xx) = letx:r x:r = PT(x)x:s x:s = PT(x)S = Unify(r = s r = s t)inx : Sr x : Ss xx:St 予酚椒秧矢李舆临农痉沙键赖倒缚袖炼庙漫埃搓苏枯痴妖香嚣裔麓船粗瓤第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断定定理理 如如果果PT (U) = M: ，那那么么Erase (M) = U，并且，并且 M: 的每个实例是可证明的的每个实例是可证明的定定理理 如如果果 M: 是是可可证证明明的的定定型型断断言言，并并且且Erase (M) = U，那那么么PT (U)一一定定成成功功，并并产产生生一个定型断言，使得一个定型断言，使得 M: 是它的一个实例是它的一个实例 骡哭粉翟忱打逆顷抵赖农韵快礁音栽堵瘁喝慷讯赏旋朵攘籽杜下象荒乎什第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断9.2.4 隐式定型隐式定型历历史史上上，许许多多类类型型推推断断问问题题都都被被公公式式化化为为对对无无类类型型项使用证明规则进行证明的问题项使用证明规则进行证明的问题这这些些证证明明系系统统通通常常称称为为隐隐式式定定型型系系统统，因因为为一一个个项项的类型不是由项的语法显式地给定的的类型不是由项的语法显式地给定的此时，类型推断本质上是一个公理理论的判定问题此时，类型推断本质上是一个公理理论的判定问题乐睡肾匿凡烤率势邵梢阅筷晴阅怠助剖补虎斥迅近疤岳隔洼寒海饿求碍浅第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断隐式定型证明隐式定型证明系统系统 c: c是类型是类型 的常量，的常量， 中无类型变量中无类型变量 (cst)x: x: (var) (abs) (app)(add var) , x : U : ( x.U) : U : V: UV : U : , x : U : x不在不在 中中 股微咳篡砒踢鼻汐炎饭航饲叮趁链蒜石巫挑针苇纯邻卒低鄙挚征土崖芥房第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断引理引理 如果如果 M: 是良类型的项，那么是良类型的项，那么|-C Erase(M) . 反过来反过来, 如果如果|-C U ， 那那 么么 存存 在在 类类 型型 化化 的的 项项 M: ， 使使 得得Erase(M)=U 埂罪食利膳铆访终笨果泛土革崖弊拢针成全躇钵现鸯堂炕舰牡蝶狠曙渐豫第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断9.2.5 定型和合一的等价定型和合一的等价类型推断和合一是算法地等价的类型推断和合一是算法地等价的每个类型推断问题产生一个合一问题每个类型推断问题产生一个合一问题每个合一问题出现在某个项的类型推断中每个合一问题出现在某个项的类型推断中 仗非挥征辜荧帽那次骤菏匿涩饵鹿洽舵赡染拆角系激茅蹈舔帛舷仗伟军蔓第9部分类型推断第9部分类型推断9.2 带类型变量的带类型变量的 类型推断类型推断另一个类型推断算法另一个类型推断算法本质上是从定型到合一的归约本质上是从定型到合一的归约TE(c, t) = t = , 其中其中 是是c的类型，的类型， 中无自由变量中无自由变量TE(x, t) = t = tx， 其中其中tx 是是x的类型的类型TE(U V, t) = TE(U, r) TE(V, s) r = s t其中其中r，s都是新的类型变量都是新的类型变量TE( x.U, t) = TE(U, s) t = tx s其中其中s是新的类型变量是新的类型变量如如果果U是是无无类类型型项项，t是是类类型型变变量量，并并且且E = TE(U, t)，那那么么U的的每每个个定定型型是是S U U: St的的一一个个实实例例（对对某个使某个使E能够合一的能够合一的最一般合一代换最一般合一代换 S）腆宙努想拉鲤式口骚汛佩政债怜碰妹疹氖虫脾馒蛮旺演舶沤倒傈整掀塑剐第9部分类型推断第9部分类型推断习习 题题 第一次：第一次：9.2蟹怔泊前质色堤疮秃足沽酗又末龟怜茨代暴瓷拦丙黔界几臀剔猛莲残宋员第9部分类型推断第9部分类型推断