Semantic Web Notes

说说C语言和内存对齐

我看东西，看得快，忘得也奇快。大概2星期重新研究过内存对齐，现在都快忘光了，于是赶紧再回忆一下。

所谓内存对齐，即使得数据所在内存地址的起点应尽量对齐(是某个值的公倍数)，而不是凌乱不堪的。一般我们把8个bit看成1一个byte，用byte来做存储的单位，其实也是一种内存对齐的机制——这样处理器访问数据只需要访问8的倍数即可。

内存对齐的目的很简单，这样有利于提供访问的速度（特别是在栈中）。对于对齐的内存地址，处理器访问一次即可得到，而未对齐的地址，可能需要访问两次才行。

那内存对齐的最小单位是什么呢？其实不同平台上不同的编译器都有自己的决定(猜的)，编译器的这个决定叫做默认对齐系数。我们在自己编写程序的时候很少会去注意到这个对齐问题，这个很正常，因为这机制本身就应该是对程序员透明的。但是，我们还是能够在程序中觉察到对齐机制的存在。如果程序员没有正确意识到对齐机制的存在，有的时候它甚至会让程序的行为不正确。我举个小小的例子来说明下。
假设有这样一个结构体

typedef struct ex{
	int c1;
	char c2;
        int c3;
}ve;  /*  1  */

我的运行环境是gcc4.0+, ubuntu8.04, 32位单核cpu，sizeof(char)是1，sizeof(int)是4，猜猜sizeof(ve)的值会是多少？如果程序员不清楚内存对齐的概念的话会认为这个值是6，但其实是12。在这里面，有4个成员需要对齐，c1,c2,c3,ve，c1,c2,c3跟ve的对齐规则并不一致。

c1,c2,c3的对齐过程如下（对齐系数是4的前提下）：假设第一个成员放在offset为0的位置，那么c1所占的内存就是[0~3]，而c2所占的内存是[4]，c3所占的内存不是[5~8]，而是[8~12]，但如果c3是char类型的话，c3所占的内存就是[5]。

所以结构体内成员的对齐规则如下：假设第一个成员的offset是0，则之后成员的对齐系数是系统的对齐系数（可以通过pragma pack(x)来指定）和自身长度两者间较小的值。比如，系统的对齐系数是4，而char的长度是1，那么char就按1对齐。而int的长度是4，于系统对齐系数一致，则按4对齐。

从上面这个规则，我们可以看到一个有趣的问题，在结构体内，成员的摆放顺序不同，结构体所占空间是不同的。比如，

typedef struct ex{
	char c1;
	char c2;
        int c3;
}ve; /*  2  */

与

typedef struct ex{
	char c1;
	int c3;
        char c2;
}ve; /*  3  */

，前者所占的空间是8，而后者所占空间是12。但是对于程序的逻辑而言，两者的定义是完全一致的。了解对齐规则是有好处的，至少我们写出来的结构体空间占用更小些。

说完了c1,c2,c3的对齐，下面说ve的对齐。sizeof(ve)的值事实上并不是如我们分析的c1,c2,c3对齐完之后所占空间的累加，它自身也是需要对齐的。结构体的对齐规则如下：取其成员中占用空间最长的值，我们的例子中是int类型，值是4，然后跟系统的对齐系数比较，取较小值为ve的对齐系数。如果我们在结构体2中，语句int c3;后面再加一句char temp;我们可以算出成员所占的空间是9，而ve所占的空间是12。

Posted in C/C++ | 4 Comments »

IDE的意义

这两天在看一本书：Managing Projects with GNU Make。我每次看书，都会产生一些跟书的内容本身并不非常相关的想法。我看这本书的目的是要为easyC-API建立一个好用的makefile文件，另外也是对其有些好奇。

待到书看了一半，我就想到了IDE，Eclipse CDT, DEV C++等帮助我们创建管理项目的工具。我觉得那才是一个程序员应该去用的工具，而不是去手工一个makefile文件。因为看着这些makefile的编写规则，我觉得让它的自动生成是完全可以做到的，既然可以利用工具完全可以做到，普通的程序员就完全不需要去了解这里面的机制，就像我们不了解Java的Byte Code，也不了解JVM生存Byte Code的规则，但是我们依然能写出漂亮的Java应用。用人手工去写makefile文件是存在许多弊端的:

1. 需要非常精通makefile的规则，也就是需要额外的学习；
2. 非常容易出错，对于大型的项目而言，几乎难以避免；
3. 程序员之间沟通不方便，makefile文件虽然是比较直观的，但是不同的人编写风格存在着较大的差异，不如用工具生成的容易理解——如果采用工具生成，甚至你都不必去理解它；

我要说的是，手工编写makefile很酷，但是只能自己玩，不要强迫别人跟你一起玩。以上结论，对Ant同样适用。

Posted in Techs, Think Free | 2 Comments »

降低选择的数量

如果我们要设计一个系统（或者框架，或者程序设计语言），我们是让它对实现一个功能有一种解决方案好，还是有20种解决方案好（对系统的使用者而言）？这个问题似乎很容易回答，显然是有20种方案更好些。20种不同的方案显然都有着不同的优缺点，可以使得方案的效果更加的可控，挑选的余地更大。一般情况下是是这样的，不过我最近看书的时候常常想一个问题：假使从20个方案挑选一个需要的难度和花费，比直接使用第一种方案要高很多，那么有着更多的解决办法还是一件好事么？

我的观点是否定的。我从程序设计语言的角度来举个例子。假如有一天我设计了一种新的程序设计语言，名字叫SuperPERL（我不是要讽刺Perl），其最大的特点就是自由。实现每个功能都可以有无数的写法，使得不同背景的程序员都能够轻松过渡到SuperPERL。比如，打开文件这样的操作，有如下几种写法：

//方法1：
File file=new file("path");
InputStream is=new FileInputStream(file);
Scanner s=new Scanner(is);
 
//方法2：%%表示调用shell命令
StringBuffer fb=new StringBuffer();
StringBuffer.addContent("%%echo $myfile>$fb");
 
//方法3:
 
File *file=open_file("myfile")
//方法4:
.....

看着其实很不错，SuperPERL能把各种语言都能融会贯通，程序员能够随心所欲的写出正确的代码，一个C程序或者一个Java程序员，或者Basic程序员都能顺利的使用这种语言。但是如果我们面对的是一位初学者呢？他买了A书，然后学到SuperPERL打开文件是按方法1做的，买了B书，然后学到打开文件是按方法4作的，然后他的老师告诉他应该按方法2做，他同学，一位大牛告诉他SuprePERL中最具效率的打开文件的方法应该是第二种，其他方法都是土鳖做法……如果在学习SuperPERL中的每一个功能都要发生以上的故事，我想他肯定会放弃这种编程语言的。
其次是沟通的困难，一个C转过来的程序员，很快乐的编写着SuperPERL程序：用着自己熟悉的语法，写出非常时尚的代码。但是他同事可能以前是一位Pascal程序员，不难想象这两位用着同一种编程语言共同开发项目时会产生的困境——互相之间看不懂对方的代码。

功能不是越多越方便，选择不是越多越好，对于程序设计语言，对于各种应用框架而言，尤其如此。如果我是某个语言或者框架的设计师，我的设计准则肯定会有一条是：公开的概念（也就是使用者需要学习的概念）越少越好，拥有的选择越少越好。少的概念有利于初学者的学习，也有利于开发者之间的沟通。

想想Java世界无数需要理解与学习的概念吧，Java世界正朝着相反的方向前进。

Posted in Think Free, wordpress | No Comments »

easyC-API中关于动态数组(Vector)的实现与使用方法简介

动态数组在C语言中是比较常用的，实现起来也是很简单明了的，这篇文章我简单给出一个动态数组的实现(easyC-API中的实现与此基本一致，稍稍复杂些)。首先，定义动态数组如下：

typedef struct easyc_vector{
    int size;
    int base_size;
    int actual_size;
    eType *base;
    eType (*get)(int, const struct easyc_vector *);
    void (*set)(int,eType,const struct easyc_vector *);
    eType (*remove)(int,struct easyc_vector *);
    void (*sort)(int (*compare)(const void *,const void *),struct easyc_vector *s);
    void (*add)(eType,struct easyc_vector *);
}c_vector;

eType是数据类型，这里我们假设它是整型。
动态数组的初始化由函数make_vector负责，具体函数的实现我就不给出了。可以看出这个结构支持动态数组的创建，插入，查找，删除，添加，取长度，及排序等基本操作。这些操作对于数组而言，已经是相当够用了。

可能有朋友对它的排序如何实现感兴趣，这里排序是通过系统标准库中的qsort实现的。这是一个小技巧。可以看到排序函数的定义如下：

