上次课程小结

上次课程小结内容摘要：

的类型为 α ， 则 p的类型是pointer(α) ， 因此函数 deref(p)的类型应该是： α .pointer(α) → α () 即对于任何一个类型为 α 的对象，函数 deref(p)是将指向 α 对象的一个指针类型映射到该对象。 deref习惯上也被称为脱引用。 1 多态函数、类型变量与类型推断 2 含多态函数语言的文法 多态函数与单态函数的本质区别是形参不但可以是常量也可以是变量。 因此对 ()和 ()的文法进行扩充，将含有类型变量的类型定义引入产生式。 P → D。 E D → D。 D | id : Q Q →  | T () T → T 39。 →39。 T | T T | unaryconstructor(T) | basictype | typevariable | (T) E → E(E) | E, E | id 此扩充与将数据的简单变量扩充为含有数组元素类似。 首先，文法将原来的单态类型 T扩展为多态类型 Q， Q除了包括 T产生式的全部，又引入了受约束的类型变量。 同时 T产生式中增加了类型变量，即将类型变量引入类型。 引入数组元素后的赋值句文法 A → V := E V → id[EL] | id EL→ EL ， E | E E → E + E | ( E ) | V 2 含多态函数语言的文法（续 1） 例 按文法 ()书写的一个程序如下： P → D。 E D → D。 D | id : Q Q →  | T () T → T 39。 →39。 T | T T | unaryconstructor(T) | basictype | typevariable | (T) E → E(E) | E, E | id deref : α .pointer(α) → α。 q : pointer(pointer(int))。 defef(deref(q))。 首先声明 deref和 q，然后是函数调用 defef(deref(q))，其中内层函数调用的返回值作为外层调用的实参。 显然，两个相同的函数在不同位置的出现具有不同的参数类型和返回值类型。 2 含多态函数语言的文法（续 2） deref : α .pointer(α)→α。 q : pointer(pointer(int))。 defef(deref(q))。 P→D。 E D→D。 D | id : Q Q→ |T () T→T 39。 →39。 T|T T|unaryconstructor(T) |basictype|typevariable|(T) E→E(E)|E,E|id (a) 函数调用的语法树→(作用于)函数名 参数(b) deref ( deref (int)) 的语法树deref0 →iderefi q→0(c) deref(deref(int)) 语法树上各节点的类型deref0 →derefi qpointer (αi) → αipointer (pointer(int) )pointer(α0)→α0i αi= pointer(int)→0α0=int函数名作用于参数得到函数返回值 每次引入一个固定变元 结 束（ 2020年 4月 29日） “ 五一 ” 节快乐。 （五一后第一周两次课。 ） 多态函数的简单回顾 • 多态函数、类型变量与类型推断 • 含多态函数语言的文法 deref : α .pointer(α)→α。 q : pointer(pointer(int))。 defef(deref(q))。 (b) deref ( deref (int)) 的语法树deref0 →iderefi q→0P→D。 E D→D。 D | id : Q Q→ |T () T→T 39。 →39。 T|T T|unaryconstructor(T) |basictype|typevariable|(T) E→E(E)|E,E|id P → D。 E D → D。 D | id : Q Q →  | T () T → T 39。 →39。 T | T T | unaryconstructor(T) | basictype | typevariable | (T) E → E(E) | E, E | id (c) deref(deref(int)) 语法树上各节点的类型deref0 →derefi qpointer (αi) → αipointer (pointer(int) )pointer(α0)→α0i αi= pointer(int)→0α0=int• 每次引入一个新类型变量 • 替换变量试图得到匹配 • 保留替换结果以继续匹配 代换、实例与合一 多态函数类型检查的一般方法：首先设法消除类型变量，然后判定消除类型变量后的类型表达式是否结构等价。 具体有三点与单态的类型检查不同： (1) 消除约束变元 类型表达式中约束变元在语法树中的每次出现均要被替换为自由变元，且同一类型表达式的多态函数的不同出现，变元可以有不同的类型。 方法是每引入一个多态类型表达式，就为变元引入一个新类型变量。 如将 (α)→α 改为 pointer(α 0)→α 0或pointer(α i)→α i，从而消除了全称量词和约束变元。 代。