【文章內容簡介】 的類型為 α ， 則 p的類型是pointer(α) ， 因此函數 deref(p)的類型應該是： ?α .pointer(α) → α () 即對于任何一個類型為 α 的對象，函數 deref(p)是將指向 α 對象的一個指針類型映射到該對象。 deref習慣上也被稱為脫引用。 1 多態(tài)函數、類型變量與類型推斷 2 含多態(tài)函數語言的文法 多態(tài)函數與單態(tài)函數的本質區(qū)別是形參不但可以是常量也可以是變量。因此對 ()和 ()的文法進行擴充，將含有類型變量的類型定義引入產生式。 P → D 。 E D → D。 D | id : Q Q → ? | T () T → T 39?！?9。 T | T T | unaryconstructor(T) | basictype | typevariable | (T) E → E(E) | E, E | id 此擴充與將數據的簡單變量擴充為含有數組元素類似。首先，文法將原來的單態(tài)類型 T擴展為多態(tài)類型 Q， Q除了包括 T產生式的全部，又引入了受約束的類型變量。同時 T產生式中增加了類型變量，即將類型變量引入類型。 引入數組元素后的賦值句文法 A → V := E V → id[EL] | id EL→ EL ， E | E E → E + E | ( E ) | V 2 含多態(tài)函數語言的文法（續(xù) 1） 例 按文法 ()書寫的一個程序如下： P → D 。 E D → D。 D | id : Q Q → ? | T () T → T 39?！?9。 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 含多態(tài)函數語言的文法（續(xù) 2） deref : ?α .pointer(α)→α 。 q : pointer(pointer(int))。 defef(deref(q))。 P→D 。 E D→D 。 D | id : Q Q→ ?|T () T→T 39?！?9。 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)) 語法樹上各節(jié)點的類型deref0 →derefi qpointer (αi) → αipointer (pointer(int) )pointer(α0)→α0i αi= pointer(int)→0α0=int函數名作用于參數得到函數返回值 每次引入一個固定變元 結 束（ 2020年 4月 29日） “ 五一 ” 節(jié)快樂！ （五一后第一周兩次課！） 多態(tài)函數的簡單回顧 ? 多態(tài)函數、類型變量與類型推斷 ? 含多態(tài)函數語言的文法 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?！?9。 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?！?9。 T | T T | unaryconstructor(T) | basictype | typevariable | (T) E → E(E) | E, E | id (c) deref(deref(int)) 語法樹上各節(jié)點的類型deref0 →derefi qpointer (αi) → αipointer (pointer(int) )pointer(α0)→α0i αi= pointer(int)→0α0=int? 每次引入一個新類型變量 ? 替換變量試圖得到匹配 ? 保留替換結果以繼續(xù)匹配 代換、實例與合一 多態(tài)函數類型檢查的一般方法：首先設法消除類型變量，然后判定消除類型變量后的類型表達式是否結構等價。具體有三點與單態(tài)的類型檢查不同： (1) 消除約束變元 類型表達式中約束變元在語法樹中的每次出現均要被替換為自由變元，且同一類型表達式的多態(tài)函數的不同出現，變元可以有不同的類型。 方法是每引入一個多態(tài)類型表達式，就為變元引入一個新類型變量。 如將 ?(α)→α 改為 pointer(α 0)→α 0或pointer(α i)→α i，從而消除了全稱量詞和約束變元。 代