第五章類型檢查

本章內容靜態檢查中最典型的部分—類型檢查： 類型系統、類型檢查、多態函數、重載忽略其它的靜態檢查：控制流檢查、唯一性檢查、關聯名字檢查分析器類型檢查器中間代碼生成器語法樹語法樹中間表示記號流第五章類型檢查本章內容分析類型中間語法樹語法樹中間15.1

類型在編程語言中的作用5.1.1

執行錯誤和安全語言介紹一些和程序運行有聯系的概念5.1類型在編程語言中的作用5.1.1執行錯誤和安全語言25.1

類型在編程語言中的作用5.1.1

執行錯誤和安全語言程序運行時的執行錯誤分成兩類會被捕獲的錯誤（trappederror）5.1類型在編程語言中的作用5.1.1執行錯誤和安全語言35.1

類型在編程語言中的作用5.1.1

執行錯誤和安全語言程序運行時的執行錯誤分成兩類會被捕獲的錯誤（trappederror）例：非法指令錯誤5.1類型在編程語言中的作用5.1.1執行錯誤和安全語言45.1

類型在編程語言中的作用5.1.1

執行錯誤和安全語言程序運行時的執行錯誤分成兩類會被捕獲的錯誤（trappederror）例：非法指令錯誤、非法內存訪問5.1類型在編程語言中的作用5.1.1執行錯誤和安全語言55.1

類型在編程語言中的作用5.1.1

執行錯誤和安全語言程序運行時的執行錯誤分成兩類會被捕獲的錯誤（trappederror）例：非法指令錯誤、非法內存訪問、除數為零5.1類型在編程語言中的作用5.1.1執行錯誤和安全語言65.1

類型在編程語言中的作用5.1.1

執行錯誤和安全語言程序運行時的執行錯誤分成兩類會被捕獲的錯誤（trappederror）例：非法指令錯誤、非法內存訪問、除數為零引起計算立即停止5.1類型在編程語言中的作用5.1.1執行錯誤和安全語言75.1

類型在編程語言中的作用5.1.1

執行錯誤和安全語言程序運行時的執行錯誤分成兩類會被捕獲的錯誤（trappederror）例：非法指令錯誤、非法內存訪問、除數為零引起計算立即停止不會被捕獲的錯誤（untrappederror）

5.1類型在編程語言中的作用5.1.1執行錯誤和安全語言85.1

類型在編程語言中的作用5.1.1

執行錯誤和安全語言程序運行時的執行錯誤分成兩類會被捕獲的錯誤（trappederror）例：非法指令錯誤、非法內存訪問、除數為零引起計算立即停止不會被捕獲的錯誤（untrappederror）

例：下標變量的訪問越過了數組的末端5.1類型在編程語言中的作用5.1.1執行錯誤和安全語言95.1

類型在編程語言中的作用5.1.1

執行錯誤和安全語言程序運行時的執行錯誤分成兩類會被捕獲的錯誤（trappederror）例：非法指令錯誤、非法內存訪問、除數為零引起計算立即停止不會被捕獲的錯誤（untrappederror）

例：下標變量的訪問越過了數組的末端例：跳到一個錯誤的地址，該地址開始的內存正好代表一個指令序列5.1類型在編程語言中的作用5.1.1執行錯誤和安全語言105.1

類型在編程語言中的作用5.1.1

執行錯誤和安全語言程序運行時的執行錯誤分成兩類會被捕獲的錯誤（trappederror）例：非法指令錯誤、非法內存訪問、除數為零引起計算立即停止不會被捕獲的錯誤（untrappederror）

例：下標變量的訪問越過了數組的末端例：跳到一個錯誤的地址，該地址開始的內存正好代表一個指令序列錯誤可能會有一段時間未引起注意5.1類型在編程語言中的作用5.1.1執行錯誤和安全語言115.1

類型在編程語言中的作用5.1.1

執行錯誤和安全語言良行為的程序不同場合對良行為的定義略有區別例如，沒有任何不會被捕獲錯誤的程序5.1類型在編程語言中的作用5.1.1執行錯誤和安全語言125.1

類型在編程語言中的作用5.1.1

執行錯誤和安全語言良行為的程序不同場合對良行為的定義略有區別例如，沒有任何不會被捕獲錯誤的程序安全語言任何合法程序都是良行為的5.1類型在編程語言中的作用5.1.1執行錯誤和安全語言135.1

類型在編程語言中的作用5.1.1

執行錯誤和安全語言良行為的程序不同場合對良行為的定義略有區別例如，沒有任何不會被捕獲錯誤的程序安全語言任何合法程序都是良行為的通常是設計一個類型系統，通過靜態的類型檢查來拒絕不會被捕獲錯誤5.1類型在編程語言中的作用5.1.1執行錯誤和安全語言145.1

類型在編程語言中的作用5.1.1

執行錯誤和安全語言良行為的程序不同場合對良行為的定義略有區別例如，沒有任何不會被捕獲錯誤的程序安全語言任何合法程序都是良行為的通常是設計一個類型系統，通過靜態的類型檢查來拒絕不會被捕獲錯誤但是，設計一個類型系統，它正好只拒絕不會被捕獲錯誤是非常困難的5.1類型在編程語言中的作用5.1.1執行錯誤和安全語言155.1

類型在編程語言中的作用5.1.1

