« April 2009 | Main | June 2009 »

May 26, 2009

lua 中判断字符串前缀

一个 lua 的小技巧

在写 lua debugger 的时候,我需要判断一个字符串的前缀是不是 "@" 。

有三个方案:

  1. 比较直观的是 string.sub(str,1,1) == "@"
  2. 感觉效率比较高的是 string.byte(str) == 64
  3. 或者是 string.find(str,"@") == 1

我推荐第三种。(注:在此特定运用环境下。因为用于判定 source 的文件名,大多数情况都是 @ 开头。如果结果为非,则性能较低)

第一方案 string.sub 会在生成子串的时候做一次字符串 hash ,感觉效率会略微低一些。

第二方案效率应该是最好,但是需要记住 @ 的 ascii 码 64 。如果前缀是多个字符也不适用。

May 25, 2009

lua 调试器制作注意

前两年写过一个 lua 的调试器,blog 上有截图

不过调试器设计的关键不在于界面,在于调试协议。前两年的那个是设计的不完整的。

最近同事强烈要求引擎提供一个强力的调试工具,虽然我个人不太依赖调试去写代码。甚至认为,经过反复调试才正确工作的代码不是好代码。不过周末还是花了点时间重新制作了一个 lua 调试器。

中间发现一些问题,非常让人吐血。列在这里,做个记录。

一开始我比较担心 lua 的 debug hook 会降低运行性能。所以考虑的优化比较多。

都说提前优化是万恶之源,此话绝对不假。可挡不住的诱惑是,制作一个几乎不影响运行性能的调试器,更为实用。而且这个东西我构思了好几年,优化策略也思考再三,不算提前优化吧。

基本优化策略是把被调试程序分成三种调试状态:

  1. 无须 hook 的状态。这个状态下,没有设置断点,lua 程序可以全速去跑。只要定期查询一下,调试器有没有指令输入即可。( 和 gdb 一样,这个调试器支持且暂时仅支持远程调试)这个轮询,可以放在程序主循环内,定期跑一下即可。几乎不会影响正常的程序运行。这样,我可以随时 attach 到正在工作的 lua 进程上。

  2. 高密度的 hook 状态,使用 lua debug hook 的 line 模式。每条 lua 指令都被 hook ,用来检测断点的工作。

  3. 低密度的 hook 状态。仅使用 lua debug hook 的 call/return 模式。这个模式下,仅仅返回进入和返回被 hook ,可以做一些粗略的判断。

实现的时候发现几个问题。

我原来的计划中,使用 call/return 的 hook 消息,监视 lua 运行所在的源文件/ 函数。 一旦发现没有断点,则可以使用第三模式运行,提高被监控状态的运行效率。

当然,如果所有断点都被 disable ,则切换到第一状态。

事实上,简单的在 call/return 的 hook 内获取上级函数的 source 是不够的。因为,lua 的 call hook 发生的时候,已经进入被调用函数;而 lua 的 return hook 发生,尚还停留在调用函数的最后一行。也就是说,可能没有机会回到被调用者。

比如在 a.lua 中写上两个函数调用 :

foo1()

foo2()

而把 foo1 和 foo2 定义在 b.lua 中。如果仅仅 hook call/return 。会发现 foo1() 和 foo2() 调用期间,从 hook 中,没有回到 a.lua 。假设在 foo2() 上设置断点,就没有机会断下来。

想来想去,补救的方法是:当发生 return 或 tail return 时,多看一级堆栈,获得调用者的 source 名。不过这样还是有点问题,有可能调用者是从 C 或是一段运行期产生的代码中过来,依然回溯不到正确的位置。正确的做法是一直回溯到可识别的源代码文件名。( @ 开头的字符串)

最后再查表判定是否需要切换 hook 的 mask 状态。

另一点是关于 lua 的 tail return 的,return 和 tail return 是分开的事件,在实现 step over 的功能时务必小心。

关于无效代码行的判定没有想到特别好的方案。即设置断点时,如果设置在无效行上,应该向上移动到有效位置。虽然 lua 的 debug 模块提供了一些相关的支持,但是比较有限。靠监控运行的当前函数来反复匹配合适的断点位置,代码写起来会过于繁琐。

