程式設計語言概念
程式設計語言概念圖書作者： John C.Mitchell 著 馮建華、王益、廖雨果、李國良 譯
出版社：清華大學出版社
ISBN：7302111073
出版時間： 2005-10第1版
印刷時間：2005-10第1次印刷
開 本： 16
價 格(元)：56
最好的程式設計語言就是編程思考中的概念上的世界。
——Alan Perlis，NATO軟體工程技術會議，羅馬，1969
程式設計語言為程式設計師寫出一個好的程式提供了所需的抽象機制、組織原則以及控制結構。本書所介紹的是在程式設計語言中出現的概念，即在程式設計語言的實現過程中產生的問題，以及語言的設計方式對程式開發產生的影響。
前 言
最好的程式設計語言就是編程思考中的概念上的世界。
--Alan Perlis，NATO軟體工程技術會議，羅馬，1969
程式設計語言為程式設計師寫出一個好的程式提供了所需的抽象機制、組織原則以及控制結構。本書所介紹的是在程式設計語言中出現的概念，即在程式設計語言的實現過程中產生的問題，以及語言的設計方式對程式開發產生的影響。
本書分為4個部分：
n 第1部分：函式與基本原理
n 第2部分：過程、類型、記憶體管理與控制
n 第3部分：模組、抽象與面向對象程式設計
n 第4部分：並發性與邏輯編程
第1部分將Lisp作為分析程式設計語言的示例，對其進行了簡單介紹，內容包括編譯器結構、解析、朗母達演算以及指稱語義。可計算性一章還涉及了編譯時程式分析和最佳化的限制。
第2部分通過過程化的Algol系列語言和ML，介紹了類型、記憶體管理和控制結構。
第3部分介紹使用抽象數據類型、模組和對象來組織程式。由於目前面向對象編程廣受推崇，於是我們對幾種面向對象語言進行了對比。有專門的章節對simula、Smalltalk、C++和Java進行研究和比較。
第4部分介紹了支持並發性的語言機制和邏輯編程。
本書面向的讀者是有一定編程基礎的大學本科高年級學生和研究生新生。他們理解C或其他過程化語言，熟悉C++或者其他面向對象的程式設計語言。如果讀者具備一些Lisp、Scheme或者ML的經驗將會對第1部分和第2部分的理解有所幫助，但不具備這些背景知識也同樣能學好這門課程。對算法和數據結構進行簡單分析的經驗也對理解本書有所幫助。例如，在比較某種構造的實現方式的時候，如果能夠區分常數時間複雜性、多項式時間複雜性和指數時間複雜性將有助於理解。
在學習了本書之後，讀者將會對過去40年中所使用過的各種程式設計語言有更好的理解，對程式設計語言的設計過程中出現的問題和折衷有更深的認識，也會對所使用的程式設計語言的利弊有更透徹的了解。由於不同的語言體現了不同的編程概念，把其他語言中的思想引入到自己所編寫的程式中將會提高讀者的編程能力。
致謝
這本書的手稿源於我從1993年開始開設的一門程式設計語言課程（Standford CS 242）的筆記。每年都有精力充沛的助教幫助我調試課程的示例程式，設計課程作業和準備解決方案模型。該課程的組織和內容都受益於他們的建議。特別感謝Kathleen Fisher，他在1993年和1994年擔任助教，並於1995年我不在校的時候教授課程。Kanthleen早些年幫我組織材料，並在1995年將我的手稿轉錄成線上文檔。感謝Amit Patel主動組織布置作業和解決方案，感謝Vitaly Shmatikov對程式設計語言術語表做出的不懈努力。Anne Bracy、Dan Bentley和Stephen Freund仔細地校對了許多章節。
劍橋大學出版社的Lauren Cowles、Alan Harvey和David Tranah給予我支持和幫助。我要特別感謝Lauren對草稿的所有12章都仔細閱讀並詳細做注。同時也要感謝他們邀請的校閱者，他們對本書的早期版本提出了很多寶貴的建議。Zena Ariola從本書的初稿開始就連續幾年在俄勒岡州大學教授此書，並提出了很多很好的建議；還有很多其他講師也提供了很多建議。
最後，特別感謝Krzystof Apt對"邏輯編程"一章做出的貢獻。
John C. Mitchell
目錄
第1部分函式與基本原理
第1章導言 2
1.1程式設計語言 2
1.2目標 3
1.2.1總體目標 3
1.2.2特殊主題 3
1.3程式設計語言的歷史 4
1.4組織：概念和語言 5
第2章可計算性 7
2.1部分函式與可計算性 7
2.1.1表達式、錯誤和非終止符 7
2.1.2部分函式 8
2.1.3可計算性 9
2.2本章小結 11
習題 11
第3章Lisp語言：函式、遞歸和列表 13
3.1Lisp語言的歷史 13
3.2好的語言設計 13
3.3語言簡述 15
3.4Lisp設計中的創新 18
3.4.1語句和表達式 18
3.4.2條件表達式 19
3.4.3Lisp抽象機 20
3.4.4把程式作為數據 23
3.4.5函式表達式 24
3.4.6遞歸 25
3.4.7高階函式 25
3.4.8垃圾收集 26
3.4.9純Lisp與副作用 29
3.5本章小結 30
習題 30
第4章基本原理 38
4.1編譯器和語法 38
4.1.1一個簡單編譯器的結構 38
4.1.2文法和解析樹 41
4.1.3解析和優先權 43
4.2朗母達演算 44
4.2.1函式和函式表達式 44
4.2.2朗母達表達式 45
4.2.3朗母達演算編程 49
4.2.4歸約、匯合和範式 51
4.2.5朗母達演算的重要特徵 52
4.3指稱語義 52
4.3.1目標語言和元語言 53
4.3.2二進制數的指稱語義 54
4.3.3While程式的指稱語義 55
4.3.4透視和非標準語義 58
4.4函式型語言和命令型語言 60
4.4.1命令語句和聲明語句 60
4.4.2功能型程式和命令型程式 61
4.5本章小結 65
習題 66
第2部分過程、類型、記憶體管理與控制
第5章Algol與ML語言 74
5.1Algol家族的程式語言 74
5.1.1Algol 60 74
5.1.2Algol 68 76
5.1.3Pascal 77
5.1.4Modula 78
5.2C語言的發展 78
5.3LCF系統和ML 80
5.4ML程式設計語言 82
5.4.1互動會話和運行時環境 82
5.4.2基本類型和類型構造器 85
5.4.3模式、聲明、函式表達式 89
5.4.4ML數據類型的聲明 92
5.4.5ML的引用單元與賦值 94
5.4.6ML小結 97
5.5本章小結 98
習題 98
第6章類型系統和類型推測 105
6.1程式設計中的類型 105
6.1.1程式的組織和文檔 105
6.1.2類型錯誤 106
6.1.3類型與最佳化 107
6.2類型安全和類型檢查 108
6.2.1類型安全 108
6.2.2編譯時和運行時的類型檢查 108
6.3類型推測 110
6.3.1第一個類型推測的示例 110
6.3.2類型推測算法 111
6.4多態和重載 118
6.4.1參數多態 118
6.4.2參數多態的實現 120
6.4.3重載 122
6.5類型聲明和類型等價性 123
6.5.1透明的類型聲明 123
6.5.2C語言的聲明和結構 124
6.5.3ML類型聲明 125
6.6本章小結 126
習題 127
第7章作用域、函式和存儲管理 133
7.1塊結構的語言 133
7.2內嵌塊 135
7.2.1活動記錄和局部變數 135
7.2.2全局變數和控制鏈 138
7.3函式和子程式 139
7.3.1函式的活動記錄 139
7.3.2參數傳遞 141
7.3.3全局變數（一階情況） 144
7.3.4末端遞歸（一階情況） 146
7.4高階函式 148
7.4.1一階函式 148
7.4.2將函式傳遞給函式 149
7.4.3從嵌套作用域中返回函式 152
7.5本章小結 154
習題 155
第8章順序語言中的控制 168
8.1結構化控制 168
8.1.1意大利麵條式的代碼 168
8.1.2結構化控制 168
8.2異常 169
8.2.1異常機制的目的 169
8.2.2ML異常 171
8.2.3C++異常 173
8.2.4關於異常的更多內容 175
8.3延續 179
8.3.1表示"程式其餘部分"的函式 179
8.3.2延續傳遞形式和末端調用 180
8.3.3延續的編譯 183
8.4函式和求值順序 183
8.5本章小結 186
習題 187
第3部分模組、抽象與面向對象程式設計
第9章數據抽象和模組化 192
9.1結構化程式設計 192
9.1.1數據細化 193
9.1.2模組化 194
9.2支持抽象機制的語言 196
9.2.1抽象 197
9.2.2抽象數據類型 198
9.2.3ML抽象數據類型 198
9.2.4表達無關性 201
9.2.5數據類型介紹 202
9.3模組 204
9.3.1Modula和Ada 205
9.3.2ML模組 207
9.4一般抽象 210
9.4.1C++函式模板 210
9.4.2標準的ML算符 212
9.4.3C++標準模板庫 215
9.5本章小結 218
習題 220
第10章面向對象語言的概念 226
10.1面向對象設計 226
10.2面向對象語言中的4個基本概念 227
10.2.1動態查找 227
10.2.2抽象 229
10.2.3子類型 231
10.2.4繼承 232
10.2.5作為對象的閉包 233
10.2.6繼承不是子類型 234
10.3編程結構 235
10.4設計模式 236
10.5本章小結 239
10.6展望：Simula、Smalltalk、C++、Java 239
習題 240
第11章對象的歷史：Simula和Smalltalk 246
11.1Simula面向對象機理 246
11.1.1對象和仿真 246
11.1.2Simula的主要概念 247
11.2Simula中的對象 247
11.2.1Simula中面向對象的基本特點 248
11.2.2一個點線圓的例子 248
11.2.3示例代碼和對象表示 250
11.3Simula中的子類和繼承 251
11.3.1對象類型和子類型 252
11.4Smalltalk的發展 254
11.5Smalltalk語言的特點 255
11.5.1術語 255
11.5.2類和對象 255
11.5.3繼承 258
11.5.4Smalltalk的抽象性 260
11.6Smalltalk的靈活性 260
11.6.1動態查找和多態 260
11.6.2布爾變數和塊 261
11.6.3self和super 262
11.6.4系統擴充：Ingalls測試 263
11.7子類型與繼承的重要性 264
11.7.1對象類型作為接口 264
11.7.2子類型 265
11.7.3子類型和繼承 265
11.8本章小結 267
習題 268
第12章C++對象與運行效率 277
12.1設計目標和限制 277
12.1.1與C的兼容性 277
12.1.2C++的成功 278
12.2C++概述 278
12.2.1增加了C中沒有的對象 279
12.2.2面向對象的特點 282
12.2.3好的決定和問題所在 282
12.3類、繼承和虛函式 284
12.3.1C++類和對象 284
12.3.2C++派生類（繼承） 285
12.3.3虛函式 287
12.3.4為什麼C++的查找比Smalltalk的查找簡單 288
12.4子類型 292
12.4.1子類型原理 292
12.4.2公有基類 293
12.4.3public成員的特殊類型 294
12.4.4抽象基類 294
12.5多重繼承 295
12.5.1多重繼承的實現 296
12.5.2命名衝突、繼承和虛擬基類 298
12.6本章小結 301
習題 302
第13章可移植性和安全性：Java語言 319
13.1Java語言概述 320
13.1.1Java語言的目標 320
13.1.2設計決策 320
13.2Java的類和繼承 322
13.2.1類和對象 322
13.2.2包和可視性 325
13.2.3繼承 325
13.2.4抽象類和接口 327
13.3Java的類型及子類型關係 328
13.3.1類型的分類 328
13.3.2類和接口的子類型關係 329
13.3.3數組、協變和反協變 330
13.3.4Java 異常類的層次關係 331
13.3.5子類型多態和通用編程 333
13.4Java系統架構 336
13.4.1Java虛擬機 336
13.4.2類載入器 337
13.4.3Java連結器、檢驗器及類型約束 337
13.4.4位元組碼解釋器和方法查詢 338
13.5安全特性 342
13.5.1緩衝區泄漏攻擊 343
13.5.2Java沙箱 344
13.5.3安全和類型安全 346
13.6本章小結 347
習題 349
第4部分並發性與邏輯編程
第14章並發和分散式編程 358
14.1並發的基本概念 359
14.1.1執行順序和非確定性 359
14.1.2通信、協調和原子性 361
14.1.3互斥和封鎖 361
14.1.4信號量 364
14.1.5管程 365
14.2Actor模型 366
14.3並發ML 369
14.3.1執行緒和通道 369
14.3.2選擇式通信和保護命令 371
14.3.3一流的同步操作：事件 373
14.4Java的並發性 377
14.4.1執行緒、通信與同步 378
14.4.2同步方法 380
14.4.3虛擬機與存儲模型 382
14.4.4分散式程式設計與遠程方法調用 386
14.5本章小結 388
習題 390
第15章邏輯編程範例和Prolog 396
15.1邏輯編程的歷史 396
15.2邏輯編程範例的簡要概述 397
15.2.1說明性編程 397
15.2.2互動編程 397
15.3作為原子動作統一解決的等式 398
15.3.1項 398
15.3.2置換 399
15.3.3最通用的合一置換 399
15.3.4合一算法 400
15.4子句作為過程聲明的一部分 402
15.4.1簡單子句 402
15.4.2計算過程 402
15.4.3子句 404
15.5Prolog編程 405
15.5.1單個程式的多重使用 405
15.5.2邏輯變數 406
15.6Prolog中的數學 409
15.6.1數學運算符 410
15.6.2數學比較關係 410
15.6.3對算術表達式的賦值 412
15.7控制、雙性語法和元變數 414
15.7.1剪下 414
15.7.2雙性語法和元變數 415
15.7.3控制設備 416
15.7.4失敗的否定 418
15.7.5高階編程和Prolog中的元編程 419
15.8Prolog的評價 421
15.9書目評價 423
15.10本章小結 423
附錄A程式實例補充 425
A.1程式和面向對象機制 425
A.1.1類型的程式：典型案例版本 426
A.1.2shape程式：面向對象版本 430
附錄B術語表 433