執行錯誤和安全語言禁止錯誤（forbiddenerror）不會被捕獲錯誤集合+會被捕獲錯誤的一個子集5.1類型在編程語言中的作用5.1.1執行錯誤和安全語言165.1

類型在編程語言中的作用5.1.1

執行錯誤和安全語言禁止錯誤（forbiddenerror）不會被捕獲錯誤集合+會被捕獲錯誤的一個子集為語言設計類型系統的目標是在排除禁止錯誤5.1類型在編程語言中的作用5.1.1執行錯誤和安全語言175.1

類型在編程語言中的作用5.1.1

執行錯誤和安全語言禁止錯誤（forbiddenerror）不會被捕獲錯誤集合+會被捕獲錯誤的一個子集為語言設計類型系統的目標是在排除禁止錯誤良行為程序和安全語言也可基于禁止錯誤來定義5.1類型在編程語言中的作用5.1.1執行錯誤和安全語言185.1

類型在編程語言中的作用5.1.2類型化語言和類型系統類型化的語言變量的類型變量在程序執行期間的取值范圍5.1類型在編程語言中的作用5.1.2類型化語言和類型系195.1

類型在編程語言中的作用5.1.2類型化語言和類型系統類型化的語言變量的類型類型化的語言變量都被給定類型的語言并且表達式、語句等語法構造的類型都是可以靜態確定的例如，類型boolean的變量x在程序每次運行時的值只能是布爾值，not(x)總有意義5.1類型在編程語言中的作用5.1.2類型化語言和類型系205.1

類型在編程語言中的作用5.1.2類型化語言和類型系統類型化的語言變量的類型類型化的語言未類型化的語言不限制變量值范圍的語言：

一個運算可以作用到任意的運算對象，其結果可能是一個有意義的值、一個錯誤、一個異常或一個語言未加定義的結果例如：LISP語言5.1類型在編程語言中的作用5.1.2類型化語言和類型系215.1

類型在編程語言中的作用5.1.2類型化語言和類型系統類型化的語言變量的類型類型化的語言未類型化的語言顯式類型化語言類型是語法的一部分5.1類型在編程語言中的作用5.1.2類型化語言和類型系225.1

類型在編程語言中的作用5.1.2類型化語言和類型系統類型化的語言變量的類型類型化的語言未類型化的語言顯式類型化語言隱式類型化的語言不存在隱式類型化的主流語言，但可能存在忽略類型信息的程序片段，例如不需要程序員聲明函數的參數類型5.1類型在編程語言中的作用5.1.2類型化語言和類型系235.1

類型在編程語言中的作用5.1.2類型化語言和類型系統類型系統語言的組成部分,由一組定型規則（typingrule）構成，這組規則用來給各種語言構造指派類型5.1類型在編程語言中的作用5.1.2類型化語言和類型系245.1

類型在編程語言中的作用5.1.2類型化語言和類型系統類型系統語言的組成部分,由一組定型規則（typingrule）構成，這組規則用來給各種語言構造指派類型設計類型系統的根本目的是用靜態檢查的方式來保證合法程序運行時的良行為5.1類型在編程語言中的作用5.1.2類型化語言和類型系255.1

類型在編程語言中的作用5.1.2類型化語言和類型系統類型系統語言的組成部分,由一組定型規則（typingrule）構成，這組規則用來給各種語言構造指派類型設計類型系統的根本目的是用靜態檢查的方式來保證合法程序運行時的良行為類型系統的形式化類型表達式、定型斷言、定型規則5.1類型在編程語言中的作用5.1.2類型化語言和類型系265.1

類型在編程語言中的作用5.1.2類型化語言和類型系統類型系統語言的組成部分,由一組定型規則（typingrule）構成，這組規則用來給各種語言構造指派類型設計類型系統的根本目的是用靜態檢查的方式來保證合法程序運行時的良行為類型系統的形式化類型表達式、定型斷言、定型規則類型檢查算法通常是靜態地完成類型檢查5.1類型在編程語言中的作用5.1.2類型化語言和類型系275.1

類型在編程語言中的作用5.1.2類型化語言和類型系統良類型的程序沒有類型錯誤的程序5.1類型在編程語言中的作用5.1.2類型化語言和類型系285.1

類型在編程語言中的作用5.1.2類型化語言和類型系統良類型的程序沒有類型錯誤的程序合法程序良類型程序（若語言定義中無其它方式表示的約束）5.1類型在編程語言中的作用5.1.2類型化語言和類型系295.1

類型在編程語言中的作用5.1.2類型化語言和類型系統良類型的程序沒有類型錯誤的程序合法程序良類型程序（若語言定義中無其它方式表示的約束）類型可靠（typesound）的語言所有良類型程序（合法程序）都是良行為的類型可靠的語言一定是安全的語言5.1類型在編程語言中的作用5.1.2類型化語言和類型系305.1

類型在編程語言中的作用5.1.2類型化語言和類型系統語法的和靜態的概念 動態的概念 類型化語言 安全語言 良類型程序 良行為的程序5.1類型在編程語言中的作用5.1.2類型化語言和類型系315.1

類型在編程語言中的作用5.1.2類型化語言和類型系統未類型化語言可以通過徹底的運行時詳細檢查來排除所有的禁止錯誤如LISP語言5.1類型在編程語言中的作用5.1.2類型化語言和類型系325.1

