深入理解運算原理｜從簡單的機器到無所不能的程式

第6章

無為的程式設計

如果你想從零開始製作蘋果派，必須先創造出宇宙。

—

卡爾 薩根（

Carl Sagan

）

我們一直在這本書試著構建運算的模型來瞭解運算。截至目前，我們已經設計了具有各

種限制的簡單虛擬機器來建構運算模型，並且看到不同的限制產生了具有不同運算能力

數量的系統。

第 5 章的圖靈機很有趣，因為就算不依賴複雜的功能，它們也能實作複雜的行為。圖靈

機僅配備磁帶、讀寫磁帶頭、固定的一組規則，就具有足夠的彈性來模擬具有更佳儲存

能力或非決定論執行或我們想要的其他任何幻想功能的機器行為。這告訴我們，完整運

算不需要底層非常復雜的機器，只需要資料儲存、取回的能力，並使用它們做出簡單的

決策。

運算模型的外觀不一定要像機器，它們可以看起來像程式語言。第 2 章的 SIMPLE 程

式語言當然可以執行運算，但它並不如圖靈機簡潔。它已經有很多語法（數值、布林、

二進位運算式、變數、指定、序列、條件式、迴圈），而我們甚至還沒有開始加入適合

編寫實際程式的功能：字串、資料結構、程序呼叫等。

要將 SIMPLE 轉變成真正實用的程式語言會是困難的工作，因此所產生的設計將會包

含很多附帶的細節，而且也不會過於顯露運算的本質。從零開始並且創造一些小小程式

語言世界的圖靈機將會更加有趣，這樣我們可以看到哪些是運算不可或缺的功能，而哪

些只是附帶的小點綴。

我們將在本章鑽研一種稱為

無型別

lambda

演算

（

untyped lambda calculus

）的超迷你程

式語言。首先，我們將嘗試以 Ruby 方言並且盡量少用語言的功能來編寫接近 ...