程序設(shè)計語言理論基礎(chǔ)

第1章 引言 1.  
1.1 模型程序設(shè)計語言    
1.2 λ記法    
1.3 等式,4歸約和語義 4  
1.3.1 公理語義    
1.3.2 操作語義    
1.3.3 指稱語義 5  
1.4 類型和類型系統(tǒng) 6  
1.5 記法和數(shù)學(xué)約定    
1.6 集合論基礎(chǔ)知識    
1.6.1 基礎(chǔ) 9  
1.6.2 關(guān)系和函數(shù) 12  
1.7 語法和語義 14  
1.7.1 目標(biāo)語言和元語言 14  
1.7.2 文法    
1.7.3 詞法分析和語法分析    
1.7.4 數(shù)學(xué)解釋示例 17  
1.8 歸納法 18  
1.8.1 自然數(shù)歸納法    
1.8.2 表達(dá)式和證明上的歸納法 21  
1.8.3 良基歸納法 26  
第2章 PCF語言 30  
2.1 引言 30  
2.2 PCF語法 31  
2.2.1 概述 31  
2.2.2 布爾值和自然數(shù) 31  
2.2.3 配對及其函數(shù) 34  
2.2.4 聲明和語法慣用形 37  
2.2.5 遞歸和不動點(diǎn)算子 40  
2.2.6 PCF語法總結(jié)和精選實(shí)例 43  
2.3 PCF程序及其語義 45  
2.3.1 程序和結(jié)果 45  
2.3.2 公理語義 46  
2.3.3 指稱語義 48  
2.3.4 操作語義 49  
2.3.5 由各種形式語義定義的等價關(guān)系 51  
2.4 PCF歸約和符號解釋程序 52  
2.4.1 不確定性規(guī)約 52  
2.4.2 歸約策略 56  
2.4.3 最左優(yōu)先和懶歸約策略 57  
2.4.4 并行歸約 60  
2.4.5 積極PCF 61  
2.5 PCF編程樣例,43表達(dá)能和限度 64  
2.5.1 記錄和n元組 64  
2.5.2 搜索自然數(shù) 65  
2.5.3 迭代和尾遞歸 67  
2.5.4 完全遞歸函數(shù) 70  
2.5.5 部分遞歸函數(shù) 72  
2.5.6 并行操作的不可定義性 75  
2.6 PCF的變體和擴(kuò)展 81  
2.6.1 擴(kuò)展的概述 81  
2.6.2 unit與求和類型 81  
2.6.3 遞歸類型 84  
2.6.4 提升類型 88  
第3章 泛代數(shù)及代數(shù)數(shù)據(jù)類型 97  
3.1 引言 97  
3.2 代數(shù)規(guī)范概述 98  
3.3 代數(shù),58基調(diào)和項(xiàng) 99  
3.3.1 代數(shù) 99  
3.3.2 代數(shù)項(xiàng)語法 99  
3.3.3 代數(shù)和項(xiàng)的解釋 101  
3.3.4 代入引理 104  
3.4 等式,63可靠性和完備性 105  
3.4.1 等式 105  
3.4.2 項(xiàng)代數(shù)和代入 106  
3.4.3 語義蘊(yùn)涵和等式證明系統(tǒng) 107  
3.4.4 完備性的形式 115  
3.4.5 同余,68商和演繹完備性 115  
3.4.6 非空類子和最小模型性質(zhì) 118  
3.5 同態(tài)和始代數(shù) 119  
3.5.1 同態(tài)和同構(gòu) 119  
3.5.2 始代數(shù) 121  
3.6 代數(shù)數(shù)據(jù)類型 125  
3.6.1 規(guī)范和數(shù)據(jù)抽象 125  
3.6.2 始代數(shù)語義和數(shù)據(jù)類型歸納 127  
3.6.3 例子和錯誤值 131  
3.6.4 錯誤值的其他解決方法 135  
3.7 重寫系統(tǒng) 135  
3.7.1 基本定義 135  
3.7.2 匯聚性和可證相等性 138  
3.7.3 終止性 140  
3.7.4 臨界對 143  
3.7.5 左線性非重疊重寫系統(tǒng) 148  
3.7.6 局部匯聚,84終止和完備性 151  
3.7.7 代數(shù)數(shù)據(jù)類型的應(yīng)用 153  
第4章 簡單類型化?演算 156  
4.1 引言 156  
4.2 類型 157  
4.2.1 語法 157  
4.2.2 類型的解釋 157  
4.3 項(xiàng) 159  
4.3.1 上下文相關(guān)語法 159  
4.3.2 λ→項(xiàng)的語法 160  
4.3.3 帶有積. 和的項(xiàng)及其相關(guān)類型 165  
4.3.4 公式與類型的對應(yīng) 166  
4.3.5 類型求取算法 169  
4.4 證明系統(tǒng) 171  
4.4.1 等式和理論 171  
4.4.2 歸約規(guī)則 178  
4.4.3 具有附加規(guī)則的歸約 180  
4.4.4 一致性和保持性的證明論方法 182  
4.5 Henkin模型,102可靠性和完備性 186  
4.5.1 通用模型和項(xiàng)的含義 186  
4.5.2 作用結(jié)構(gòu),104外延性和框架 187  
4.5.3 環(huán)境模型條件 188  
4.5.4 類型和等式可靠性 192  
4.5.5 不帶空類型的Henkin模型的完備性 195  
4.5.6 帶有空類型的完備性 197  
4.5.7 組合子和組合模型條件 198  
4.5.8 組合代數(shù)和?代數(shù) 200  
4.5.9 其他類型的Henkin模型 201  
第5章 類型化λ演算模型 204  
5.1 引言 204  
5.2 域論模型和不動點(diǎn) 204  
5.2.1 遞歸定義和不動點(diǎn)算子 204  
5.2.2 完全偏序,116提升和笛卡兒積 206  
5.2.3 連續(xù)函數(shù) 209  
5.2.4 不動點(diǎn)和完全連續(xù)層次 212  
5.2.5 PCF的CPO模型 218  
5.3 不動點(diǎn)歸納 223  
5.4 計算適當(dāng)性和完全抽象 227  
5.4.1 近似原理和計算適當(dāng)性 227  
5.4.2 帶并行操作的PCF的完全抽象 231..  
5.5 遞歸理論模型 237  
5.5.1 引言 237  
5.5.2 樸素集 239  
5.5.3 完全遞歸層次 241  
5.6 部分等價關(guān)系和遞歸 244  
5.6.1 類型的部分等價關(guān)系解釋 244  
5.6.2 部分組合代數(shù)的一般化 246  
5.6.3 提升,131部分函數(shù)和遞歸 249  
5.6.4 遞歸和固有序 251  
5.6.5 有效CPO的提升,133積和函數(shù)空間 256  
第6章 命令式程序 260  
6.1 引言 260  
6.2 while程序 261  
6.2.1 L值和R值 261  
6.2.2 while程序的語法 262  
6.3 操作語義 263  
6.3.1 表達(dá)式中的基本符號 263  
6.3.2 位置和存儲 263  
6.3.3 表達(dá)式求值 264  
6.3.4 命令的執(zhí)行 265  
6.4 指稱語義 269  
6.4.1 帶有存儲的類型化λ演算 269  
6.4.2 語義函數(shù) 271  
6.4.3 操作語義和指稱語義的等價性 275  
6.5 關(guān)于while程序的前-后斷言 277  
6.5.1 一階和部分正確性斷言 277  
6.5.2 證明規(guī)則 278  
6.5.3 可靠性 283  
6.5.4 相對完備性 284  
6.6 附加程序構(gòu)造的語義 288  
6.6.1 概述 288  
6.6.2 帶有局部變量的模塊 288  
6.6.3 過程 294  
6.6.4 組合程序塊和過程聲明 295  
第7章 范疇和遞歸類型 299  
7.1 引言 299  
7.2 笛卡兒閉范疇 299  
7.2.1 范疇論與類型化語言 299  
7.2.2 范疇,162函子和自然變換 300  
7.2.3 笛卡兒閉范疇的定義 307  
7.2.4 可靠性和項(xiàng)的解釋 314  
7.2.5 Henkin模型作為CCC 325  
7.2.6 含義函數(shù)的范疇刻劃 327  
7.3 Kripke λ模型和函子范疇 329  
7.3.1 概述 329  
7.3.2 可能世界 329  
7.3.3 作用結(jié)構(gòu) 329  
7.3.4 外延性,171組合子和函子范疇 331  
7.3.5 環(huán)境和項(xiàng)的含義 333  
7.3.6 可靠性和完備性 335  
7.3.7 Kripkecλ模型作為笛卡兒閉范疇 336  
7.4 遞歸類型的域模型 338  
7.4.1 一個啟示性的例子 338  
7.4.2 圖,177錐和極限 341  
7.4.3 F代數(shù) 343  
7.4.4 ω 鏈和初始F代數(shù) 345  
7.4.5 O范疇和嵌入 348  
7.4.6 余極限和O余極限 350  
7.4.7 局部連續(xù)函子 353  
7.4.8 該通用方法的例子 355  
第8章 邏輯關(guān)系 359  
8.1 邏輯關(guān)系概述 359  
8.2 作用性結(jié)構(gòu)上的邏輯關(guān)系 359  
8.2.1 邏輯關(guān)系的定義 359  
8.2.2 基本引理 361  
8.2.3 部分函數(shù)和模型的理論 365  
8.2.4 邏輯部分等價關(guān)系 366  
8.2.5 商和外延性 366  
8.3 證明論的結(jié)果 369  
8.3.1 Henkin模型的完備性 369  
8.3.2 正則化 371  
8.3.3 匯聚和其他歸約性質(zhì) 373  
8.3.4 有fix和附加操作的歸約 377  
8.4 部分滿射和特殊模型 385  
8.4.1 部分滿射和完整的古典層次 385  
8.4.2 完整的遞歸層次 386  
8.4.3 完整的連續(xù)層次 388  
8.5 表示獨(dú)立性 389  
8.5.1 動機(jī) 389  
8.5.2 實(shí)例語言 390  
8.5.3 普通的表示獨(dú)立性 392  
8.6 邏輯關(guān)系的推廣 393  
8.6.1 引言 393  
8.6.2 啟示性例子：全偏序和Kripke模型 394  
8.6.3 尋求原像體和關(guān)系 399  
8.6.4 與邏輯關(guān)系的比較 402  
8.6.5 一般情形和應(yīng)用到特殊范疇 404  
第9章 多態(tài)與模塊性 407  
9.1 引言 407  
9.1.1 概述 407  
9.1.2 類型作為函數(shù)實(shí)參 407  
9.1.3 通積與通和 411  
9.1.4 類型作為規(guī)范 412  
9.2 預(yù)知多態(tài)演算 414  
9.2.1 類型和項(xiàng)的語法 414  
9.2.2 與其他多態(tài)形式比較 418  
9.2.3 等式證明系統(tǒng)和歸納 421  
9.2.4 預(yù)知多態(tài)的模型 422  
9.2.5 ML風(fēng)格的多態(tài)說明 425  
9.3 不可預(yù)知多態(tài) 428  
9.3.1 引言 428  
9.3.2 理論的表達(dá)性和性質(zhì) 429  
9.3.3 歸約的終止 441  
9.3.4 語義模型總結(jié) 445  
9.3.5 基于全總域的模型 447  
9.3.6 部分等價關(guān)系模型 450  
9.4 數(shù)據(jù)抽象與存在類型 456  
9.5 通積. 通和與程序模塊 460  
9.5.1 ML模塊語言 460  
9.5.2 帶有積與和的預(yù)知演算 465  
9.5.3 以積與和來表示模塊 468  
9.5.4 預(yù)知性和論域之間的關(guān)系 469  
第10章 類型適應(yīng)性和相關(guān)概念 472  
10.1 引言 472  
10.2 有類型適應(yīng)性的簡單類型化λ演算 474  
10.3 記錄 478  
10.3.1 記錄類型適應(yīng)性的一般性質(zhì) 478  
10.3.2 帶記錄和類型適應(yīng)性的類型化演算 479  
10.4 類型適應(yīng)性的語義模型 482  
10.4.1 概述 482  
10.4.2 類型適應(yīng)性的轉(zhuǎn)換解釋 482  
10.4.3 類型的子集解釋 488  
10.4.4 部分等價關(guān)系作為類型 493  
10.5 遞歸類型和對象的一個記錄模型 497  
10.6 帶衍類型約束的多態(tài) 504  
第11章 類型推理 513  
11.1 類型推理的介紹 513  
11.2 帶類型變量的λ→的類型推理 516  
11.2.1 λt→語言 516  
11.2.2 代入,253實(shí)例和合一 517  
11.2.3 主參數(shù)分離類型求取算法 521  
11.2.4 隱式類型求取 524  
11.2.5 類型求取和合一的等價性 526  
11.3 帶多態(tài)聲明的類型推理 530  
11.3.1 ML類型推理和多態(tài)變量 530  
11.3.2 兩個隱式類型求取規(guī)則集 531  
11.3.3 類型推理算法 533  
11.3.4 ML1和ML2的等價性 538  
11.3.5 ML類型推理的復(fù)雜度 541  
參考文獻(xiàn) 548