程序設計方法, 2/e How to Design Programs: An Introduction to Programming and Computing, 2/e

作者簡介
Matthias Felleisen

美國東北大學計算機科學學院Trustee教授，世界知名的計算機科學家，他最為人知的他是PLT Scheme（Racket）語言的創始人。
2009年，他獲得Karl V. Karlstrom傑出教育家獎。
2010年，他獲得了SIGCSE計算機科學教育傑出貢獻獎。
2012年，他獲得了SIGPLAN編程語言成就獎，以表彰他編程語言領域顯著和持久的貢獻。

Robert Bruce Findler 美國西北大學計算機科學副教授

Matthew Flatt 美國猶他大學計算機學院教授

Shriram Krishnamurthi 美國布朗大學計算機科學教授
（本書第一作者是其餘3位作者的博士生導師）

譯者簡介

朱崇愷

美國猶他大學計算機科學碩士，碩士生導師為本書第三作者馬修·弗拉特。
中文圈內最早的PLT Scheme（Racket的前身）研究者之一。
除了翻譯本書，還翻譯過Programming Languages: Application and Interpretation （PLAI）和Object-Oriented Programming Languages: Application and Interpretation（OOPLAI）。
 

目 錄

 

 

 

開篇：如何編程

算術　3

輸入和輸出　6

計算的多種方式　10

一個程序，多個定義　13

另一個定義　15

現在你是一名程序員了　17

不！　17

第　一部分 固定大小的數據

第　1章 算術　20

1.1　數值的算術　21

1.2　字符串的算術　22

1.3　二者的混合　23

1.4　圖像的算術　24

1.5　布爾值的算術　26

1.6　布爾值的混合　27

1.7　謂詞：瞭解你的數據　29

第　2章 函數和程序　31

2.1　函數　31

2.2　計算　33

2.3　函數的復合　36

2.4　全局常量　38

2.5　程序　39

第3章　程序設計方法　49

3.1　設計函數　50

3.2　熟練習題：函數　54

3.3　領域知識　54

3.4　從函數到程序　54

3.5　關於測試　55

3.6　設計世界程序　56

3.7　虛擬寵物世界　63

第4章　區間、枚舉和條目　65

4.1　條件編程　65

4.2　條件計算　67

4.3　枚舉　69

4.4　區間　71

4.5　條目　75

4.6　條目的設計　80

4.7　有限狀態世界　82

第5章　添加結構體　88

5.1　從位置到posn結構體　88

5.2　posn的計算　88

5.3　posn的編程　89

5.4　定義結構體類型　91

5.5　結構體的計算　94

5.6　結構體的編程　97

5.7　數據的空間　102

5.8　結構體的設計　105

5.9　世界中的結構體　106

5.10　圖形編輯器　107

5.11　再探虛擬寵物　109

第6章　條目和結構體　111

6.1　再談條目的設計　111

6.2　世界的混合　119

6.3　輸入錯誤　121

6.4　世界中的檢查　124

6.5　相等謂詞　125

第7章　總結　127

獨立章節1　初級語言　128

初級語言的詞匯　128

初級語言的文法　129

初級語言的含義　131

含義和計算　133

初級語言中的錯誤　133

布爾表達式　135

常量定義　136

結構體類型定義　137

初級語言中的測試　139

初級語言的錯誤消息　140

第二部分　任意大的數據

第8章　鏈表　146

8.1　創建鏈表　146

8.2　'()是什麽，cons又是什麽　149

8.3　用鏈表編程　151

8.4　使用鏈表進行計算　154

第9章　使用自引用數據定義進行設計　156

9.1　熟練習題：鏈表　160

9.2　非空鏈表　161

9.3　自然數　166

9.4　俄羅斯套娃　168

9.5　鏈表和世界程序　171

9.6　關於鏈表和集合　174

第　10章 再談鏈表　178

10.1　生成鏈表的函數　178

10.2　鏈表中的結構體　180

10.3　鏈表中鏈表以及文件　183

10.4　再談圖形編輯器　189

第　11章 組合式設計　197

11.1　list函數　197

11.2　函數的組合　199

11.3　遞歸的輔助函數　200

11.4　一般化的輔助函數　204

