程序設計語言概念

程序設計語言編程思考概念。

--，NATO軟體工程技術會議，羅馬，1969

：

第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