在调试器中查看变量的值,最好注意一下潜在的副作用。主要是 metatable 造成的。用 rawget 去取 table 里的数据更靠谱一些,需要小心的是是 tostring 的 meta 方法调用。

lua 的高阶用法中,往往会由一段代码生成新的代码运行。让调试器识别这种情况,并给予支持,会带来许多方便。(主要是格式化源码,并对 unix 和 dos 的回车做兼容比较麻烦)


周六一天本来把调试器已经写完,后来发现一些隐藏的 bug 。越看代码越不顺眼,然后周日推翻重写了一次。

新的版本主要是建立起一个调试状态机。把调试器的各种状态严格区分。比如运行态和阻塞交互状态。以及大状态下的小状态划分。

因为后面会做一个图形交互前端,对调试指令的协议定义要求比较严格。文档也仔细研究过,参考了 gdb 的协议。


做完的感觉就是累。没想到后面有没完没了的小需求加进来。幸亏中途一咬牙重写了。否则肯定在周末是完成不了的。不算 socket 通讯部分(以前自己实现的一个模块),暂时有 1000 行 lua 代码吧,比第一个版本简洁很多,但比我预期代码规模大一些。也不能算太好看。


btw,我在选择调试器默认端口时,选了个 3563 。16 进制为 0xdeb 。 昨天 Sean 同学告诉我,这个是个知名端口: 乃 Wacom C 的调试器端口。吼吼,真是英雄所见略同。

May 20, 2009

X Window 的 Resize 处理

程序员在陌生领域工作时,都想寻求范例。看起来,我们都很依赖 Meme Machine 。

可惜的是, X Window 领域的直接针对 XLib 编程的范例太少。偶尔碰到点问题都让人很痛苦。只有反复研究文档了。

我的程序在处理 Resize 消息时老是不正确,仔细阅读文档后,发现是以前理解有问题。

起先,我为窗口消息注册了 ResizeRedirectMask ,然后在消息循环中就可以得到一个 ResizeRequest 消息。然后,我处理这个消息,但结果总是不对。

今天研究了一下,发现 ResizeRedirectMask 会导致 no further processing is performed 。也就是说,通知你 resize 请求后,X 系统就不管你了。至于还差什么事情要做(比如改变客户区大小),我也不知道该怎么做才完全正确。(如果在 Windows 里,应该是调用 DefaultWindowProc )

不过解决方法其实也很简单,不用注册 ResizeRedirectMask ,而注册 StructureNotifyMask 。在窗口改变的时候, X 会发一个 ConfigureNotify 。因为这个只是 Notify ,所以 X 会把所有它应该做的事情做的周全。

btw, Sean 同学推荐我用一下 XCB ,因为 XLib 用起来实在是太头痛了。这是个替代物。

May 10, 2009

树结构的管理

要写过多少代码才能得到哪怕一点真谛?

多少年过来,我在潜意识的去追求复杂的东西。比如我自幼好玩游戏,从小到大,一直觉得玩过的游戏过于简单(无论是电子游戏还是桌面游戏),始终追寻更复杂规则的游戏,供我沉浸进去。或许是因为,有了更高的理解和控制复杂度的能力,就可以更为轻松的驾御复杂性。

这很好的解释了 2000 年到 2004 年我对 C++ 的痴迷。还有对设计模式的迷恋。

