Archive for the ‘Lambda’ Category

动态语言的尴尬

Monday, August 6th, 2007

一提到动态语言,一般都会想到像 Python、Perl 以及 Ruby 之类的语言了,按照 Wikipedia 上的定义,动态语言是这样的:

Dynamic programming language is a term used broadly in computer science to describe a class of high level programming languages that execute at runtime many common behaviors that other languages might perform during compilation, if at all. These behaviors could include extension of the program, by adding new code, by extending objects and definitions, or by modifying the type system, all during program execution. These behaviors can be emulated in nearly any language of sufficient complexity, but dynamic languages provide direct tools to make use of them.

动态也不是说着玩的,一般 dynamic programming language 都是 dynamic typed ,换句话说:变量无类型,而值有类型。像以下的代码当然是基本要求了:

a = 12;
a = "foo";

当然还有其他动态的地方,比如,如果语言是面向对象的,那么对象的特征甚至类型通常都可以在运行时改变,甚至类也可以多次被“打开”进行修饰和修改,总之就是想怎么变就怎么变,让人写起程序来跟捏泥巴似的,哪儿不像了揉一下重新捏。再换个说法,动态语言之于静态语言,就好像它引入了时间,而不在是静止的了。静态语言编译好之后就是那个样子了,而动态语言得到的东西说不定过一会儿就和刚才不一样了(当然事情不是那么绝对,因为即使是静态语言也可以修改自己的二进制代码,关于这一点,甚至有关系到动态语言的定义的争论)。

然而动态语言这种特性却也有尴尬的一面,因为它让源代码变得“不可信”了。

在开源社区里面有一个普遍的观点:源代码是最好的注释。注释有可能(并且通常是)滞后于源代码,更关键的是,源代码没法骗人,代码怎么写,程序就必然是那个样子的了。而现在到了动态语言里面,这招不好用了,比如,在 Rails 里面,那些 model 通常是一些空类,但是你却看到在其他代码里面调用它们的许多乱七八糟的方法,而且这些方法在父类里面也没有定义:函数就这样凭空造出来了!真神奇!现在什么 grep ,TAGS 通通都不灵了!比如在 Pascal 里面,你可以搜索“function”就得到关于函数定义的语句。而在 Ruby 里面呢?比如,要找函数 foo ,可能可以搜索 def *(self.)?foo ,这是比较常用的定义函数的方法了,用简单的文本搜索工具就可以搜索到。但是定义函数的方法远远不止这一种啊。

Read the rest of this page »

我以前的笔记

Wednesday, July 25th, 2007

以前用 Emacs Muse 写了不少的笔记,自己觉得有些东西还是挺有用的,至少我自己也经常回去查阅,有些东西不记下来过一段时间还真忘记了。只是一直没有合适的地方挂出来给大家分享。虽然现在已经很少再添加新的东西了,不过既然有这个机会,我还是挂出来,免得白白写了些东西,只有我自己看到了。 :)

我把它放在了这里: http://pluskid.lifegoo.com/wiki/index.html

不愉快的 Qt 之旅

Sunday, May 27th, 2007

今天尝试用 Qt 来写一个小程序,从网上抓取一些东西,并解析一下保存到本地。很简单的功能,但是却写得非常不舒服。

大致看了一下 Qt 提供的库,似乎应有尽有了。一大堆 GUI Widget 可以构建丰富的界面,方便的 QHttp 可以用于下载 Web 页面,并使用 QRegExp 进行解析,还有 Qt 强大的 QTextCodec 可以在各种编码之间进行转换。并且 Qt 4 提供了 MCV 方式,让我能轻松地把事务和视图分开处理。一切都是那么完美,似乎是专门为我准备的一样。然而它们并不是为我准备的。

我相信使用 QHttp 下载文件是非常容易的事情,于是我决定先做界面。我打算做一个列表,其中每一项对应于 Model 的一个下载会话,里面使用 QLabel 以及 QProgressBar 之类的 Widget 组装出一个会话的详细内容的展示,如果可能的话,我还想做成 Compact View 和 Expanded View 两种模式,只对当前选中的项使用 Expanded View 。看上去就像 Esperanza 的播放列表那样。

