C'mon, It's Turing Machine! (Part 2)
October 17th, 2011
(Following the 1st part )
Write Your Own Machine
File machines/an_irrational_number.machine includes all the fundamental elements to create your own Turing Machine.
- The lines start with semicolons are comments.
- Non-comment non-empty lines are m-configurations, each of them consists of 4 columns (separated by vertical lines), which in turn are:
- Name of current m-configuration.
- The symbol read from current square of the tape—m-configurations with same name could behave differently while reading different symbols.
- Operations, separated by commas. Valid operations are:
- P{x}: Write {x} to current square of the tape.
- E: Erase any symbol in current square.
- L/R: move the cursor one square left/right.
- Next m-configuration—what should be done after current m-configuration?
Now, try to write your own machine, and run it!
What’s Next?
Universal Turing Machine , of course. (What else otherwise?)
(It requires reading Chapter 7 and 9 of The Annotated Turing . Although I haven’t started yet, I can feel it’s not an easy task. Any contribution would be highly appreciated.)
Meanwhile, I started building a web UI running Turing Machines with Compojure . Take a look at web folder. You can trial it with:
$ lein ring server
It also makes sense to tidy it up and make it more interactive.
I also want to build an iOS application…but that’s another story.
You might want to try something more interesting, e.g. to write a general Turing Machine to determine any given Turing Machine would halt or not; to solve the Entscheidungsproblem ; etc.
Anyway, enjoy :D
C'mon, It's Turing Machine! (Part 1)
October 12th, 2011
Spent about 10 hours, I wrote my first program with Clojure : an implementation of Turing Machine as described in Alan Turing’s famous paper ” On Computable Numbers, With An Application To The Entscheidungsproblem ”.
(Note: Charles Petzold’s book The Annotated Turing is a good point to understand Turing’s paper.)
Get Started
First of all, you need clone the codebase from GitHub:
$ git clone git://github.com/gigix/turing_machine.git
In order to build it, you also need install Leiningen—which is pretty easy on my MacBook Pro with MacPorts:
$ sudo port install leiningen
Now you can build the codebase and see if everything works:
$ cd turing_machine/clojure && ./build.sh
You should see turing_machine-1.0.0-SNAPSHOT-standalone.jar being packaged, as well as a “tape” being printed as following:
(0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1)
That’s the binary form of rational number 1/3 (0.010101…). You just executed a Turing Machine which calculates 1/3 and prints the result to a tape—actually we only calculate and display the starting 10 squares of the tape, because it’s simply impossible to finish the calculation, because it’s infinite.
Calculate An Irrational Number
There’s another machine lays in machines/an_irrational_number.machine, which calculates an irrational number with following form:
0.01011011101111011111…
You can run this machine with following instruction—the algorithm is more complicated, so you have to run more steps to see a reasonable shape:
$ java -jar turing_machine-1.0.0-SNAPSHOT-standalone.jar machines/an_irrational_number.machine 1000
The starting part of the tape looks like following:
And here’s the “source code” (formal name should be “m-configurations”, in which “m” stands for “machine”) of this machine, which I will explain in more detail in next section:
(To be continued…)
代码风险分级
March 29th, 2011
（本文基本上出自 FindBugs ）
阻碍风险
逻辑正确性风险
这些缺陷模式的出现可能意味着程序员错误地描述了代码逻辑，从而导致程序行为出错。例如：
- 不可能的类型转换。
- 永远为假的
instanceof操作 - 对
null调用equals方法 - 对不同类型的对象进行相等性比较
多线程正确性风险
这些缺陷模式的出现可能意味着程序员对多线程环境编程不熟悉，在程序运行中可能随机引发错误。例如：
- 对
Boolean值同步可能导致死锁 notify()或wait()不配对- 对
readObject()方法同步 - 错误的静态变量缓式初始化
关键风险
易受恶意代码攻击
这类缺陷模式表示代码没有足够的封装或是放松了已有的封装，在极端情况下可能遭受恶意代码的攻击，或引入不易诊断的错误。例如：
- 以返回可修改对象的形式暴露内部细节
public访问级的finalize()方法- 非
final的成员变量 - 在成员变量中保存可修改的容器
安全性风险
这类缺陷模式可能意味着程序员没有充分考虑安全性需求，可能降低系统的安全性水平。例如：
- 在代码中硬编码密码
- HTTP响应分拆漏洞
- JSP跨站脚本漏洞
- SQL注入漏洞
主要风险
性能风险
这类缺陷模式可能导致系统性能水平不必要地降低。例如：
- 不必要的原生变量装箱/拆箱
- 显式调用垃圾收集
- 调用低效的浮点数构造器
-
URL的性能缺陷
不佳编程实践
这类缺陷模式指示出不够好的编程习惯，会给维护带来困难，特殊情况下有可能导致程序行为错误。例如：
- 用
==或!=进行字符串比较 clone()方法没有调用super.clone()- 丢弃异常
- 用
removeAll()方法清空容器
享受代码之美
September 4th, 2008
（本文系 《代码之美》 的推荐序）
“希望写出漂亮代码的开发者可以向艺术家们学习一些东西。画家常常放下手中的画笔，然后远离画布一段距离，围着它转一转，翘起脑袋，斜着看看，再从不同的角度看看，在不同的光线下看看。在寻求美的过程中，他们需要设计这样一些视角并使它们融为一体。如果你的画布是个集成开发环境（IDE）而你的媒介就是代码，想一想，你如何做到离开画布一段距离，用挑剔的眼光从不同的视角来审视你的作品？──这将使你成为一个更优秀的程序员，并帮你写出美丽的代码。”
写这段话的Alberto Savoia在他的文章里真的没有讲什么令人敬畏的高技术或是大架构，他讲的是每个计算机系的大二学生都熟悉的二分查找。所以Savoia真的是在讲如何写出漂亮的代码，所以才选择了这么一个所有人都清楚得不能再清楚的例子。你会觉得这种事情都是些不谙世事的小程序员才会热衷于干的吧？可这位Savoia却是从Google离职以后开创了Agitar Software公司（http://www.agitar.com/）的不折不扣的创业者。有意思吗？一个胡须花白、在这个行业里厮混了数十年、拥有自己公司的老家伙，还在乐此不疲地谈论“漂亮的代码”。
这本《代码之美》就是由三十多篇像这样有意思的文章组成的。像Brian Kernighan、Tim Bray、Charles Petzold、Douglas Schmidt、Yukihiro Matsumoto这样的名字，你甚至很难想象他们同时出现在同一本书上。或许也只有“漂亮的代码”这样的话题才能激起他们共同的兴趣。于是就有了这本了不起的书：从正则表达式匹配器到图像处理，从通信到基因排序，这些可能是世界上最优秀的程序员毫不吝啬地向读者展示：不论面对什么问题、使用什么语言，代码的美感都是始终存在的，而且这种美感应该是程序员毕其一生不懈追寻的。
作为《重构》的译者，不时有人会问我一些关于重构的问题，其中一个问题让我最感为难：为什么要这样做？真的，如果不是要修改代码，也不是要添加功能，为什么要把这段代码抽取出来呢？让每个方法都保持5行以内的长度到底有什么好处呢？这种时候与其说是有什么利弊权衡，毋宁说就是为了让代码“更漂亮”。当然了，在大部分时间里，软件开发是一项集合了科学、工程和服务的工作，但──至少在我们的内心深处──它多少还有那么一点艺术的成分。除了完成任务以外让自己手上的代码更具美感，也算是对自己作为程序员的梦想的小小坚持吧。
所以，既然你已经拿起了这本书，就暂时放开那些功利的目标吧──别误会，这可不是一本没用的书，通过阅读这些“高手”们的编程心得，对自己的能力提升就算不能立竿见影至少也有潜移默化之功。但那也只是装珍珠的盒子而已。在一个安静的周末，给自己泡上一杯清茶，跟着三十三位顶尖高手畅游在代码世界，在他们的指引下遍赏代码之美，这才是作为一个程序员最大的享受呢。
