計算機程序的構(gòu)造和解釋(原書第2版)典藏版
定 價:79 元
叢書名:計算機科學(xué)叢書
- 作者:[美]哈羅德·阿貝爾森 (Harold Abelson) 等
- 出版時間:2019/7/1
- ISBN:9787111630548
- 出 版 社:機械工業(yè)出版社
- 中圖法分類:TP311.1
- 頁碼:
- 紙張:膠版紙
- 版次:
- 開本:16開
本書曾是美國麻省理工學(xué)院計算機科學(xué)專業(yè)的入門課程教材之一, 從理論上講解計算機程序的創(chuàng)建、 執(zhí)行和研究。 主要內(nèi)容包括:構(gòu)造過程抽象,構(gòu)造數(shù)據(jù)抽象,模塊化、 對象和狀態(tài),元語言抽象,寄存器機器里的計算等。
第2版前言
軟件很可能確實與其他任何東西都不同,它的本意就是被拋棄:這一觀點就是總將它看作一個肥皂泡嗎?
—Alan J. Perlis
自1980年以來,本書的材料就一直在MIT作為計算機科學(xué)入門課程的基礎(chǔ)。在本書第1版出版之前,我們已經(jīng)用這一材料教了4年課,而到第2版出版,時間又過去了12年。我們非常高興地看到這一工作得到廣泛認(rèn)可,并被結(jié)合到其他一些教材中。我們已經(jīng)看到我們的學(xué)生掌握了本書中的思想和程序,并將它們構(gòu)筑到新的計算機系統(tǒng)或者語言的核心里—我們的學(xué)生已經(jīng)變成了我們的創(chuàng)造者。我們非常幸運能有如此有能力的學(xué)生和如此有建樹的創(chuàng)造者。
在準(zhǔn)備這一新版本的過程中,我們采納了成百條澄清性建議,它們來自我們自己的教學(xué)經(jīng)驗,也來自MIT和其他地方的同行們的評述。我們重新設(shè)計了本書里大部分主要程序設(shè)計系統(tǒng),包括通用型算術(shù)系統(tǒng)、解釋器、寄存器機器模擬器和編譯器,也重寫了所有的程序?qū)嵗,以保證任何符合IEEE的Scheme標(biāo)準(zhǔn)(IEEE 1990)的Scheme實現(xiàn)都能運行這些代碼。
這一版本中強調(diào)了幾個新問題,其中最重要的是計算模型里對于時間的處理所起的中心作用:帶有狀態(tài)的對象、并發(fā)程序設(shè)計、函數(shù)式程序設(shè)計、惰性求值和非確定性程序設(shè)計。這里為并發(fā)和非確定性新增加了幾節(jié),我們也設(shè)法將這一論題集成到整本書里,貫穿始終。
本書第1版基本上是按照我們在MIT一學(xué)期課程的教學(xué)大綱撰寫的。第2版中由于有了增加的這些新材料,已經(jīng)不可能在一個學(xué)期里覆蓋所有內(nèi)容了,所以教師需要從中做一些選擇。在我們自己的教學(xué)里,有時會跳過有關(guān)邏輯程序設(shè)計的一節(jié)(4.4節(jié));讓學(xué)生使用寄存器機器模擬器,但不去討論它的實現(xiàn)(5.2節(jié));對于編譯器則只給出粗略的概述(5.5節(jié))。即便如此,這仍然是一門內(nèi)容非常多的課程。一些教師可能希望只覆蓋前面的三章或者四章,而將其他內(nèi)容留給后續(xù)課程。
第1版前言
一臺計算機就像是一把小提琴。你可以想象一個新手試了一個音符后丟掉了它。后來他說,聽起來真難聽。我們已經(jīng)從大眾和我們的大部分計算機科學(xué)家那里反復(fù)聽到這種說法。他們說,計算機程序?qū)別具體用途而言確實是好東西,但它們太缺乏彈性。一把小提琴或者一臺打字機也同樣缺乏彈性,那是在你學(xué)會了如何去使用它們之前。
—Marvin Minsky,“為什么說程序設(shè)計很容易成為一種媒介,
用于表述理解浮淺、草率而就的思想”
本書是麻省理工學(xué)院(MIT)計算機科學(xué)的入門教材。在MIT主修電子工程或者計算機科學(xué)的所有學(xué)生都必須學(xué)這門課,作為“公共核心課程計劃”的四分之一。該計劃還包含兩個關(guān)于電路和線性系統(tǒng)的科目,以及一個關(guān)于數(shù)字系統(tǒng)設(shè)計的科目。我們從1978年開始涉足這些科目的開發(fā),從1980年秋季以后,我們就一直按照現(xiàn)在這種形式教授這門課程,每年600到700個學(xué)生。大部分學(xué)生此前沒有或者很少有計算方面的正式訓(xùn)練,雖然許多人玩過計算機,也有少數(shù)人有豐富的程序設(shè)計或者硬件設(shè)計經(jīng)驗。
我們所設(shè)計的這門計算機科學(xué)入門課程主要考慮了兩個方面。首先,我們希望建立起一種認(rèn)識:計算機語言并不僅僅是一種讓計算機去執(zhí)行操作的方式,更重要的,它是一種表述有關(guān)方法學(xué)的思想的新穎的形式化媒介。因此,程序必須寫得能夠供人們閱讀,偶爾地去供計算機執(zhí)行。其次,我們相信,在這一層次的課程里,最基本的材料并不是特定程序設(shè)計語言的語法,不是高效完成某種功能的巧妙算法,也不是算法的數(shù)學(xué)分析或者計算的本質(zhì)基礎(chǔ),而是一些能夠控制大型軟件系統(tǒng)的復(fù)雜性的技術(shù)。
我們的目標(biāo)是,完成了這一科目的學(xué)生能對程序設(shè)計的風(fēng)格要素有一種很好的審美觀。他們應(yīng)該掌握了控制大型系統(tǒng)的復(fù)雜性的主要技術(shù)。他們應(yīng)該能夠去讀50頁長的程序,只要該程序是以一種值得模仿的形式寫出來的。他們應(yīng)該知道在什么時候哪些東西不需要去讀,哪些東西不需要去理解。他們應(yīng)該很有把握地去修改一個程序,同時又能保持原來作者的精神和風(fēng)格。
這些技能并不僅僅適用于計算機程序設(shè)計。我們所教授和提煉出來的這些技術(shù),對于所有的工程設(shè)計都是通用的。我們在適當(dāng)?shù)臅r候隱藏起一些細(xì)節(jié),通過創(chuàng)建抽象去控制復(fù)雜性。我們通過建立約定的界面,以一種“混合與匹配”的方式組合起一些標(biāo)準(zhǔn)的、已經(jīng)很好理解的片段去控制復(fù)雜性。我們通過建立一些新的語言去描述各種設(shè)計,每種語言強調(diào)設(shè)計中的一個特定方面并降低其他方面的重要性,以控制復(fù)雜性。
設(shè)計這門課程的基礎(chǔ)是我們的一種信念—“計算機科學(xué)”并不是一種科學(xué),而且其重要性也與計算機本身并無太大關(guān)系。計算機革命是關(guān)于我們?nèi)绾稳ニ伎迹约叭绾稳ケ磉_自己的思考的。在這個變化里,最基本的東西就是出現(xiàn)了一種或許最好稱為過程性認(rèn)識論的現(xiàn)象—如何從命令式的觀點去研究知識的結(jié)構(gòu),這一觀點與經(jīng)典數(shù)學(xué)領(lǐng)域中所采用的更具說明性的觀點是完全不同的。數(shù)學(xué)為精確處理“是什么”提供了一種框架,而計算則為精確處理“怎樣做”提供了一種框架。
在教授這里的材料時,我們采用的是Lisp語言的一種方言。我們絕沒有形式化地教授這一語言,因為完全不必那樣做。我們只是使用它,學(xué)生可以在幾天之內(nèi)就學(xué)會它。這也是類Lisp語言的重要優(yōu)
哈羅德•阿貝爾森(Harold Abelson)是MIT 1992年度MacVicar Faculty Fellow。在MIT電子工程和計算機科學(xué)系工作,得到過重要的計算機科學(xué)教育獎——IEEE計算機學(xué)會的Booth獎。
杰拉爾德•杰伊•薩斯曼(Gerald Jay Sussman)是Matsushita電子工程教授。在MIT電子工程和計算機科學(xué)系工作,得到過重要的計算機科學(xué)教育獎——ACM的Karlstrom獎。
朱莉•薩斯曼(Julie Sussman)是作家和編輯,同時使用自然語言和計算機語言寫作。
出版者的話
序
第2版前言
第1版前言
致謝
第1章 構(gòu)造過程抽象1
1.1 程序設(shè)計的基本元素3
1.1.1 表達式3
1.1.2 命名和環(huán)境5
1.1.3 組合式的求值6
1.1.4 復(fù)合過程7
1.1.5 過程應(yīng)用的代換模型9
1.1.6 條件表達式和謂詞11
1.1.7 實例:采用牛頓法求平方根14
1.1.8 過程作為黑箱抽象17
1.2 過程及其產(chǎn)生的計算20
1.2.1 線性的遞歸和迭代21
1.2.2 樹形遞歸24
1.2.3 增長的階28
1.2.4 求冪29
1.2.5 最大公約數(shù)32
1.2.6 實例:素數(shù)檢測33
1.3 用高階函數(shù)做抽象37
1.3.1 過程作為參數(shù)37
1.3.2 用lambda構(gòu)造過程41
1.3.3 過程作為一般性的方法44
1.3.4 過程作為返回值48
第2章 構(gòu)造數(shù)據(jù)抽象53
2.1 數(shù)據(jù)抽象導(dǎo)引55
2.1.1 實例:有理數(shù)的算術(shù)運算55
2.1.2 抽象屏障58
2.1.3 數(shù)據(jù)意味著什么60
2.1.4 擴展練習(xí):區(qū)間算術(shù)62
2.2 層次性數(shù)據(jù)和閉包性質(zhì)65
2.2.1 序列的表示66
2.2.2 層次性結(jié)構(gòu)72
2.2.3 序列作為一種約定的界面76
2.2.4 實例:一個圖形語言86
2.3 符號數(shù)據(jù)96
2.3.1 引號96
2.3.2 實例:符號求導(dǎo)99
2.3.3 實例:集合的表示103
2.3.4 實例:Huffman編碼樹109
2.4 抽象數(shù)據(jù)的多重表示115
2.4.1 復(fù)數(shù)的表示116
2.4.2 帶標(biāo)志數(shù)據(jù)119
2.4.3 數(shù)據(jù)導(dǎo)向的程序設(shè)計和可加性122
2.5 帶有通用型操作的系統(tǒng)128
2.5.1 通用型算術(shù)運算129
2.5.2 不同類型數(shù)據(jù)的組合132
2.5.3 實例:符號代數(shù)138
第3章 模塊化、對象和狀態(tài)149
3.1 賦值和局部狀態(tài)149
3.1.1 局部狀態(tài)變量150
3.1.2 引進賦值帶來的利益154
3.1.3 引進賦值的代價157
3.2 求值的環(huán)境模型162
3.2.1 求值規(guī)則163
3.2.2 簡單過程的應(yīng)用165
3.2.3 將框架看作局部狀態(tài)的展臺167
3.2.4 內(nèi)部定義171
3.3 用變動數(shù)據(jù)做模擬173
3.3.1 變動的表結(jié)構(gòu)173
3.3.2 隊列的表示180
3.3.3 表格的表示183
3.3.4 數(shù)字電路的模擬器188
3.3.5 約束的傳播198
3.4 并發(fā):時間是一個本質(zhì)問題206
3.4.1 并發(fā)系統(tǒng)中時間的性質(zhì)207
3.4.2 控制并發(fā)的機制210
3.5 流220
3.5.1 流作為延時的表220
3.5.2 無窮流226
3.5.3 流計算模式的使用232
3.5.4 流和延時求值241
3.5.5 函數(shù)式程序的模塊化和對象的
模塊化245
第4章 元語言抽象249
4.1 元循環(huán)求值器251
4.1.1 求值器的內(nèi)核252
4.1.2 表達式的表示255
4.1.3 求值器數(shù)據(jù)結(jié)構(gòu)260
4.1.4 作為程序運行求值器264
4.1.5 將數(shù)據(jù)作為程序266
4.1.6 內(nèi)部定義269
4.1.7 將語法分析與執(zhí)行分離273
4.2 Scheme的變形—惰性求值276
4.2.1 正則序和應(yīng)用序277
4.2.2 一個采用惰性求值的解釋器278
4.2.3 將流作為惰性的表284
4.3 Scheme的變形—非確定性計算286
4.3.1 amb和搜索287
4.3.2 非確定性程序的實例290
4.3.3 實現(xiàn)amb求值器296
4.4 邏輯程序設(shè)計304
4.4.1 演繹信息檢索306
4.4.2 查詢系統(tǒng)如何工作315
4.4.3 邏輯程序設(shè)計是數(shù)理邏輯嗎321
4.4.4 查詢系統(tǒng)的實現(xiàn)324
第5章 寄存器機器里的計算343
5.1 寄存器機器的設(shè)計344
5.1.1 一種描述寄存器機器的語言346
5.1.2 機器設(shè)計的抽象348
5.1.3 子程序351
5.1.4 采用堆棧實現(xiàn)遞歸354
5.1.5 指令總結(jié)358
5.2 一個寄存器機器模擬器359
5.2.1 機器模型360
5.2.2 匯編程序364
5.2.3 為指令生成執(zhí)行過程366
5.2.4 監(jiān)視機器執(zhí)行372
5.3 存儲分配和廢料收集374
5.3.1 將存儲看作向量374
5.3.2 維持一種無窮存儲的假象378
5.4 顯式控制的求值器383
5.4.1 顯式控制求值器的內(nèi)核384
5.4.2 序列的求值和尾遞歸388
5.4.3 條件、賦值和定義391
5.4.4 求值器的運行393
5.5 編譯397
5.5.1 編譯器的結(jié)構(gòu)399
5.5.2 表達式的編譯402
5.5.3 組合式的編譯407
5.5.4 指令序列的組合412
5.5.5 編譯代碼的實例415
5.5.6 詞法地址422
5.5.7 編譯代碼與求值器的互連425
參考文獻431
練習(xí)表437
索引439