前些天花了一些时间读这本书《计算的本质：深入剖析程序和计算机》。总的来说这本书非常不错。虽然讲述的是一些看似理论的东西，
里面有不少短小的 Ruby 程序，读起来还是非常有趣的。回想当年大学的时候有一门课程叫做形式语言与自动机，当时觉得这门课真是太没劲了。理论的东西终究需要一些实践才能掌握，早早读到这样的书就好了。

首先第一部分介绍了一些基本 Ruby 语法，十来页的介绍就够了。Ruby 的语法真的是非常直观，人性化的。两年前我被 Ruby 吸引，现在我每天大部分时间都敲着 Ruby 代码，用 Ruby 很省事！对 Ruby 来说数据也是程序是很常见的，这本书使用 Ruby 来做示例是很好的选择。

什么是程序？这是一个可以从各个角度深入的问题，程序是程序员表达自己脑海中的思想的形式。我们需要从编程语言开始，语言的语法和语义完整地定义了一门编程语言。这本书开始以小步语义来解释一个简单的语言，这样就得到一个的解释器程序。小步语义提供了一种轻松的方式来模拟计算的中间过程。随后介绍了大步语义，我觉得这两者之间的关联有些像自顶向下和自底向上。然后介绍了 treetop 这个工具，自定义 grammar 来实现一个简单的语法解释器。

第三章开始介绍自动机，从最简单的确定性有限自动机开始 (DFA)，然后是非确定性自动机 (NFA) 和正则表达式。我原来上学的时候大多在手动画这些状态图，远没这些简单的代码好玩。
有输入，有状态，有输出，这些状态机就是最简单的机器了。而 NFA 虽然看起来比 DFA 有更多的特性，但本质上它可以转化为 DFA。为了增加计算能力，为自动机加上一些外部存储。用自带栈的确定性有限状态机 (DPDA) 能识别出平衡字符串。

第五章介绍图灵机，图灵机本质上是有外部存储的状态机。我之前看过图灵传记，图灵对密码学非常感兴趣，而且在二战中破译了大量德军密电。图灵机的概念很简单，而计算的本质就是如此简单直接的描述。模拟图灵机的过程倒并没什么大的乐趣。

第六章开始 lambda 演算，lambda 演算是从另外一个角度去理解计算。这一章非常好玩，这里只是用了 Ruby 的三个特性：对变量的引用，创建 proc，调用 proc 来实现一个极小的编程语言。lambda 演算的基本元素就是这三个：

<exp> ::= <var>                :变量引用
| (lambda (<var>) <exp>)       :创建 proc
| (<exp> <exp>)                :调用 proc

从这些简单的元素构建出语言的各种特性非常好玩，最终一个简单的 gcd 被解释成充满了 proc 的 Ruby 程序，然后就能运行了。

后面几章继续简述了可计算行问题。停机问题表明我们无法拥有能力不受限制的编程语言，淡淡的忧伤。

这位作者Tom Stuart的博客非常有料，他在自己的网站上用幽默了一把I Have No Idea What I’m Doing，这本书是这么写出来的。