類型在編程語言中的作用5.1.2類型化語言和類型系統未類型化語言可以通過徹底的運行時詳細檢查來排除所有的禁止錯誤如LISP語言類型化語言類型檢查也可以放在運行時完成，但影響效率一般都是靜態檢查，類型系統被用來支持靜態檢查靜態檢查語言通常也需要一些運行時的檢查數組訪問越界檢查5.1類型在編程語言中的作用5.1.2類型化語言和類型系335.1

類型在編程語言中的作用5.1.2類型化語言和類型系統實際使用的一些語言并不安全禁止錯誤集合沒有囊括所有不會被捕獲的錯誤Pascal語言

無標志的變體記錄類型函數型參數5.1類型在編程語言中的作用5.1.2類型化語言和類型系345.1

類型在編程語言中的作用5.1.2類型化語言和類型系統實際使用的一些語言并不安全禁止錯誤集合沒有囊括所有不會被捕獲的錯誤Pascal語言用C語言的共用體（union）來舉例 unionU{intu1;int

u2;}u; int

p; u.u1=10; p=u.u2;

p=0;5.1類型在編程語言中的作用5.1.2類型化語言和類型系355.1

類型在編程語言中的作用5.1.2類型化語言和類型系統實際使用的一些語言并不安全C語言還有很多不安全的并且被廣泛使用的特征，如： 指針算術運算、類型強制、參數個數可變5.1類型在編程語言中的作用5.1.2類型化語言和類型系365.1

類型在編程語言中的作用5.1.2類型化語言和類型系統實際使用的一些語言并不安全C語言還有很多不安全的并且被廣泛使用的特征，如： 指針算術運算、類型強制、參數個數可變在語言設計的歷史上，安全性考慮不足是因為強調代碼的執行效率5.1類型在編程語言中的作用5.1.2類型化語言和類型系375.1

類型在編程語言中的作用5.1.2類型化語言和類型系統實際使用的一些語言并不安全C語言還有很多不安全的并且被廣泛使用的特征，如： 指針算術運算、類型強制、參數個數可變在語言設計的歷史上，安全性考慮不足是因為強調代碼的執行效率在現代語言設計上，安全性的位置越來越重要5.1類型在編程語言中的作用5.1.2類型化語言和類型系385.1

類型在編程語言中的作用5.1.2類型化語言和類型系統實際使用的一些語言并不安全C語言還有很多不安全的并且被廣泛使用的特征，如： 指針算術運算、類型強制、參數個數可變在語言設計的歷史上，安全性考慮不足是因為強調代碼的執行效率在現代語言設計上，安全性的位置越來越重要C的一些問題已經在C++中得以緩和更多一些問題在Java中已得到解決5.1類型在編程語言中的作用5.1.2類型化語言和類型系395.1

類型在編程語言中的作用5.1.3

類型化語言的優點從工程的觀點看，類型化語言有下面一些優點

開發的實惠較早發現錯誤類型信息還具有文檔作用5.1類型在編程語言中的作用5.1.3類型化語言的優點405.1

類型在編程語言中的作用5.1.3

類型化語言的優點從工程的觀點看，類型化語言有下面一些優點

開發的實惠較早發現錯誤類型信息還具有文檔作用

編譯的實惠程序模塊可以相互獨立地編譯5.1類型在編程語言中的作用5.1.3類型化語言的優點415.1

類型在編程語言中的作用5.1.3

類型化語言的優點從工程的觀點看，類型化語言有下面一些優點

開發的實惠較早發現錯誤類型信息還具有文檔作用

編譯的實惠程序模塊可以相互獨立地編譯運行的實惠可得到更有效的空間安排和訪問方式5.1類型在編程語言中的作用5.1.3類型化語言的優點425.2

描述類型系統的語言類型系統主要用來說明編程語言的定型規則,它獨立于類型檢查算法5.2描述類型系統的語言類型系統主要用來說明編程語言的定型435.2

描述類型系統的語言類型系統主要用來說明編程語言的定型規則,它獨立于類型檢查算法定義一個類型系統，一種重要的設計目標是存在有效的類型檢查算法5.2描述類型系統的語言類型系統主要用來說明編程語言的定型445.2

描述類型系統的語言類型系統主要用來說明編程語言的定型規則,它獨立于類型檢查算法定義一個類型系統，一種重要的設計目標是存在有效的類型檢查算法類型系統的基本概念可用于各類語言，包括函數式語言、命令式語言和并行語言等5.2描述類型系統的語言類型系統主要用來說明編程語言的定型455.2

描述類型系統的語言類型系統主要用來說明編程語言的定型規則,它獨立于類型檢查算法定義一個類型系統，一種重要的設計目標是存在有效的類型檢查算法類型系統的基本概念可用于各類語言，包括函數式語言、命令式語言和并行語言等本節討論用形式方法來描述類型系統5.2描述類型系統的語言類型系統主要用來說明編程語言的定型465.2

描述類型系統的語言類型系統主要用來說明編程語言的定型規則,它獨立于類型檢查算法定義一個類型系統，一種重要的設計目標是存在有效的類型檢查算法類型系統的基本概念可用于各類語言，包括函數式語言、命令式語言和并行語言等本節討論用形式方法來描述類型系統然后討論實例語言時：先定義語法，再給出類型系統的形式描述，最后寫出類型檢查的翻譯方案5.2描述類型系統的語言類型系統主要用來說明編程語言的定型475.2