第　12章 項目：鏈表　212

12.1　現實世界中的數據：字典　212

12.2　現實世界中的數據：iTunes　213

12.3　文字游戲—組合的示例　217

12.4　文字游戲—問題的核心　220

12.5　貪吃蛇　221

12.6　簡單俄羅斯方塊　223

12.7　全面太空戰爭　225

12.8　有限狀態機　226

第　13章 總結　231

獨立章節2　Quote和Unquote　232

Quote　232

Quasiquote和Unquote　233

Unquote　Splice　236

第三部分　抽象

第　14章 無處不在的相似性　242

14.1　函數的相似性　242

14.2　不同的相似性　243

14.3　數據定義的相似性　246

14.4　函數是值　248

14.5　函數的計算　249

第　15章 設計抽象　252

15.1　抽象的示例　252

15.2　簽名的相似性　255

15.3　單個控制點　259

15.4　模板的抽象　259

第　16章 使用抽象　261

16.1　現有的抽象　261

16.2　局部定義　264

16.3　局部定義增強表達能力　266

16.4　local的計算　268

16.5　使用抽象的示例　271

16.6　用抽象設計　274

16.7　熟悉抽象的習題　275

16.8　項目中的抽象　276

第　17章 匿名函數　278

17.1　lambda函數　278

17.2　lambda的計算　280

17.3　用lambda抽象　282

17.4　用lambda制定規範　284

17.5　用lambda表示　289

第　18章 總結　293

獨立章節3　作用域和抽象　294

作用域　294

中級語言的循環　298

模式匹配　304

第四部分　交織的數據

第　19章 S表達式之詩　310

19.1　樹　310

19.2　森林　316

19.3　S表達式　317

19.4　對交織數據的設計　321

19.5　項目：二叉查找樹　322

19.6　函數的簡化　325

第　20章 迭代改進　327

20.1　數據分析　327

20.2　數據定義的改進　328

20.3　函數的改進　330

第　21章 解釋器的改進　332

21.1　表達式的解釋　332

21.2　變量的解釋　335

21.3　函數的解釋　336

21.4　解釋一切　338

第　22章 項目：XML商業　340

22.1　XML和S表達式　340

22.2　XML枚舉的呈現　344

22.3　領域特定語言　348

22.4　讀入XML　352

第　23章 同時處理　355

23.1　同時處理兩個鏈表：情況1　355

23.2　同時處理兩個鏈表：情況2　356

23.3　同時處理兩個鏈表：情況3　357

23.4　函數的簡化　360

23.5　設計讀入兩個復雜輸入的函數　361

23.6　熟練習題：兩個輸入　362

23.7　項目：數據庫　365

第　24章 總結　374

獨立章節4　數值的本質　375

固定大小的數值算術　375

溢出　379

下溢出　379

教學語言中的數值　380

第五部分　生成遞歸

第　25章 非標準遞歸　386

25.1　無結構體的遞歸　386

25.2　忽略結構體的遞歸　389

第　26章 設計算法　393

26.1　調整設計訣竅　393

26.2　終止　394

26.3　對比結構化遞歸和生成遞歸　396

26.4　做出選擇　397

第　27章 主題的變化　401

27.1　初試分形　401

27.2　二分查找　403

27.3　初探解析　407

第　28章 數學的例子　411

28.1　牛頓法　411

28.2　數值積分　414

28.3　項目：高斯消元　418

第　29章 回溯的算法　423

29.1　圖的遍歷　423

29.2　項目：回溯　430

第30章　總結　434

獨立章節5　計算的成本　435

具體的時間和抽象的時間　436

“數量級”的定義　440

為何使用謂詞和選擇函數　442

第六部分　知識的累積

第31章　知識的丟失　446

31.1　結構處理的問題　446

31.2　生成遞歸的問題　449

第32章　累積器風格函數的設計　453

32.1　認識到需要累積器　453

32.2　添加累積器　454

32.3　將函數轉換為累積器風格　455

32.4　帶鼠標的圖形編輯器　464

第33章　累積的更多用途　466

33.1　累積器和樹　466

33.2　帶累積器的數據表示　470

33.3　作為結果的累積器　474

第34章　總結　479

尾聲：繼續前進　481