程序設(shè)計語言：概念和結(jié)構(gòu)

第一部分   引      言
第1章   程序設(shè)計語言的位置 2
1.1   走向高級語言 2
1.1.1   機器語言是晦澀難懂的 3
1.1.2   匯編語言是低級的 3
1.1.3   高級語言的優(yōu)點 5
1.2   規(guī)模的問題 6
1.2.1   人的錯誤因素 6
1.2.2   程序設(shè)計語言扮演的角色 7
1.3   程序設(shè)計范型 7
1.3.1   命令式程序設(shè)計 8
1.3.2   函數(shù)式程序設(shè)計 9
1.3.3   面向?qū)ο蟮某绦蛟O(shè)計 11
1.3.4   邏輯程序設(shè)計 12
1.3.5   語言的選擇 12
1.4   語言實現(xiàn)：在裂谷上架橋 12
1.4.1   編譯 13
1.4.2   解釋 14
1.4.3   編譯器和解釋器：對比 15
練習 15
引文注記 16
第2章   語言的描述：語法結(jié)構(gòu) 18
2.1   表達式的記法 20
2.1.1   前綴記法 20
2.1.2   后綴記法 21
2.1.3   中綴記法：優(yōu)先級和結(jié)合性 21
2.1.4   混合記法 22
2.2   抽象語法樹 22
2.3   詞語法 24
2.4   上下文無關(guān)文法 25
2.4.1   文法介紹 25
2.4.2   上下文無關(guān)文法的定義 26
2.4.3   BNF：Backus-Naur范式 26
2.4.4   語法分析樹描繪了具體語法 27
2.4.5   語法的歧義性 28
2.4.6   懸空的else的歧義性 28
2.4.7   導出 29
2.5   表達式的文法 30
2.5.1   中綴表達式中的表列 30
2.5.2   從抽象語法到具體語法 31
2.6   文法的各種變形 33
2.6.1   擴充的BNF 33
2.6.2   語法圖 35
練習 35
引文注記 38
第二部分   命令式程序設(shè)計
第3章   語句：結(jié)構(gòu)化程序設(shè)計 41
3.1   結(jié)構(gòu)化程序設(shè)計的必要性 41
3.1.1   靜態(tài)程序和動態(tài)計算 41
3.1.2   命令式語言的設(shè)計原則 42
3.1.3   一個例子 42
3.1.4   不變式：程序設(shè)計 43
3.2   語法制導的控制流 44
3.2.1   語句的復(fù)合 44
3.2.2   選擇：條件語句 45
3.2.3   循環(huán)結(jié)構(gòu)：while和repeat 46
3.2.4   定性迭代：for循環(huán) 48
3.2.5   選擇：case語句 48
3.2.6   case語句的實現(xiàn) 49
3.3   設(shè)計考慮：語法 50
3.3.1   序列：分隔符和終止符 50
3.3.2   避免懸空的else 52
3.4   處理循環(huán)中的特殊情況 53
3.4.1   循環(huán)中的break和continue語句 54
3.4.2   return語句 56
3.4.3   goto語句 56
3.5   使用不變式做程序設(shè)計 56
3.5.1   前條件和后條件 57
3.5.2   實例：線性搜索 58
3.6   部分正確性的證明規(guī)則 60
3.6.1   斷言和公式 61
3.6.2   復(fù)合語句的證明規(guī)則 61
3.6.3   條件語句的證明規(guī)則 62
3.6.4   有關(guān)while語句的規(guī)則 62
3.6.5   關(guān)于賦值的規(guī)則 62
3.6.6   化簡規(guī)則 63
3.6.7   Pascal中的語句 63
3.7   C語言的控制流 63
3.7.1   賦值運算符 64
3.7.2   表達式里的賦值 65
3.7.3   C語言的for循環(huán)：非定性迭代 65
3.7.4   循環(huán)中的break和continue語句 66
練習 66
引文注記 70
第4章   類型：數(shù)據(jù)表示 72
4.1   類型的作用 72
4.1.1   值和它們的類型 73
4.1.2   類型表達式 73
4.1.3   本章中的類型 73
4.1.4   靜態(tài)布局決策 74
4.1.5   有關(guān)類型名. 數(shù)組和記錄的預(yù)覽 75
4.2   基本類型 76
4.2.1   枚舉 76
4.2.2   整型和實型 77
4.2.3   布爾表達式的短路求值 77
4.2.4   子域 78
4.2.5   基本類型的布局 78
4.2.6   程序設(shè)計的風格：字符和類型轉(zhuǎn)換 78
4.3   數(shù)組：元素的序列 79
4.3.1   數(shù)組類型 79
4.3.2   數(shù)組的布局 81
4.3.3   數(shù)組邊界和存儲分配 82
4.3.4   數(shù)組的值和初始化 83
4.4   記錄：命名的域 84
4.4.1   記錄類型有一組特定的域 84
4.4.2   變量聲明分配存儲空間 84
4.4.3   對記錄的操作 84
4.4.4   數(shù)組和記錄的比較 85
4.5   聯(lián)合和變體記錄 85
4.5.1   變體記錄的布局 86
4.5.2   變體記錄損害類型安全 87
4.6   集合 88
4.6.1   集合的值 88
4.6.2   集合類型 88
4.6.3   集合類型的實現(xiàn) 88
4.6.4   集合的運算 88
4.7   指針：效率和動態(tài)存儲分配 89
4.7.1   指針類型 90
4.7.2   指針操作 90
4.7.3   數(shù)據(jù)結(jié)構(gòu)的增長和縮減 90
4.7.4   懸空指針和存儲流失 91
4.7.5   指針作為代理 92
4.8   兩種字符串列表 95
4.8.1   Pascal的一種表示 95
4.8.2   C語言的一種表示 96
4.9   類型和錯誤檢查 97
4.9.1   變量約束：變量的類型 98
4.9.2   類型系統(tǒng)：表達式的類型 98
4.9.3   類型檢查的基本規(guī)則 99
4.9.4   類型名和類型等價 99
4.9.5   靜態(tài)和動態(tài)類型檢查 101
練習 102
引文注記 104
第5章   過程活動 105
5.1   對過程的介紹 106
5.1.1   過程調(diào)用 106
5.1.2   過程的要素 106
5.1.3   遞歸：過程的多個活動 109
5.1.4   過程的價值 109
5.2   參數(shù)傳遞方式 110
5.2.1   值調(diào)用 110
5.2.2   引用調(diào)用 111
5.2.3   值結(jié)果調(diào)用 113
5.3   名字的作用域規(guī)則 114
5.3.1   詞法作用域和動態(tài)作用域 114
5.3.2   詞法作用域與局部變量的重命名 115
5.3.3   宏展開與動態(tài)作用域 116
5.3.4   按名調(diào)用與詞法作用域 117
5.4   源文本中的嵌套作用域 118
5.4.1   聲明的作用域 118
5.4.2   嵌套作用域：C中的變量聲明 119
5.4.3   嵌套作用域：Pascal中的過程聲明 121
5.5   活動記錄 122
5.5.1   活動間的控制流 122
5.5.2   活動記錄的元素 124
5.5.3   堆存儲分配和釋放 127
5.5.4   堆棧分配和釋放 127
5.5.5   在編譯時分配靜態(tài)變量 128
5.6   詞法作用域：在C中的過程 128
5.6.1   C程序的存儲布局 129
5.6.2   局部變量的存儲 129
5.6.3   C的過程調(diào)用和返回 130
5.6.4   運行時的變量訪問 131
5.6.5   過程作為參數(shù) 131
5.6.6   懸空指針 132
5.6.7   尾遞歸消除 132
5.7   詞法作用域：嵌套過程和Pascal 135
5.7.1   可見性規(guī)則 135
5.7.2   訪問非局部變量：控制鏈和訪問鏈 136
5.7.3   過程的調(diào)用和返回 138
5.7.4   過程作為參數(shù) 139
5.7.5   用于快速訪問的區(qū)頭向量 139
練習 141
引文注記 143
第三部分   面向?qū)ο蟪绦蛟O(shè)計
第6章   數(shù)據(jù)和操作 147
6.1   程序構(gòu)造的結(jié)構(gòu) 147
6.1.1   過程：提高計算的層次 148
6.1.2   程序靜態(tài)文本的模塊劃分 149
6.1.3   用戶定義數(shù)據(jù)類型 150
6.1.4   幾種方法的比較 151
6.2   信息隱藏 152
6.2.1   動機：區(qū)分行為與實現(xiàn) 152
6.2.2   數(shù)據(jù)不變式 154
6.2.3   數(shù)據(jù)的可見性 154
6.2.4   實現(xiàn)的隱藏和程序開發(fā) 154
6.3   使用模塊設(shè)計程序 155
6.3.1   表達式求值程序的設(shè)計 155
6.3.2   程序組織 157
6.3.3   討論：程序組織 161
6.4   模塊和用戶定義類型 161
6.4.1   導出名字和導入名字 161
6.4.2   導出類型 162
6.5   C++的類聲明 164
6.5.1   類聲明中的數(shù)據(jù)和操作 164
6.5.2   將類名作為定義的類型使用 166
6.5.3   公用. 私用和保護成員 167
6.6   C++的動態(tài)存儲分配 168
6.6.1   指向?qū)ο蟮闹羔?168
6.6.2   用建構(gòu)函數(shù)和析構(gòu)函數(shù)進行動態(tài)
存儲分配 169
6.6.3   鏈表的單元 169
6.7   模板：參數(shù)化類型 172
6.8   C++對象的實現(xiàn) 173
6.8.1   一個簡單實現(xiàn) 173
6.8.2   函數(shù)體的在線展開 174
6.8.3   類聲明中的私用變量 174
練習 175
引文注記 178
第7章   面向?qū)ο蟪绦蛟O(shè)計 179
7.1   什么是對象 179
7.1.1   對象的外部和內(nèi)部視圖 179
7.1.2   形狀的屬性 180
7.2   面向?qū)ο蟮乃枷?181
7.2.1   將對象組織為類層次結(jié)構(gòu) 181
7.2.2   對象響應(yīng)消息, 對象具有狀態(tài) 182
7.3   繼承 184
7.3.1   接收者決定一個消息的含義 185
7.3.2   信息隱藏是為了可擴充性 186
7.3.3   添加子類 187
7.3.4   對象和類 189
7.4   用C++語言做面向?qū)ο蟮某绦蛟O(shè)計 189
7.4.1   C++語言回顧 189
7.4.2   基類和派生類 190
7.4.3   公用基類 190
7.4.4   虛函數(shù) 191
7.4.5   C++中形狀實例的細節(jié) 193
7.4.6   初始化和繼承 194
7.5   一個擴充的C++例子 194
7.5.1   素數(shù)篩 194
7.5.2   基類 196
7.5.3   派生類 196
7.5.4   基類和派生類的初始化 196
7.5.5   子類型和超類型 197
7.5.6   虛函數(shù) 198
7.5.7   生成過濾器對象 199
7.5.8   剩余的程序 199
7.6   派生類和信息隱藏 199
7.6.1   公用和私用的基類 200
7.6.2   私用性原理 200
7.6.3   繼承成員的可訪問性 201
7.7   Smalltalk中的對象 202
7.7.1   系統(tǒng)類 202
7.7.2   類定義中的元素 203
7.7.3   消息語法 205
7.8   Smalltalk對象的self 207
7.8.1   發(fā)送給self的消息 208
7.8.2   發(fā)送給super的消息 208
練習 209
引文注記 212
第四部分   函數(shù)式程序設(shè)計
第8章   函數(shù)式程序設(shè)計的要素 215
8.1   一個很小的表達式語言 215
8.1.1   Little Quilt操作什么 215
8.1.2   為方便而做的擴充 217
8.1.3   評論：Little   Quilt的設(shè)計 219
8.2   類型：值和運算 220
8.2.1   構(gòu)造和檢查值的操作 221
8.2.2   基本類型 221
8.2.3   類型的積 221
8.2.4   ML中的類型 223
8.3   函數(shù)聲明 224
8.3.1   函數(shù)作為算法 225
8.3.2   函數(shù)聲明和應(yīng)用的語法 225
8.3.3   遞歸函數(shù) 226
8.4   表達式的求值方式 226
8.4.1   最內(nèi)求值 227
8.4.2   選擇性求值 227
8.4.3   遞歸函數(shù)的求值 228
8.4.4   從左到右的最外求值 228
8.4.5   短路求值 230
8.5   詞法作用域 231
8.5.1   val約束 231
8.5.2   fun約束 232
8.5.3   嵌套的約束 233
8.5.4   同時約束 233
8.6   類型檢查 234
8.6.1   類型推理 234
8.6.2   類型名和類型等價 235
8.6.3   重載：多重含義 235
8.6.4   強制：隱式類型轉(zhuǎn)換 236
8.6.5   多態(tài)性：參數(shù)化類型 236
練習 237
引文注記 240
第9章   一個有類型語言中的函數(shù)式
程序設(shè)計 241
9.1   表的探查 241
9.1.1   表上的運算 242
9.1.2   定義在表上的兩個函數(shù)：append
和reverse 242
9.2   函數(shù)的分情況聲明 244
9.2.1   函數(shù)應(yīng)用 245
9.2.2   模式 246
9.2.3   模式和情況分析 246
9.3   函數(shù)作為一級的值 248
9.3.1   將函數(shù)映射到表的各個元素上 249
9.3.2   匿名函數(shù) 251
9.3.3   選擇性復(fù)制 251
9.3.4   積累結(jié)果 252
9.4   ML：隱含類型 253
9.4.1   類型推理 253
9.4.2   參數(shù)化多態(tài)性 254
9.5   數(shù)據(jù)類型 254
9.5.1   值構(gòu)造符 255
9.5.2   微分：一個傳統(tǒng)實例 257
9.5.3   多態(tài)數(shù)據(jù)類型 258
9.5.4   討論 259
9.6   ML的異常處理 259
9.7   在Standard ML中實現(xiàn)Little Quilt 261
9.7.1   一些輔助函數(shù) 262
9.7.2   拼塊的表示 263
9.7.3   sew運算 263
9.7.4   turn運算 264
9.7.5   拼塊的顯示 266
9.7.6   Little   Quilt中的表達式 267
練習 269
引文注記 271
第10章      表的函數(shù)式程序設(shè)計 272
10.1   Scheme, 一種Lisp方言 272
10.1.1   為什么用Scheme 273
10.1.2   如何與Scheme解釋器交互 273
10.1.3   怎樣寫表達式 274
10.1.4   怎樣定義函數(shù) 275
10.1.5   匿名函數(shù)值 275
10.1.6   條件式 275
10.1.7   let結(jié)構(gòu) 276
10.1.8   引號 277
10.2   表的結(jié)構(gòu) 278
10.2.1   表元素 278
10.2.2   表的運算 279
10.3   表的操作 280
10.3.1   一個有用的函數(shù) 281
10.3.2   連接兩個表 281
10.3.3   將函數(shù)映射到表的所有元素上 282
10.3.4   關(guān)聯(lián)表 283
10.3.5   子表達式的表 284
10.3.6   一個參數(shù)化的函數(shù) 285
10.4   啟發(fā)性的實例：微分 286
10.4.1   語法制導的微分 286
10.4.2   常量 287
10.4.3   變量 287
10.4.4   對和式與乘積的微分規(guī)則 287
10.4.5   和式的微分 287
10.4.6   乘積的微分 289
10.4.7   對微分程序的總結(jié) 289
10.5   表達式化簡 290
10.6   表的存儲管理 292
10.6.1   cons分配單元 293
10.6.2   相等的概念 293
10.6.3   分配和釋放 295
練習 296
引文注記 298
第五部分      其他范型
第11章   邏輯式程序設(shè)計 300
11.1   用關(guān)系做計算 301
11.1.1   關(guān)系 301
11.1.2   規(guī)則和事實 301
11.1.3   查詢 302
11.2   Prolog初步 304
11.2.1   項 304
11.2.2   與Prolog交互 305
11.2.3   存在性查詢 305
11.2.4   全稱性的事實和規(guī)則 306
11.2.5   否定作為失敗 307
11.2.6   合一 308
11.2.7   算術(shù) 309
11.3   Prolog的數(shù)據(jù)結(jié)構(gòu) 309
11.3.1   Prolog中的表 309
11.3.2   項作為數(shù)據(jù) 310
11.4   程序設(shè)計技術(shù) 312
11.4.1   猜測和驗證 312
11.4.2   用變量作為項里的占位符 314
11.4.3   差表 317
11.5   Prolog的控制 318
11.5.1   合一和替換 319
11.5.2   將規(guī)則應(yīng)用于目標 320
11.5.3   Prolog搜索樹 322
11.5.4   目標的順序?qū)⒏淖兘?323
11.5.5   規(guī)則順序影響對解的搜索 324
11.5.6   出現(xiàn)檢查問題 326
11.6   割 326
11.6.1   割作為第一個條件 327
11.6.2   割的作用 328
11.6.3   應(yīng)用割的程序設(shè)計 329
11.6.4   否定等同于失敗 332
練習 333
引文注記 334
第12章   并發(fā)程序設(shè)計導引 336
12.1   硬件的并行性 336
12.1.1   輸入/輸出的并行執(zhí)行 336
12.1.2   中斷和分時 337
12.1.3   多處理器組織結(jié)構(gòu) 338
12.1.4   反應(yīng)式系統(tǒng) 338
12.2   流：隱式的同步 338
12.2.1   進程網(wǎng)絡(luò) 339
12.2.2   管道實例 339
12.3   作為交錯的并發(fā)性 340
12.3.1   線程的交錯 341
12.3.2   Ada中的并發(fā)作業(yè) 341
12.4   進程的活性性質(zhì) 343
12.4.1   資源共享限制并發(fā)性 343
12.4.2   哲學家就餐問題 343
12.4.3   死鎖：無法繼續(xù) 344
12.4.4   活鎖：沒有進程能夠取得進展 344
12.4.5   公平性 344
12.4.6   避免死鎖的發(fā)生 345
12.5   共享數(shù)據(jù)的安全訪問 345
12.5.1   “非確定”的進程 345
12.5.2   臨界區(qū)和互斥 346
12.5.3   可串行化與安全性 347
12.6   Ada中的并發(fā)性 348
12.6.1   握手式同步 348
12.6.2   同步通信 349
12.6.3   有選擇的接收 352
12.7   共享變量的同步訪問 353
12.7.1   對緩沖區(qū)的直接訪問 353
12.7.2   信號量：互斥 355
練習 359
引文注記 362
第六部分      語言的描述
第13章   語義方法 366
13.1   綜合屬性 368
13.1.1   求值順序 369
13.1.2   總結(jié) 369
13.2   屬性文法 370
13.3   自然語義 372
13.3.1   一個計算器 372
13.3.2   環(huán)境為名字約束值 373
13.3.3   let約束 373
13.3.4   基于Prolog的實現(xiàn) 375
13.4   指稱語義 376
13.5   一個Scheme計算器 377
13.6   詞法作用域中的lambda表達式 378
13.6.1   lambda表達式的自然語義 379
13.6.2   環(huán)境的一種實現(xiàn) 380
13.7   一個解釋器 381
13.7.1   常量 381
13.7.2   加引號項 381
13.7.3   變量 382
13.7.4   條件表達式 382
13.7.5   let表達式 382
13.7.6   lambda表達式 383
13.7.7   函數(shù)應(yīng)用 384
13.7.8   初始化環(huán)境 384
13.7.9   解釋器的使用 385
13.8   一個擴充：遞歸函數(shù) 386
13.8.1   作為值的遞歸函數(shù) 386
13.8.2   對解釋器的修改 387
練習 388
引文注記 389
第14章   靜態(tài)類型和Lambda演算 390
14.1   純lambda演算中的相等 391
14.1.1   語法約定 392
14.1.2   自由變量和約束變量 392
14.1.3   替換 393
14.1.4   beta-相等 394
14.2   再論替換 395
14.3   純lambda項的計算 396
14.3.1   歸約 397
14.3.2   不終止的歸約 398
14.3.3   Church-Rosser定理 398
14.3.4   計算規(guī)則 399
14.4   作為lambda項的程序設(shè)計結(jié)構(gòu) 400
14.4.1   一個應(yīng)用lambda演算 400
14.4.2   Curry化 401
14.4.3   常量的歸約規(guī)則 401
14.4.4   語言ML0 402
14.4.5   不動點算子 403
14.5   帶類型的lambda演算 404
14.6   多態(tài)類型 406
14.6.1   取自標準ML的例子 406
14.6.2   顯式的多態(tài)性 407
14.6.3   單態(tài)與多態(tài) 408
14.6.4   Core-XML的類型規(guī)則 409
練習 411
引文注記 412
第15章   語言概覽 414
15.1   Pascal：一種教學語言 414
15.1.1   Pascal的程序結(jié)構(gòu) 415
15.1.2   聲明 415
15.1.3   類型 416
15.1.4   表達式 416
15.1.5   語句 416
15.2   C：系統(tǒng)程序設(shè)計 417
15.2.1   C語言程序結(jié)構(gòu) 417
15.2.2   C的函數(shù) 418
15.2.3   C的變量聲明 419
15.2.4   表達式 419
15.2.5   C的控制流 420
15.2.6   指針和數(shù)組 420
15.2.7   頭文件 421
15.2.8   標準輸入/輸出 422
15.3   C++：多種程序設(shè)計風格 422
15.3.1   C++中的類 422
15.3.2   C++的繼承 424
15.4   Smalltalk語言 424
15.4.1   表達式 426
15.4.2   類和實例方法 426
15.4.3   系統(tǒng)類 427
15.5   Standard ML 428
15.5.1   與ML解釋器交互 428
15.5.2   基于模式匹配的函數(shù)定義 430
15.5.3   數(shù)據(jù)類型 430
15.5.4   異常 430
15.6   Scheme：一種Lisp方言 431
15.6.1   基本結(jié)構(gòu) 432
15.6.2   表操作    433
15.7   Prolog 434
15.7.1   項 435
15.7.2   與Prolog交互 436
15.7.3   規(guī)則 436
15.7.4   查詢 436
15.7.5   算術(shù) 436
15.7.6   作為數(shù)據(jù)的項 437
參考文獻 438
索引 450