Eric S. Raymond 说:尽量不要去想一种语言或操作系统最多能做多少事情,而是尽量去想这种语言或操作系统最少能做的事情——不是带着假想行动,而是从零开始。禅称为“初心”(beginner's mind)或者叫“虚心”(empty mind) 。

代码写多了,问题见过了,甚至是同一问题解决多了。模式这种东西自在心底,不必拿出来。时时的从零去想,总能重新明白一些道理。

为什么说语言重要也不重要,算法和数据结构重要也不重要。对要解决的问题的领域的理解很重要(即明白真正要做什么)。理解了,我们才可以用面向对象,用模式去套问题;可理解了,我们又不真的需要这些繁杂的抽象。

闲话放一边,今天想谈谈树结构的管理。

这个问题来自游戏引擎里对对象的管理。有时也出现在 GUI 模块中。

我以前总结过,所谓面向对象,就是可以用统一的方法对不同的对象进行同样的操作。而这个过程,需要我们把对象的同质引用放到一个容器中。这个容器,绝大多数情况下,由一个集合结构即可胜任。

而有些复杂的问题领域中,我们又需要树型结构的容器。有时是为了优化(比如在 3d 引擎中,用树结构描述对象的位置相对关系,以及用于裁减),有时是为了分类(比如把所有 npc 放到一颗子树下,而把 item 放到另一颗下)。

本质上,容器的处理异于普通对象,而树结构即容器之容器。把容器之容器看成一个单体,有利于问题的简化。

处理这种复杂数据结构,动态语言相对于 C/C++ 这样的静态语言,有比较明显的优势。但是在性能方面又有明显的劣势。权衡之下,我们需要做的是采用 C 去实现底层细节,而动态语言做高层管理,并控制粒度,减少控制频率。

据我个人观察和实践,虽然最终游戏 engine 管理的树结构非常繁杂。但 C/C++ 部分运转起来之后,需要特别控制的节点层次并不多。

但是,若想充分利用动态语言的动态性,在子树构建阶段,又非常有可能触及比较复杂的树层次。只到构建子树完毕,大多数中间层次和节点永远都不会再被特别控制。

具体的例子有 3d 粒子系统,人物换装系统等等。如果用动态语言去描述那些小部件的搭建过程会比(在 C/C++ 里)较轻松。但是搭建完毕后,可能持续引用的节点并不多。大部分中间节点留在 C 层自我运转就足够了。

这就是我上面说的粒度问题。在构建的局部阶段,我们需要局部的细粒度。而在全局控制阶段,我们则需要全局的粗粒度。

如果一贯的保持细粒度,对于动态语言很可能发生性能问题。而增加动态语言和 C 底层的结合度,也更有对象生命期管理的麻烦事。如果只是麻烦倒也罢了,随之带来的 gc 的负担往往也不可小窥。


我现在的解决方案:

把树节点分为匿名和具名两类。匿名节点只在构建期对上下文可见。具名节点,可以以路径名(相对或绝对)方式引用。

如果以 lua 为实作,接口类似这个样子。

create()
with(function(self) 
  -- do something with self
end)

create("name")
with("name",function(self)
  -- do something with node "name"
end)

create 方法可以在当前的位置创建一个子节点,可以给这个子节点起名,也可以匿名。

with 方法可以引用一个节点(如果给出名字,则找到具名节点,如果不给名字,则引用最近创建的一个匿名节点),并执行一个代码块(以 closure 方式给出),在这个代码块中可以引用这个节点对象 self ,操作 self 的各种属性和方法。但是 self 不可以传递到代码块之外。即不能被外面引用。这点在运行期通过锁机制保证。如果想长期引用一个节点,必须通过节点名。

除此之外,提供两个销毁节点的方法:

clear (name) 清除具名节点下的所有子节点。匿名节点不提供清理方法。

delete (name) 删除具名节点本身以及其下的子树,同样对匿名节点无效。

不提供任何枚举子节点和遍历子树的接口。(那些是 C 层次的事情)

为什么这样设计?仅仅这几个接口足够了吗?

这样,我们保证了动态语言层和 C 层关系的足够简单。尤其是规避了复杂的生命期管理。所有的节点都通过 create 构建,到 clear/delete 消亡。动态语言层有能力得到所有生命期信息。

而动态语言层没有移动子树和直接的持久引用特定树节点对象的能力,这向 C 层担保了绝对不会有悬空指针。具体到使用 lua 做封装时,我们简单的用 lightuserdata 引用 C 对象即可。

为什么提供 clear 和 delete 两种销毁节点的形式?这是因为我们没有枚举和遍历的接口,没有这两个接口,可以方便维持动态语言层上的对象粒度。

clear 用于插槽(slot) ,比如人物换装。模型的手上就可以有一个叫 hand (或 left_hand)的 slot ,供我们把武器的模型插上去。更换武器时,clear hand 这个 slot ,然后在其上重新创建新对象即可。

名字相对路径的支持,使得在特定位置创建子树可以做为通用模块。

delete 用于动态生成的对象本身。比如我们可以把场景中的 npc 挂在 root.npc 的子树下。再为每个 npc 以 id 为名创建节点。销毁 npc 即 delete root.npc.xxx (xxx 为 id)

匿名节点的设计,可以把大量复杂的子树构建过程交给动态语言去完成。

with 方法可以为上层程序员提供一个安全屏障。最主要是节点有效的保障。


上周末有同事问我,要不要增加移动子树的接口。比如有时我们需要把主角模型从一个地图层移到另一个地图层(比如从高楼上跳下)。我觉得这可能是个伪需求。

显示上的约束条件(模型依附在那个位置),和场景树的管理应该分离。比如不可以因为人物围着桌子跑,就把人的模型挂在桌子的坐标系内。

但另一些时候,我们需要让人物跨场景,则完全可以在旧场景中删除,然后在新场景中创建。在显示的表现上也可以做到不让用户察觉。

当然,也可能因为优化需要,或是实现简化的需要,我们需要增加这样一个方法。

move (name, parent)

把一个具名节点移动到另一个具名节点之下。

这最后一个方法或许是个可选项。


今天写了 400 多行 lua 代码,始终没什么感觉。看来周末就是应该休息一下。

最近想提高一点团队的工作效率,大家开会决定,以后每天最晚到岗时间提前到上午 10:30 。对我还是有点痛苦的 :) 我这几年,一直都习惯于中午再起床了。不过坚持了一周,感觉还行。也自然而然的把自己的下班时间提前到了 1:00 左右,睡眠似乎没受太大影响。

