Donald Knuth#

在本書所有受訪者中，Donald Knuth 或許是最不需要介紹的。過去四十多年來，他一直在撰寫多卷本巨著 The Art of Computer Programming——基礎演算法和資料結構的聖經，被 American Scientist 列為二十世紀最重要的 12 本物理科學專著之一，與 Russell、Einstein、Dirac、Feynman、von Neumann 的著作並列。他普及了 Big-O 符號在演算法分析中的使用，發明了 LR parsing，並為 goto 語句辯護以回應 Dijkstra 的批評。

但他不僅是理論家。1976 年完成 The Art of Computer Programming 第三卷後，Knuth 花了本應一年的休假來撰寫排版軟體 TeX 和 METAFONT，結果花了十年。在此過程中，他發明了一種新的程式設計風格——literate programming（文學程式設計），以及一種至今仍是最先進水準的段落斷行演算法。

他的眾多獎項包括首屆 ACM Grace Murray Hopper Award（1971）、Turing Award（1974）和 National Medal of Science（1979）。1990 年他停止使用電子郵件，解釋說他的工作不是「站在事物頂端」而是「深入事物底部」。

學習程式設計#

初識電腦#

1956 年秋天進入 Case Institute of Technology 就讀大一
該學期學校剛好買了一台 IBM 650——第一台大量生產的電腦
在統計實驗室打工為統計學家製表資料，透過窗戶看到閃爍燈光的機器，覺得很迷人
一天下午有人在黑板上為新生解說這台機器的功能

第一個程式#

找到機器手冊，裡面有十行的範例程式——覺得它們「有點蠢」，看起來可以改進
Case 是少數允許大學生親手碰機器的學校（其他學校需要專人操作）
晚上可以去操作機器，嘗試自己的修改，發現修改真的有效
IBM 650 是十進位機器，這讓它感覺更「人性化」

真正的程式設計啟蒙#

寫了一個約 100 行的程式來計算質因數，花了兩週除錯，找到 100 多個 bug
第二個程式是二進位和十進位轉換
第三個程式——井字棋（tic-tac-toe）——才真正讓他成為程式設計師
寫了三個版本，其中一個是自我學習的：從零開始學習，每輸一局就記住自己可疑的走法和對手的好走法，400 局後就能玩得不錯

Knuth 學習程式設計的方式：自己摸索一個程式，坐在機器前花數週時間，讓它一點一點變得更好。他不認同 Dijkstra 說的「學生在最初幾年不應該碰機器」的觀點——學習需要在所有層次上看到事物。

The Art of Computer Programming#

寫作動機與方法#

試圖組織圍繞所討論主題的大量智慧，從各個來源收集，統一成一個整體
目前在寫的部分，起始材料是以數學行話寫成的論文——他試圖去除行話，給出關鍵思想
每五頁就是某個人一生的職業成果
他把答案都寫出來，因為知道十年後自己也不會記得怎麼做

書的受眾與平衡#

時常在「太複雜了不該討論」和「太簡單了沒有好東西」之間掙扎
關於 Binary Decision Diagrams (BDDs) 的章節竟有超過 260 道練習
大多數人會挑選自己需要的部分閱讀，而非從頭讀到尾
嘗試以對實際程式設計師最相關的方式來探索領域，而非追求學術聲望

實用主義取向#

不使用平衡樹或 AVL 樹，除非知道會是非常大的樹
偏好使用普通的二元搜尋樹加上一個隨機化技巧
刻意省略那些只在 n 超過百萬時才有理論優勢的資料結構

TeX 與程式設計實踐#

TeX 的開發過程#

1977-78 年首次撰寫 TeX，當時還沒有 literate programming
在大筆記本上用鉛筆手寫程式碼，六個月後才開始輸入電腦
結構化程式設計給了他不變量（invariants）的觀念，讓他有信心在六個月不測試的情況下寫程式碼
這是第一代系統，很多架構需要在實際使用後才能確定

寫 TeX 對寫書的影響#

使用結構化程式設計解決真實（非玩具）問題的經驗，影響了他描述演算法的方式
讓他理解了快取策略、計算趨勢等實務知識
發現軟體佔據大腦的程度遠超預期——無法同時全職教書和全職寫軟體
這讓他對做大型軟體專案的人產生特別的敬佩

程式設計時間估算#

程式設計比寫書更難，也更難估算時間
即使是 Knuth 自己，也常常低估程式的豐富度和所需時間
管理程式設計師的人不應期望時間估算是可預測的

Literate Programming（文學程式設計）#

核心理念#

技術寫作的第一原則：了解你的讀者
第二原則：用互補的方式說兩次——正式地和非正式地，讓讀者從兩個方向強化理解
技術寫作中通常有冗餘：先給形式定義，再給非正式的直覺解釋
Literate programming 提供了一個自然框架，在自然語言（英文）和形式語言（C、Lisp 等）之間切換

寫程式的順序#