在翻看了 Qt 所带的示例以及 QListView 、QTableView 等类的 API 等文档之后,我大致了解了 Qt 的 MCV 模式:

  • Model 持有数据。
  • View 负责显示数据。也担当了一种 Controller 的角色。
  • 还有一个叫做 Delegate 的东西,它可以用于实现单项数据的编辑 (通常你有一个 List 或者是 Table 的数据) ,如果要做精细的显示,也可以让 Delegate 取代 View 的显示功能。

现在我只要从 QAbstractItemModel 继承一个自己的 Model 来保存和管理自己的下载会话,再继承一个 QAbstractItemDelegate 用于展示会话, View 应该可以用默认的 QTableView 之类的了。

到这里一切顺利。我再具体查看了下 Model 的工作方式:

  • Model 提供函数让 View 得以知道数据的行数和列数。
  • View 会调用 Model 的 index 函数,得到某行某列的一个元素的索引,这是一个 QModelIndex
  • View 会调用 Model 的 data 函数,传递一个先前获得的索引,来取得特定元素的值。
  • Model 使用诸如 dataChanged 之类的信号通知 View 数据改变了。

于是我决定在 Model 维护一个会话的 List ,每个会话通过信号通知 Model 状态改变,而 Model 再通知 View 更新视图。但是细节上比较麻烦,一堆的会话连接到 Model 上,信号发过来,无法区分是哪个会话,可以为每个会话加一个 id ,然后由 Model 来管理 id ,并在发送信号的时候带上 id 。但是现在是 View 来向 Model 索取数据,它使用行和列的索引作为标识,一个想法是把 id 就做成行号,于是某个 id 的会话发送信号说状态改变了,我正好可以就那个 id 告诉 View 第几行的数据改变了。可是如果我想要移除下载完成的会话的话,这样就不好办了,移除会话以后剩下的会话的行号就要变了,而 id 并没有得到自动同步。每次,某个 id 的会话报告状态改变, Model 需要查找一下所有的行,看哪一行对应到该 id ,然后通知 View 该行改变了。这显得非常麻烦,似乎是由于 View 强行使用行列作为数据的索引造成的。不过没关系,我干脆直接报告所有的行都变化了就好了。

而 Delegate 也相当复杂,想要实现编辑,可以提供一个 Widget ,然后显示的时候却要实现 paint 函数。我更希望使用一系列 Widget 组装起来实现一个 View 的显示,而不是自己去画。我搜索了一下邮件列表,发现 Qt 现在确实不提供这种便利,只有自己画,还好 Qt 提供了一些可以画出基本 Widget 的函数,可是诸如 Layout 之类的功能就只能自己来管理了。还有一个地方相当奇怪,我在下载了一些真实程序的源代码浏览了之后,发现 View 从 Model 那里取数据的时候还有一个 Role 参数,而 Role 不同的时候期望返回不同的东西,其中有字体、颜色、背景以及图标等,这些原本应该由 View 来处理的东西竟然全部要从 Model 那里取!最近时常用 Ruby on Rails 写一点 Web 应用,觉得 MCV 模式使用起来很顺,但是现在用 Qt 的这套构架却觉得异常别扭。

经过痛苦地编码,最后终于实现了一个还比较理想的 UI 界面。现在看来,还是 HTML + CSS 写界面舒服啊,虽然 HTML 这么多年也饱经沧桑了,但是毕竟是专门用于做界面的语言。我想不久以后在桌面应用程序这一块的专用 UI 语言也该大行其道了吧 (如果那个时候还有桌面应用的话) ,好像 Mozilla 和微软都有这类似的东西吧 ( XUL 以及 XAML 之类的东西 ) ?

接下来是下载,QHttp 用起来还是很方便的,下载之后用 QTextCodec 进行编码转换,然后使用 QRegExp 进行解析。查看了文档,发现 QRegExp 居然不支持多行搜索!后来发现下载的文件一直不对。跟踪了好久,发现是 QHttp 在指定要下载的路径的时候比较麻烦,而用了 QUrl 反而好像是在帮倒忙,结果资源位置都指定错了。