另,为近期的工作安排花了日程图,大大的挂在墙上。好象花点时间搞点形式主义出来,还真有点效果。 :D

May 09, 2009

在文本模式下显示中文

办公室里我有两台桌面机,一台装的 Windows ,另一台装的 freeBSD 和 Ubuntu 双系统。上班的时候,两台机器我都开着,跑 freeBSD 的时候比较多。

在 freeBSD 下,我很少进 X 。主要是写服务器程序,或者是用来 ssh 到别的服务器上做管理。纯文本模式很清爽,速度很快,让人心情愉快。

唯一的烦恼是,有时候屏幕上有那么几个汉字显示不出来。有时是代码里的中文注释(所以我本人虽然英文极滥,也坚持用英文写注释),有时是别的机器上的一些文件名。

以前有同学向我推荐 zhcon ,类似以前 dos 下的中文系统。可这个玩意性能极低。用它我还不如直接用 X 呢。

周末,我花了两个小时写了个小程序,算是自己的解决方案。

我们知道,VGA 的文本模式,是可以自己换字模的。用 vidcontrol -f 即可。

文本模式可以显示 256 个不同字符,一般用不了那么多。比如 freeBSD 的 syscons 就用了 4 个字符去画鼠标光标。原理就是动态修改字模。有兴趣的同学可以参考 /usr/src/sys/dev/syscons/scvgarndr.c

最简单的办法是用 [128,255] 的 128 个字符临时显示汉字,可以支持 64 个不同的汉字。考虑到鼠标光标占用了 4 个位置。其实是 62 个汉字。

一般也够用了。

我写了几行小程序干这件事情,支持管道操作。从标准输入读入 UTF-8 文本,发现是非 ASCII 集合中的,就临时生成对应的点阵字模(通过 freetype ),把这些字符映射到 [128,255] 之间,输出到标准输出。

以上基本满足我自己的需要。


如果有精力,我希望可以嵌入 syscons 中。比如按下 Scroll Lock 滚屏时,同时检查屏幕上是否有中文,有则做对应转换。在 Scroll Lock 模式下,不必考虑跟 Ascii 冲突的问题,可用的字符是全部 256 个。如果还不够用,可以定时切换字模,并不暂时不可显示的字符做特殊处理(标记为 ? )

再牛 X 一点,可以嵌入一个中文输入法。

