【正文】 if : ?? . boolean ?? ?? ?? 。 為完成類型檢查 – 把它用抽象語言來改寫（見下一頁） 多 態(tài) 函 數(shù) length : ? 。 unify (E1. type, mknode ( ??‘, , p) )。 begin if t是基本類型 then return t else if t是類型變量 then return S(t) else if t 是 t1? t2 then return subst(t1) ? subst(t2) end 多 態(tài) 函 數(shù) 實例 把 subst函數(shù) 用于 t后所得的類型表達(dá)式是 t的一個實例，用 S (t)表示。 | typevariable q : pointer (pointer (integer))。 E D ? D。 E 引入類型變量、笛卡 D ? D。 E 引入類型變量、笛卡 D ? D。 對 p的類型一無所知： ? begin return p? ? = pointer(? ) end。 對 p的類型一無所知： ? begin return p? ? = pointer(? ) end。 對 p的類型一無所知： ? begin return p? end。 begin return p? end。 length ( [―sun‖, ―mon‖, ―tue‖] ) length ( [10, 9, 8 ] ) 都等于 3 多 態(tài) 函 數(shù) ? 多態(tài)函數(shù) – 允許變元的類型有多種不同的情況 – 函數(shù)體中的語句的執(zhí)行能適應(yīng)變元類型有多種不同的情況（區(qū)別于重載的特征） ? 多態(tài)算符 – 例如： 數(shù)組索引 、 函數(shù)應(yīng)用、通過指針間接訪問 – 相應(yīng)操作的代碼段接受不同類型的數(shù)組、函數(shù)等 – C語言手冊中關(guān)于取地址算符 amp。 計算過程并不涉及 表元的數(shù)據(jù)類型 但語言的類型系統(tǒng) 使得該函數(shù)不能通用 多 態(tài) 函 數(shù) 例：用 ML語言很容易寫出求表長度的程序而不必管表元的類型 fun length (lptr) = if null (lptr) then 0 else length (tl (lptr)) + 1。 lptr := lptr?. next end。 begin len := 0。 針對這個類型，可以寫出下頁的表長函數(shù) 多 態(tài) 函 數(shù) function length(lptr : link) : integer。 cell = record info : integer。 S2 {S. type = if S1. type == void and S2. type == void then void else type_error } 簡單類型檢查器的說明 類型檢查 ——程序 P ? D。 else = type_error。amp。 else = type_error。amp。 D D ? id : T {addtype (, )} T ? boolean { = boolean} T ? integer { = integer} T ? ?T1 { = pointer()} T ? array [num] of T1 { = array(, )} 簡單類型檢查器的說明 類型檢查 ——聲明語句 D ? D。 D D ? id : T {addtype (, )} addtype：把類型信息填入符號表 簡單類型檢查器的說明 類型檢查 ——聲明語句 D ? D。 j := i mod 2020 簡單類型檢查器的說明 類型系統(tǒng) 環(huán)境規(guī)則 (Env ?) (Decl Var) 其中 id : T是該簡單語言的一個聲明語句 略去了 基于程序中所有聲明語句來構(gòu)成整個 ?的規(guī)則 ? |– ? ?|?T, id ? dom (?) ?, id : T |? ? 簡單類型檢查器的說明 語法規(guī)則 (Type Bool) (Type Int) (Type Void) void用于表示語句類型 表明編程語言和定型斷言的類型表達(dá)式并非完全一致 ? |? ? ? |? boolean ? |? ? ? |? integer ? |? ? ? |? void 簡單類型檢查器的說明 語法規(guī)則 (Type Ref) (T ? void) 具體語法： ?T (Type Array) (T ? void) (N0) 具體語法： array [N] of T (Type Function) (T1, T2 ? void) 定型斷言中的類型表達(dá)式用的是抽象語法 ? |? T ? |? pointer(T) ? |? T, ? |? N : integer ? |? array(N, T) ? |? T1, ? |? T2 ? |? T1 ? T2 簡單類型檢查器的說明 定型規(guī)則 ——表達(dá)式 (Exp Truth) (Exp Num) (Exp Id) ? |? ? ? |? truth : boolean ? |? ? ? |? num : integer ?1, id : T, ?2 |? ? ?1, id : T, ?2 |? id : T 簡單類型檢查器的說明 定型規(guī)則 ——表達(dá)式 (Exp Mod) (Exp Index) (0 ? E2 ? N?1) (Exp Deref) ? |? E1: integer, ? |? E2: integer ? |? E1 mod E2: integer ? |? E1: array(N,T), ? |? E2: integer ? |? E1[E2] : T ? |? E : pointer(T) ? |? E? : T 簡單類型檢查器的說明 定型規(guī)則 ——表達(dá)式 (Exp FunCall) ? |? E1: T1 ? T2, ? |? E2: T1 ? |? E1 (E2) : T2 簡單類型檢查器的說明 定型規(guī)則 ——語句 (State Assign) (T=boolean or T= integer) (State If) (State While) ? |? id : T, ? |? E : T ? |? id := E : void ? |? E : boolean, ? |? S : void ? |? if E then S : void ? |? E : boolean, ? |? S : void ? |? while E do S: void 簡單類型檢查器的說明 定型規(guī)則 ——語句 (State Seq) ? |? S1: void, ? |? S2: void ? |? S1。 S E ? truth | num | id | E mod E | E [ E ] | E? | E (E ) 簡單類型檢查器的說明 ? 例 i : integer。 S D ? D 。 ?p = 0。 = 10。} u。第五章 類 型 檢 查 本章內(nèi)容 – 靜態(tài)檢查中最典型的部分 — 類型檢查： 類型系統(tǒng)、類型檢查、多態(tài)函數(shù)、重載 – 忽略其它的靜態(tài)檢查： 控制流檢查、唯一性檢查、關(guān)聯(lián)名字檢查 語法 分析 器 類型 檢查 器 中間 代碼 生成 器 語法樹 語法樹 中間 表示 記號流 類型在編程語言中的作用 執(zhí)行錯誤和安全語言 介紹一些和程序運行有聯(lián)系的概念 類型在編程語言中的作用 執(zhí)行錯誤和安全語言 程序運行時的執(zhí)行錯誤分成兩類 ? 會被捕獲的錯誤 （ trapped error） 類型在編程語言中的作用 執(zhí)行錯誤和安全語言 程序運行時的執(zhí)行錯誤分成兩類 ? 會被捕獲的錯誤 （ trapped error） – 例： 非法指令錯誤 類型在編程語言中的作用 執(zhí)行錯誤和安全語言 程序運行時的執(zhí)行錯誤分成兩類 ? 會被捕獲的錯誤 （ trapped error） – 例： 非法指令錯誤、非法內(nèi)存訪問 類型在編程語言中的作用 執(zhí)行錯誤和安全語言 程序運行時的執(zhí)行錯誤分成兩類 ? 會被捕獲的錯誤 （ trapped error） – 例： 非法指令錯誤、非法內(nèi)存訪問 、 除數(shù)為零 – 引起計算立即停止 ? 不會被捕獲的錯誤 （ untrapped error） – 例：下標(biāo)變量的 訪問越過了數(shù)組的末端 – 例： 跳到一個錯誤的地址，該地址開始的內(nèi)存正好代表一個指令序列 – 錯誤可能會有一段時間未引起注意 類型在編程語言中的作用 執(zhí)行錯誤和安全語言 良行為的程序 – 不同場合對良行為的定義略有區(qū)別 – 例如，沒有任何不會被捕獲錯誤的程序 安全語言 – 任何 合法程序都是良行為的 – 通常是設(shè)計一個類型系統(tǒng)，通過靜態(tài)的類型檢查來拒絕不會被捕獲錯誤 – 但是，設(shè)計一個類型系統(tǒng)，它正好只拒絕不會被捕獲錯誤是非常困難的 類型在編程語言中的作用 執(zhí)行錯誤和安全語言 ? 禁止錯誤 （ forbidden error） – 不會被捕獲錯誤 集合 + 會被捕獲錯誤的一個子集 – 為語言設(shè)計類型系統(tǒng)的目標(biāo)是在排除 禁止錯誤 良行為程序和安全語言也可基于禁止錯誤來定義 類型在編程語言中的作用 類型化語言和類型系統(tǒng) 類型化的語言 ? 變量的類型 – 變量在程序執(zhí)行期間的取值范圍 類型在編程語言中的作用 類型化語言和類型系統(tǒng) 類型化的語言 ? 變量的類型 ? 類型化的語言 – 變量都被給定類型的語言 – 表達(dá)式 、語句等程序構(gòu)造的類型都可以靜態(tài)確定 – 例 如，類型 boolean的變量 x在程序每次運行時的值只能是布爾值 ， not (x)總 有意義 類型在編程語言中的作用 類型化語言和類型系統(tǒng) 類型化的語言 ? 變量的類型 ? 類型化的語言 ? 未類型化的語言 – 不限 制變