主题：【注意】道歉--刀耕火种的繁荣时代 的连接上次给错了 -- 柚子
家园 【注意】道歉--刀耕火种的繁荣时代 的连接上次给错了 刀耕火种的繁荣时代
刘新宇
2006年三月
在以前的一篇文章《资源管理的变法》中，我曾经为了读者理解方便，刻意把宋朝说成自然环境恶劣，生产落后的“刀耕火种”时代。这其实是胡言乱语的，不可当真。实际上宋朝可以说是我国古代极其繁荣的一个顶点。经过了宋朝连年战乱后的元朝，其繁荣和文明的程度仍然让马可波罗感到震惊。在他的游记中即使除去关于元大都的叙述，对于南宋故都杭州的描写，也仍然让人惊讶不已。
问题就是在于，在我们现代人看来的“刀耕火种”时代，没有电，没有石油，没有汽车，没有空调和抽水马桶，文明和繁盛是如何实现的呢？
如果说今天软件开发界的文明和繁盛中，面向对象是一个代表；C++和Java这些是实现繁荣的电，石油和汽车。那么在“刀耕火种”的时代，只有ANSI C这个冷兵器，如何实现“盛世”呢？
首先要看一看盛世的特点，比如汉代的“文景之治”，唐代的“贞观之治”“开元盛世”。在物质丰富的同时，政治也比较宽松，文化得到发展。这些都可以归纳成一些特点。在软件开发领域，面向对象也有一些特点，最主要的是如下三个：
封装性
继承性
多态性
按照一贯的风格，为了方便读者理解，这里按部就班，把上述三个特性类比为文明社会的3个特点：
封装性——政治组织制度
继承性——人才选拔制度
多态性——财政税收制度
实现手法上，做这样的类比：
C++的实现手法——现代社会的实现手法
C 的实现手法——古代社会的实现手法
最后本文再给出在不支持多线程的操作系统上实现多线程的手法。
首先看文明社会中的政治组织制度。政治组织中非常重要的一点就是“按部就班，各司其职”。同时官员和职能也明确划分，共同“封装”在指定的部门里。对应于面相对象的封装性，其特征也是如此。这一特性把算法和数据结构等在概念上属于同一事物的内容，统一包装起来，例如C++中：
class Encapsulate{
public:
void setValue(const int v){value=v;}
const int getValue() const {return value;}
private:
int value;
};
包装内部既有数据value，也有方法如setValue和getValue，这些方法可以按照非常明确的从属关系加以调用，例如：
int main(int argc, char* argv[]){
Encapsulate v;
v.setValue(3);
cout<<"value = "<<v.getValue()<<"\n";
//error cout<<v.value;
reuturn 0;
}
政府分门别类，官员按部就班。现代文明社会可以，汉代的“九品中正”，唐代的“三省六部”也行。用ANSI C实现封装性的思路是使用函数指针。由于在ANSI C中，结构体的含义类似C++和Java中的类。虽然C中的结构体不允许含有函数成员，但是函数指针可以被当作普通的数据成员放入结构体中。唯一要做的就是，一定要正确初始化这些函数指针。所以ANSI C实现的封装特性如下：
首先在头文件中：
struct Encapsulate{
int value;
void (*setValue)(struct Encapsulate* p, const int v);
const int (*getValue)(struct Encapsulate* p);
};
struct Encapsulate* create();
然后在C文件中：
static void setValue(struct Encapsulate* p, const int v){
p->value=v;
}
static const int getValue(struct Encapsulate* p){
return p->value;
}
struct Encapsulate* create(){
Encapsulate* p=(Encapsulate*)malloc(sizeof(Encapsulate));
p->setValue=setValue;
p->getValue=getValue;
return p;
}
现在可以看看封装的效果：
int main(int argc, char* argv[]){
Encapsulate* e=create();
e->setValue(e, 3);
printf("value = %d\n", e->getValue(e));
free(e);
reuturn 0;
}
不仅输出和前面一摸一样，而且在调用方式上也非常相似。如果为了理解方便，还可以定义一个self变量：
struct Encapsulate{
//略
struct Encapsulate* self;
};
在初始化create时：
struct Encapsulate* create(){
Encapsulate* p=(Encapsulate*)malloc(sizeof(Encapsulate));
p->self = p;
p->setValue=setValue;
p->getValue=getValue;
return p;
}
这样调用的时候，就可以按照这个形式：
e->setValue(e->self, 3);
人才选拔和培养是现代文明社会中非常重要的一环，通过人才的培养和选拔，社会中沉淀的知识和经验得以积累，前人的成果得以被后人“继承”。继承性是“文明中”代码重用的重要基础之一。在C++中，子类从父类继承，可以获得父类的大量特性，例如：
class Base{
public:
void setValue(int v){value=v;}
int getValue(){return value;}
int value;
};
class Derived:public Base{
public:
void increase(){value++;}
void decrease(){value--;}
int key;
};
子类通过继承，可以在具有父类所有特性的同时，再增加子类特殊的内容，而原来针对父类的操作，也可以针对子类而不必重新改动，例如：
void initBase(Base* p){
p->setValue(0);
}
void display(Base* p){
cout<<"value="<<p->getValue()<<"\n";
}
int main(int argc, char* argv[]){
Derived foo;
initBase(&foo);
foo.increase();
foo.increase();
display(&foo);
foo.decrease();
display(&foo);
foo.key=3;
}
现代社会通过社会化的教育体系实现的功能，在古代社会同样可以实现，春秋时孔子就搞“民间教育”，弟子三千，贤者七十有二。在选拔上，现代社会有各种考试，在汉代有“举孝廉和举秀才”，唐代开始有国家统一的考试。因此继承性不是C++和Java的专利，也可以通过ANSI C加以实现，思路是在子结构体的起始位置，放入父结构体的一段数据[3]。这样只要将子结构体强制类型转换为父结构体后，就可以直接被直接当作父结构体操作。这样操作不会出现问题的原因在于，那些针对父结构体的函数，只会访问子结构体数据的前面一段，而不会访问到后继的数据部分。这个思路用ANSI C实现如下：
首先在头文件中这样定义：
struct Base{
void (*setValue)(struct Base* self, int v);
int (*getValue)(struct Base* self);
int value;
};
void constructBase(struct Base* p);
struct Derived{
struct Base base; /*实现继承*/
void (*increase)(struct Derived* self);
void (*decrease)(struct Derived* self);
int key;
};
void constructDerived(struct Derived* p);
void initBase(struct Base* p);
void display(struct Base* p);
由于C中没有构造函数的概念，所以constructXXX负责了一部分的任务，在C文件中，上述定义的实现如下：
/* Base member functions */
static void setValue(struct Base* self, int v){
self->value=v;
}
static int getValue(struct Base* self){
return self->value;
}
void constructBase(struct Base* p){
p->setValue=setValue;
p->getValue=getValue;
}
/* Derived member functions */
static void increase(struct Derived* self){
self->base.value++; /*或者((struct Base*)self)->value++;*/
}
static void decrease(struct Derived* self){
self->base.value--; /*或者((struct Base*)self)->value--;*/
}
void constructDerived(struct Derived* p){
constructBase((struct Base*)p); /*调用父类构造函数*/
p->increase=increase;
p->decrease=decrease;
}
/* global functions */
void initBase(struct Base* p){
p->setValue(p, 0);
}
void display(struct Base* p){
printf("value=%d\n", p->getValue(p));
}
上面代码中，最体现特点的是带有汉字的注释部分，这些都表明，子结构一旦向上转换为父结构后，就可以被当作父结构来对待。这是面向对象中继承的英文解释：is a type of的良好诠释。下面可以测试一下：
int main(int argc, char* argv[]){
struct Derived foo;
constructDerived(&foo);
initBase((struct Base*)&foo);
foo.increase(&foo);
foo.increase(&foo);
display((struct Base*)&foo);
foo.decrease(&foo);
display((struct Base*)&foo);
foo.key=3;
return 0;
}
调用方式和前面C++的基本一致，输出结果也一摸一样。
文明社会的政府为了保证其财政收入，都拥有一套财政税收制度。基本含义不变而课税方法多样，有的关注生产环节，有的关注流通环节，还有的着眼在消费。这样的“多态性”可以保证提纲挈领，纲举目张。在C++中多态性（这里是指运行时的多态，实现编译期多态的模板技术暂不讨论）通过虚函数(virtual function)和override/overwrite进行实现（这里暂且不提overload）。例如：
class Point{
public:
Point(int _x, int _y):x(_x), y(_y){};
virtual double radius(){ return sqrt(double(x*x+y*y)); }
int x;
int y;
};
class Point3D:public Point{
public:
Point3D(int _x, int _y, int _z):Point(_x, _y), z(_z){};
double radius(){return sqrt(double(x*x+y*y+z*z)); }
int z;
};
int main(int argc, char* argv[]){
Point* p=new Point(1,1);
cout<<"radius ="<<p->radius()<<"\n";
delete p;
p= new Point3D(1,1,2);
cout<<"radius ="<<p->radius()<<"\n";
delete p;
}
在这个例子里，Point定义了平面上的点，而Point3D定义了空间上的点，当计算点到原点的距离radius的时候，平面的计算方法和空间的计算方法不同，在这里多态的表现就是，子类Point3D重新实现了父类Point的计算方法，而其他内容则采取“拿来主义”一并继承过来。
虽然现代社会拥有完善的各种课税，比如生产和销售环节的增值税，建筑服务行业的营业税，针对企业和个人的所得税，其根本是提供国家的财政收入。在中国古代，春秋时期鲁国在前594年即实行了“初税亩”，按照土地向私有者课征。此后各朝变迁变法，税收都是其中重要一环。用ANSI C实现多态的方法如下：
首先在头文件中定义普通平面上的点和三维空间的点，并按照前面的做法，建立继承关系，为了说明多态的灵活性，还增加了一个彩色平面点的定义。：
struct point{
double (*radius)( struct point* self);
void (*display)(struct point* self, const char* name);
int x;
int y;
};
struct point* create_point(int x, int y);
struct point3D{
struct point super;
int z;
};
struct point* create_point3D(int x, int y, int z);
enum color_t{RED, GREEN, BLUE};
struct color_point{
struct point super;
enum color_t color;
};
struct point* create_color_point(int x, int y, enum color_t color);
在这套继承体系中，三维空间点和彩色平面点都从普通平面点继承来，但是在使用虚函数实现多态上有一些区别。三种点各自实现显示信息的方法display，但是彩色点直接使用平面点的radius方法计算到原点的距离，而三维空间点则override这个计算的方法。具体的实现如下：
/* point in 2D plan default member function */
static double radius(struct point* self){
return sqrt((double)(self->x*self->x + self->y*self->y));
}
static void display(struct point* self, const char* name){
printf("point %s: x=%d, y=%d\n", name, self->x, self->y);
}
static void init_point(struct point* p, int x, int y){
p->x=x;
p->y=y;
p->radius=radius;
p->display=display;
}
/* point ctor */
struct point* create_point(int x, int y){
struct point* p=(struct point*)malloc(sizeof(struct point));
init_point(p, x, y);
return p;
}
普通平面点得以实现后，现在实现三维点，需要override的方法包括radius和display，另外在构造时还要额外初始化z成员：
/* point3D overrided member function */
static double radius3D(struct point* self){
/* downcasting will cause warning */
struct point3D* p=(struct poin3D*)self;
return sqrt((double)(self->x*self->x+
self->y*self->y+
p->z*p->z));
}
static void display3D(struct point* self, const char* name){
struct point3D* p=(struct poin3D*)self;
printf("3D point %s: x=%d, y=%d, z=%d\n", name, self->x, self->y, p->z);
}
static void init_point3D(struct point3D* p, int z){
p->z=z;
((struct point*)p)->radius=radius3D; /* override */
p->super.display=display3D; /* override */
}
/* point 3D ctor */
struct point* create_point3D(int x, int y, int z){
struct piont3D* p=(struct point3D*)malloc(sizeof(struct point3D));
init_point((struct point*)p, x, y);
init_point3D(p, z);
return (struct point*)p;
}
平面上的彩色点直接使用父类的radius函数，但是需要override计算距离的radius函数。
/* color point used its fathers radius methods,
* only display function is overwrote
*/
static void display_color(struct point* self, const char* name){
struct color_point* p=(struct color_point*)self;
printf("color point %s: x=%d, y=%d, color=%d\n", name, self->x, self->y, p->color);
}
static void init_color_point(struct color_point* p, enum color_t color){
p->color=color;
p->super.display=display_color; /* only display function is overridden */
}
/* color point ctor */
struct point* create_color_point(int x, int y, enum color_t color){
struct color_piont* p=(struct color_point*)malloc(sizeof(struct color_point));
init_point((struct point*)p, x, y);
init_color_point(p, color);
return (struct point*)p;
}
现在可以测试一下这套继承体系的多态特性：
int main(int argc, char* argv[]){
struct point* p=create_point(1, 1);
printf("radius of p1=%f\n", p->radius(p));
p->display(p, "p1");
free(p);
p=create_point3D(1, 1, 2);
printf("radius of p2=%f\n", p->radius(p));
p->display(p, "p2");
free(p);
p=create_color_point(1, 1, RED);
printf("radius of p3=%f\n", p->radius(p));
p->display(p, "p3");
free(p);
return 0;
}
调用方法和C++的如出一辙，运行结果如下：
radius of p1=1.414214
point p1: x=1, y=1
radius of p2=2.449490
3D point p2: x=1, y=1, z=2
radius of p3=1.414214
color point p3: x=1, y=1, color=0
输出结果也和预想的一致，至此“刀耕火种”的ANSI C基本实现了用C++和Java体现出的面向对象三大特性。当然这里还有不完美的地方，比如没有办法限制访问权限。C++和Java提供语言级别的public, private等关键字来实现一定程度的数据隐藏。在本文的实现方法中，虽然可以通过把方法置于C文件内部实现部分private意义上的隐藏，但是却暴露了所有的数据成员。另外C++和Java都提供的函数overload，也没有给出有效的实现。但这已经不足以阻止用“刀耕火种”建立“繁荣时代”了。古代文明的魅力也正在于此。
盛世还有一些代表性的城市繁荣，比如唐的长安，北宋的汴梁，南宋的杭州。虽然现代化的大都市有惊人的硬件环境，但是在缺乏这些现代化硬件的古代，依然能够实现城市的繁荣。比如现代操作系统，天生支持多线程。可是在不支持多线程的系统上，依然不能阻止实现运算调度的尝试。这些尝试虽然不是本质上的并行处理（现代操作系统在单CPU下也不是真正意义上的并行，而是时间片的调度，当然Intel最近热炒的双核不算在内），但是依然能够给使用者并发的感觉。
下面就用C++语言本身（不使用任何多线程库）实现多线程的感觉。其思路来自一种称之为ActiveObject[4]的模式。这种思路往往类似传统的戏剧。比如《三国演义》里面长板坡，开始情节单一，过一会就出现了两个条线(thread)，一条线赵云冲进去救刘备家小去了。另一条线张飞护着刘备跑，并且设置假伏兵。两条线同时发生，都要演出，可是却只有一个舞台。办法是舞台上先演一段赵云，张飞等演员在后台休息，然后大幕落下，赵云等演员撤到后台休息，张飞他们出来再演一段。然后再次赵云上前台演，张飞去后台休息……如此往复。观众们丝毫不觉得奇怪，而很自然的认为这两段故事同时发生。演出的关键在于合理的分隔每段故事上演的时间片，让观众没有割裂的感觉。这个思路其实就是单CPU，单进程实现多线程的思路。
首先定义一个线程类，这个就是张飞和赵云的故事这种并发故事的抽象描述：
class thread{
public:
thread(int period):period_(period*1000),time_(0){};
virtual void run()=0;
virtual bool finish()=0;
bool wait(){
return (time_++%period_)!=0;
}
private:
long period_;
long time_;
};
线程的构造函数中，导演可以事先决定每段故事的演员要在后台休息的时间period，每次休息时间一到(time_++%period为0的时候)，演员们就停止休息上前台演出(run)。故事的每条线有一个结束的标志finish，当故事结束时，就再也不用到舞台上演出了。
舞台调度的实现如下：
class schedular{
public:
static schedular& instance(){
static schedular inst;
return inst;
}
void start(){
while(!queue_.empty()){
thread* p=queue_.front();
queue_.pop_front();
if(!p->wait())
p->run();
if(!p->finish())
queue_.push_back(p);
else
delete p;
}
}
void add(thread* p){
queue_.push_back(p);
}
~schedular(){
while(!queue_.empty()){
delete queue_.front();
queue_.pop_front();
}
}
private:
schedular(){}
schedular(const schedular&);
const schedular& operator=(const schedular&);
list<thread*> queue_;
};
舞台只有一个，所以被设计为singleton。在演出前，导演可以预先把这些故事线索(thread)加入到舞台调度的列表(queue_)中去，然后一旦演出开始(start)，舞台调度就不断查看调度表，把表头的故事拿出来，看看是否他们应该上台，如果该上台了，就通知他们演出(run)一段。这段演出结束后，调度询问他们所演的全部故事是否已经结束了，如果还没有，就把他们的故事再次放到调度表的最后面，然后去准备演下一条故事线索。一旦这个故事线索演出完毕，比如说赵云已经抱着阿斗冲出来了，调度就不会再把故事放到调度表的最后。赵云就可以卸装喝水彻底休息了。
现在就可以给出一个具体的故事线索作为例子了：
class counter: public thread{
public:
counter(const string name, int value, int s):thread(s), name_(name), value_(value){}
void run(){
cout<<"thread "<<name_<<": count "<<value_--<<"\n";
}
bool finish(){
return (value_<=0);
}
private:
string name_;
int value_;
};
这个故事就是：“从前有座山，山上有个庙，庙里有个和尚在将故事，讲的故事是：从前有座山……”这样的循环故事，每次上台演出就讲一句，直到讲到累了(value_为0)为止。每次在后台休息s-1分后，上台讲一句。
此后就可以演出了，导演让两个这样的故事线索同时上演，间隔的时间不同：
int main(int argc, char* argv[]){
schedular::instance().add(new counter(string("hello"), 20, 2));
schedular::instance().add(new counter(string("me"), 10, 5));
schedular::instance().start();
}
演出的效果如下：
thread hello: count 20
thread me: count 10
thread hello: count 19
thread hello: count 18
thread me: count 9
thread hello: count 17
thread hello: count 16
thread hello: count 15
thread me: count 8
thread hello: count 14
thread hello: count 13
thread me: count 7
thread hello: count 12
thread hello: count 11
thread hello: count 10
thread me: count 6
thread hello: count 9
thread hello: count 8
thread me: count 5
thread hello: count 7
thread hello: count 6
thread hello: count 5
thread me: count 4
thread hello: count 4
thread hello: count 3
thread me: count 3
thread hello: count 2
thread hello: count 1
thread me: count 2
thread me: count 1
作为现在的中国人，多少对“古代盛世”怀有一些复杂的情节。有的人怀念，恨不得能够回到唐朝去生活；有的人理性地说光是晚上没有电就受不了。有时面对计算机，手机，汽车这些东西，我也会怀疑究竟人类技术的发展是一种社会的进步还是倒退。有时候看到早上一路小跑赶公共汽车的人们生怕上班打卡迟到，我也会想究竟古代是否要活的这么紧张。
现代人还是很难摆脱历史的阴影，we learn from history that people never learn from history，看着我们一遍一遍重复古人走过的轨迹——揭竿而起，励精图治，贪污腐败，天灾人祸，战乱流离……这样兴衰治乱的演出，上帝一定也觉得很没有意思吧。
参考书目：
[1] Apache httpd source code: http://httpd.apache.org/
[2] APR, apache runtime library source code: http://apr.apache.org/
[3] Peter. Wright. Beginning GTK/GNOME programming. Peer Information. 2000
[4] Robot C. Martin, Agile software development: principles, patterns, and practice. Printice Hall. 2002.
家园 【讨论】几个商榷的地方 1）
void setValue(const int v){value=v;}
C/C++是Pass-by-value，所以对于简单数据类型的传值，const是不必要的。
一般在传一个reference或pointer的Input parameter使用const，来避免其内容被函数修改。
2）Point和Point3D之间不存在继承关系。（而Point和color_point之间存在继承关系）。
C++的继承关系是严格的IS_A关系，也就是说，Derived class必须拥有base class的所有public和protected属性和method。Base class的public virtual function可视作derived class的一个default implementation。（在base class无法缺省实现时，则常为pure virtual function），显然因为3D的Point多了一个z坐标，彻底改变了2维点的物理意义，两者没有这种IS_A关系。严格来说这更像一个Has-A关系。
虽然数学上两者有紧密联系，而在C++中因为不是严格的IS_A关系，所以不能使用继承。
因为多一个Z-坐标，2D point和3D point只能视作两个独立的class，或许实现上3D point class可以composite 2D point class.
Scott Meyers在他的Effective C++有一个Item（记不清是具体哪个Item了）是专门解释这一点了。记得他老人家举的例子是，矩形和正方形之间不存在继承关系。
3)Thread这个例子有个明显问题，
queue_不是thread safe的，对queue_的操作应要加上Mutex或其他类似的东东加以保护。
家园 谢谢回贴 首先谢谢回贴，有讨论才能有进步，沙龙永远胜过一言堂。
>void setValue(const int v){value=v;}
>
>C/C++是Pass-by-value，所以对于简单数据类型的传值，const是不必要的。
>一般在传一个reference或pointer的Input parameter使用const，来避免其内容被函数修改。
这点非常同意，实际上应该是这样的：
TypeResult function(const TypeClass& v){ //pass const reference to avoid temp copy ctor
value=TypeClass(v); //保护性copy，防止v是一个cracker恶意继承自TypeClass的类
}
对于上述setValue，本质希望能够直接对比到ANSI C的实现上，如果涉及保护性copy,和pass by reference
及pass by value，这些language-level的特性，并不是OO的特性，也无法和ANSI C的实现对比了。
>2）Point和Point3D之间不存在继承关系。（而Point和color_point之间存在继承关系）。
>C++的继承关系是严格的IS_A关系，也就是说，Derived class必须拥有base class的所有public和protected属性和 >method。Base class的public virtual function可视作derived class的一个default implementation。（在base >class无法缺省实现时，则常为pure virtual function），显然因为3D的Point多了一个z坐标，彻底改变了2维点的> 物理意义，两者没有这种IS_A关系。严格来说这更像一个Has-A关系。
>虽然数学上两者有紧密联系，而在C++中因为不是严格的IS_A关系，所以不能使用继承。[ｃcｈeｒe.com 西西河 无> 斋主人]
>因为多一个Z-坐标，2D point和3D point只能视作两个独立的class，或许实现上3D point class可以composite 2D >point class.
>Scott Meyers在他的Effective C++有一个Item（记不清是具体哪个Item了）是专门解释这一点了。记得他老人家举> 的例子是，矩形和正方形之间不存在继承关系。
关于inheritance和compose，这个也是最近OO中特别强调的一点。例子很多，事实上在某些极端的情况下比如Java， 只有interface可以被implement，而不主张继承任何非抽象类。总之，的确继承在前些年被滥用了，更多的情况下
应该是compose，但是如果你仔细读我的ANSI C代码，就会发现，使用ANSI C实现继承时，只有一个办法——就是 compose，sub struct HAS_A base struct data section。
严格说，按照OO思想，如果采用C++或者JAVA这个继承体系如下：
template<class T>
class point{
public:
virtual const T& getCoordinate(int demension) = 0;
virtual double radius() = 0;
};
tempalte<int n, class T = int>
class pointX: public point<T>{
public:
const T& getCoordinate(int demension){
if(demension < 0 || demension > n)
throw std::runtime_error("out of demension");
return coordinates[n];
}
double radius(){
for(int i=0, res=0; i<n; ++i)
res+=coordinates[i]*coordinates[i]
return sqrt(res);
}
private:
T[n] coordinates;
};
typedef piontX<2> point2D;
typedef pointX<3> point3D;
class colored_point:public point2D{
//...
};
>3)Thread这个例子有个明显问题，
>queue_不是thread safe的，对queue_的操作应要加上Mutex或其他类似的东东加以保护。
这个我觉得你没有理解我的意思，我是在不支持多线程的机器上实现多线程，例如在MS-DOS上，
只有我一个process一个task，哪里有同步的问题呢？