描述類型系統的語言類型系統的形式化類型系統是一種邏輯系統

有關自然數的邏輯系統- 自然數表達式（需要定義它的語法）

a+b,3-良形公式 （邏輯斷言，需要定義它的語法）

a+b=3,(d=3)(c<10)-推理規則 a<b,b<ca<c5.2描述類型系統的語言類型系統的形式化a<b,485.2

描述類型系統的語言類型系統的形式化類型系統是一種邏輯系統

有關自然數的邏輯系統 類型系統- 自然數表達式 類型表達式

a+b,3 intint-良形公式

a+b=3,(d=3)(c<10) -推理規則 a<b,b<ca<c5.2描述類型系統的語言類型系統的形式化a<b,495.2

描述類型系統的語言類型系統的形式化類型系統是一種邏輯系統

有關自然數的邏輯系統 類型系統- 自然數表達式 類型表達式

a+b,3 intint-良形公式 定型斷言

a+b=3,(d=3)(c<10) {x:int}|–x+3:int-推理規則 ({x:int}叫做定型環境)a<b,b<ca<c5.2描述類型系統的語言類型系統的形式化a<b,505.2

描述類型系統的語言類型系統的形式化類型系統是一種邏輯系統

有關自然數的邏輯系統 類型系統- 自然數表達式 類型表達式

a+b,3 intint-良形公式 定型斷言

a+b=3,(d=3)(c<10) {x:int}|–x+3:int-推理規則 定型規則

|–M:int,|–N:int

|–M+N:int

a<b,b<ca<c5.2描述類型系統的語言類型系統的形式化|–M515.2

描述類型系統的語言類型系統的形式化類型表達式具體語法：出現在編程語言及定型斷言中抽象語法：出現在類型檢查的實現中下一節開始舉例定型斷言本節討論它的一般形式定型規則本節討論它的一般形式5.2描述類型系統的語言類型系統的形式化525.2

描述類型系統的語言5.2.1

斷言斷言的形式 |–S

S的所有自由變量都聲明在

中其中

是一個靜態定型環境，如x1:T1,…,xn:TnS的形式隨斷言形式的不同而不同斷言有三種具體形式5.2描述類型系統的語言5.2.1斷言535.2

描述類型系統的語言環境斷言

|–

該斷言表示

是良形的環境將用推理規則來定義環境的語法(而不是用文法)5.2描述類型系統的語言環境斷言545.2

描述類型系統的語言環境斷言

|–

該斷言表示

是良形的環境將用推理規則來定義環境的語法語法斷言

|–

nat

在環境

下，nat是類型表達式將用推理規則來定義類型表達式的語法(而不是用文法)5.2描述類型系統的語言環境斷言555.2

描述類型系統的語言環境斷言

|–

該斷言表示

是良形的環境將用推理規則來定義環境的語法語法斷言

|–

nat

在環境

下，nat是類型表達式將用推理規則來定義類型表達式的語法定型斷言

|–

M:T 在環境

下，M具有類型T 例：

|–true:boolean x:nat

|–x+1:nat將用推理規則來確定語法構造實例的類型5.2描述類型系統的語言環境斷言565.2

描述類型系統的語言有效斷言

|–

true:boolean無效斷言

|–true:nat5.2描述類型系統的語言有效斷言575.2

描述類型系統的語言5.2.2

推理規則習慣表示法前提、結論公理、推理規則

1

|–S1,…,

n|–Sn

|–S5.2描述類型系統的語言5.2.2推理規則1|–585.2

描述類型系統的語言5.2.2

推理規則（規則名） （注釋） 推理規則 （注釋）環境規則 (Env

)

|–

5.2描述類型系統的語言5.2.2推理規則595.2

描述類型系統的語言5.2.2

推理規則（規則名） （注釋） 推理規則 （注釋）環境規則 (Env

) 語法規則 (TypeBool)

|–

|–

|–boolean5.2描述類型系統的語言5.2.2推理規則|–605.2

描述類型系統的語言5.2.2

推理規則（規則名） （注釋） 推理規則 （注釋）環境規則 (Env

) 語法規則 (TypeBool) 定型規則 (Val+)

|–

|–

|–boolean

|–M:int,|–N:int

|–M+N:int

5.2描述類型系統的語言5.2.2推理規則|–615.2

描述類型系統的語言5.2.3

類型檢查和類型推斷類型檢查 用語法制導的方式，根據上下文有關的定型規則來判定程序構造是否為良類型的程序構造的過程5.2描述類型系統的語言5.2.3類型檢查和類型推斷625.2

描述類型系統的語言5.2.3

類型檢查和類型推斷類型檢查 用語法制導的方式，根據上下文有關的定型規則來判定程序構造是否為良類型的程序構造的過程類型推斷 類型信息不完全的情況下的定型判定問題 例如：f(x:t)=E

和f(x)=E的區別5.2描述類型系統的語言5.2.3類型檢查和類型推斷635.3

簡單類型檢查器的說明5.3.1

一個簡單的語言P

D;SD

D;D|id:TT

boolean|integer|array[num]ofT|

T|T‘

’TS

