計算的本質(深入剖析程序和電腦) 计算的本质:深入剖析程序和计算机

<內容簡介>

《計算的本質：深入剖析程序和計算機》借助簡單的Ruby代碼示例，全面、深入地介紹計算理論和編程語言設計。作者註重實用性，在讀者熟知的背景知識下，以明晰的可工作代碼闡釋了形式語義、自動機理論，以及通過lambda演算進行函數式編程等計算問題，並為讀者自行探索打下了良好基礎。
《計算的本質：深入剖析程序和計算機》面向熟悉某種現代編程語言卻非科班出身的程序員，是一本幫你真正理解計算機科學和計算原理的優秀參考書。

<章節目錄>

封面介紹 X
前言 XI
第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