Abstract Factory和Factory Method的区别

不得不说这两个囧模式看到我现在都还是不能很确认自己是不是真的了解它们之间的区别了。主要原因估计是Abstract Factory一般通过Factory Method来实现的原因。

（下文中，首字母大写正体的表示一个模式，如Abstract Factory，指的是Abstract Factory这个模式；首字母大写粗斜体的表示一个类，如Factory表示一个Factory的类；小写字母的表示一个对象，如factory表示某个类的一个实例，一个对象；其他的可以通过上下文区分其含义。）

经过多番钻牛角尖和刨书的结果，它们两个的区别，我认为还是比较基本的一点：虽然均属创建型模式，但是Abstract Factory是对象型而Factory Method是类型的（强烈BS一下中译版把这么重要的区别给弄没了）。

更具体一点来说，Abstract Factory把一系列的对象的创建留给了一个factory对象去创建。这里面包含了一个动态的概念：你可以动态地决定你的factory的将创建一堆什么东西（通过选择不同的Concrete Factory）。

而Factory Method则是一个静态的概念，它把一个对象的创建推迟到了子类，我们知道这在C++里面可以通过虚拟函数来实现。之所以说是静态的是因为，Factory Method里面的Product，在你进行类设计的阶段时就已经被固定为是经过Creator通过某个操作来创建的。为了创建一个Product的对象，你必须要通过Creator的这个操作进行。

尽管用什么Creator的子类对象来创建哪个Product的子类对象还是动态的，但是这不是Factory Method关心的范围。这也是因为Factory Method是类创建型模式所决定的：它关心的是Creator和Product两个类（包括子类）之间的关系：Creator负责了Product的创建，而这种创建将依赖于在Creator上面定义的一个操作（也就是一个factory method，“because it is resposible for “manufacturing” an object”）实现。这其实定义了一个Creator(Factory)->Product的关系。

而Abstract Factory之所以显得和Factory Method很接近——Abstract Factory指定了许多的操作，然后再在Concrete Factory里面定义好这些操作，负责创建对应的Concrete Product——是因为Abstract Factory通过Factory Method来实现的原因（所以，Abstract Factory里面的那些操作都可以称为是factory method）。

但Abstract Factory并非只能通过Factory Method来实现。如果说通过Factory Method来实现Abstract Factory使得Abstract Factory定义的类间和类层次结构与Factory Method很接近的话，通过Prototype来实现的Abstract Factory将可以把这个结构坎掉一大半，让Abstract Factory与Factory Method不再相似，只剩下一堆操作。这堆操作只起到接口的作用，并没有定义像Factory Method中那样的关系：尽管对象还是经由Abstract Factory这些操作产生，但本质上已经不再是Factory->Product的关系了（Prototype模式里面通过拷贝对象原型来产生新的对象，是一种prototype->product的关系。注意字体）。

然而根本不用管是否Factory->Product，因为Abstract Factory关心的只是，提供接口，隐藏内部细节，使得可以通过不同的factory object用相同的接口来产生不同系列的产品对象（其实就是不管如何都是显示为一个factory->product的关系。注意字体）。

这也是为何Abstract Factory定位为一个对象创建型的模式的原因吧。

javascript里面的this