id:=E|ifEthenS|whileEdoS|S;SE

truth|num|id|EmodE|E[E]|

E

|E(E)5.3簡單類型檢查器的說明5.3.1一個簡單的語言645.3

簡單類型檢查器的說明例：

i:integer;

j:integer;

j:=imod20005.3簡單類型檢查器的說明例：655.3

簡單類型檢查器的說明5.3.2類型系統環境規則(Env

) (DeclVar)其中id:T是該簡單語言的一個聲明語句略去了基于程序中所有聲明語句來構成整個的規則

|–

|

T,id

dom(

)

,id:T|

5.3簡單類型檢查器的說明5.3.2類型系統|T,665.3

簡單類型檢查器的說明語法規則(TypeBool) (TypeInt)(TypeVoid)void用于表示語句類型表明編程語言和定型斷言的類型表達式并非完全一致

|

|

boolean

|

|

integer

|

|

void5.3簡單類型檢查器的說明語法規則||675.3

簡單類型檢查器的說明語法規則(TypeRef)(T

void) (TypeArray)(T

void) (N>0)(TypeFunction)(T1,T2

void)定型斷言中的類型表達式也可以用抽象語法

|

T

|

pointer(T)

|

T,

|

N:integer

|

array(N,T)

|

T1,

|

T2

|

T1

T25.3簡單類型檢查器的說明語法規則|T|685.3

簡單類型檢查器的說明定型規則——表達式(ExpTruth) (ExpNum)(ExpId)

|

|

truth:boolean

|

|

num:integer

1,id:T,

2|

1,id:T,

2|

id:T5.3簡單類型檢查器的說明定型規則——表達式|695.3

簡單類型檢查器的說明定型規則——表達式(ExpMod) (ExpIndex)

(0

E2

N1)(ExpDeref)

|

E1:integer,

|

E2:integer

|

E1modE2:integer

|

E1:array(N,T),

|

E2:integer

|

E1[E2]:T

|

E:pointer(T)

|

E

:T5.3簡單類型檢查器的說明定型規則——表達式|E705.3

簡單類型檢查器的說明定型規則——表達式(ExpFunCall)

|

E1:T1

T2,

|

E2:T1

|

E1(E2):T25.3簡單類型檢查器的說明定型規則——表達式|E715.3

簡單類型檢查器的說明定型規則——語句(StateAssign)(T=booleanor

T=integer)(StateIf)(StateWhile)

|

id:T,

|

E:T

|

id:=E:void

|

E:boolean,

|

S:void

|

ifEthenS:void

|

E:boolean,

|

S:void

|

whileEdoS:void5.3簡單類型檢查器的說明定型規則——語句|id725.3

簡單類型檢查器的說明定型規則——語句(StateSeq)

|

S1:void,

|

S2:void

|

S1;S2:void5.3簡單類型檢查器的說明定型規則——語句|S1735.3

簡單類型檢查器的說明5.3.3

類型檢查設計語法制導的類型檢查器設計依據是上節的類型系統類型環境的信息進入符號表對類型表達式采用抽象語法 具體：array[N]ofT 抽象：array(N,T)

T

pointer(T)考慮到報錯的需要，增加了類型type_error5.3簡單類型檢查器的說明5.3.3類型檢查745.3

簡單類型檢查器的說明5.3.3

類型檢查——聲明語句D

D;DD

id

:T {addtype(id.entry,T.type)}

addtype：把類型信息填入符號表5.3簡單類型檢查器的說明5.3.3類型檢查——聲明語句755.3

簡單類型檢查器的說明5.3.3

類型檢查——聲明語句D

D;DD

id

:T {addtype(id.entry,T.type)}T

boolean {T.type=boolean}T

integer

{T.type=integer}T

T1

{T.type=pointer(T1.type)}5.3簡單類型檢查器的說明5.3.3類型檢查——聲明語句765.3

簡單類型檢查器的說明5.3.3

類型檢查——聲明語句D

D;DD

id

:T {addtype(id.entry,T.type)}T

boolean {T.type=boolean}T

integer

{T.type=integer}T

T1

{T.type=pointer(T1.type)}T

array

[num]ofT1

{T.type=array(num.val,T1.type)}5.3簡單類型檢查器的說明5.3.3類型檢查——聲明語句775.3

簡單類型檢查器的說明5.3.3

類型檢查——聲明語句D

D;DD

id

:T {addtype(id.entry,T.type)}T

boolean {T.type=boolean}T

integer

{T.type=integer}T

T1

{T.type=pointer(T1.type)}T

array

[num]ofT1

{T.type=array(num.val,T1.type)}T

T1

‘

’T2

{T.type=T1.type

T2.type}5.3簡單類型檢查器的說明5.3.3類型檢查——聲明語句785.3

簡單類型檢查器的說明類型檢查——表達式E

truth

{E.type=boolean}E

num

{E.type=integer}E

id

{E.type=lookup(id.entry)}5.3簡單類型檢查器的說明類型檢查——表達式795.3

簡單類型檢查器的說明類型檢查——表達式E

truth

{E.type=boolean}E

num

{E.type=integer}E

id

{E.type=lookup(id.entry)}E

E1

modE2

{E.type=ifE1.type==integerand

E2.type==integertheninteger

elsetype_error}5.3簡單類型檢查器的說明類型檢查——表達式805.3