不需要按照編譯器要求的順序呈現程式——而是按讀者最容易理解的順序
自己的程式設計方式既不完全是 top-down 也不完全是 bottom-up
心理上選擇「接下來做什麼我最有成就感」——解決最令人擔憂但又準備好面對的問題
最終程式的順序幾乎總是按照他思考的順序自然排列

Jon Bentley 的觀察（Knuth 轉述）：世界上只有 2% 的人天生是超級程式設計師，也只有 2% 的人天生是超級作家。而 Knuth 期望所有人同時是兩者。但隨著部落格的普及，一般人的寫作能力已大幅提升，所以這個論點不再那麼有力。

實際效果#

他相信有些程式不用 literate programming 就不可能完成——例如 MMIX 模擬器（170 頁），光分拆成子程式不足以讓它在智力上可管理
在 Stanford 與七位大學生嘗試，六位喜愛並沿用至今，一位討厭
寫給自己看也很有價值——一年後回頭看能確切知道當時在想什麼
TeX 是歷史上被最多人在某個時間點理解的程式之一，歸功於 literate programming 的文件能力

對黑箱和可重用軟體的批評#

有一種「對可重用軟體的過度強調」——人們製作封閉的黑箱，只允許設定參數
如果寫程式只是從函式庫中呼叫函式、找到正確的參數組合，誰還會想以此為業？
打開黑箱、理解內部、根據需求調整——幾乎總能做得更好
類比數學：數學書充滿定理，但你幾乎不會直接套用某個定理——而是看證明，然後修改假設來適應你的問題。軟體也是如此。

Knuth 並非說黑箱無用——如果必須打開每個黑箱才能使用函式庫，結果會更慢更差。但他希望程式設計師有能力也有自由去打開黑箱，理解並改進內部的東西。

除錯方法#

使用 GDB#

GNU debugger 的開發者意識到可以讓前處理器寫出的程式與高階原始碼對應
因此 GDB 可以直接在 CWEB 原始碼層級進行除錯——不需要看低階 C 程式碼
這利用了 C 語言中的 __LINE__ 指令

Sanity Check（健全性檢查）#

會寫大量檢查資料結構的程式碼——冗餘性、參考計數等
健全性檢查可能讓程式慢 100 倍，但能在崩潰前數十億步就發現錯誤
約 10% 的程式碼專門用於除錯時才需要的健全性檢查
健全性檢查程式碼同時也記錄了資料結構

窮舉測試#

例如寫了一個新的乘法程式，就用 256 個數字相互乘以窮舉測試
乘到 2 x 3 就失敗了——修好後再測，直到 256 x 256 全部正確

攻擊者心態#

為 TeX 寫了極端的「酷刑測試」（torture test）
訣竅是忘記自己是作者，想像是別人寫的程式然後攻擊它
一生都是挑剔者（nitpicker），喜歡從找錯誤中獲得快感
比起證明某個東西正確，更容易進入「找反例」的心態

對形式驗證的看法#

永遠不可能真正「證明」程式正確——驗證器可能有 bug，規格可能有 bug
Tony Hoare 的第一篇形式證明論文（“Proof of a Program: FIND”）中就有兩三個 bug
TeX 是為人類使用而設計的，要定義「正確」都很困難
自己寫的程式中，根本不知道如何陳述所有的 assertion

對錯誤日誌的看法#

保留了 TeX 的完整錯誤日誌（“The Errors of TeX”）
但記錄錯誤並沒有防止他犯同樣的錯——因為他總是在嘗試更難的東西
如果回去寫以前那種簡單的程式，就不會犯那些錯了
總是在自己能力的極限運作——所以永遠會有 bug

Knuth 對銀彈的看法：「每三年就會出現一個新的流行語，號稱能解決所有問題。Extreme programming 是最近兩三年的。再之前是別的東西。會有很多人跳上那班車，然後發現：『噢，還是很難。』」

對程式語言的看法#

C 語言中的指標#

認為 C 語言中指標的使用是程式設計中最重要的革命之一
當 x 是指標且 x + 1 根據 x 指向的東西不同而跳不同距離——這是表示法上的驚人改進
起初以為是大錯誤，後來發現很喜歡

指標在 64 位元時代的困境#

在 64 位元機器上，每個指標佔 64 位元，但實際只用 32 位有意義
指標讓資料結構大小翻倍，而且快取效率降低
不得不改用陣列加上複雜的巨集來模擬指標

完美程式語言的幻想#

1974 年曾預言 1984 年會有「Utopia 84」——完美的程式語言取代 COBOL 和 Fortran
這沒有發生——每種新語言都清理了前代已理解的東西，然後加入實驗性的新東西
沒有人願意在「已理解的部分」停下來，保持乾淨和穩定
Pascal 曾有這個哲學但沒有成功持續
Java 不夠好——不夠可擴展

學術界與工業界#

1960 年代學術界遠超工業界
1980 年代情況逆轉——工業界在嘲笑大學裡禁止 goto 的教條
後來大學又在網路和大資料方面超前
來回擺盪，但目前演算法和資料結構社群有太多「巴洛克式」的東西——精巧但與實踐脫節