昨天的思考中遇到了this的问题。ECMA-262中，this是在执行上下文(Execution Contexts）中被首次提及的，所以或许我应该先了解一下什么是执行上下文。

执行上下文？

Excution Contexts（我简称EC吧），当程序的控制流进入一段ECMAScript可执行代码时，就会进入一个EC。活动EC在逻辑上会形成一个栈，栈顶EC就是当前运行的EC。

ECMAScript可执行代码？

ECMA-262中定义了三类这样的可执行代码：

• 全局代码：用C的概念类比的话，就是main函数里面的所有语句。javascript程序的源代码，除了函数体以外，都可以看成是全局代码。
  
  我好像一直在混淆javascript和ECMAScript的概念了？其实ECMAScript可以认为是javascript和jscript的泛化，是一个标准化的规范。虽然我不知道javascript是不是完全兼容于ECMA的规范，不过ECMA中定义的大部分概念，对javascript应该都是适用的。
  
• eval代码：eval，但凡解释性语言基本都有的东西。当然apply也是。eval/apply可谓亲密无间的伙伴，不过在这里它不是主角。eval代码就是应用到内建的eval函数的那些字符串。性质类似于全局代码。
  
• 函数代码：全局代码里面并没有包括函数体的源代码，函数体的源代码属于函数代码的一部分。当然，函数体的源代码中如果包含嵌套的函数体，嵌套的那部分则是属于另一段的函数代码的。上一篇文章里面说过函数也可以通过new Function来创建，所以new Function的最后一个参数，也就是函数体，也会被看作是一段函数代码。

我猜想EC的并非以一种对象实现的。ECMA-262里面从头到尾都没有提起过所谓execution context object，甚至连context object的概念也没有看见。会有不少对象和引用附加在一个EC上，大概可以把EC理解成一个小型集合吧。

那么this到底和EC有什么关系？
this是EC上附加的一个……引用。this的值与调用者（主要对函数而言）和被执行的代码有关，并且值在进入EC的时候就已经定下来了。this是不可修改的。

this是跟可执行代码类型有关的：

• 对于全局代码，this引用到全局对象。
  
  什么是全局对象？
  
  全局对象是javascript的一类原生对象Global Object，在进入EC之前就已经被创建。它有几个特点：
  
  
  
  • 不能通过new constructor构造。
  
  
  • 不能用作函数调用。
  
  
  • Global Object的类型以及prototype是跟具体的javascript的实现细节相关的。
  
  javascript提供的内建值（NaN，Infinity和undefined）、内建函数（eval，parseInt等）以及其他原生对象的构造函数（Object，Function等）都是Global Object的提供的属性。可以向Global Object中添加各种其他的属性。
  
  Global Object处于作用域链的最高层。至于什么是作用域链……再说吧，现在已经离题很远了。
  
  根据这些，现在可以猜想到的一点就是，在javascript里面这样的调用：
  

  eval("alert('hello');");

  
  其实是等价于下面这样的伪代码：
  

  global_object.eval("alert('hello');");

  
  回到this。因为对于全局代码，this引用到了全局对象，所以在全局代码里面使用this，跟没使用效果是一样的orz：
  

  this.a="hello";
  this.alert(a===this.a);



• eval代码
  
  当进入的是eval代码的EC时，上一个EC，被称作调用上下文。eval代码里面的this，与调用上下文里面的this是一样的。如果没有调用上下文，那么eval代码会做与全局代码一样的处理。
  

  function test() {
  eval("this.a = 'hello';");
  alert(a);
  }
  test();
  

  不过实际上，这里的this用了跟没有用也是一样的。


• 函数代码
  
  this的值由调用者提供。当调用者不是对象时，this将引用到全局对象上。

看到这里，虽然还没弄清楚到底调用者怎样提供this的值，不过可以猜想，如果调用者是对象的话，那么this将会引用到调用者自身。这就可以解释为什么new constructor的时候，this是指向实例化的对象了。如果作为普通函数调用，按照之前对全局代码得出的结论，应该跟global_object.a_function的调用是一样的。这样想的话，调用者就是全局对象了。

那样的话，总算明白了普通函数里面的this有什么意思了……

function test_class () {
this.v1 = '1';
}

/* new constructor方式调用，function code的
调用者为新实例化的对象，this引用到这个对象上。*/
alert((new test_class()).v1);

alert(v1); // 调用失败，v1未定义
test_class(); // 普通函数调用，this为全局对象
alert(v1); // 经过上面的调用，全局对象里面有了v1的定义

不过让ECMA-262里面提到的一点我不太明白：eval代码可能会没有调用上下文。那会是什么样的情况呢？是指eval语句是第一句的情况吗？还是说只有eval一句的情况呢？

说到这里仍然是有很多不明不白，唯一清晰了的就是this在普通函数里面有什么含意……嘛既然标题是关于this的，我也不去想先了。留给后一篇post吧。

Javascript中prototype的菜鸟级思考

进入主题之前不得不承认，一直以来我都把javascript看成是java的缩水版，同一个公司出品。我一直不太喜欢java那笨重的身体，于是，javascript就也被我放进了不喜欢的PL的队列里面，javascript在我脑子里面大概都有4、5年没有更新过了。直到上个月着手为xtheukn做些小修小改的时候开始，我对javascript的理解才有了质的变化。

虽然挺想认真地再学一下这个有趣又强大的小玩意，不过时间是最大的问题啊……所以下面写的东西，可能会很肤浅也很多错误……

---

今天特意认真的看了看有关javascript的prototype部分，算是把之前不太懂的弄懂了一点了吧。

不过，大概还是停留在很低的水平上……

什么是prototype？

或许是我搜索能力问题，也或许是我脑子不太灵活的问题，自己在网上搜了不少关于prototype的讲解，但看了又看还是不太懂。后来找到了ECMA-262，仔细读了读，总算明白了什么是prototype了。

按照ECMA-262的定义，prototype是一个对象。利用prototype，可以在ECMAScript（javascript和jscript的泛化）中实现继承，它被构造函数（constructor）所持用的，可以通过constructor.prototype引用。

那么什么是构造函数？

构造函数其实跟普通的函数，单从函数的定义上面来说，可以说是完全一样的。唯一区分构造函数和普通函数的，大概就只有new操作符了。当new操作符作用在一个函数的时候，将会产生一个对象，然后在这个对象上调用这个函数，初始化这个对象里面的成员。

function BaseClass () {
this.var1 = 'Base';
}
var baseobj = new BaseClass();

然后baseobj.var1就会包含值'Base'了。javascript里面的所有对象，都可以通过new constructor(...)来实例化。

假如没有了new，那么对BaseClass的调用就是普通的函数调用，这时的baseobj就不是一个BaseClass的对象了，而仅仅是BaseClass这个函数的返回值。

当然，这样的话，对this的理解就不能停留在C++的层面上了。有空再慢慢看看这个this的含义吧。

在函数定义好以后它就持有一个prototype对象的引用，也就是constructor.prototype。这很正常，因为函数在javascript也是一个对象，到prototype对象的引用其实就是这个函数对象上的一个成员变量。constructor代表一个具体的构造函数名，比如说在上面的代码片段，constructor对应了BaseClass，引用BaseClass的prototype对象应通过BaseClass.prototype来引用。

函数对象

把函数也作为一种对象在解释语言里面很常见。在javascript里面，函数对象（Function Object）是一种原生的对象，也可以通过new constructor来实例化：

var func = new Function("v1", "v2", "return v1+v2;");

上面的语句定义了一个函数func，等价于：

function func(v1, v2) {
return v1+v2;
}

而当一个对象被成功实例化以后，它就会隐式的引用到构造函数持有的prototype对象上面。一个对象总会有一个隐式引用的prototype对象。

如果BaseClass的对象baseobj要引用一个变量var1，那么首先当然会去查找当前的baseobj对象上面有没有这个var1变量，如果有，取其值；如果没有，则通过这个隐式的引用回溯到BaseClass的prototype对象上面继续查找。很容易可以想到，如果在这个prototype对象上找不到var1，那么，因为这个prototype对象也是一个对象，它也有隐式引用的prototype对象，所以将会继续回溯到BaseClass.prototype对象所引用的prototype对象上继续进行查找，直到找到为止，否则就返回undefined。这种prototype之间的引用也称为prototype链。

需要记住的是prototype只能通过constructor.prototype来进行显式的引用，被构造函数实例化的对象只有隐式的引用，没办法显式的访问，所以类似BaseClass.prototype.prototype这样的调用是会失败的，除非BaseClass.prototype引用到的是一个函数对象。不过似乎构筑这种情况没什么实用性可言。

通过prototype链，javascript就可以实现继承了：

1 function BaseClass() {
2 this.var1 = 'Base';
3 }
4 function DerivedClass() {
5 this.var2 = 'Derived';
6 }
7 DerivedClass.prototype = new BaseClass();
8 var derobj = new DerivedClass();

这里关键的一句是第7行的语句。它把DerivedClass.prototype引用到一个BaseClass的实例（方便起见，记为baseobj）上面了。于是当第8行语句实例化一个DerivedClass的对象derobj时，derobj就会有一个对baseobj产生隐式引用，当在derobj访问一个不存在的变量时，就会通过隐式引用回溯到baseobj里查找。继承就是通过这样的方式实现了。

当然，因为baseobj是被DerivedClass所持有的，所以所有DerivedClass实例化的实例，都会隐式引用到同一个对象上面，也就是说，当baseobj有所变动，DerivedClass的所有实例都会受到影响。

需要注意的是哪些对象之间存在引用，是何种引用。假设存在构造函数CF，CF持有的prototype对象CFp，以及CF实例化的两个对象CF1和CF2：

1. CF1和CF2是CF实例化而得到的，所以CF1和CF2对CFp存在隐式的引用。
2. CFp是一个对象，假设构造它的构造函数是CFpCF，被实例化时CFpCF持有的prototype对象是CFpCFp，那么CFp对CFpCFp就存在隐式的引用。
3. CF是一个函数，函数也是对象，也是通过某个构造函数实例化而得的，假设为CFCF，那么CF对CFCF也存在隐式引用。
4. 最后，CF是一个构造函数，所以它有一个对CFp的显式引用。

从上面可见，CF1、CF2和CF之间是没有引用被引用关系的。也就是说，CF1、CF2对CFp的引用，是不受CF干预的。也就是说当CF.prototype改变了以后，CF1和CF2对CFp的引用是不会变的。

会产生循环引用吗？

我曾经考虑过这样的语句序列：

function func1() {}
function func2() {}
func1.prototype = new func2();
func2.prototype = new func1();
var v1 = new func2();
alert(v1.vv1);

看上去好像当v1检索vv1变量的时候：v1中不存在vv1变量，到func2.prototype找-->到func1.prototype找-->到func2.prototype找-->...，似乎会变成一个循环。

定义一个函数（也就是创建一个函数对象）的过程中有以下几个重要的动作：

1. 创建一个原生的Function对象F
2. 创建一个原生的Object对象O
3. F.prototype <- O
4. 返回F

实际的过程比上面列出复杂得多，不过已经足可见一个构造函数持有的prototype对象，是在定义的时候就已经引用到一个Object对象了。

然后看看func1.prototype = new func2()时发生了什么：

1. 一个func2的实例F2被创建，根据当前func2的prototype是引用到一个Object对象O上面的，所以F2也是引用到这个O上面。
2. func1.prototype <- F2

前面提到，constructor和实例化的对象之间是没有引用关系的， constructor.prototype的改变并不会影响已经实例化的对象所引用的对象，所以，F2此时仍然指向Object对象O上。 然后当下一句被执行的时候，func1.prototype已经被改变而指向F2，所以new func1所创建的对象F1会指向F2，而func2.prototype指向func1.prototype已经改变以后再实例化的F1。 然后v1被实例化，指向func2.prototype即F1。

然后看看实际的回溯路径： v1-->F1-->F2-->O

并没有构成循环。

---

想到这里算了。好像写了不少没用的东西了……不过就体谅一下我这等菜鸟吧。如果你发现有错的，请务必告诉我。

然后又一天被我这样花掉了，sigh……

The Game of Life

介绍

　　与其说是game，其实它更像是一个simulation，在1970年由英国数学家J. H. Conway提出的。The Game of Life的规则很简单：假设有一个无边界的矩形网格（我更喜欢把它称作宇宙，或者universe），这个矩形网格中的每个单元可被一个有机体占据（同样地，我更爱细胞这个词，或者cell）。被占据的单元称为活的（alive），未占据的单元称为死的（dead）。哪一个单元是活的要根据其周围活的邻居单元（neighbor）的数目而一代代（generation）地发生变化，规则如下：

1. 给定单元的邻居是与它在垂直、水平或对角方向上相接的8个单元。
2. 如果一个单元是活的，但没有邻居单元是活的，或者仅有一个邻居单元是活的，则在下一代，此单元就会因孤独而死亡。
3. 如果一个单元是活的，且有4个或4个以上的邻居单元也是活的，则在下一代，此单元会因为拥塞而死亡。
4. 一个活的单元，如果具有2个或3个或的邻居单元，则此单元在下一代仍是活的。
5. 如果一个单元是死的，则在下一代，如果它不多不少刚好有3个邻居单元是活的，则此单元变成活的。所有其他死的单元在下一代仍是死的。
6. 所有的出生和死亡都刚好在同一时间发生，因此正在死亡的单元有助于另一个单元的出生，但它不能通过减少阻塞而组织其他单元的死亡；正在出生的单元也不能保护或杀死上一代中活着的单元。

　　以上是我从我第一次看到The Game of Life的书——Data structures and Program Design In C++——里面节选出来的，除了括号里面的字，因为我比较喜欢那样的称呼^_^。

　　第（6）点可能有点怪怪的，举个例子说。假如下面的×代表一个alive的cell，◎、①代表一个dead的cell，那么对于以下这样的情况，◎的位置的cell因为刚好有3个neighbors，将会变活。但这不会影响到旁边的标记为①的cell的生死，①位置的cell只有2个neighbors，没办法继续存活。

　◎①
×××

　　就是这么简单的6条规则（我承认我的那本书上写得有点长气），但这么简单的几条规则确可以变化出相当复杂的过程。不同的初始宇宙配置（就是第一代宇宙的模样），演变下去规模可以变得十分庞大复杂，也可能慢慢的变得稳定，有的甚至灭绝（全部细胞都挂了――b）。

　　在The Game of Life发明后不久，Martin Gardner就在Scientific American的专栏里面对它进行了讨论，很多人为之着迷。

　　没有理由的感叹一下，The Game of Life，会不会就是我们的现实生活的一个写照呢？在我们活着的这样的复杂不堪的世界里面，说不定只有几条十分简单的规则在不停运转着。

　　只是我们还没有发现（或者说没完全发现）The Game of Our Life的规则而已。

当上帝的助手——实现The Game of Life

　　Conway给我们定下了6条规则而把宇宙交给了我们。我第一次实现The Game of Life（好长……后面简称tgol好了）是在C++上，大约是2年前的事情了吧。最近无意中在emacs里面再次发现了它的身影，又正逢我在学习python，正好拿来练习练习。

　　于是好几个版本的tgol（在我编写的时候，tgol被我称做Life Game）诞生了，限界不限界的都有，到今天成功进化到了1.3.2版（其实我不太会定版本号――b，下载的链接可以在文章末尾找到），学到的还是不少的。

• 有界还是无界？

　　在Conway设定的tgol里面的universe本来是无界的。由于边界的原因，有界的结果跟无界的有时是大相径庭的。主要原因在于有界的宇宙，细胞一旦到边界了就无法继续发展，因而边界外也不会产生活细胞对边界内的universe进行干涉。

　　绝对不会是最有效，但绝对是最简单的实现有界tgol的算法就是一个矩形数组（在python里面就是list的嵌套），然后从最开始遍历到最后。对于边界的cell可以加入额外的监视哨消除特殊性，然后就没什么好说的了。

　　而对于无界tgol，用这样的算法实现会相对复杂一点。我们或许可以申请一个相当大的数组去表达我们的宇宙，但我们并没办法阻止细胞们的增长，再大的数组也可能容不下我们的细胞。而且随着数组的增长，遍历整个数组的时间会变得越来越长。第一版的tgol就是用这样的算法实现的，结果前100多200代耗时还忍受得了，200代之后就变得蜗牛一样了。

　　这似乎是个解决的办法：随时缩少数组的规模。这对于某些增大了然后又缩小的细胞社会（society）似乎是有效的。缩少数组的规模并非意味限制宇宙的大小，很简单的例子是，用一个100×100的数组去表示一个只有1个细胞的宇宙，很明显是小题大做，一个3×3的数组就足够了，10000次遍历和9次遍历差别可是很大的哦^_^。

　　然而事实上这种做法没什么效果，首先是，细胞社会不会一直缩小下去，很可能过两三代以后又开始变大了，虽然确实缩小了遍历次数，然而对于整个运行来说，显得苍白无力；其次是，有些society会一直膨胀不缩小，在我发布的1.3.2版里面的”five block”就是很典型的例子。

　　对于用数组存储universe的这条路径，我还构思过一个方法，然而没有用来实现：只对需要计算的cell进行计算。所谓的“需要计算的cell”，就是存在变活或变死可能性的cell。很明显一个没有neighbor的dead cell是不可能变活的，存在变化的只有仍然alive的cell以及它们的邻居。为了用这种方法，必须对这些需要计算的细胞进行额外的记录（不然还是得从头遍历一次来确认）。在一次计算结束后，剔除无法存活的细胞，对剩下的细胞继续进行计算，这样遍历的次数就会大大的降低了。

　　这跟稀疏矩阵十分相似。

• 三元组还是十字链表？

　　作为稀疏矩阵的两种常用实现方法，我认为三元组比较直观，十字链表比较灵活。

　　而应用在tgol又是怎样的情况呢？

　　为了索引某个位置的细胞是否存活，查找是必须的。在理想的情况里面，对于三元组，一次索引就意味着平均要花上０.5(number_of_cells+1)次的比较。相比起来，十字链表需要的次数要少一些：假设细胞们很整齐的排成m×n，那么要索引到一个细胞平均起来需要0.5(m+n+2)次（行平均次数＋列平均次数）比较。如果进一步假设m=n=sqrt(number_of_cells)，平均就要花上(sqrt(number_of_cells)+1)次的比较。

　　而要决定一个细胞存亡的命运，必须进行9次索引操作（8次用于邻居，1次用于自身），合起来一共是9×number_of_cells次索引。

　　看得出用十字链表效率上是比较高的，主要原因应该是出于十字链表本身可按行按列遍历。当然换来的是空间上的损耗，不过从性能提升的角度来看，那些损耗是“物超所值”的。

• Cross List? Hash table?

　　哈希表的使用完全归功于我的tgol启蒙书——还是开头我说的那本。实际上，v1.3.2的实现就是用哈希表而不是十字链表实现的。事实上我没用十字链表实现过tgol，因为在我想到十字链表实现法之后的不久我就再次拜读了启蒙书去了，并发现hash table的效率似乎更优于cross list。

　　Hash table以其O(1)的时间复杂度著名，主要原因在于它在实现上还是一个数组，要访问hash table里面的元素就跟访问数组一样——直接定位，即使有冲突的问题存在，但无论是顺序hash table还是链式hash table都有一个有效的解决方法（我个人更欣赏链式的）。

　　那么选择hash table的原因就很明显了：O(1)的时间复杂度。这意味着，对于每个细胞，很多情况下1次查找就可以索引出结果了。尽管hash table中的冲突现象难以消除，但对于一个合理大小的hash table配合一个合理的hash函数来说，冲突是比较少的。

　　这样效率上的优势就很明显了，hash table的实现，可以把索引需要的查找次数控制在次低（仅仅从指定cell的查找次数方面评价，正牌的数组绝对是大哥，随机索引一次完成。而对于有一定规模的数据，hash table的冲突是很难避免的，而解决冲突必定会引入更多次的索引）。

---

　　回头一看发现自己已经写了2千多字了……希望自己写的不是些无用的废话吧。

　　刚刚回看自己的tgol代码，发现有些小细节还可以改进，代码就先不公开贴上来了，等我再写好点先……由于1.3.2里面用到了windows的API的关系，拙作暂时只能运行在windows系统上，可以在这里下载用py2exe发布好的win32-binary。1.3.2还只是windows console下的字符版，以后有时间，或许会利用python再写一个gui版吧。

　　感谢Conway的The Game of Life给我带来的欢乐。