簡單類型檢查器的說明類型檢查——表達式E

E1[E2]{E.type=ifE2.type==integerand E1.type==array(s,t)thent elsetype_error}5.3簡單類型檢查器的說明類型檢查——表達式815.3

簡單類型檢查器的說明類型檢查——表達式E

E1[E2]{E.type=ifE2.type==integerand E1.type==array(s,t)thent elsetype_error}E

E1

{E.type=ifE1.type==pointer(t)thent elsetype_error}5.3簡單類型檢查器的說明類型檢查——表達式825.3

簡單類型檢查器的說明類型檢查——表達式E

E1[E2]{E.type=ifE2.type==integerand E1.type==array(s,t)thent elsetype_error}E

E1

{E.type=ifE1.type==pointer(t)thent elsetype_error}E

E1(E2){E.type=ifE2.type==sand E1.type==s

tthent

elsetype_error}5.3簡單類型檢查器的說明類型檢查——表達式835.3

簡單類型檢查器的說明類型檢查——語句S

id:=E{if

(id.type==E.type&&E.type

{boolean,integer})S.type=void;

elseS.type=type_error;}

5.3簡單類型檢查器的說明類型檢查——語句845.3

簡單類型檢查器的說明類型檢查——語句S

id:=E{if

(id.type==E.type&&E.type

{boolean,integer})S.type=void;

elseS.type=type_error;}

S

ifEthenS1{S.type=ifE.type==boolean thenS1.type elsetype_error}5.3簡單類型檢查器的說明類型檢查——語句855.3

簡單類型檢查器的說明類型檢查——語句S

whileEdoS1

{S.type=ifE.type==booleanthenS1.type

elsetype_error}5.3簡單類型檢查器的說明類型檢查——語句865.3

簡單類型檢查器的說明類型檢查——語句S

whileEdoS1

{S.type=ifE.type==booleanthenS1.type

elsetype_error}S

S1;S2

{S.type=ifS1.type==voidand S2.type==voidthenvoid

elsetype_error}5.3簡單類型檢查器的說明類型檢查——語句875.3

簡單類型檢查器的說明類型檢查——程序P

D;S

{P.type=ifS.type==voidthenvoid elsetype_error}5.3簡單類型檢查器的說明類型檢查——程序885.3

簡單類型檢查器的說明5.3.4類型轉換E

E1opE2{E.type= ifE1.type==integerandE2.type==integer theninteger elseifE1.type==integerandE2.type==real thenreal elseifE1.type==realandE2.type==integer thenreal

elseifE1.type==realandE2.type==real thenreal elsetype_error}5.3簡單類型檢查器的說明5.3.4類型轉換895.4

多態函數5.4.1為什么要使用多態函數例：用Pascal語言寫不出求表長度的通用程序typelink=

cell; cell=record info:integer; next:link end;5.4多態函數5.4.1為什么要使用多態函數905.4

多態函數functionlength(lptr:link):integer; varlen:integer; begin len:=0; whilelptr<>nildobegin len:=len+1; lptr:=lptr

