云风的 BLOG: 在脚本语言中一个取巧实现 OO 的方法

今天，脚本编译器连同前段写的虚拟机全部完工了，很有成就感。
跟 lua 一样，复杂的数据类型我只支持了 table ，这个 table 即可以做 array 也可以做 hash_map 用。一般用 lua 的人都会用 table 去模拟 class 。lua 只对这个做了非常有限的扩展：在 lua 的文档中，我们可以看到

function t.a.b.c:f (...) ... end 可以等同于 t.a.b.c.f = function (self, ...) ... end

就我用 lua 的经验，这个转换用途不是特别大，只是少写个 self 而已。

这次我自己设计脚本语言，针对脚本支持 OO 的问题，特别做了些改进。

看一段脚本，这是用我自己定义的语言写的：
A={};
function A.sum (_self)
{
return .a + .b;
}

function A.print (_self)
{
print(->sum());
return _self;
}

a={A,
.a=100,
.b=200,
};

a->print();

这是一个非常简单的例子。全局函数 print 是我测试程序注册的。我是这样想的，把成员函数放到一张 table 里。这里是 A.sum 和 A.print 两个，放进了 A 这个 table。然后我创建了对象 a={A,.a=100,.b=200};
这里默认 a[0] 放的是 vtbl，就是 table 初始化队列的第一项。如果用 -> 来调用函数的话，比如 a->sum() 就在编译时转化成 a[0]->sum(a)

在函数里，如果用 . 开头的变量，就自动展开成 _self.x 。这个 _self 是函数的第一个参数。需要在函数定义中明确写出来，但是名字可以随便。不过名字必须用 _ 开头。同理 ->sum() 就展开成 _self->sum()
所以，在一个成员函数中，我们可以看到所有以 . 开头的变量操作都可以看成是成员变量。以 -> 开头的函数调用，可以看成是成员函数调用。当然，这里所有成员函数都和 C++ 中虚函数的概念相同。如果需要给 A 类写个静态函数，即不需要传 self 的话，可以用 A.static_func() 这样调用了。

我在这里用名字来强制约定变量的类型。_ 开头的全部是局部变量，否则就是全局。这样可以方便很多编译的工作，也让代码比较容易读，在弱类型检查的脚本里，还可以避免一些笔失误。

Comments

云风大哥，有空来我blog看看，我blog写的大都是些Web/脚本/RIA这些。我的blog到目前为止快2万字了居然只有一个评论，我感到很郁闷，什么时候能有你这么多人来看啊。

Posted by: Atry | (13) January 27, 2006 04:35 AM

对.NET的字符串处理方式很是喜欢，简单的字符串拼接用String.Format，复杂的就用StringBuilder，String本身是不可以修改的

Posted by: Atry | (12) December 6, 2005 05:38 PM

顺便说说OO的实现，我是比较欣赏javascript的原型继承， http://community.csdn.net/Expert/topic/4395/4395601.xml?temp=.6752283 你看这个现象，这说明什么呢，javascript的每个对象都有一个原型，访问对象的成员的时候，如果找不到，就在原型对象里面去找，原型对象里面再找不到这个成员，就到原型的原型里面去找。 delete操作只能删除在这个对象本身里面的成员。这种办法实现OO就用不着每个对象一个vtbl了。只需要每个对象一个加一个指向原型的指针就OK了。这种做法实现继承也很容易。 javascript有两个问题没有解决，第一个问题是继承，现在一般的用法是用new一个基类对象作为派生类的原型，这是很粗糙的做法，构造函数的问题并没有解决。往往就不得不在构造函数中什么也不做，另外手动调用一个初始化函数。另一个问题就是所有函数都是虚函数，派生类如果不小心重写了基类的函数就不好意思了。对于成员函数的调用，你用的办法： “a->sum() 就在编译时转化成 a[0]->sum(a)”，把原型，或者说vtbl局限在[0]里面不妥，对于数组，这会和数组元素冲突。应该在对象中增加一个物理位置，我的意思是C语言定义里面就要给他留这个原型的地方。而且这个原型不应只用于函数，还应包括存取过程。因为，在原型中继承变量是非常丑陋的，假如对变量进行修改，我们知道原型是所有同类型对象共有的，假如进行了修改就不堪设想。而调用函数的时候光有这个转换是不够的。是不是应该增加一个语法，不以虚函数来调用函数，而是调用当前函数所在的原型的该函数，例如，你写的函数是调用虚函数（我用prototype(_self)来代替你原文_self[0]一边区分这和0这个索引的区别）： function A.b(_self) { print(->sum()); /*这个被展开为 for(local _class = _self;_class; _class = prototype(_class)) { if(_class.sum) { _class.sum(_self); break; } } throw error("member \"sum\" not find"); */ return _self; } 另外一种调用比如用 => 运算符，就这样展开，也就是调用调用=>sum的b函数所在的类本身的sum函数： function A.b(_self) { print(=>sum()); /* 这个被展开为 A.sum(_self); */ return _self; } 如果prototype(_self)就等于A的话，那么这时候两种调用没有区别，但是如果_self并不是直接的A对象，而是从A派生的B的对象，那么->sum就会优先调用B.sum，找不到B.sum，才通过prototype(B)找到A，调用A.sum，而=>sum不管什么情况都调用A.sum