或者还有第 2 方案,就是改造 less 。让 less 支持在控制台下显示汉字,如果汉字一次显示不完,暂停就是了。


ps. 莫向我索要代码。只是想应付自己的需要,写的太乱,各种路径也是写死的,不好意思拿出来丢人。需要自己写的,关键技术(更换字模)除了参考 /usr/src/sys/dev/syscons/scvgarndr.c 外,我还参考了: /usr/src/usr.sbin/vidcontrol/vidcontrol.c 。不过几十行程序而已,自己动手,丰衣足食。还是开源系统好啊。:D

另外,如果有同学知道世界上已经存在了上面我说的东西(比如按下 Scroll Lock 就把屏幕上的汉字显示出来),请告之。:D 若是有同学想写一个,我们可以私下交流一下。

May 06, 2009

回顾 Forth

第一件事就是没有钩子。不要留一个接口,想着未来的什么时候当问题变化时插入一些代码,因为问题会以你不能预见的方式变化。反正这个成本肯定是浪费了。不要预测,只解决你眼前的问题。by Charles Moore (Forth 之父)

今天也是机缘巧合,莫名其妙的翻出老资料温习 Forth 了。我想是个心结吧。19 年前,我痴迷于 Forth ,只看到了皮毛;13 年前,我进入大学的第一年,在校图书馆借出的第一本书,就是《Forth 语言》,读书笔记写了 20 多页。

只到今天,我才有机会,有能力,去仔细探究 Forth 的深层思想。当然,由于时间有限,几个小时的阅读,也只算是初窥门径。原本是想研究下 Forth 的系统实现,对同事正在设计的 3d 粒子系统,提供一些建议的。

碰巧又读到 Charles Moore 在 99 年的访谈稿 1x Forth ,颇多感慨。题头那段话,我在一周前刚好苦口婆心的对一同事说过,只差几个字而已。


最近很忙,既然晚上不能睡的再晚了,只好早上早点起。现在改为 10:20 起床了,比过往的 12:20 足足提早了 2 小时。感觉每天可用的时间的确长了许多。

晚上回家的时候,小巷子里总有两条狗。见我走过来便会汪汪狂吠,然后冲过来。头几次我心里还有点点害怕。次数多了也就习惯了。通常它们会冲到我跟前一米左右缓下来,跟着我一直走到家门口。跟它们打招呼也不大搭理,也就是用眼神盯着。

我想起同事养的一只贵宾。我每天都煮好两鸡蛋带到公司,饿的时候吃掉。上次体检 B 超的时候医生说我胆固醇太高,我便尽量不吃蛋黄了。若是那条狗在公司,我只要一敲鸡蛋,它就飞奔到我的座位前坐下,摇尾乞怜。已经不只听一个养狗的人说,鸡蛋黄对狗有莫大的吸引力了。

这两天,我吃完鸡蛋,都把蛋黄带着。夜路上再碰见那两条狗儿,就抛给它们。

这个时候,我居然会想起奥贝斯坦。

May 05, 2009

今天遭遇太好笑的房东

前段工作太忙,有天中午停水,我开了水龙头见没水忘记关,结果水淹了洗手间。地漏不畅,所以漏水到了楼下。

晚上晚饭时就接到楼下邻居愤怒的电话,急忙从公司奔回家看。看人家家里到处是水,心有不忍。也是想把事情早点解决掉,最后当晚提了一万元作为赔偿。

老实说,按实际损失(楼下家里并没有怎么装修),我心里价位也就是 3000 块最多了。只是我自己犯了错误,感觉对不起邻居,说赔多少就爽快的答应了。大家还是合合气气做邻居。这段时间进进出出,还笑着打打招呼。

没想到这房东不乐意了。觉得我工资卡上的钱是天上掉下来的,说拿就拿出来。成天想着让我也给她一点。理由是地板被泡坏了。老天,水是从洗水间直接漏下去的,顺着楼下那家的天花板滴的满屋子。

我们家当天,客厅地板一点毛病都看不出来。这么多天下来,地板也丝毫没有异样。

我这人就这毛病,是我的责任,我绝对不推卸,无中生有的事情让我去承担,那就没那么容易。