void (*sort)(int (*compare)(const void *,const void *),struct easyc_vector *s);

，需要的参数是一个用户实现的比较大小的函数，及一个指向动态数组的指针。我们来看看它是如何把排序的工作委托给qsort的，以下是这个函数的实现：

void easyc_vector_sort(int(*compare)(const void *a ,const void *b),c_vector *s){
	qsort(s->base,s->size,sizeof(eType),compare);
	return;
}

感谢函数指针，使得我们能把功能的委托变的更加容易与自然。

以下的代码是对这个动态数组简单的使用，可以看到，使用起来还是蛮自然的。

#include
#include"easyc_ds.h"
int cmp(const void*a,const void *b){
	return *(eType *)a-*(eType *)b;
}
int main(){
	c_vector s;
	s=make_vector(1);
	s.add(1,&s);
	s.add(5,&s);
	s.add(3,&s);
	s.sort(cmp,&s);
	printf("%d\n",s.get(0,&s));
	printf("%d\n",s.get(1,&s));
	printf("%d\n",s.get(2,&s));
	return 0;
}

easyc_ds.h定义了所有数据结构的结构，声明了所有的方法。当然您在编译以上测试代码的时候还需要使用我们的静态库(libeasyc_ds.a)。

如果您对我们的代码有兴趣，可以去easyC-API的主页上获取最新的源代码，二进制库文件，测试代码及makefile文件。如果您使用的是windows系统，我们编译好的二进制文件会不兼容，请您在自己编译器上重新编译，至于源代码，它是跨平台的。

Posted in C/C++ | No Comments »

Google浏览器Chrome即将发布

虽然不是google Fans，不过作为google服务的重度依赖者，对google的产品一直都蛮关注。刚刚在求实上看到有同学介绍google开发的浏览器，很Orz。我一直认为google brower, google OS, google phone都是GFans的自娱自乐，没想到确有其事。

按照google官方blog中的文章A fresh take on the browser，9月2日，Google的浏览器google chrome的beta就要放出，也就是今天阿（注意一点点时差的区别）Gfans上对此也有介绍。为了配合这个浏览器的发布，google特意做了一套漫画。我这边网速有问题，一直不能正常显示。

google chrome是开源的，基于什么协议我还没有查到。加油吧，google chrome，真希望土鳖IE用的人越来越少，那么将来我们的网银就能支持firefox拉，娃哈哈。

网页开发者们或许会关心google chrome对web标准的支持如何，我想应该不会比IE6差吧。拭目以待吧。

Posted in Techs | 1 Comment »

关于C语言的typedef

注：本文的内容只是对自己学习到知识的一些简单总结，并没有考证过C的规范和手册进行求证。

很多文章，甚至于很多教材，对c语言的typedef的解释是有错误的，以致于许多学习C语言的人对typedef的理解往往有偏差。

一种最常见的错误观点是typedef定义了现有类型的一个别名（alias），比如

typedef int EType;/* (1) */

是给int类型取了一个EType的别名。在这种情况下，似乎也能解释的通，但是，如果碰到这样一个typedef定义呢：

typedef int (*f)(double,int); /* (2) */

观其名，识其行，看typedef的名字就明白它的意思是定义类型。typedef不是简单的给现有类型取一个别名，或者简单的进行字符替换，typedef是利用现有的数据类型类定义一个新的类型。比如语句（1），从概念上我们应当认为是定义了一种新的数据类型，只是这种新类型跟int类型是吻合的。而语句（2）定义了一种新的类型f，f这种类型是一个参数为double,int，返回值是int的函数指针类型。

那么如何去分析，识别typedef定义的类型呢？我从Tony Bai的文章中学到了蛮好的方法。方法就是看看去掉typedef之后，剩下的语句中把相应的变量(记为p)变成了什么类型，那么加上typedef之后，这个p就成了这种类型的名字。

举语句(2)的例子，把typedef去掉，原句就成了

int (*f)(double,int); /* (3) */

，这是一个很普通的函数指针的定义，这个时候f就是指向一个参数为double,int返回值为int的函数指针变量，那么加上typedef之后，f就是指向…..的函数指针类型。

再举一个通俗的例子，将语句(1)的typedef去掉，就成了

int EType;/* (4) */

我们可以清楚的看到，EType是一个int类型的变量，那么加上typedef，EType实际上就成了一个int类型。

Posted in C/C++ | 6 Comments »

Feedsky的服务有些不稳定

