Yukang's Page

Understanding Computation

2015-02-10

前些天花了一些时间读这本书《计算的本质:深入剖析程序和计算机》。总的来说这本书非常不错。虽然讲述的是一些看似理论的东西,
里面有不少短小的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,这本书是这么写出来的。

使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章