今天房东晚上到我家里静坐来了。相当郁闷。

我坐那听她叽叽喳喳,感觉这人还真不可理喻。尽说些自相矛盾的话,一开始我是心里发笑,最终还是把笑容写在脸上了。只是不好说破。

末了,还被她甩上一句,今天你肯定恨死我了。我这一走,你把我们家冰箱啊什么的弄坏掉,然后不租房子了走人,我可就亏大了。赔偿的事情就算先不说,今天先加一万押金,防止我做坏事。让我还真是哭笑不得。

什么叫自相矛盾?

先说,楼下那点损失算什么?其实干了啥都没有,根本不用赔什么钱。 然后说,你看楼下都那样了,我家这地板能好么?最少赔 4,5 万呐。

然后我们谈是否续租的问题:(我是 6 月到期,并且有 5000 押金在她那)

先说,你这不租了,我损失多大啊。再找房客要时间,而且房子旧了,租金还要便宜。(一定要继续住,而且房租还得加) 然后说,我这房子不愁租的,我打听过了,换个房客,房租一年至少可以多一万。(您租不租无所谓的,不求您)

那么续约呢?

她说,“那不能一年年签了。你住过的别人来住不就要压我价钱了。至少签三年。”

我晕…… “哦,三年啊,我都三十多了,说不准得在您的房子里结婚了”

“啊?对啊。那可不行! 嗯,不过呢,现在有本事的人都四十才结婚的。”

谈到房租的问题,

先说,合同上应该多写点,我很有钱,也不在乎钱,不过房子租金高也有面子。

我说,我这人遵纪守法。你不愿意纳个人所得税就算了,我租你的房子合同上多少钱,我可都去地税局自掏腰包帮你把税交了的。然后我逗她说,你说不缺钱,那么你少收我几个房租,我们把合同金额写高点。反正我还是掏这么多钱,无非少给点您,多给点国家。然后这房东利马不干了,急忙回到:那还是多点钱好,钱总是好用的。

谈到税的问题了:我一本正经的说,这我可得给您上上课,纳税是我们公民的义务。她一听连连说是。 接下来说,但是还是不交的好,你这一交了,在地税备了案。下面的房客不肯交了,查下来,我多大的损失啊。

最后,我实在受不了跟一个很有素质,但就是无法用我的逻辑体系去沟通的有钱人沟通。说,要么把,我们去打民事官司吧。当然了,这挺麻烦,不过我会花大价钱请个大律师朋友全权帮我处理这事。这样至少我个人不麻烦了。不就是花点钱么,您也不在乎钱,法律是公正的。

她一听就不愿意了,说,好吧,那我今天就不走了。你今天晚上搬走,算我违约(租房合同)法院说啥那就是啥了。


好吧,我承认很心里真的在笑她了。也为自己纠缠在这点小事上耽误时间不值。

虽然我已经打算她要什么就给什么了,但还是忍不住逗逗。给了个意见:

不如我们把地板都拆下来看看,请第三方机构严格鉴定。如果有一切损害,我双倍赔偿(其实我认定这房东的地板一点损失都没有);不过呢,如果鉴定结果说没问题呢,请您赔偿我一点点精神损失费。

我觉得这中年妇女都快跳起来了,说,那怎么行。就算鉴定,损伤了赔双倍没问题,但是即使没问题,这拆下来了再还原,我这也蒙受损失了,也得赔。(寒,感情我证明自己没错了,也得赔偿您呐)好吧,说了几句,她还是没忘记补上一句,其实我不在乎钱的,我很好说话的。


还有好多好笑的,不写了。最后我认栽。最后按她的意思,赔偿一万,并续租一年(五万租金)。

写字条的时候,把情况写明,说这事就算了解了。她犹豫着不想签字,说,这样写不好吧。说不再追究地板的事情,你要明年把我地板(故意)刮花了,我怎么办啊。我的地板很贵的…… 真的很无语。

好不容易把她老人家送出门。没过两分钟就上来敲门:明天你会把钱打到我帐上的吧?我可都签字了的。只好提醒她,似乎你收我的钱都不开收条的哦。