我决定让 Qt 的体验和这个程序暂时告一段落。今天的经历实在是让原本在我心目中地位很高的 Qt 程序库一下子降低了许多。用 Qt 构建出来的 KDE 用起来觉得处处设计都很贴心,而今天用 Qt 却好像感觉很多地方该有的功能没有,不该有的功能一大堆,特别别扭。所谓更换工作就是最好的休息,先把这个小程序放一放好了,要不然要对 Qt 积攒太多偏见了。

Play with macro

Friday, May 25th, 2007

Lisp 的宏可谓是异常强大。我所接触过的宏大约算三种:

  • 一种是 C 语言的宏,这几乎可以算是功能最弱但又用得最多的宏了。只做非常简单的语法分析,并进行文本替换。但是实际上这种简单的宏为 C/C++ 带来了许多额外的能力,不过从来这个东西好像也没有专门的文献以及教材详细讲解,大多是经验丰富的程序员们通过源代码互相传播关于宏的知识,而且许多方面在各个不同的编译器上的结果都是不一样的,所以一直以来宏也只有那部分非常常见的用法为大家所广泛接收并使用。事实上,如果你感兴趣,可以去看一看 boost.preprocessor ,你会了解到其实宏可以做很多很多的事情。
  • 一种是 C++ 的模板,我把这看作一种宏,因为模板也是操纵代码,而并不在运行期存在。C++ 的模板比起原始的宏来说要强大了许多,它会进行语法分析,并且藉由篇特化等特性让它具有了许多意想不到的能力。我不知道 C++ 模板最初设计出来是不是有一点取代宏的初衷,不过现在看来似乎完全没有走在这个方向。模板和宏都有各自的用处。模板+内联函数+常量等特性可以在一定程度上取代宏,但是宏仍然有它生存的地方。而模板似乎是刚刚找到了自己真正的方向,发展出如今鼎鼎大名的“范型编程” (GP) 。我对模板也处于刚刚开始了解的状态,不过模板似乎还处在发展初期,不像 OOP 一类的技术,先有了一套已经研究透了的理论,才拿出来实现,模板似乎是无心插柳柳成荫,做出模板这个特性以后突然发现原来模板还有这样那样的用法,实现各种各样特性的方法被人们发掘出来,种种特性令人振奋!然而也正是因为初衷并不是用来做那些事情的吧,即使可以技巧性很强地实现那些范型技术,可是却有许多尴尬的地方,例如如果出现编译错误,往往错误信息是风马牛不相及,编译速度过慢,不方便查看模板扩展后的结果,不便于调试,而且模板的种种变态的用法甚至会轻松把编译器搞挂掉。因此,模板相关的技术都需要更进一步地发展,才能更广泛地投入工业使用啊,要不然就只有作为学院派的高级玩具了。明年 C++0x 就要出来了,也算是非常令人期待的了。
  • 最后就是 Lisp 的宏了。不管是老式的 C 宏还是 C++ 的新式模板,都是独立于原来的语言的另一种语言,他们运行于编译期(如果把预处理也包含在编译期内的话)。而 Lisp 的宏与它们的最大的区别就是,Lisp 宏与 Lisp 本身是相同的一种语言,完全相同,只不过宏运行于编译期。加上 Lisp 强大的表处理能力,就能对它自己进行随心所欲的控制了(Lisp 语言本身是由表组成的)。这往往让 Lisp 的宏成为独特的威力强大的完全区别于基于文本替换的宏以及更高级的模板等技术。

宏的一个常见的用途就是用于定义“新的语言”。Steve Bourne 在为 Unix Version 7 写 shell 的时候 (就是著名的 Bourne Shell) 曾经用宏让 C 语言“变成了” Algol-68:

1
2
3
4
5
6
7
8
9
10
11
#define STRING char *
#define IF if (
#define THEN ) {
#define ELSE } else {
#define FI ;}
#define WHILE while (
#define DO ) {
#define OD ;}
#define INT int
#define BEGIN {
#define END }

然后他这样写代码:

1
2
3
4
5
6
7
8
9
10
11
INT compare(s1, s2)
    STRING s1;
    STRING s2;
BEGIN
    WHILE *s1++ == *s2
    DO IF *s2++ == 0
        THEN return (0);
        FI
    OD
        return(*--s1 - *s2);
END

