Archive for December, 2007

Write a Scheme Interpreter in Ruby(1): Parser & Analyser

Saturday, December 15th, 2007

leaf.gif也算是突然心血来潮吧,就想写一个 Scheme 的解释器,其实也是心血来潮了许多次了,只是一直都只是一个想法,最主要的原因还是因为自己对编译原理一无所知吧,也许明年上过编译原理课之后就好写了。不过这次真是心血来潮了,拦都拦不住,怕是等不到明年了。

不管写得出来写不出来,也都先试试吧!多次见石老师演示过 boost::spirit ,计算理论课上也学过了上下文无关文法,似乎还是知道个大概。于是我就开始找 Ruby 的 parser 库。

好像 parser 也有许多种,什么 Recursive Descent 之类的术语我也不懂,所以即使想去邮件列表里面问也不知道如何描述的好。找了半天似乎没有发现一个像 boost::spirit 那种级别的 parser 库,不过找到了 Peter Cooper 写的一个 Recursive Descent parser 实现(只有 255 行代码)。便下载下来,准备开工了!

Read the rest of this page »

Multiton

Friday, December 14th, 2007

Multiton 类似于 Singleton ,目的是要保证某种单一性。但是和 Singleton 的一个区别就是:Singleton 对于一个类只可能有一个对象,而 Multiton 则可能有多个对象,仅当用于构造的参数相同时,才保证唯一性。有许多地方都有这种模式的应用,例如 Lisp 或者 Ruby 里的 symbol ,同名的 symbol interned symbol 总是同一个对象。还有 Java 里的 String 也是这样的。

最近心血来潮在用 Ruby 做一个玩具级别的 Scheme 解释器,要表示 Scheme 里的 symbol 、number 和 string 的类,为了不过于浪费空间,决定把它们都做成 Multiton 这种模式。这里其实已经有了一个 Ruby 的 Multiton 实现,不过我决定自己实现一个简单一些的。

Read the rest of this page »

单元测试的绿条条

Tuesday, December 11th, 2007

其实自己对单元测试那套东西也是听说过不少的,而且自己也觉得挺有道理,却是嘛,如果有测试结果摆在那里的话,重构起来胆子都会更壮!不过我却大多数时候都是在提心吊胆地写代码,虽然项目已经分成了几个小的模块,但是当用到其他模块的功能时却老是担心会有错误,而且却是经常会有 bug 散布在各个模块中。

我明白单元测试的重要性,可是却总是“没有时间”(或者所用的工具不太合适)去写单元测试。直到最近有了亲身体验,我才明白:我以前根本没有明白单元测试的重要性!

Read the rest of this page »

More on Continuation

Monday, December 10th, 2007

我在前一篇文章中用构造二叉树的 iterator 的例子来介绍了一下 Continuation 。Jack评论中向我提了两个问题:

  1. many people know about the CPS transformation, and callcc as a means to get hold of the implicit continuation (”the rest of the computation”), but we often have a hard time using continuations: there’s a large gap between understanding code which uses callcc and the ability to actually synthesize a solution to a problem using callcc. We lose easy-understanding in using callcc, what we get? If we get a lot, how?
  2. When should we adopt callcc and how can we express callcc idea using pencil and paper easily.

我发现我好像是自己沉醉在了 Continuation 的奇妙之中,却没有把事情说清楚。在这篇文章中我会回答他提出的这两个问题,并希望借此推广 Continuation 的思想。 :)

Read the rest of this page »

Linux World 2007 @ ZJU

Sunday, December 9th, 2007

今天是 Linux World 2007 @ ZJU 系列活动的第二场,嗯,我也作为主讲人之一。今天的主题是 Emacs 和 Vim ,三个主讲人,step 和我讲 Emacs 、Rhythm 讲 Vim 。我本来是准备了两套资料,如果气氛还好就讲“Emacs 生存指南”;如果场面不够活跃的话我就退出精心准备的秘密武器了——各种各样关于 Emacs 的趣闻。

最后还是选择了后者,虽然还是有些紧张,不过我想这次讲座有进步,比上次好了。至少场下都笑了,我的目的就达到了,因为 Emacs 的基础知识的话,step 在前面都讲得差不多了。总之大概还是比较成功的一次讲座了:上次 MSTC 的 “Without IDE” 的讲座,回来以后大家都安慰我,叫我加油;但这次还是许多人赞的,而且很多人觉得很有趣。但是始终是不能完全成功吧,其实那根本是不可能达到的。讲座只有那么短的时间,不可能各个层次的人都照顾到,所以最多只能照顾到大多数人了。 ;)

我把我的资料附在这里,其中 Funny.Emacs.org 就是我今天用的内容了。如果你是比较新版的 Emacs ,应该内置了 org-mode 的支持(否则可能需要自己去下载这个插件),看起来会比较方便,特别是里面一些超链接是直接可以点击的。

Continuation

Tuesday, December 4th, 2007

Continuation 是什么?简而言之,就是代码执行状态,利用它可以把当前的执行状态保存起来,以供以后调用。Scheme 应当是最早支持完整的 Continuation 的语言了,事实上从理论上来说,任何支持 Closure 的语言都能手工实现 Continuation ,不过许多语言还是提供了现成的 Continuation 的支持,例如 Ruby 就有一个类似于 Scheme 的 call/cc(call-with-current-continuation) 的函数 callcc (因为“/”在 Ruby 里面不能作为变量名,所以最多只能做到这么像了 ;) )用于支持 Continuation 。

说了半天,到底 Continuation 是个什么东西?它能用来干什么?事实上如果限制到词法作用域之内,goto 也可以算作一个简化版的 Continuation 。一个更高级一点的例子是 setjmp/longjmp 或者是大多数人更熟悉的“异常(Exception)”都可以算作“只出不进”的 Continuation 。而真正意义上的 Continuation 比它们都有趣得多。下面让我们通过一个例子来发现它的神秘之处。

Read the rest of this page »

修改参数造成的问题

Sunday, December 2nd, 2007

这次也是做 Numerical Analysis 的作业出现的问题了。按照惯例,是学生提供一个函数,让 OJ 的 main 函数来调用,得到结果。这次是迭代取得矩阵最大特征值的题目,那个被调用的函数中传递进来一个二维数组 a 用来表示矩阵。

Read the rest of this page »

2007 冬季毅行

Saturday, December 1st, 2007

毅行是 ZJU 的传统项目了,沿山路从玉泉校区出发走到之江校区。以前参加过两次,第一次是加入国防社团的队伍,记得好像是暴走了,到得还挺早的;第二次是我们 cc98 Linux 天地版自己组织了三个队伍,因为天气原因临时改道,所以后面走得比较轻松;这次是加入了 MSTC 的老字号“MSTC 休闲观光队”。

Read the rest of this page »

Google Reader 终于有推荐功能了

Saturday, December 1st, 2007

Google Reader 终于有推荐功能了,那么多数据,也终于开始挖掘了。点那个“Discover”按钮,就能够看到推荐的种子,不像以前那样分类列表排出来,这个是按照你自己的爱好来做推荐的,感觉还不错。 :)