【正文】 a的類(lèi)型是： pointer(array(0.. i1 –1, … array(0.. in –1, t)… )) 例 題 2 在 X86/Linux機(jī)器上 ， 編譯器報(bào)告最后一行有錯(cuò)誤： inpatibl。} main() { fun()。 fun() { printf(―%d,%d,%d\n‖, a, a+1, amp。 例 題 1 typedef int A[10][20]。 B *fun() { return(a)。 typedef int B[20]。 } 該函數(shù)在 Linux上用 gcc編譯時(shí) ， 沒(méi)有錯(cuò)誤 。 A *fun() { return(amp。 } 該函數(shù)在 Linux上用 gcc編譯時(shí) ， 報(bào)告的錯(cuò)誤如下： 第 6行： warning: return from inpatible pointer type 例 題 1 typedef int A[10][20]。 A a。a的值都是數(shù)組 a的首地址，它們的使用是否有區(qū)別的？ 用四個(gè) C文件的編譯報(bào)錯(cuò)或運(yùn)行結(jié)果來(lái)提示。 ? 數(shù)組名代表數(shù)組的首地址。為地址運(yùn)算符， amp。 問(wèn)題： 如果 a是一個(gè)數(shù)組名，那么表達(dá)式 a和 amp。a為變量 a的地址。 例 題 1 C語(yǔ)言 ? 稱 amp。 function ―? ‖ (x, y : plex ) return plex。 function ―? ‖ (x, y : plex ) return plex。 function ―? ‖ (x, y : plex ) return plex。 match ( length (lptr), if (null (lptr), 0, length (t1(lptr)) +1) ) 多 態(tài) 函 數(shù) 行 定 型 斷 言 代 換 規(guī) 則 (1) lptr : ? (Exp Id) (2) length : ? (Exp Id) (3) length(lptr) : ? ? = ? ? ? (Exp FunCall) (4) lptr : ? 從 (1)可得 (5) null : list(?n) ? boolean (Exp Id)和(Type Fresh) (6) null(lptr) : boolean ? = list (?n) (Exp FunCall) (7) 0 : integer (Exp Num) (8) lptr : list(?n) 從 (1)可得 多 態(tài) 函 數(shù) 行 定 型 斷 言 代 換 規(guī) 則 (9) tl : list(?t) ? list(?t) (Exp Id)和(Type Fresh) (10) t1(lptr) : list(?n) ?t = ?n (Exp FunCall) (11) length : list(?n) ? ? 從 (2)可得 (12) length(t1(lptr)) : ? (Exp FunCall) (13) 1 : integer (Exp Num) (14) + : integer ? integer ? integer (Exp Id) 多 態(tài) 函 數(shù) 行 定 型 斷 言 代 換 規(guī) 則 (15) length (t1(lptr)) +1 : integer ? = integer (Exp FunCall) (16) if : boolean ??i ??i ??i (Exp Id)和(Type Fresh) (17) if ( ... ) : integer ?i = integer (Exp FunCall) (18) match : ?m ? ?m ??m (Exp Id)和(Type Fresh) (19) match ( … ) : integer ?m=integer (Exp FunCall) 多 態(tài) 函 數(shù) fun length (lptr) = if null (lptr) then 0 else length (tl (lptr)) + 1。 + : integer ? integer ? integer 。 0 : integer 。 null : ?? . list (?) ? boolean 。 lptr : ? 。 E. type := p} E ? E1, E2 {E. type := mknode ( ??‘, , )} E ? id {E. type := fresh (lookup())} 多 態(tài) 函 數(shù) apply: ?o derefo:pointer(?o) ? ?o apply : ?i derefi : pointer(?i) ? ?i q: pointer(pointer(integer)) 表 達(dá) 式 ： 類(lèi) 型 代 換 q : pointer(pointer(integer)) derefi : pointer(?i) ? ?i derefi(q) : pointer(integer) ? i= pointer(integer) derefo : pointer(?o) ? ?o derefo(derefi (q)) : integer ?o = integer 多 態(tài) 函 數(shù) 確定表長(zhǎng)度的 ML函數(shù) fun length (lptr) = if null (lptr) then 0 else length (tl (lptr)) + 1。 例子（ s t 表示 s是 t 的實(shí)例 ） pointer ( integer ) pointer (? ) pointer ( real ) pointer (? ) integer ? integer ? ?? pointer (? ) ? ? ? 多 態(tài) 函 數(shù) 下面左邊的類(lèi)型表達(dá)式不是右邊的實(shí)例 integer real 代換不能用于基本類(lèi)型 integer ? real ? ? ? ? 的代換不一致 integer ? ? ? ?? ? 的所有出現(xiàn)都應(yīng)該代換 多 態(tài) 函 數(shù) 合一 如果存在某個(gè)代換 S使得 S (t1) = S (t2)， 那么這兩個(gè)表達(dá)式 t1和 t2能夠 合一 最一般的合一代換 ? S(t1) = S(t2)； ? 對(duì)任何其它滿足 S?(t1) = S?(t2)的代換 S?， 代換S?(t1)是 S (t1)的實(shí)例 多 態(tài) 函 數(shù) 多態(tài)函數(shù)的類(lèi)型檢查 多態(tài)函數(shù)和普通函數(shù)在類(lèi)型檢查上的區(qū)別 (1)同一多態(tài)函數(shù)的不同出現(xiàn)無(wú)須變?cè)邢嗤?lèi)型 apply: ?o derefo:pointer(?o) ? ?o apply : ?i derefi : pointer(?i) ? ?i q: pointer(pointer(integer)) deref(deref (q ))的帶標(biāo)記的語(yǔ)法樹(shù) 多 態(tài) 函 數(shù) (2)必須把類(lèi)型相同的概念推廣到類(lèi)型合一 apply: ?o derefo:pointer(?o) ? ?o apply : ?i derefi : pointer(?i)? ?i q: pointer(pointer(integer)) deref(deref (q ))的帶標(biāo)記的語(yǔ)法樹(shù) 多 態(tài) 函 數(shù) (2)必須把類(lèi)型相同的概念推廣到類(lèi)型合一 (3)要記錄表達(dá)式合一的結(jié)果 apply: ?o derefo:pointer(?o) ? ?o apply : ?i derefi :pointer(?i) ? ?i q: pointer(pointer(integer)) deref(deref (q ))的帶標(biāo)記的語(yǔ)法樹(shù) 多 態(tài) 函 數(shù) 檢查多態(tài)函數(shù)的翻譯方案 E?E1 (E2 ) {p := mkleaf (newtypevar)。 D | id : Q 笛卡兒積類(lèi)型、 Q ? ?typevariable. Q | T 多態(tài)函數(shù) T ? T ??‘T | T ? T | unaryconstructor ( T ) | basictype | typevariable | ( T ) E ? E (E ) | E, E | id 多 態(tài) 函 數(shù) 代換、實(shí)例和合一 代換 : 類(lèi)型表達(dá)式中的類(lèi)型變量用其所代表的類(lèi)型表達(dá)式去替換 多 態(tài) 函 數(shù) 代換、實(shí)例和合一 代換 : 類(lèi)型表達(dá)式中的類(lèi)型變量用其所代表的類(lèi)型表達(dá)式去替換 function subst (t : type_expression ) : type_expression。 多 態(tài) 函 數(shù) 一個(gè)含多態(tài)函數(shù)的語(yǔ)言 P ? D。的論述是： 如果運(yùn)算對(duì)象的類(lèi)型是 ‘ … ’ ，那么結(jié)果類(lèi)型是指向 ‘ … ’ 的指針 ” 。 fun length (lptr) = if null (lptr) then 0 else length (tl (lptr)) + 1。 fun length (lptr) = if null (lptr) then 0 else length (tl (lptr)) + 1。 length := len end。 while lptr nil do begin len := len + 1。 var len : integer。 next : link end。 S {P. type := if S. type = void then void else type_error } 類(lèi)型檢查器的規(guī)格說(shuō)明 類(lèi)型轉(zhuǎn)換 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 } 多態(tài)函數(shù) 為什么要使用多態(tài)函數(shù) 例：用 Pascal語(yǔ)言寫(xiě)不出求表長(zhǎng)度的通用程序 type link = ?cell 。 D D ? id : T {addtype (, )} T ? boolean { := boolean} T ? integer { := integer} T ? ?T1 { := pointer()} T ? array [num] of T1 { := array(, )} T ? T1 ??‘ T2 { := ? } 類(lèi)型檢查器的規(guī)格說(shuō)明 類(lèi)型表達(dá)式的抽象語(yǔ)法 ? 基本類(lèi)型 boolean, char, integer, real ? 構(gòu)造類(lèi)型 – 數(shù)組類(lèi)型 array(I, T) – 指針類(lèi)型 pointer(T) – 積類(lèi)型 T1 ? T2 – 函數(shù) T1 ? T2 – 記錄（例） record((address ? integer) ? (lexeme ? array(1..10, char))) – 類(lèi)型表達(dá)式中還可以出現(xiàn)類(lèi)型名字和類(lèi)型變量 類(lèi)型檢查器的規(guī)格說(shuō)明 類(lèi)型檢查 ——表達(dá)式 E ? truth { := boolean } E ? num { := integer} E ? id { := lookup()} 類(lèi)型檢查器的規(guī)格說(shuō)明 類(lèi)型檢查 ——表達(dá)式 E ? truth { := boolean } E ? num { := integer} E ? id { := lookup()} E ? E1 mod E2 { := if = integer and E2. type = integer then integer else type_error } 類(lèi)型檢查器的規(guī)格說(shuō)明 類(lèi)型檢查 ——表達(dá)式 E ? E1