Posted by: Atry | (11) December 6, 2005 05:25 PM

lua 是否用 double 还是用 int 也是可以用宏开关控制的 :) 有个宏是 lua_Number 不知道记错没有

Posted by: Cloud | (10) December 6, 2005 04:32 PM

不好意思，是我搞错了。是我1年以前看Lua源码的时候的一个误解，搞混淆了，Lua函数调用堆栈是1024，我当时以为那个是hash表分配的空间大小。 static void newentry (lua_State *L, stringtable *tb, TString *ts, int h) { ts->nexthash = tb->hash[h]; /* chain new entry */ tb->hash[h] = ts; tb->nuse++; if (tb->nuse > (lint32)tb->size && tb->size size*2); } 刚才重新看了一下，hash表大小是成倍增长的。在Lua中数字都是double，即使是紧凑整数，也还要做转换才能索引。本来对你说的“完全不用 strcmp 的操作”感到难以理解，看了源代码之后才发现果然如此 int luaO_equalObj (const TObject *t1, const TObject *t2) { if (ttype(t1) != ttype(t2)) return 0; switch (ttype(t1)) { case LUA_TNUMBER: return nvalue(t1) == nvalue(t2); case LUA_TSTRING: case LUA_TUSERDATA: return tsvalue(t1) == tsvalue(t2); case LUA_TTABLE: return hvalue(t1) == hvalue(t2); case LUA_TFUNCTION: return clvalue(t1) == clvalue(t2); default: LUA_ASSERT(ttype(t1) == LUA_TNIL, "invalid type"); return 1; /* LUA_TNIL */ } } 的确这里没有strcmp，但是请看：TString *luaS_newlstr (lua_State *L, const char *str, size_t l) { unsigned long h = hash_s(str, l); int h1 = h & (L->strt.size-1); TString *ts; for (ts = L->strt.hash[h1]; ts; ts = ts->nexthash) { if (ts->len == l && (memcmp(str, ts->str, l) == 0)) return ts; } /* not found */ ts = (TString *)luaM_malloc(L, sizestring(l)); ts->marked = 0; ts->nexthash = NULL; ts->len = l; ts->u.s.hash = h; ts->u.s.constindex = 0; memcpy(ts->str, str, l); ts->str[l] = 0; /* ending 0 */ L->nblocks += sizestring(l); newentry(L, &L->strt, ts, h1); /* insert it on table */ return ts; } 每次建立字符串的时候，为了保证内存中相同内容的字符串只有一份，这就有这个memcmp的开销在里面了。虽然他的字符串指定了大小，所以用memcmp比strcmp快，但是这个字符串还是得要经过比较的。 -------------------------- 又看了点代码，发现像一般a.b这样的调用，"b"这个字符串memcmp的开销在编译时！！有一个全局的stringtable里面放了所有的字符串，在编译的时候，就会把所有用引号直接定义的字符串添加到里面。除非是a["b".."c"]这样才会产生运行时memcmp的开销，的确厉害。现在真的感到Lua真的很厉害，我现在觉得他这样的做法，可以让动态类型，动态hash表的效率接近静态类型。至于把每个编译时把每个字符串用一个id来做散列，我想，和用指针相比，最大的好处就是字符串id都是紧凑连续的，能减少冲突。

Posted by: Atry | (9) December 6, 2005 04:28 PM

