《程式設計語言概念》為程式設計師寫出一個好的程式提供了所需的抽象機制、組織原則以及控制結構。本書所介紹的是在程式設計語言中出現的概念，即在程式設計語言的實現過程中產生的問題，以及語言的設計方式對程式開發產生的影響。
基本介紹
前言,結構,概述,略述,讀者群體,本書作用,致謝,目錄,
前言
最好的程式設計語言就是編程思考中的概念上的世界。
結構
概述
本書分為4個部分：
第1部分：函式與基本原理
第2部分：過程、類型、記憶體管理與控制
第3部分：模組、抽象與面向對象程式設計
第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.1 Lisp語言的歷史 13
3.2 好的語言設計 13
3.3 語言簡述 15
3.4 Lisp設計中的創新 18
3.4.1 語句和表達式 18
3.4.2 條件表達式 19
3.4.3 Lisp抽象機 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.3 While程式的指稱語義 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.1 Algol家族的程式語言 74
5.1.1 Algol 60 74
5.1.2 Algol 68 76
5.1.3 Pascal 77
5.1.4 Modula 78
5.2 C語言的發展 78
5.3 LCF系統和ML 80
5.4 ML程式設計語言 82
5.4.1 互動會話和運行時環境 82
5.4.2 基本類型和類型構造器 85
5.4.3 模式、聲明、函式表達式 89
5.4.4 ML數據類型的聲明 92
5.4.5 ML的引用單元與賦值 94
5.4.6 ML小結 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.2 C語言的聲明和結構 124
6.5.3 ML類型聲明 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.2 ML異常 171
8.2.3 C++異常 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.3 ML抽象數據類型 198
9.2.4 表達無關性 201
9.2.5 數據類型介紹 202
9.3 模組 204
9.3.1 Modula和Ada 205
9.3.2 ML模組 207
9.4 一般抽象 210
9.4.1 C++函式模板 210
9.4.2 標準的ML算符 212
9.4.3 C++標準模板庫 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.1 Simula面向對象機理 246
11.1.1 對象和仿真 246
11.1.2 Simula的主要概念 247
11.2 Simula中的對象 247
11.2.1 Simula中面向對象的基本特點 248
11.2.2 一個點線圓的例子 248
11.2.3 示例代碼和對象表示 250
11.3 Simula中的子類和繼承 251
11.3.1 對象類型和子類型 252
11.4 Smalltalk的發展 254
11.5 Smalltalk語言的特點 255
11.5.1 術語 255
11.5.2 類和對象 255
11.5.3 繼承 258
11.5.4 Smalltalk的抽象性 260
11.6 Smalltalk的靈活性 260
11.6.1 動態查找和多態 260
11.6.2 布爾變數和塊 261
11.6.3 self和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.2 C++的成功 278
12.2 C++概述 278
12.2.1 增加了C中沒有的對象 279
12.2.2 面向對象的特點 282
12.2.3 好的決定和問題所在 282
12.3 類、繼承和虛函式 284
12.3.1 C++類和對象 284
12.3.2 C++派生類（繼承） 285
12.3.3 虛函式 287
12.3.4 為什麼C++的查找比Smalltalk的查找簡單 288
12.4 子類型 292
12.4.1 子類型原理 292
12.4.2 公有基類 293
12.4.3 public成員的特殊類型 294
12.4.4 抽象基類 294
12.5 多重繼承 295
12.5.1 多重繼承的實現 296
12.5.2 命名衝突、繼承和虛擬基類 298
12.6 本章小結 301
習題 302
第13章 可移植性和安全性：Java語言 319
13.1 Java語言概述 320
13.1.1 Java語言的目標 320
13.1.2 設計決策 320
13.2 Java的類和繼承 322
13.2.1 類和對象 322
13.2.2 包和可視性 325
13.2.3 繼承 325
13.2.4 抽象類和接口 327
13.3 Java的類型及子類型關係 328
13.3.1 類型的分類 328
13.3.2 類和接口的子類型關係 329
13.3.3 數組、協變和反協變 330
13.3.4 Java 異常類的層次關係 331
13.3.5 子類型多態和通用編程 333
13.4 Java系統架構 336
13.4.1 Java虛擬機 336
13.4.2 類載入器 337
13.4.3 Java連結器、檢驗器及類型約束 337
13.4.4 位元組碼解釋器和方法查詢 338
13.5 安全特性 342
13.5.1 緩衝區泄漏攻擊 343
13.5.2 Java沙箱 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.2 Actor模型 366
14.3 並發ML 369
14.3.1 執行緒和通道 369
14.3.2 選擇式通信和保護命令 371
14.3.3 一流的同步操作：事件 373
14.4 Java的並發性 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.5 Prolog編程 405
15.5.1 單個程式的多重使用 405
15.5.2 邏輯變數 406
15.6 Prolog中的數學 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.8 Prolog的評價 421
15.9 書目評價 423
15.10 本章小結 423
附錄A 程式實例補充 425
A.1 程式和面向對象機制 425
A.1.1 類型的程式：典型案例版本 426
A.1.2 shape程式：面向對象版本 430
附錄B 術語表 433