今天我的种子feed.feedsky.com/juchen以及绑定的域名feed.kylogs.com都无法访问。访问feedsky的时候也出现了mysql数据库错误。另外，访问feed.feedsky.com/juchen的话如果运气好，耐心足的话还能访问到，而绑定的域名是根本不能访问（我试了下别人的域名绑定，也同样不能访问），这样的情况，基本上有一个下午了。

以前听说feedsky每周末都要习惯性的出问题，看来还真是有可能。

老实说我一直很喜欢feedsky，频频不稳定的情况发生让人担心是不是feedsky缺乏足够的盈利方式以致发展遇到了瓶颈。

Posted in Techs | No Comments »

easyC-API项目介绍

/*—————————————————————————————————————
*-Version :1.0
*-Auther : Chen Ju
*-Auther Email: sammy105{@}gmail.com
*-Auther Site : http://www.kylogs.com/blog
*—————————————————————————————————————
*/

easyC-API的目的及内容

easyC-API的目的是要建立一个C语言的实用包，使得C使用起来更加的简便。它主要包括5个部分：

1. 常见的数据结构及其基本函数库
2. 更好更方便的字符串处理函数库
3. 数值计算函数库（包括高精度计算）
4. 解析器（XML, RSS, RDF的解析）
5. 正则表达式函数库

easyC-API遵循的协议

GPL Version 3(访问)

easyC-API目前完成的情况

项目刚刚开始，目前仅完成了stack及linkedlist部分

easyC-API目前的成员

• sammy105
• palwang723

参与easyC-API的开发

需要说明的是easyC-API并不是具有太多难度的项目，如果您只是抱着学习与练习的目的，我们也欢迎您的加入。您可以从http://easyc-api.googlecode.com/svn/trunk获得最新的源代码及测试代码。如果需要参与开发，可以发信给我，或者在本文章下留言，我会跟您信件联系。

参与easyC-API开发需要掌握的知识

1. 由于easyC-API是C语言的项目，所以您需要比较熟悉C语言，请务必要清楚C与C++之间的分别。
2. 最好的情况下，您还需要掌握gcc的使用方法，makefile的编写方法，及make的使用方法。
3. 最好的情况下，您还需要明白C的静态库，动态库的概念及生成方法。
4. 当您成为了我们的commiter，我们会提供一些简单的学习资料，这些资料都可以从网上获得。

当然，2跟3不是必须的，因为您也可以使用集成开发工具来进行编程，比如,DEVC++，或者Eclipse with CDT等等。

下一篇介绍easyC-API的开发指南。

Posted in C/C++ | No Comments »

提取Web Service的语义

本文所谓的语义是对机器而言。

关于对Web Service进行语义标注，已经有太多的论文了（访问）。一般都是利用本体描述语言根据WSDL对Web Service重新描述，比如，把WSDL转换到OWL-S。其实这样做法是比较简单的，比较有挑战性的是如何将WSDL中一些名字（关键字）转换成具有语义的概念。比如，WSDL中某个方法的参数是（温度，湿度，降水概率，风速风向）这样一个复杂类型，在将其转化成比如OWL-S时候，如何用一个识别并将其匹配到比如<weather>本体，进一步如何产生这个<weather>本体。都是很困难的事情，这件事情在很多论文中都被回避掉了。当然，这只是一个细节。

其实一件比较有趣的事情是还可以从WSDL中获得关于operation的描述（description），operation的名字（比如BookSalesRank），参数的名字等文本性信息中获得关于这个Web Service所具有功能的内容，分类信息。如果让我们人去看一个WSDL文件，即使不去看operation，message等等定义，就看自然语言描述的解释性，注释性的内容，也能大概的了解到这个Web Service是干什么的。显然，信息是存在的，既然存在，问题机器就成了如何从自然语言中去提取关于Web Service功能，分类信息。

关键字提取的方法其实有很多，首先就是解析出单个的词，比如BookSalesRank，可以解析成Book Sales Rank，解析出之后，去掉许多常用词，比如”the”, “a”, “accepts”, “returns”….因此要维护一个大概有700个词左右的这样一个StopWords的词典。然后根据关键词的词频，关键词出现的位置（这也很重要）对不同的关键字打分，取出一定数量分值较高的词汇。如何系统已经有一个分类标准，或者本体词典，就可以计算出各个关键词跟现有分类标准出语义上的相似度(通过WordNet)，从而可以给对Web Service的语义标注提供提示。

Posted in Semantic Web | No Comments »