【導讀】否相等來進行類型檢查。完全相同，則稱兩個類型表達式結構等價。反映在類型表達式的語法樹上，就是兩棵語法樹完全相同。的函數值的類型為int。當類型構造符層次很多并且僅在最底。層不等價時，算法的效率較低。確可以確定不等價的情況排除。即為了提高效率，犧牲一些。次要信息是否也相等。一條從根到葉子的路徑。對鏈上每個節(jié)點編碼，形成一個類。型編碼的字符串或者整型數。標類型保留數組元素類型。型保留返回值的類型。問題：×與record的簡化如何處理？簡化后的類型表達式為array。將其從左到右轉換為編碼，得到1001110001。同的類型名，使得它們具有不同的類型。能進行運算，從而避免了潛在的錯誤；

　　

【正文】 end unify。 s := find(m)。 t := find(n)。 分別找到 m和 n所在等價類的代表 if s=t then return true。 elsif s和 t代表相同基本類型 then union(s,t)。 return true。 elsif s和 t代表相同類型構造符并分別有孩子節(jié)點 (s1, s2)和 (t1, t2) then union(s, t)。 構造等價類 return unify(s1, t1) and unify(s2, t2)。 分別合一左右孩子 elsif s或 t代表一個變量 then union(s, t)。 return true。 else return false。 其它均不可合一 end if。 多態(tài)函數的類型檢查（續(xù) 3） 多態(tài)函數文法 ()中表達式類型檢查的語義規(guī)則： E→E 1(E2) { γ := mkleaf(newtypevar)。 unify(,mknode(39?！?9。, ,γ) 。 := γ 。 } () |E1, E2 { := mknode(39。 39。, , )。 } |id { := fresh()。 } 函數調用 E→E1(E2) 的語義處理：設 =α 且在函數聲明時 α 已確定 (α=s→t )，設 =β 。則應有未知類型γ ，使得 S(α)=S(β→γ) 。 為此設 α 語法樹的根節(jié)點為 n，并建立一個類型為 γ 的葉節(jié)點和一個類型為 β→γ 的新節(jié)點 m。若 m與 n合一成功則其結果 γ 成為 。 m: →β γn: →s tderef(deref(q))的類型檢查 例 用算法 ()，對 deref(deref(q))進行類型檢查。 E→E 1(E2) { γ := mkleaf(newtypevar)。 unify(,mknode(39?！?9。, ,γ) 。 := γ 。 } () |id { := fresh()。 } E5E1 ( E4 )deref E2 ( E3 )deref qE1 → deref =fresh()=pointer(α 0)→α 0 E2 → deref =fresh()=pointer(α 1)→α 1 E3 → q =fresh()=pointer(pointer(int)) E4 → E2(E3) =γ 1=pointer(int) E5 → E1(E4) =γ 0=int deref(deref(q))的類型檢查（續(xù) 1） 確定 ： 建立葉子 γ 1和→γ 1的新節(jié)點 m： n2:→: 6pointer: 5α1:4pointer(α 1)→α 1 : n3:pointer: 9pointer: 8int: 7pointer(pointer(int)) : 合一 n2和 m，即unify(11, 6)： m : →: 11n3: pointer: 9 γ1: 10pointer: 8int: 7unify(11,6)union(11,6)→6unify(9,5) unfiy(10,4)union(9,5)→5 find(4)=8unify(8,4) union(10,8)→8union(8,4)→8得到 =pointer(int)： pointer: 5 pointer: 8int: 7m:→: 6: E4 → E2(E3) =γ 1=pointer(int) deref(deref(q))的類型檢查（續(xù) 2） 再確定 ： 建立葉子 γ 0和 →γ 0的新節(jié)點 m39。： E5→E1(E4) pointer: 8 γ0: 13 m 39。 :→ : 12int: 7合一 n1和 m39。，即unify(12, 3)： n1:→: 3pointer: 2α0:1pointer(α 0)→α 0 : union(8,2)→2 find(1)=7unify(12,3)union(12,3)→3unify(8,2) unfiy(13,1)unify(7,1) union(13,7)→7union(7,1)→7得到 =int： pointer: 2int: 7 m 39。:→: 3有環(huán)類型的合一操作 real: 2→: 1real: 4→: 3→: 5real: 6union(1,5)→1unify(1,3)union(1,3)→1unify(2,4) unfiy(1,5)unify(2,6) unify(1,3)find(1)=find(3)real: 2→: 1→: 1real: 2結 束（ 2020年 5月 10日） ()與 () 聲明時 id類型的確定 P → D。 E D → D。D D → id : T { addtype(entry(), )。} T → char { := char。 } () | integer { := integer。 } | ^T1 { := pointer()。} | array[num]of T1 { := array(, )。} 函數作為類型在語法上的描述： D → id : T { addtype(entry(), )。} () T → T1 → T2 { := → 。 } E → E1(E2) { := if =s and =s→t then t else type_error。 } 返回