lua 的源码我看过了. 标准的闭散列hash map 算法，没有那么流氓的啦. 不需要 hash 的时候也不会创建 hash table 用紧凑数字做 key 的 hash map 的效率等同于 array . 这点如果不想读 lua source code 的话，可以看我前段写的那篇相关文章。

Posted by: Cloud | (8) December 6, 2005 12:54 PM

并不是每一个对象都需要map，绝大部分对象都不需要，应该是只在需要用到map的地方用map。能够在编译前推算出变量名的地方统统放到固定的数组里。 Lua里面很牛氓的一点就是任何一个表初始就分配一个1024*4的hash表，完全是浪费内存，正确的做法是只有需要用容器的对象才分配hash表给他

Posted by: Atry | (7) December 6, 2005 09:32 AM

脚本中不能用固定数组来解决 map 。因为语言的动态的，取一个 key 不光是编译时的操作，还是运行时的操作。否则就没有脚本的优势了。现在流行的 hash 表都是用数组来实现，做闭散列。而不是用链表做开散列。在用紧凑数字做 key 的时候，hash 表的效率和数组等同。

Posted by: Cloud | (6) December 5, 2005 08:21 PM

不论是用字符串还是指针还是数字来做key的hash表，和一个固定数组相比，效率还是有不小的差距的，而且hash表要处理冲突，另外还有内存的浪费

Posted by: Atry | (5) December 5, 2005 06:18 PM

lua 里 string 做 key 和 int 一样的高效。这点我前面写的东西已经提过。lua 是用指针做 key 的，可以完全不用 strcmp 的操作而我的语言，所有的 key 在编译时都会变成唯一id, 而不存放 string

Posted by: Cloud | (4) December 5, 2005 05:00 PM

其实如果要高效的话，可以不用hash表来做类，用字符串来做为查找的索引这是没有必要的，字符串的散列也有开销。变量名可以在编译时确定，根本不必作为一个字符串放到运行时，只应该在做容器的时候才用hash表和数组。对于弱类型的解释语言，每一个变量都是一样大小的基类指针，然后再在其中找到类型信息，完全可以在编译的时候记录下每个对象使用过的成员，然后放到成员数组里。这样的代码，我是按类似javascript的语法写的： function A() { var object = {a:"xxxx",b:1,c:2,d:null}; object.a = 3; object.b = "hello"; object.x = "world"; object["c"] = 4; object["d"] = 4; object["e"] = 4; } 编译器把他解释成这样： function A() { var object = {0 /*a*/ : "xxxx", 1 /*b*/ : 1, 2 /*c*/ : 2, 3 /*d*/ : null, 4 /*x*/ : null, members: {a:0,b:1,c:2,d:3,x:4} }; object[0] = 3; object[1] = "hello"; object[4] = "world"; object[object.member["c"]] = 4; object[object.member["d"]] = 4; object[object.member["e"]] = 4; //因为object.member["e"]是找不到的，所以这里出错 } 这种实现方式和hash表直接索引相比，效率会更高，前例中object并不是一个hash表，而只是一个编译时就已知大小的数组，而且对于使用语言的程序员来说，仍然不必定义成员变量才使用，而是编译器自动做了这个工作。类型中另外放一个hash表以便兼容用字符串来索引已经使用过的变量。当然，如果不定义变量直接用字符串来索引，还是会出错，正如上面的object["e"]

Posted by: Anonymous | (3) December 5, 2005 03:57 PM

去风前辈你好：我的机子是C2.0,256M,MX400的，我用DX9.0编程生成了一个随机的地形图，并让其绕Y轴旋转，用的是索引的方法生成的，有光源，900个正方形时还可以，可当我增加到1600个时，旋转就有点卡了;下面我的生成代码：我想一个游戏生成的三角形应该远多于3200个，请告诉我是怎么回事，谢了！！！！

Posted by: starimpact | (2) December 5, 2005 02:02 PM

有趣！受教了！你的书现在很火，昨天去南京的书店逛，顺便帮你调查了一下，有很多人买，书店基本都没货了。我不做游戏，下次你写技术专题的书我再买.什么时候回家在红钢城的新华书店签售，估计是很有意思的事，呵呵！

Posted by: dawndu | (1) December 5, 2005 12:44 PM

云风的 BLOG

思绪来得快去得也快，偶尔会在这里停留

在脚本语言中一个取巧实现 OO 的方法

Comments

Post a comment