04 2008 档案
寻路算法：模仿Tower Defense Flash做了一个小游戏
摘要: 第一次用C#写游戏。在C#上写算法果然是一个挑战，时间复杂度太大的话造成的后果比C++明显好多，于是总是尽量把东西做成O(n)或者O(nlogn)。这次就在上面实现了一个寻路算法。
这个寻路算法是这样的：在16×16的方格上有一些终点，东西在格子上只能上下左右行动。每一个格子需要记录到其中一个终点的最近的路的第一个方向（就像三层循环的寻路算法一样，最后给出矩阵的那个）。
阅读全文
posted @
2008-04-30 05:29 陈梓瀚(vczh) 阅读(4526) |
评论 (5) 编辑
今天发现自己的array类太慢
摘要: Lazy Compile使用Syngram动态创建语法分析器的代码实在是太慢了，debug竟然需要8秒钟来处理91条比较长的文法。于是我打开了Visual Studio 2008的Performance Wizard查看运行时消耗的资源，结果发现竟然都消耗在自己那个array类的operator[]里面了。那一段代码是用来检查文法的左递归引用关系是否出现环的。结果就把用到的四个array全部换成bool*了，当时只是为了创建二维数组方便使用了array类。
过后，debug的时间立刻降为2秒钟不到，于是我又打开Performance Wizard看了一次，这次消耗的瓶颈终于转移到一个合理的地方了。
结果：array竟然比指针慢了无穷多倍，得找个时候重新写一次。不过这段代码好象是去年写的，也没经过什么性能测试，也难怪发现不了问题。在此帖上代码，等Lazy Script写完了重新审查一下自己的那套模板库（NTL，Non-standard Template Library，娃哈哈）。
阅读全文
posted @
2008-04-27 19:53 陈梓瀚(vczh) 阅读(2665) |
评论 (6) 编辑
关于类型推导的设想
摘要: 这几天一直在忙学校的比赛，到了今天终于有空了。
Lazy Script的语法实在是很复杂，因此不得不在进行第一步的名字检查之后把原本的语言转换为内部使用的一种元语言。这种元语言设计的原则是尽量简单。譬如列表构造和do-end语句就需要被转换掉。进行了转换以后，就需要对元语言进行一个类型方程组的建立。这一步暂时还没有建模好，而且实际工作需不需要真的构造出一组方程组还不知道。目前还比较没有头绪的就是如何对模板函数的类型方程建模。
举个例子，譬如我们对上一篇文章中提到的代码进行类型方程组的构造：
阅读全文
posted @
2008-04-27 10:16 陈梓瀚(vczh) 阅读(2182) |
评论 (0) 编辑
Vczh Lazy Script 语法分析器完成
摘要: 花了两天的时间终于完成了Vczh Lazy Script的语法分析工作。语法分析是编译的第一步，旨在把输入的字符串（代码）分析称跟代码结构一致的语法树，以便后续工作。
藉着去年开发的Syngram工具包，这两天过得还算轻松，仅仅对语言做了一份配置，不过这份配置也花掉了1200多行代码。语法分析其余的部分是数据结构。目前的数据结构仅仅用于再现语言的结构，而没有附加任何的数据。接下来的工作是检查所有的identifier，看看有没有哪些identifier是使用错误的。一般来说都是在左值使用函数、类构造标签参数不全、转移运算符指向的函数并没有声明成函数等等比较基本的东西。但是后续的工作就相当地麻烦了。
作为一门lazy+pure的函数范式程序语言，我模仿了Haskell的大部分语法，加上自己的一点点修改（因为Haskell的语法实在是太诡异了），但是主要功能是没有变化的。等上面所说的identifier完成以后，我就要开始写Lazy的类型推导程序了。类型推导程序用于计算出代码中省略的类型声明，相当于把整份代码转换成类型方程然后求解
阅读全文
posted @
2008-04-22 04:03 陈梓瀚(vczh) 阅读(2636) |
评论 (4) 编辑
如何实现语言中的闭包（Closure）
摘要: 已经忘了是去年还是前年听到微软说要在C# 3.0里为C#添加lambda表达式，与此同时Java的团队也一直在说想为Java添加lambda表达式。到了今天，C#似乎已经把这个特性加进去了，Java还没有。Java说这个特性还在计划列表之中，不过暂时可以使用匿名类来代替。想必是因为在Java中表示函数指针的方法比较奇怪罢……
其实无论是lambda表达式（事实上应该叫匿名函数）或是匿名类，都能归属到一种叫闭包的东西上面。闭包原来是代数中的用语，只是那些研究理论的老大们觉得这玩意儿也能拉到“闭包”里面去，于是就叫闭包了。匿名函数原本是丘奇发明的一个lambda-calculus的其中一部分，后来计算机的老大们突然发现lambda-calculus非常适合用来充当程序设计语言的模型，于是就对它进行了非常多的扩充，还弄了个什么类型理论出来。好像扯远了。
想象一下如下使用闭包的代码：
MyClosure=func(Number1)
{
return func(Numbe
阅读全文
posted @
2008-04-20 21:55 陈梓瀚(vczh) 阅读(7764) |
评论 (5) 编辑
Vczh Lazy Script 上下文无关文法
摘要: ExpCmList -> Expression ["," ExpList]
ArrCmList -> [LeftValue "<-"] Expression ["," ArrList]
CaseList -> LeftValue ":" Expression ";" [CaseList]
DoList -> ([LeftValue "="]Expression | LeftValue "::" TypeDes ) ";" [DoList]
WhereList -> (FuncHead | FuncBody) ";" [WhereList]
Exp0 ->
Exp0 -> FuncName
Exp0 -> "(" [ExpCmList] ")"
Exp0 -> "[" [ExpCmList] "]"
Exp0 -> "[" Expression "|" ArrCmList "]"
Exp0 阅读全文
posted @
2008-04-20 20:50 陈梓瀚(vczh) 阅读(1909) |
评论 (3) 编辑