现在的许多人素质的确是高多了。不像上次楼下那家,差不多快冲上来纠住我说,你丫的要不赔钱,我找黑社会的人废了你(原话是:我认识很多人的,一个电话能叫 30 个来)。好吧,上次我没笑出来,这次我真的笑了。

May 03, 2009

树型打印一个 table

php 中有个 print_r 函数,可以递归打印一张表。很多 php 程序员喜欢用这个去调试程序。

我想,所有写过一定代码量的 lua 程序员都会写一个类似的东西放着备用吧。这两天调试 lua 程序的时候,发现以前做的简陋的 print_r 不够好用。对于复杂的 table 打印出来一大篇很不直观。结果就放下手头的工作,花了整整一个小时,写了下面几十行代码。把 table 输出成树结构。

比如:

a = {}

a.a = { 
    hello = { 
        alpha = 1 ,
        beta = 2,
    },
    world =  {
        foo = "ooxx",
        bar = "haha",
        root = a,
    },
}
a.b = { 
    test = a.a 
}
a.c = a.a.hello

print_r(a)

可以输出成:

+a+hello+alpha [1]
| |     +beta [2]
| +world+root {.}
|       +bar [haha]
|       +foo [ooxx]
+c {.a.hello}
+b+test {.a}

代码参考这里:

树型打印一个 table

其实实现的细节需要注意的就两个地方:一个是考虑循环引用的问题。(一般用 table 模拟树结构都会记录一个 parent 节点的引用,这样就造成了循环引用)

一个是表格线的处理,对最后一个子节点需要特殊处理。

这段代码的输出风格不算美观,至少不如那些显示文件目录结构的命令行工具。不过我觉得是够用就成,另外需要尽量紧凑,不浪费空间。需要更美观的同学,其实也可以很容易的对其改进。

May 01, 2009

在 lua 中实现函数的重载

警告:记录以下内容纯粹自娱,请勿轻易用于项目。我个人也不赞同随意使用语法糖去改造语言。

我们知道 C++ 里有函数重载的特性,程序员可以为一个看起来同名的函数做多份实现,让编译器通过调用时的参数类型去指定链接器链接最为匹配的一份实现。对于死忠的 C++ 程序员,这绝对是最必不可少的利器。如果没有它,那些 template 绝对玩不出现在这么多花来,当然也就没那么多机会拿着“充满智慧” 花哨的 template 代码来 YY 自己的智商了。

哦,写 lua 的所谓脚本程序员不要沮丧,其实 lua 中可玩的花样也很多。一样可以写出让同行瞠目结舌的代码来。比如这个函数重载的问题,虽然 lua 不可能做所谓编译期运算(动态生成代码或许勉强算一个),也没有什么静态链接过程。

但 lua 是个有趣的语言,下面看我怎么模拟出一个类似的东西来。

我们的目标大约是这样的:

    define.test {
        "number",
        function(n)
            print("number",n)
        end
    }

    define.test {
        "string",
        "number",
        function(s,n)
            print("string number",s,n)
        end
    }

    define.test {
        "number",
        "...",
        function(n,...)
            print("number ...",n,...)
        end
    }

    define.test {
        "...",
        function(...)
            print("default",...)
        end
    }

然后调用 test 的时候,可以通过调用参数,分发到不同的函数实现上去。当然,需要找到最接近的匹配。


test(1)
test("hello",2)
test("hello","world")
test(1,"hello")

将输出

number  1
string number   hello   2
default hello   world
number ...      1       hello

这件事情其实很容易做,只需要额外为每个需要用多态函数的环境记录一张表。里面放上同名函数的分发器。而分发器按事先注册的参数表去检查匹配参数,找到最合适的对应函数定义。

如果得不到任何匹配就抛出异常,这样也可以在需要强类型检查时增强一些安全性。

不过这些事情当然会有性能上的开销,也就是代价吧。既然是玩具代码,我也没太优化,纯粹是过节自娱。

大家节日快乐。

附上代码: LuaFunctionOverload

ps. 如果在定义函数的地方,定义参数默认值也很容易,这里就不给出代码了。