.next end; length:=lenend;5.4多態函數functionlength(lpt915.4

多態函數用ML語言很容易寫出求表長度的程序而不必管表元的類型。funlength(lptr)= ifnull(lptr)then0 elselength(tl(lptr))+1;5.4多態函數用ML語言很容易寫出求表長度的程序而不925.4

多態函數用ML語言很容易寫出求表長度的程序而不必管表元的類型。funlength(lptr)= ifnull(lptr)then0 elselength(tl(lptr))+1;length([“sun”,“mon”,“tue”])length([10,9,8])都等于35.4多態函數用ML語言很容易寫出求表長度的程序而不935.4

多態函數多態函數允許變元有不同的類型5.4多態函數多態函數945.4

多態函數多態函數允許變元有不同的類型體中的語句可以在變元類型不同的情況下執行（區別于重載的特征）5.4多態函數多態函數955.4

多態函數多態函數允許變元有不同的類型體中的語句可以在變元類型不同的情況下執行（區別于重載的特征）多態算符用于以不同類型的變元執行的代碼段5.4多態函數多態函數965.4

多態函數多態函數允許變元有不同的類型體中的語句可以在變元類型不同的情況下執行（區別于重載的特征）多態算符用于以不同類型的變元執行的代碼段例如：數組索引5.4多態函數多態函數975.4

多態函數多態函數允許變元有不同的類型體中的語句可以在變元類型不同的情況下執行（區別于重載的特征）多態算符用于以不同類型的變元執行的代碼段例如：數組索引、函數作用5.4多態函數多態函數985.4

多態函數多態函數允許變元有不同的類型體中的語句可以在變元類型不同的情況下執行（區別于重載的特征）多態算符用于以不同類型的變元執行的代碼段例如：數組索引、函數作用、通過指針間接訪問5.4多態函數多態函數995.4

多態函數多態函數允許變元有不同的類型體中的語句可以在變元類型不同的情況下執行（區別于重載的特征）多態算符用于以不同類型的變元執行的代碼段例如：數組索引、函數作用、通過指針間接訪問C語言手冊中關于指針&的論述是：如果運算對象的類型是‘…’，那么結果類型是指向‘…’的指針”5.4多態函數多態函數1005.4

多態函數5.4.2

類型變量length的類型可以寫成

.list(

)

integer

允許使用類型變量，還便于討論未知類型在不要求標識符的聲明先于使用的語言中，通過類型變量的使用去確定程序變量的類型5.4多態函數5.4.2類型變量1015.4

多態函數例：functionderef(p); begin returnp

end; 5.4多態函數例：1025.4

多態函數例：functionderef(p); --對p的類型一無所知：

begin returnp

end; 5.4多態函數例：1035.4

多態函數例：functionderef(p); --對p的類型一無所知：

begin returnp --

=pointer(

)end; 5.4多態函數例：1045.4

多態函數例：functionderef(p); --對p的類型一無所知：

begin returnp --

=pointer(

)end; deref的類型是

.pointer(

)

5.4多態函數例：1055.4

多態函數5.4.3一個含多態函數的語言P

D;E 引入類型變量、笛卡D

D;D|id:Q 兒積類型、多態函數

Q

type-variable.Q|T T

T‘

’T|T

T |unary-constructor

(T) |basic-type |type-variable |(T)E

E(E)|E,E|id5.4多態函數5.4.3一個含多態函數的語言1065.4

多態函數5.4.3一個含多態函數的語言P

D;E 引入類型變量、笛卡D

D;D|id:Q 兒積類型、多態函數

Q

type-variable.Q|T T

T‘

’T|T

T 這是一個抽象語言, |unary-constructor

(T)忽略了函數定義的 |basic-type 函數體 |type-variable |(T)E

E(E)|E,E|id5.4多態函數5.4.3一個含多態函數的語言1075.4

多態函數5.4.3一個含多態函數的語言P

D;ED

D;D|id:QQ

type-variable.Q|TT

T‘

’T|T

T |unary-constructor

(T) 一個程序： |basic-type deref:

.pointer(

)

; |type-variableq:pointer(pointer(integer)); |(T) deref(deref(q))E

E(E)|E,E|id5.4多態函數5.4.3一個含多態函數的語言1085.4

多態函數類型系統中增加的推理規則

環境規則

(EnvVar)語法規則(TypeVar)(TypeProduct)

|

,

dom(

)

,

|

1,

,

2|

1,

,

2|

|

T1,

|

T2

|

T1

T25.4多態函數類型系統中增加的推理規則|1095.4

多態函數類型系統中增加的推理規則

語法規則(TypeParenthesis)(TypeForall)(TypeFresh)

|

T

|

(T)

,

|

T

|

.T

|

.T,

,

i|

,

i

|

[

i

/

]T

5.4多態函數類型系統中增加的推理規則|1105.4

多態函數類型系統中增加的推理規則定型規則(ExpPair)(ExpFunCall)(S是T1和T3的最一般的合一代換)

|

E1:T1，|

E2:T2

|

E1,E2:T1

T2

|

E1:T1

T2,

|

E2:T3

|

E1(E2):S(T2)5.4多態函數類型系統中增加的推理規則|E1115.4

多態函數5.4.4

代換、實例和合一代換:類型表達式中的類型變量用其所代表的類型表達式去替換5.4多態函數5.4.4代換、實例和合一1125.4

多態函數5.4.4

代換、實例和合一代換:類型表達式中的類型變量用其所代表的類型表達式去替換functionsubst(t:type_expression):

type_expression;begin ift是基本類型thenreturnt elseift是類型變量thenreturnS(t) elseift是t1

t2thenreturn

subst(t1)

subst(t2)end5.4多態函數5.4.4代換、實例和合一1135.4

多態函數實例

把subst函數用于t后所得的類型表達式是t的一個實例，用S(t)表示。例子（s<t表示s是t的實例）pointer(integer)<pointer(

)pointer(real)<pointer(

)integer

integer<

pointer(

)<

<

5.4多態函數實例1145.4

多態函數下面左邊的類型表達式不是右邊的實例integer real

代換不能用于基本類型integer

real

的代換不一致integer

的所有出現都應該代換5.4多態函數下面左邊的類型表達式不是右邊的實例1155.4

多態函數合一

如果存在某個代換S使得S(t1)=S(t2)，那么這兩個表達式t1和t2能夠合一最一般的合一代換S(t1)=S(t2)；對任何其它滿足S

(t1)=S

(t2)的代換S

，代換S

(t1)是S(t1)的實例5.4多態函數合一1165.4

多態函數5.4.5多態函數的類型檢查多態函數和普通函數在類型檢查上的區別(1)同一多態函數的不同出現無須變元有相同類型apply:

oderefo:pointer(

o)

oapply:

iderefi:pointer(

i)

iq:pointer(pointer(integer))deref(deref

(q))的帶標記的語法樹5.4多態函數5.4.5多態函數的類型檢查appl1175.4

多態函數(2)必須把類型相同的概念推廣到類型合一apply:

oderefo:pointer(

o)

oapply:

iderefi

:pointer(

i)

iq:pointer(pointer(integer))deref(deref

(q))的帶標記的語法樹5.4多態函數(2)必須把類型相同的概念推廣到類型合1185.4

多態函數(2)必須把類型相同的概念推廣到類型合一(3)要記錄類型表達式合一的結果apply:

oderefo:pointer(

o)

oapply:

iderefi

:pointer(

i)

iq:pointer(pointer(integer))deref(deref

(q))的帶標記的語法樹5.4多態函數(2)必須把類型相同的概念推廣到類型合1195.4

多態函數檢查多態函數的翻譯方案E

E1(E2) {p=mkleaf(newtypevar); unify(E1.type,mknode(‘

’,E2.type,p));

E.type=p}E

E1,E2

{E.type=mknode(‘

’,E1.type,E2.type)}E

id {E.type=fresh(lookup(id.entry))}5.4多態函數檢查多態函數的翻譯方案1205.4

多態函數apply:

oderefo:pointer(

o)

oapply:

iderefi

:pointer(

i)

iq:pointer(pointer(integer))表

達

式

：

類

型

代

換

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

5.4多態函數apply:oderefo:poi1215.4

多態函數確定表長度的ML函數funlength(lptr)= ifnull(lptr)then0 elselength(tl(lptr))+1;5.4多態函數確定表長度的ML函數1225.4

多態函數length:

; lptr:

;if:

.boolean

;null:

.list(

)

boolean;tl:

.list(

)

list(

);0:integer;1:integer;+:integer

integer

integer;match:

.

;match( length(lptr), if(null(lptr),0,length(tl(lptr))+1))5.4多態函數length:; lptr1235.4

多態函數行

定

型

斷

言

代

換

規

則

(1)lptr:

(ExpId)

(2)length:

(ExpId)

(3)length(lptr):

=

(ExpFunCall)

(4)lptr:

從(1)可得

(5)null:list(

n)

boolean

(ExpId)和(TypeFresh)

(6)null(lptr):boolean

=list(

n)(ExpFunCall)

(7)0:integer

(ExpNum)

(8)lptr:list(

n)從(1)可得

5.4多態函數行定型斷言代換規1245.4

多態函數行

定

型

斷

言

代

換

規

則

(9)tl:list(

t)

list(

t)(ExpId)和(TypeFresh)(10)tl(lptr):list(

n)

t=

n

(ExpFunCall)(11)length:list(

n)

從(2)可得

(12)length(tl(lptr)):

(ExpFunCall)

(13)1:integer

(ExpNum)(14)+:integer

integer

integer

(ExpId)5.4多態函數行定型斷言代換規1255.4

多態函數行

定

型

斷

言

代

換

規

則

(15)

length(tl(lptr))+1:

integer

=integer

(ExpFunCall)(16)if:boolean

i

i

i

(ExpId)和(TypeFresh)(17)if(...):integer

i=integer

(ExpFunCall)(18)match:

m

m

m

(ExpId)和(TypeFresh)

(19)match(…):integer

m=integer

(ExpFunCall)5.4多態函數行定型斷言代換規1265.4

多態函數funlength(lptr)= ifnull(lptr)then0 elselength(tl(lptr))+1;length函數的類型是

.list(

)

integer

5.4多態函數funlength(lptr)=1275.5

類型表達式的等價當允許對類型表達式命名后：類型表達式是否相同就有了不同的解釋出現了結構等價和名字等價兩個不同的概念typelink=

cell;var next :link; last :link; p :

cell; q,r :

cell;5.5類型表達式的等價當允許對類型表達式命名后：1285.5

類型表達式的等價5.5.1類型表達式的結構等價兩個類型表達式完全相同（當無類型名時）typelink=

cell;var next :link; last :link; p :

cell; q,r :

cell;5.5類型表達式的等價5.5.1類型表達式的結構等價1295.5

類型表達式的等價5.5.1類型表達式的結構等價兩個類型表達式完全相同（當無類型名時）類型表達式樹一樣typelink=

cell;var next :link; last :link; p :

cell; q,r :

cell;5.5類型表達式的等價5.5.1類型表達式的結構等價1305.5

類型表達式的等價5.5.1類型表達式的結構等價兩個類型表達式完全相同（當無類型名時）類型表達式樹一樣相同的類型構造符作用于相同的子表達式typelink=

cell;var next :link; last :link; p :

cell; q,r :

cell;5.5類型表達式的等價5.5.1類型表達式的結構等價1315.5

類型表達式的等價5.5.1類型表達式的結構等價兩個類型表達式完全相同（當無類型名時）把類型名都用它們定義的類型表達式代換，所得兩類型表達式完全相同(類型定義無環時)typelink=

cell;var next :link; last :link; p :

cell; q,r :

cell;5.5類型表達式的等價5.5.1類型表達式的結構等價1325.5

類型表達式的等價類型表達式的結構等價測試sequiv(s,t)(無類型名時)ifs

和t

是相同的基本類型then returntrueelseifs==array(s1,s2)andt==array(t1,t2)then returnsequiv(s1,t1)andsequiv(s2,t2)elseifs==s1

s2andt==t1

t2then returnsequiv(s1,t1)andsequiv(s2,t2)elseifs==pointer(s1)andt==pointer(t1)then returnsequiv(s1,t1)elseifs==s1

s2andt==t1

t2then returnsquiv(s1,t1)andsequiv(s2,t2)elsereturnfalse5.5類型表達式的等價類型表達式的結構等價測試sequi1335.5

類型表達式的等價5.5.2類型表達式的名字等價把每個類型名看成是一個可區別的類型typelink=

cell;var next :link; last :link; p :

cell; q,r :

cell;5.5類型表達式的等價5.5.2類型表達式的名字等價1345.5

類型表達式的等價5.5.2