计算的本质
出版日期:2014-11
ISBN:9787115361541
作者:[英] Tom Stuart
页数:300页
内容概要
Tom Stuart
Tom Stuart 伦敦数字产品咨询公司Codon的创始人、计算机科学家、程序员，擅长Ruby、Rails、Web应用、用户体验、面向对象设计和行为驱动开发。另外，作为顾问、导师和培训师，他经常通过网络帮助各家公司高质高效地创建软件产品。他还曾在剑桥大学做编译器优化方面的演讲，与人联合组织过Ruby大会（Ruby Manor），而且是伦敦Ruby用户组的成员。
书籍目录
封面介绍 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 110 231
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
作者简介
《计算的本质：深入剖析程序和计算机》借助Ruby全面介绍计算理论和编程语言的设计。作者注重实用性，不仅尽量抛开复杂难懂的数学符号，而且特别选用简单快捷的编程语言Ruby，在读者熟知的背景知识下，以明晰的可工作代码阐明形式语义、自动机理论，以及通过lambda演算进行函数式编程等计算机科学知识，并为让其自行探索做足准备。
本书适合计算机科学系学生，以及熟知现代编程语言，想要系统地学习计算机科学知识的程序员、软件工程师阅读参考。
发布书评
精彩书评 (总计1条)
-
非科班，ruby零基础，初学爱好者的一番胡说八道1.我不关心书上的代码是ruby实现，或是JS实现、或是Python实现，我只关心这些奇怪的符文能不能在我的机器上跑起来，何况我又不靠这本书学ruby、JS、或者python。代码效果相当好，搭配本书托管在Github上的代码[1]使用，简直愉悦！2.我也不关心世界上存在着的其余那些神书、奇书、动物书的奇迹效果，我只关心这本书对我而言是不是可理解的输入(comprehensive input)，作者直接给我看代码(show me code) 而且还是循序渐进地 (show me code)，如下："首先怎么做，为什么我们要这样做">>代码>>"然后怎么做，为什么要这样做">>代码>>“写好了，看看效果”>>代码实力写代码，实力教怎么看代码，实在很佩服这个作者！3.DFA NFA RegularExpression DPDA DTM lamba HaltingProblem TagSystem 满足好奇兴奋之余也倍感踏实，还不是因为有可以运行的代码！[1] 本书配套代码 githubhttps://github.com/tomstuart/computationbook
精彩短评 (总计33条)
-
可以跑的ruby代码，好兴奋呀！ https://github.com/tomstuart/computationbook -
书本身还是不错的，看得出作者的用心，但是定位就有点尴尬，因为理论部分的缺失所以没有办法学到很多真正有用的知识，如果算作科普书籍的话难度又有些大，没有基础很容易看的似懂非懂。归根到底是计算理论这部分知识太抽象太难了吧，不过如作者所说的用来“满足自己的好奇心”还是足够有趣的。 -
SICP -
#图灵PDF# 4.3 分。有点像大三大四两门外教课的课本欸！可爱也可爱在 Ruby 实现，啰嗦也啰嗦在这儿。如果能够压缩成 150 来页的小品，就更可爱啦！还蛮有趣的~ -
蛮适合用于入门的； -
2016年最有收获的一本技术书，从有限状态机到下推自动机，再到终极机器图灵机，能力一步步增强。中间介绍了一些图灵完备的系统，但是图灵机也有做不到的事情，也就是判断一个系统或者一段程序做了什么，最后通过介绍几个案例来弥补这些不可能做到的事情。 -
练习到了第六章，后面三章大概看了下。 -
抽象描述计算机物体和人之间关系。机器，语言，编程。以及结果的预判，可能与不可能。处理对象中方法，消息类，模块，数据，语法，语义。 -
对编译原理和计算机组成原理的解释，思想新颖 -
循序渐进而又启发性很强的一本书 -
计算理论~ -
《计算的本质》以Ruby程序为工具讲解了计算机、程序、程序语言等基本的计算机科学问题，是一本非常好的计算机科学实践书籍。使用Ruby语言模拟了各种机器的计算能力、计算机语言的语义，深入浅出的讨论了计算的本质。
书中详细探讨了各种类型机器的计算能力，机器按照计算能力分为有限自动机（FA），下推自动机（PDA），图灵机（TM），通用计算机；除图灵机与通用计算机等价外，计算能力逐渐增强。有限状态机增加外部存储的栈，扩大计算能力就是下推自动机；有限状态机增加无限长的纸带访问就是图灵机，图灵机的实质就是能够访问无限长纸带的有限状态机。
DFA可以识别正则式，NPDA可以识别回文字符串，确定性图灵机(DTM)可以进行二进制递增运算。每种机器都有相当明显的能力限制，FA无法解决涉及无限制的计数问题，例如判 -
你竟然用ruby!!于是我没看下去 -
难得的好书，简明有趣。 -
这本书的读者对象是“没有正规学习过数学或者计算机科学的朋友”，然而根据我的目前的阅读经验来看，没有基础的人是完全不可能看得懂这本书的。因为这本书主要以实战为主，理论讲的超级烂的，内容编排也不够到位……看不懂的建议先补理论吧。 -
必须是力荐，讲解通俗易懂，非常平易，可以让人轻松学习，里面的资料也比较丰富，我很喜欢。 -
非常精彩，这么薄的一本书，覆盖了图灵机、lambda演算、SKI 组合子等计算理论，并且提供了可供运行和测试的代码，还有啥不知足的呢？略微可惜的可能是因为篇幅或者作者故意限制，没有特别深入。 -
从有限状态机到图灵机，全书在引导读者剖析理论层面的计算机，lambda算法激动人心，就是Ruby语法有点琐碎。遗憾就是看的半懂。 -
习惯了站在巨人的肩膀上, 偶尔也要往下看看 -
在不到三百页的篇幅里，把自动机，图灵机，lambda过了一遍，而且还附了实现及测试代码。唯一不足的就是用工程的态度去讲解科学，会缺乏更细致的理解。看来还得先看看几本导论性质的计算理论的书，再来刷一遍，相信理解会深入一些。 -
满足好奇心 -
SICP风格 -
Ruby版编译原理 -
这半年读过的最漂亮的一本书，各种计算模型及某些通用计算模型的等价性、语义分析/语法分析以及最后一章的类型检查系统（给我感觉就是在写一个小的编译器或者解释器）、还有停机问题的具体介绍都非常精彩。最最重要的是，所有的论述都用上了 Ruby 代码，大部分例子理论上都是可以运行的！Ruby 的灵活性（比如代码即数据在某些语言中就不是很方便）给本书某些章节写实现时带来不少便利，第八章作者甚至一本正经胡说八道地用 evaluate function 写了个停机问题的函数，然后想尝试解决哥德巴赫猜想。
笔记过几天附上。 -
请教：谁能概括一下，这本书揭示计算的本质是什么？ -
1星不是说这本书写的不好, 是我看不懂 -
知识储备不足，仅看懂了跟正则表达式相关的一部分。 -
看了这本书，对学习计算理论导引有很大的帮助，这本书可以看做是计算理论导引的实战版本。 -
编程要思考这样几个关键的概念：时间（算法和流），空间（数据结构和存储），不确定性（大数分解和程序的处理未知结果），无限（堆栈和递归）。其实康德的《纯粹理性批判》不就是研究这几个概念么？ -
前半部分不错，后半部分的形式语言讲的太浅了 -
读了一半，还是比较有意思的，但是基础不好看起来还是要用心，放下了就没有读完。 -
可惜是 ruby 描述的 -
Ruby版SICP