程式設計師的本質#

2% 理論#

每 100 人中大約 2 人是天生與機器「共振」的程式設計師
這個比例在他長期觀察中幾乎是常數
即使是 Wasilla, Alaska 這樣的小鎮（10,000 人）也有約 200 個程式設計師
不同的「語法糖」和「語言方言」適合不同的個性類型——但沒有唯一最好的思考方式

對程式設計變得無聊的擔憂#

擔心很多程式設計正變成把別人的軟體拼在一起的「魔法咒語」
缺乏創意，變得太無聊
過去的樂趣來自創造新東西；現在的樂趣可能只是做完無聊的工作後得到漂亮的圖像
但他自己做的那種程式設計仍然令人興奮

Knuth 對程式設計的熱情：「天啊，我有一種必須去程式設計的需求。我早上醒來腦中就有 literate program 的句子。早餐前——我相信詩人也有這種感覺——我必須去電腦前寫下這一段，然後才能吃飯，然後我就開心了。這是一種衝動，我必須承認。」

對可重用軟體的批評#

黑箱的問題#

矩陣乘法的例子：如果有一個矩陣乘法黑箱，將實數改為複數就需要 4 次乘法；但打開黑箱，利用一個數學恆等式只需要 3 次
優先佇列、二元搜尋等——他寧可自己寫，每次根據需求調整
寫 The Art of Computer Programming 第一卷時，人們甚至不知道可以在自己的程式中使用鏈結串列和指標
他的書「打開了人們的眼界」——原來可以理解並調整資料結構，而不只是呼叫別人的套件

自己寫 vs. 用函式庫#

他寫很多程式，自認可以代表典型情況：學幾個基本概念，用文字編輯修改之前的程式碼來重用，比花時間學別人的介面更快
但承認這不適用於所有人——如果是 50 人的團隊，情況可能不同
希望「個人程式設計師為了學習而寫程式」的想法不會消亡

重要觀點總結#

關於學習#

「科學家們常犯的一個根本錯誤是：他們不理解當你在學某樣東西時，需要在所有層次上看到它。你必須先看到地板，才能建到天花板。所有這些都會進入大腦，被壓到更深處——到了某個程度，年長者會忘記他們曾經需要它。」

關於軟體的複雜性#

「軟體佔據大腦的程度遠超我的預期。它是比寫書困難得多的任務。我無法同時全職教書和全職寫軟體。」

關於永恆的 Bug#

「我認為是因為我總在嘗試更難的東西。我總是在自己能力的極限操作。如果回去寫以前那種簡單的程式，我不會犯那些錯。但那樣就沒那麼有趣了。」

關於程式設計的變遷#

結構化程式設計提供了模式，使人們能可靠地將程式組合成更大的系統
Literate programming 是他最大的轉變——從「組合正確的指令」變為「作為解說者向讀者呈現」
不同語言中的語法糖和方言適合不同個性——沒有唯一的最佳方式
抽象的概念很重要，讓我們能處理複雜系統同時保持控制感

關於 Change Files#

Literate programming 的一個意外副產品
讓使用者可以在不修改主程式的情況下自訂程式——只需要一個描述差異的 change file
TeX 曾有數百人用 change file 將其移植到不同平台
極端案例：將 TeX 從 8-bit 改為 Unicode 的 Omega 專案，change file 比主程式長 10 倍
Knuth 自己現在大量使用 change file 來做同一程式的不同實驗版本
例如研究 BDD 時，他有一個基本程式，然後用十幾個 change file 做各種變體實驗

對 Burroughs 硬體除錯的故事#

早期為 Burroughs Corporation 除錯硬體設計
工程師們給他機器規格，他嘗試構造邊界情況
在 B-5000 系列機器量產前找到了超過 200 個 bug——即使機器已經通過了模擬器測試
例如：浮點數乘法計算錯誤、堆疊在某些暫存器為空時邏輯出錯
方法是嘗試證明規格是正確的——如果無法證明，就找反例

對程式設計教育的看法#

學習的所有層次#

批評科學家們忘記自己曾經也需要從底層學起的錯誤
當年長的科學家說「我的學生不需要浪費時間在低層次的東西上」時，他們忘了那些底層知識是如何被壓入潛意識、形成直覺的
你必須先看到地板才能建到天花板

Binary Search 的教訓#

1970 年代開始的程式設計課，第一天就讓學生寫 binary search
收集後讓助教檢查——正確率不到 10%，而且有四到六種不同的 bug
Java 標準函式庫中的 binary search 也有一個存在多年的溢位 bug（(min + max) / 2）
這是黑箱問題的一個例子——如果每個人自己寫 binary search，錯誤率可能更高；但至少標準函式庫的 bug 被找到並修復了

對程式設計是否需要數學的看法#

The Art of Computer Programming 包含大量數學
但 Knuth 有時自己也懷疑讀者是否能讀懂
試圖去除行話、簡化、給出關鍵思想
電腦科學不能被歸結為 50 個簡單的東西——它真的很廣很深