当然他这样的做法遭到众人的抗议,而且 Bourne Shell 的代码也一直被认为是难以维护的典范。我在这里举这个例子并不是为了说明使用宏让语言变成另外一个样子是不好的做法。事实上,我们经常需要这样做,小到 syntax sugar ,大到 DSL (Domain Specific Language) ,我们到处都在使用宏的这种特性。而 Lisp 的这种强大的宏让事情变得更加普遍,事实上,在 Common Lisp 里面,就有一个强大的 loop 宏,它非常灵活,采用了更类似于命令式语言的风格 (例如我们熟悉的 for , while 以及 return 等) ,而不是 Lisp 原本的 map 的风格 (也因此一直不为一些保守的 Lisper 们所接受) ,另外,还有专门的宏让你可以使用中缀表达式来写 Lisp 程序 (许多人把 Lisp 的前缀表达式作为拒绝的理由) ,等等。而在于 DSL 的领域, Lisp 也和通常的其他语言的做法不同,它采用一种自底向上的做法,在 Lisp 语言本身的基础上,通过宏和表操作,构建更高层的语言应用,结果 DSL 本身其实又是 Lisp ,只不过处在更高一层,但是仍然可以使用所有最底层的 Lisp 的功能。Paul Graham 在 Programming Bottom-Up 进行了阐述。

在写 Lisp 的宏的时候,通常只要写出期望的原来的样子和期望得到的结果的样子,剩下的工作就会变得很容易了。下面我用我刚刚在 Elisp 里面做的宏作为例子来简单地介绍一下。我在前一篇 Blog 里面介绍了 smart-snippet ,可以方便地为各个 mode 定义 snippet 。然而许多时候几个不同的 mode 可以定义相同的 snippet ,例如 c-modec++-modejava-mode 可以使用相同的 snippet 。然而原来的 snippet 代码不能方便地为几个不同的 mode 定义相同的 snippet 和 key-binding 。考虑实现这个功能,我希望我在定义的时候可以这样写:

1
2
3
4
5
6
7
(smart-snippet-with-abbrev-tables
 (java-mode-abbrev-table
  c++-mode-abbrev-table
  c-mode-abbrev-table)
 
 ("if" "if ($${condition})\n{$>\n$>$.\n}$>" 'bol?)
 ("else" "else\n{$>\n$>$.\n}$>" 'bol?))

来实现分别为三个 mode 定义两个 snippet 的功能,如果手写,会写成这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
(progn
  (smart-snippet-abbrev
   'java-mode-abbrev-table
   "if"
   "if ($${condition})\n{$>\n$>$.\n}$>"
   'bol\?)
 
  (smart-snippet-abbrev
   'java-mode-abbrev-table
   "else"
   "else\n{$>\n$>$.\n}$>"
   'bol\?)
 
  (smart-snippet-abbrev
   'c++-mode-abbrev-table
   "if"
   "if ($${condition})\n{$>\n$>$.\n}$>"
   'bol\?)
 
  (smart-snippet-abbrev
   'c++-mode-abbrev-table
   "else"
   "else\n{$>\n$>$.\n}$>"
   'bol\?)
 
  (smart-snippet-abbrev
   'c-mode-abbrev-table
   "if"
   "if ($${condition})\n{$>\n$>$.\n}$>"
   'bol\?)
 
  (smart-snippet-abbrev
   'c-mode-abbrev-table
   "else"
   "else\n{$>\n$>$.\n}$>"
   'bol\?))

可以看到,首先,第一个参数是一个表,有点类似于和后面的参数做笛卡尔积的感觉。这需要一个双重嵌套的循环,没有问题,我们可以使用 loop 宏来完成,大概会像这个样子:

1
2
3
4
(defun double-loop (list1 &rest list2)
  (loop for i in list1
        collect (loop for j in list2
                      collect (list 'func i j))))

而调用 (double-loop '(1 2 3) 4 5) 就会得到这样的结果:

1
2
3
4
5
6
(((func 1 4)
  (func 1 5))
 ((func 2 4)
  (func 2 5))
 ((func 3 4)
  (func 3 5)))

得到了 (func 1 4) 这样的结构了,稍微改一下就可以用于定义单个的 snippet 。然而这里并不是我们想要的,虽然是嵌套循环,我们想要的是最后的表 (也就是 func 的函数调用) 需要处于同一层。于是我们需要一个 flatten-1 来去掉一层多余的表结构:

1
2
3
4
5
6
7
(defun flatten-1 (list)
  (cond ((atom list) list)
	((listp (car list))
	 (append (car list)
		 (flatten-1 (cdr list))))
	(t (append (list (car list))
		   (flatten-1 (cdr list))))))

调用 (flatten-1 (double-loop '(1 2 3) 4 5)) 就可以得到想要的结果了:

1
2
3
4
5
6
((func 1 4)
 (func 1 5)
 (func 2 4)
 (func 2 5)
 (func 3 4)
 (func 3 5))

下面就可以写做宏的形式:

1
2
3
4
5
6
7
8
9
10
11
(defmacro smart-snippet-with-abbrev-tables
  (abbrev-tables &rest snippets)
  `(progn
     ,@(smart-snippet-flatten-1
	(loop for table in abbrev-tables
	      collect (loop for snippet in snippets
			    collect (append
				     (list
				      'smart-snippet-abbrev
				      table)
				     snippet))))))

然后我们可以看一下效果,使用 M-x pp-eval-last-sexp 来执行下面的代码:

1
2
3
4
5
6
7
(macroexpand '(smart-snippet-with-abbrev-tables
 (java-mode-abbrev-table
  c++-mode-abbrev-table
  c-mode-abbrev-table)
 
 ("if" "if ($${condition})n{$>n$>$.n}$>" 'bol?)
 ("else" "elsen{$>n$>$.n}$>" 'bol?)))

就可以看到如下的结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
(progn
  (smart-snippet-abbrev
   java-mode-abbrev-table
   "if"
   "if ($${condition})n{$>n$>$.n}$>"
   'bol\?)
 
  (smart-snippet-abbrev
   java-mode-abbrev-table
   "else"
   "elsen{$>n$>$.n}$>"
   'bol\?)
 
  (smart-snippet-abbrev
   c++-mode-abbrev-table
   "if"
   "if ($${condition})n{$>n$>$.n}$>"
   'bol\?)
 
  (smart-snippet-abbrev
   c++-mode-abbrev-table
   "else"
   "elsen{$>n$>$.n}$>"
   'bol\?)
 
  (smart-snippet-abbrev
   c-mode-abbrev-table
   "if"
   "if ($${condition})n{$>n$>$.n}$>"
   'bol\?)
 
  (smart-snippet-abbrev
   c-mode-abbrev-table
   "else"
   "elsen{$>n$>$.n}$>"
   'bol\?))

已经很接近结果了,唯一的不足就是我们应该使用 'c-mode-abbrev-table 而不是没有 quote 的形式。这个也好办,我们写一个函数来为作为第一个参数的包含所有 abbrev-table 的表的每一个元素加上 quote

1
2
3
(defun smart-snippet-quote-element (list)
  (loop for item in list
	collect (list 'quote item)))

最后把这个函数加进去,就得到完整版的 smart-snippet-with-abbrev-tables 宏:

1
2
3
4
5
6
7
8
9
10
11
12
(defmacro smart-snippet-with-abbrev-tables
  (abbrev-tables &rest snippets)
  (let ((tables (smart-snippet-quote-element abbrev-tables)))
    `(progn
       ,@(smart-snippet-flatten-1
	  (loop for table in tables
		collect (loop for snippet in snippets
			      collect (append
				       (list
					'smart-snippet-abbrev
					table)
				       snippet)))))))

用同样的一些工具函数,我还做了 smart-snippet-with-keymap 宏,而且它们的结构都很类似,我甚至可以把这个结构抽象出来,定义一个新的宏,比如,叫做 smart-snippet-def-with ,然后使用这个宏来定义 with-abbrev-tablewith-keymap 宏,来达到代码重复程度最小化 (事实上,名如 def-xxx 的宏在 ELisp 里面是非常常见的) 。

当然,宏的用法并不局限于此。Paul Graham 在他的《On Lisp》一书中描述了大量 Lisp Macro 的技巧,如果感兴趣,可以找来阅读一下。