《計算的本質：深入剖析程式和計算機》藉助簡單的Ruby代碼示例，全面、深入地介紹計算理論和程式語言設計。作者注重實用性，在讀者熟知的背景知識下，以明晰的可工作代碼闡釋了形式語義、自動機理論，以及通過lambda演算進行函式式編程等計算問題，並為讀者自行探索打下了良好基礎。 面向熟悉某種現代程式語言卻非科班出身的程式設計師，是一本幫你真正理解計算機科學和計算原理的優秀參考書。
基本介紹
- 書名：計算的本質:深入剖析程式和計算機
- 作者：斯圖爾特 (Tom Stuart)
- 原版名稱： Understanding Computation: Impossible Code and the Meaning of Programs
- 譯者：張偉
- ISBN：7115361541
- 頁數：286頁
- 定價：52.25
- 出版社：斯圖爾特 (Tom Stuart)
- 出版時間：2014年10月1日
- 開本：16
作者簡介,推薦理由,目錄,
作者簡介
Tom Stuart 倫敦數字產品諮詢公司Codon的創始人、計算機科學家、程式設計師，擅長Ruby、Rails、Web套用、用戶體驗、面向對象設計和行為驅動開發。另外，作為顧問、導師和培訓師，他（經常通過網路）幫助各家公司高質高效地創建軟體產品。他還曾在劍橋大學做編譯器最佳化方面的演講，與人聯合組織過Ruby大會（Ruby Manor），而且是倫敦Ruby用戶組的成員。
推薦理由
掌握計算與程式語言的工作原理和真正含義，在熟悉的語言示例中習得更好的工作方式，清晰解讀有限自動機和圖靈機。
我知道你是一位編程高手，寫代碼對你而言是手到擒來的事。但是，你確定自己多年練就的編程技能不是建立在某種想當然的假設基礎上？確定自己不是每天都在“稀里糊塗”地寫代碼？確定真正理解自己的代碼是如何運行的嗎？
如果你想像“大牛”級的程式設計師一樣做開發，或者想擺脫自己半路出家的知識“囧”境，本書能夠為你真正講明白計算理論和程式語言的工作原理與真切含義。本書使用簡單的Ruby代碼做示例，沒有枯燥難記的數學符號。作者極力推崇循序漸進和從實踐中學習，他從機器、語言講到程式，又一路從最簡單的機器（有限自動機）過渡到複雜的機器（圖靈機），從設計實現簡單的程式語言到極簡的機器，而後又推理所謂“不可能”解決的問題，為讀者完美打造了輕鬆有趣的閱讀體驗。
目錄
第1章 剛好夠用的Ruby基礎 1
1.1 互動式Ruby Shell 1
1.2 值 2
1.2.1 基本數據 2
1.2.2 數據結構 3
1.2.3 proc 4
1.3 控制流 4
1.4 對象和方法 5
1.5 類和模組 6
1.6 其他特性 7
1.6.1 局部變數和賦值 7
1.6.2 字元串插值 8
1.6.3 檢查對象 8
1.6.4 列印字元串 8
1.6.5 可變參數方法（variadic method） 9
1.6.6 代碼塊 9
1.6.7 枚舉類型 10
1.6.8 結構體 11
1.6.9 給內置對象擴展方法（Monkey Patching） 12
1.6.10 定義常量 13
1.6.11 刪除常量 13
第一部分 程式和機器
第2章 程式的含義 17
2.1 “含義”的含義 18
2.2 語法 19
2.3 操作語義 19
2.3.1 小步語義 20
2.3.2 大步語義 40
2.4 指稱語義 46
2.4.1 表達式 46
2.4.2 語句 49
2.4.3 套用 51
2.5 形式化語義實踐 52
2.5.1 形式化 52
2.5.2 找到含義 53
2.5.3 備選方案 53
2.6 實現語法解析器 54
第3章 最簡單的計算機 59
3.1 確定性有限自動機 59
3.1.1 狀態、規則和輸入 60
3.1.2 輸出 60
3.1.3 確定性 61
3.1.4 模擬 62
3.2 非確定性有限自動機 65
3.2.1 非確定性 65
3.2.2 自由移動（free move） 71
3.3 正則表達式 74
3.3.1 語法 75
3.3.2 語義 78
3.3.3 解析 86
3.4 等價性 88
第4章 增加計算能力 97
4.1 確定性下推自動機 100
4.1.1 存儲 100
4.1.2 規則 101
4.1.3 確定性 103
4.1.4 模擬 103
4.2 非確定性下推自動機 110
4.2.1 模擬 113
4.2.2 不等價 115
4.3 使用下推自動機進行分析 116
4.3.1 詞法分析 116
4.3.2 語法分析 118
4.3.3 實踐性 122
4.4 有多少能力 123
第5章 終極機器 125
5.1 確定型圖靈機 125
5.1.1 存儲 126
5.1.2 規則 127
5.1.3 確定性 131
5.1.4 模擬 131
5.2 非確定型圖靈機 136
5.3 最大能力 137
5.3.1 內部存儲 137
5.3.2 子例程 140
5.3.3 多紙帶 141
5.3.4 多維紙帶 142
5.4 通用機器 142
5.4.1 編碼 144
5.4.2 模擬 145
第二部分 計算與可計算性
第6章 從零開始編程 149
6.1 模擬lambda演算 150
6.1.1 使用proc工作 150
6.1.2 問題 152
6.1.3 數字 153
6.1.4 布爾值 156
6.1.5 謂詞 160
6.1.6 有序對 161
6.1.7 數值運算 161
6.1.8 列表 168
6.1.9 字元串 172
6.1.10 解決方案 174
6.1.11 高級編程技術 178
6.2 實現lambda演算 184
6.2.1 語法 184
6.2.2 語義 186
6.2.3 語法分析 191
第7章 通用性無處不在 193
7.1 lambda演算 193
7.2 部分遞歸函式 196
7.3 SKI組合子演算 201
7.4 約塔（Iota） 210
7.5 標籤系統 213
7.6 循環標籤系統 220
7.7 Conway的生命遊戲 229
7.8 rule 110231
7.9 Wolfram的2，3圖靈機 234
第8章 不可能的程式 235
8.1 基本事實 236
8.1.1 能執行算法的通用系統 236
8.1.2 能夠替代圖靈機的程式 239
8.1.3 代碼即數據 239
8.1.4 可以永遠循環的通用系統 241
8.1.5 能引用自身的程式 245
8.2 可判定性 250
8.3 停機問題 251
8.3.1 構建停機檢查器 251
8.3.2 永遠不會有結果 254
8.4 其他不可判定的問題 258
8.5 令人沮喪的暗示 260
8.6 發生上述情況的原因 261
8.7 處理不可計算性 262
第9章 在“玩偶國”中編程 265
9.1 抽象解釋 266
9.1.1 路線規劃 266
9.1.2 抽象：乘法的符號 267
9.1.3 安全和近似：增加符號 270
9.2 靜態語義 274
9.2.1 實現 275
9.2.2 好處和限制 281
9.3 套用 284
後記 285
