01 / 導讀
導讀
引用
Felleisen, M., Findler, R. B., Flatt, M., & Krishnamurthi, S. (2018). How to Design Programs: An Introduction to Programming and Computing (2nd ed.). The MIT Press. Free official edition: https://htdp.org/
章節概要
序幕：如何程式設計
序幕讓讀者立即在 DrRacket 中動手程式設計：對數字、字串和影像進行運算，然後通過同一程式的幾個版本，逐步做出一個火箭著陸的小動畫。最後一節（"Not!"）解釋為什麼這種快速、無計劃的程式設計方式無法擴充，從而引出本書的替代方案——系統化的程式設計。
第1–2章：算術；函式與程式
第一部分"固定大小的資料"從關於數字、字串、影像和布林值的表示式講起，並介紹用於判斷值屬於哪類資料的謂詞。第2章介紹函式定義、用代換進行計算、函式的組合、全域常數，以及本書使用的兩類完整程式：批處理程序和用 big-bang 構建的互動式"世界"程式。
第3章：如何設計程式
這是全書的核心章節。它提出函式設計訣竅的六個步驟：資料定義，簽名、目的說明與函式頭，函式範例，模板，定義，以及測試。隨後把這一訣竅推廣到完整程式，強調領域知識和用 check-expect 進行測試的作用，並以虛擬寵物為貫穿範例說明如何設計世界程式。
第4–7章：區間、列舉與分項；加入結構；分項與結構；小結
這幾章把設計訣竅擴充到更豐富的資料。第4章講條件表示式及其所對應的資料定義（列舉、區間、分項），最後介紹交通訊號燈之類的有限狀態世界。第5章從 posn 開始引入結構體，接著講結構型別定義、"資料的全集"、用結構體進行設計，以及一個圖形化文本編輯器。第6章把分項與結構體結合起來，檢查輸入錯誤，並討論相等性謂詞。第7章總結這一部分：好的程式設計師設計程式而不是反覆修補，設計訣竅既有過程維度，也有資料維度。
插曲1：初級學生語言
第一個插曲精確描述教學語言 BSL：它的詞彙、語法和含義，作為一系列代數步驟的求值過程，錯誤資訊，布林表示式，常數與結構體定義，以及測試。
第8–10章：列表；用自引用資料定義進行設計；再談列表
第二部分"任意大的資料"引入由 '() 和 cons 構造的列表，說明自引用的資料定義如何匯出遞迴函式，而函式模板則跟隨資料的結構。第9章加入非空列表、作為遞迴資料的自然數、巢狀的"俄羅斯套娃"結構，以及世界程式中的列表。第10章討論產生列表的函式、列表中的結構體、列表的列表（從檔案讀入）以及重新設計的圖形化編輯器。
第11–13章：通過組合進行設計；專案：列表；小結
第11章講授如何把問題分解為輔助函式並加以組合，包括遞迴的輔助函式和起推廣作用的輔助函式。第12章提供較大的專案：詞典、iTunes 曲庫、文字遊戲、貪吃蟲遊戲、簡化版俄羅斯方塊、太空大戰遊戲和有限狀態機。小結強調針對自引用改進設計訣竅，並連同所需的資料定義一起寫出"願望清單"。
插曲2：引用與反引用
這個簡短的插曲介紹引用（quote）、準引用（quasiquote）、反引用（unquote）和拼接，作為書寫大塊資料的簡潔記法，並介紹符號這種資料。
第14–15章：處處相似；設計抽象
第三部分"抽象"從注意到第二部分中許多函式彼此相似開始。第14章對相似的函式和資料定義進行抽象，並說明函式也是值。第15章給出設計抽象的訣竅：從範例中抽象、推廣簽名、建立單一控制點，以及從模板中抽象。
第16–18章：使用抽象；匿名函式；小結
第16章講授如何使用 map、filter、foldr 等現有抽象，引入 local 區域定義及其帶來的額外表達能力，並通過範例和專案加以練習。第17章引入用於匿名函式的 lambda，用它來進行抽象、編寫規格，甚至表示資料。小結把抽象概括為建立和使用可複用程式碼兩個方面。
插曲3：作用域與抽象
這個插曲定義詞法作用域以及變數的綁定出現和被綁定出現，然後介紹另外兩種抽象機制：中級學生語言中的 for 迴圈和模式匹配。
第19–20章：S-表示式之詩；迭代求精
第四部分"交織的資料"處理由多個相互引用的定義所描述的資料：樹、森林和 S-表示式，並包括一個二叉搜尋樹專案和一節關於簡化函式的內容。第20章明確引入迭代求精，以一個經過多個版本逐步求精的計算機檔案系統模型為例。
第21–22章：求精直譯器；專案：XML 的商務應用
第21章用迭代求精的方法，為一門由表示式、變數和函式構成的小語言設計直譯器，這正是 DrRacket 互動區的核心。第22章把 XML 表示為 S-表示式，渲染 XML 列舉，討論領域專用語言，並讀取 XML 資料。
第23–24章：同時處理；小結
第23章說明如何設計接受兩個複雜輸入的函式，區分三種情況（把其中一個輸入當作原子資料、以同步方式處理兩個輸入、用二維表處理所有組合），最後是一個數據庫專案。小結指出設計訣竅可以推廣到所有形式的結構化資料。
插曲4：數的本質
這個插曲解釋定長的數字表示、上溢和下溢，以及教學語言如何區分精確數和非精確數。
第25–26章：非標準遞迴；設計算法
第五部分"生成式遞迴"引入不遵循資料結構的遞迴，例如把問題拆分為新生成的子問題。第26章為這類演算法調整設計訣竅：編碼步驟增加四個新問題，需要明確的終止性論證，並比較結構遞迴與生成式遞迴。
第27–30章：主題的變奏；數學範例；回溯演算法；小結
生成式遞迴的例子包括分形、二分查詢和語法分析初探（第27章）；牛頓法、數值積分和高斯消元專案（第28章）；以及圖的遍歷和關於 n 皇后問題的回溯專案（第29章）。小結指出，大多數電腦科學家把這類函式稱為演算法，而且它們未必對所有輸入都會終止。
插曲5：計算的代價
最後一個插曲解釋為什麼對特定輸入計時說明不了多少問題，引入抽象執行時間和"同階"的定義，並用它討論程式為什麼依賴謂詞和選擇器。
第31–34章：知識的丟失；設計累加器風格的函式；累加的更多用途；小結
第六部分"累加器"說明結構遞迴函式和生成式遞迴函式在遞迴過程中會"忘記"知識，從而導致低效或不終止。它給出一套訣竅：識別何時需要累加器、寫出累加器陳述、把函式轉換為累加器風格，並應用於樹、資料表示以及一個用滑鼠操作的圖形化編輯器。
尾聲：繼續前行
尾聲回顧計算與程式設計，並提出下一步建議：對於未來的開發者和電腦科學家，是學習 Racket 這樣的完整語言以及類、物件和型別；對於其他所有人，則是在各自領域中運用這一設計過程。
核心概念
序幕與第1–3章
- 設計訣竅：六個步驟（資料定義；簽名、目的與函式頭；範例；模板；定義；測試），引導人從問題陳述走到經過測試的函式。
- 資料定義：說明現實世界的資訊如何在程式中表示為資料，並附有範例。
- 世界程式：用
big-bang、一個狀態、一個渲染函式和若干事件處理函式構建的互動式程式。
第4–7章與插曲1
- 分項：列出若干互不相同情形的資料定義，在模板中對應為每種情形一個子句的
cond。 - 結構型別：程式設計師定義的複合資料型別，具有建構函式、選擇器和謂詞。
- 代數式計算模型：用逐步代換來求值 BSL 程式，正如 DrRacket 的單步執行器所展示的那樣。
第8–13章
- 自引用資料定義：引用自身的定義（如列表），由此匯出遞迴函式。
- 模板跟隨資料：函式程式碼的形狀反映它所處理的資料定義的形狀。
- 願望清單：列出有待日後設計的輔助函式及其簽名和目的。
第14–18章與插曲3
- 抽象：把重複出現的程式碼模式提取為一個函式，並對差異部分進行引數化。
- 函式即值：傳遞和返回函式，這是
map、filter、foldr和lambda的基礎。 - 詞法作用域：每個變量出現都對應一個通過閱讀程式文本即可找到的定義。
第19–24章
- 相互引用的資料：彼此引用的多個數據定義，需要為每個定義各寫一個模板。
- 迭代求精：先解決問題的簡化版本，再一步步加入細節。
第25–30章與插曲5
- 生成式遞迴：基於對問題的洞察、在新生成的子問題上進行的遞迴，而不是沿著資料的結構遞迴。
- 終止性論證：說明生成式遞迴函式為何最終會停止，或對其不會停止的輸入給出警告。
- 抽象執行時間：用步數的增長階來衡量代價，而不是對特定執行計時。
第31–34章
- 累加器：在遍歷過程中攜帶所收集知識的額外引數。
- 累加器陳述：說明累加器代表什麼知識，通常是原始引數與當前引數之間的差別。
評析
優點
- 可傳授的明確方法。 前言把六步設計訣竅描述為學生可以抄在索引卡上的東西，而每個部分又為每一步補充有針對性的問題。資料定義、範例、模板等中間產物，使卡住的學生或教師能夠準確看出問題出在哪裡。
- 以資料驅動的遞進。 每個部分引入一種新的資料（固定大小、任意大、交織）或一條新的設計原則（抽象、生成式遞迴、累加器），並相應擴充設計訣竅，因此本書的結構本身就在傳授"程式結構跟隨資料"的道理。
- 為初學者設計的教學語言和環境。 一系列教學語言（BSL、BSL+、ISL、ISL+）給出與學習者水平相稱的錯誤資訊，DrRacket 的單步執行器逐步展示求值過程。帶影像的互動式世界程式能提供即時的視覺反饋。
- 大量練習和反覆出現的主題。 線上版共有 528 道編號練習，虛擬寵物、文本編輯器和圖等主題在多個部分中反覆出現；前言稱這是"從後門"引入迭代求精。
局限
- 不是主流語言。 本書用基於 Racket 的教學語言講授設計，而不是 Python、Java 或 C；前言說明這是有意為之，但需要某種工業語言的學生必須在之後自行過渡，尾聲把這一步留給其他書籍。
- 篇幅與節奏。 全書有六個部分、五個插曲和五百多道練習，篇幅很長，前言本身也為學季制課程和高中課程提出了刪減方案。想快速入門的讀者可能會覺得前幾章進展緩慢。
- 狀態、物件和型別涉及有限。 變數賦值、類與物件以及靜態型別大多被推遲，尾聲把它們列為後續主題。累加器風格的程式設計以函式式方式展示，命令式迴圈被明確說明超出本書範圍。
- 規定性強。 即使是很小的函式也堅持走完每一步，這對有程式設計經驗的學生來說可能顯得繁重，儘管作者認為這種紀律正是重點所在。
在課程中的定位
在本入門程式設計書單中，How to Design Programs 是一本入門教材，側重方法而非某種特定語言。它與 Matthes 的 Python Crash Course 形成對比——後者通常被認為是以專案為導向的 Python 入門書；也與 Downey 的 Think Python 和 Guttag 的 Introduction to Computation and Programming Using Python 不同，後兩者用 Python 講授程式設計與計算。希望在程式設計、測試和遞迴方面打下紮實基礎的學生，可以先讀 HtDP，再按尾聲的建議轉向某本 Python 教材，把設計訣竅遷移到主流語言中。
Abelson 和 Sussman 的 Structure and Interpretation of Computer Programs 同樣源自 Lisp 家族傳統，通常被認為對數學的要求更高；HtDP 的前言則把自己定位為只需前代數知識即可閱讀，因此是合適的先修讀物。Kernighan 和 Ritchie 的 The C Programming Language 面向底層程式設計，最好在第一門課程之後閱讀。
如何使用本書
本書為沒有任何程式設計經驗的讀者而寫；作者認為具備前代數知識就足夠了，唯一需要的軟體是免費的 DrRacket 環境。前言同時面向自學者和教師。
前言要求自學者從頭到尾學完全書，並解出或至少知道如何解出所有練習。前言還給出三條較短的路徑：高中課程學習第一、二部分並完成一個小型遊戲專案；大學學季制課程學習第一、二、三、五部分以及插曲1和插曲3；大學學期制課程先學第一、二部分，再學第六部分中不依賴生成式遞迴的內容，然後是插曲5和其餘部分。無論哪條路徑，第3章（設計訣竅）都是必讀的，第8–9章和第14–16章是遞迴與抽象的基礎。
用單步執行器理解求值過程，在寫定義之前先寫 check-expect 測試，並依照每個資料定義的模板動手，而不是從空白頁開始。卡住時，回到設計訣竅中出問題的那一步——正如前言建議教師藉助索引卡所做的那樣。
版本與來源
本導讀依據 https://htdp.org/ 上的免費線上第二版（正文 © 2014 MIT Press，線上版釋出日期為 2026 年 5 月 28 日；印刷版由 MIT Press 於 2018 年出版）。內容取材於前言全文（包括設計訣竅、教學語言、各部分安排、建議的課程路徑以及與第一版的差異）、完整目錄、序幕、六個部分各自的開篇小節與小結章節、全部五個插曲的開頭部分、尾聲，以及第一、四、五部分中的若干小節。