如何设计一门语言（十二）——设计可扩展的类型
在思考怎么寫這一篇文章的時候，我又想到了以前討論正交概念的事情。如果一個系統被設計成正交的，他的功能擴展起來也可以很容易的保持質量這是沒錯的，但是對于每一個單獨給他擴展功能的個體來說，這個系統一點都不好用。所以我覺得現在的語言被設計成這樣也是有那么點道理的。就算是設計Java的那誰，他也不是傻逼，那為什么Java會被設計成這樣？我覺得這跟他剛開始想讓金字塔的底層程序員也可以順利使用Java是有關系的。
?
難道好用的語言就活該不好擴展碼？實際上不是這樣的，但是這仍然是上面那個正交概念的問題。一個容易擴展的語言要讓你覺得好用，首先你要投入時間來學習他。如果你想簡單的借鑒那些不好擴展的語言的經驗（如Java）來在短時間內學會如何使用一個容易擴展的語言（如C++/C#）——你的出發點就已經投機了。所以這里有一個前提值得我再強調一次——首先你需要投入時間去學習他。
?
正如我一直在群里說的："C++需要不斷的練習——vczh"。要如何練習才能讓自己借助語言做出一個可擴展的架構呢？先決條件就是，當你在練習的時候，你必須是在練習如何實現一個從功能上就要求你必須保證他的可擴展性的系統，舉個例子，GUI庫就是其中的一類。我至今認為，學會實現一個GUI庫，比通過練習別的什么東西來提高自己的能力來講，簡直就算一個捷徑了。
?
那么什么是擴展呢？簡單的來講，擴展就是在不修改原有代碼的情況下，僅僅通過添加新的代碼，就可以讓原有的功能適應更多的情況。一般來講，擴展的主要目的并不是要增加新的功能，而是要只增加新代碼的前提下修改原有的功能。譬如說原來你的系統只支持SQLServer，結果有一天你遇到了一個喜歡Oracle的新客戶，你要把東西賣給他，那就得支持Oracle了吧。但是我們知道，SQLServer和Oracle在各種協議（asp.net、odbc什么的）上面是有偏好的，用DB不喜歡的協議來連接他的時候bug特別多，這就造成了你又可能沒辦法使用單一的協議來正確的使用各種數據庫，因此擴展的這個擔子就落在你的身上了。當然這種系統并不是人人都要寫，我也可以換一個例子，假如你在設計一個GPU集群上的程序，那么這個集群的基礎架構得支持NVidia和AMD的顯卡，還得支持DirectCompute、Cuda和OpenCL。然而我們知道，OpenCL在不同的平臺上，有互不兼容的不同的bug，導致你實際上并不可能僅僅通過一份不變的代碼，就充分發揮OpenCL在每一個平臺上的最佳狀態……現實世界的需求真是orz（OpenCL在windows上用AMD卡定義一個struct都很容易導致崩潰什么的，我覺得這根本不能用）……
?
在語言里面談擴展，始終都離不開兩個方面：編譯期和運行期。這些東西都是用看起來很像pattern matching的方法組織起來的。如果在語言的類型系統的幫助下，我們可以輕松做出這樣子的架構，那這個語言就算有可擴展的類型了。
?
?
這個其實已經被人在C++和各種靜態類型的函數式語言里面做爛了。簡單的來講，C++處理這種問題的方法就是提供偏特化。可惜C++的偏特化只讓做在class上面，結果因為大家對class的誤解很深，順便連偏特化這種比OO簡單一萬倍的東西也誤解了。偏特化不允許用在函數上，因為函數已經有了重載，但是C++的各種標準在使用函數來擴展類型的時候，實際上還是當他是偏特化那么用的。我舉個例子。
?
C++11多了一個foreach循環，寫成for(auto x : xs) { … }。STL的類型都支持這種新的for循環。C++11的for循環是為了STL的容器設計的嗎？顯然不是。你也可以給你自己寫的容器加上for循環。方法有兩種，分別是：1、給你的類型T加上T::begin和T::end兩個成員函數；2、給你的類型T實現begin(T)和end(T)兩個全局函數。我還沒有去詳細考證，但是我認為缺省的begin(T)和end(T)全局函數就是去調用T::begin和T::end的，因此for循環只需要認begin和end兩個全局函數就可以了。
?
那自己的類型怎么辦呢？當然也要去重載begin和end了。現在全局函數沒有重載，因此寫出來大概是：
template<typenameT> auto begin(constT& t)->decltype(t.begin()) { returnt.begin(); }
template<typenameT> my_iterator<T> begin(constmy_container<T>& t);
template<typenameT> my_range_iterator<T> begin(pair<T, T> range);
?
如果C++的函數支持偏特化的話，那么上面這段代碼就會被改成這樣，而且for循環也就不去找各種各樣的begin函數了，而只認定那一個std::begin就可以了：
template<typenameT> auto begin(constT& t)->decltype(t.begin()) { returnt.begin(); }
template<typenameT> my_iterator<T> begin< my_container<T>>(constmy_container<T>& t);
template<typenameT> my_range_iterator<T> begin< pair<T, T>>( constpair<T, T>& range);
?
為什么要偏特化呢？因為這至少保證你寫出來的begin函數跟for函數想要的begin函數的begin函數的簽名是相容的（譬如說不能有兩個參數之類的）。事實上C++11的for循環剛開始是要求大家通過偏特化一個叫做std::range的類型來支持的，這個range類型里面有兩個static函數，分別叫begin和end。后來之所以改成這樣，我猜大概是因為C++的每一個函數重載也可以是模板函數，因此就不需要引入一個新的類型了，就讓大家去重載好了。而且for做出來的時候，C++標準里面還沒有concept，因此也沒辦法表達"對于所有可以循環的類型T，我們都有std::range<T>必須滿足這個叫做range_loopable<T>的concept"這樣的前置條件。
?
重載用起來很容易讓人走火入門，很多人到最后都會把一些僅僅看起來像而實際上語義完全不同的東西用重載來表達，函數的參數連相似性都沒有。其實這是不對的，這種時候就應該把函數改成兩個不同的名字。假如當初設計C++的是我，那我一定會把函數重載干掉，然后允許人們對函數進行偏特化，并且加上concept。既然std::begin已經被定義為循環的輔助函數了，那么你重載一個std::begin，他卻不能用來循環（譬如說有兩個參數什么的），那有意義嗎？完全沒有。
?
這種例子還有很多，譬如如何讓自己的類型可以被<<到wcout的做法啦，boost的那個serialization框架，還有各種各樣的庫，其實都利用了相同的思想——對類型做編譯期的擴展，使用一些手段使得在不需要修改原來的代碼的前提下，就可以讓編譯器找到你新加進去的函數，從而使得調用的寫法不用發生變化就可以對原有的功能支持更多的情況。至少我們讓我們自己的類型支持for循環就不需要翻開std::begin的代碼把我們的類型寫進去，只需要在隨便什么空白的地方重載一個std::begin就可以了。這就是一個很好地體現。C++的標準庫一直在引導大家正確設計一個可擴展的架構，可惜很多人都意識不到這一點，為了自己那一點連正確性都談不上的強迫癥，放棄了很多東西。
?
很多靜態類型的函數式語言使用concept來完成上述的工作。當一個concept定義好了之后，我們就可以通過對concept的實現進行偏特化來讓我們的類型T滿足concept的要求，來讓那些調用這個concept的泛型代碼，可以在處理的對象是T的時候，轉而調用我們提供的實現。Haskell就是一個典型的例子，一個sort函數必然要求元素是可比較的，一個可以比較的類型定義為實現了Ord這個type class的類型。所以你只要給你自己的類型T實現Ord這個type class，那sort函數就可以對T的列表進行排序了。
?
對于C++和C#這種沒有concept或者concept不是主要概念的語言里面，對類型做靜態的擴展只需要你的類型滿足"我可以這么這么干"就可以了。譬如說你重載一個begin和end，那你的類型就可以被foreach；你給你的類型實現了operator<等函數，那么一個包含你的類型的容器就可以被sort；或者C#的只要你的類型T<U>有一大堆長得跟System.Linq.Enumerable里面定義的擴展函數一樣的擴展函數，那么Linq的神奇的語法就可以用在你的類型上等等。這跟動態類型的"只要它長的像鴨子，那么它就是鴨子"的做法有異曲同工之效。如果你的begin函數的簽名沒寫對，編譯器也不會屌你，直到你對他for的時候編譯器才會告訴你說你做錯了。這跟很多動態類型的語言的很多錯誤必須在運行的時候才發現的性質也是類似的。
?
Concept對于可靜態擴展的類型的約束，就如同類型對于邏輯的約束一樣。沒有concept的C++模板，就跟用動態類型語言寫邏輯一樣，只有到用到的那一刻你才知道你到底寫對了沒有，而且錯誤也會爆發在你使用它的地方，而不是你定義它的地方。因此本著編譯器幫你找到盡可能多的錯誤的原則，C++也開始有concept了。
?
C#的擴展方法用在Linq上面，其實編譯器也要求你滿足一個內在的concept，只是這個概念無法用C#的語法表達出來。所以我們在寫Linq Provider的時候也會有同樣的感覺。Java的interface都可以寫缺省實現了，但是卻沒有靜態方法。這就造成了我們實際上無法跟C++和C#一樣，在不修改原有代碼的前提下，讓原有的功能滿足更多的情況。因為C#的添加擴展方法的情況，到了Java里面就變成讓一個類多繼承自一個interface，必須修改代碼了。Java的這個功能特別的雞肋，不知道是不是他故意想跟C#不一樣才設計成這個樣子的，可惜精華沒有抄去，卻抄了糟粕。
?
?
自從Java吧靜態類型和面向對象捆綁在一起之后，業界對"運行期對類型的擴展"這個主題思考了很多年，甚至還出了一本著作叫《設計模式》，讓很多人捧為經典。大家爭先恐后的學習，而效果卻不怎么樣。這是因為《設計模式》不好嗎？不是。這是因為靜態類型和面向對象捆綁在一起之后，設計一個可擴展的架構就很難嗎？也不是。真正的原因是，Java設計（好像也是抄的Simular？我記不太清楚了）的虛函數把這個問題的難題提升了一個等級。
?
用正確的概念來理解問題可以讓我們更容易的掌握問題的本質。語言是有魔力的，習慣說中文的人，思考方式都跟中國人差不多。習慣說英語的人，思考方式都跟美國人差不多。因此習慣了使用C++/C#/Java的人，他們對于面向對象的想法其實也是差不多的。這是人類的天性。盡管大家鼓吹說語言只是工具，我們應該掌握方法論什么的，但是這就跟要求男人面對一個萌妹紙不勃起一樣，違背了人類的本性，難度簡直太高了。于是我今天從虛函數和Visitor模式講起，告訴大家為什么虛函數的這種形式會讓"擴展的時候不修改原有的代碼"變難。
?
絕大多數的系統的擴展，都可以最后化簡（這并不要求你非得這么做）為"當它的類型是這個的時候你就干那個"的這么件事。對于在編譯的時候就已經知道的，我們可以用偏特化的方法讓編譯器在生成代碼的時候就先搞好。對于運行的時候，你拿到一個基類（其實為什么一定要有基類？應該有的是interface！參見上一篇文章——刪減語言的功能），那如何O(1)時間復雜度（這里的n指的是所有跟這次跳轉有關系的類型的數量）就跳轉到你想要的那個分支上去呢？于是我們有了虛函數。
?
靜態的擴展用的是靜態的分派，于是編譯器幫我們把函數名都hardcode到生成的代碼里面。動態的類型用的是動態的分派，于是我們得到的當然是一個相當于函數指針的東西。于是我們會把這個函數指針保存在從基類對象可以O(1)訪問到的地方。虛函數就是這么實現的，而且這種類型的分派必須要這么實現的。但是，寫成代碼就一定要寫程序函數嗎？
?
其實本來沒什么理由讓一個語言（或者library）長的樣子必須有提示你他是怎么實現的功能。關心太多容易得病，執著太多心生痛苦啊。所以好好的解決問題就好了。至于原理是什么，下了班再去關心。估計還有一些人不明白為什么不好，我就舉一個通俗的例子。我們都知道dynamic_cast的性能不怎么樣，虛函數用來做if的性能要遠遠比dynamic_cast用來做if的性能好得多。因此下面所有的答案都基于這個前提——要快，不要dynamic_cast！
?
?
好了，現在我們的任務是，拿到一個HTML，然后要對他做一些功能，譬如說把它格式化成文本啦，看一下他是否包含超鏈接啦等等。假設我們已經解決HTML的語法分析問題，那么我們會得到一顆靜態類型的語法樹。這棵語法樹如無意外一定是長下面這個樣子的。另外一種選擇是存成動態類型的，但是這跟面向對象無關，所以就不提了。
?
classDomBase
{
public:
????virtual ~DomBase();
?
????staticshared_ptr<DomBase> Parse(constwstring& htmlText);
};
?
classDomText : publicDomBase{};
classDomImg : publicDomBase{};
classDomA : publicDomBase{};
classDomDiv : publicDomBase{};
......
?
HTML的tag種類繁多，大概有那么上百個吧。那現在我們要給他加上一個格式化成字符串的功能，這顯然是一個遞歸的算法，先把sub tree一個一個格式化，最后組合起來就好了。可能對于不同的非文本標簽會有不同的格式化方法。代碼寫出來就是這樣——基本上是唯一的作法：
?
classDomBase
{
public:
????virtual ~DomBase();
????staticshared_ptr<DomBase> Parse(constwstring& htmlText);
?
????virtualvoidFormatToText(ostream& o); // 默認實現，把所有subtree的結果合并
};
?
classDomText : publicDomBase
{
public:
????voidFormatToText(ostream& o); // 直接輸出文字
};
classDomImg : publicDomBase
{
public:
????voidFormatToText(ostream& o); // 輸出img的tag內容
};
// 其它實現略
classDomA : publicDomBase{};
classDomDiv : publicDomBase{};
?
這已經構成一個基本的HTML的Dom Tree了。現在我提一個要求如下，要求在不修改原有代碼只添加新代碼的情況下，避免dynamic_cast，實現一個考察一顆Dom Tree是否包含超鏈接的功能。能做嗎？
?
無論大家如何苦思冥想，答案都是做不到。盡管這么一看可能覺得這不是什么大事，但實際上這意味著：你無法通過添加模塊的方式來給一個已知的Dom Tree添加"判斷它是否包含超鏈接"的這個功能。有的人可能會說，那把它建模成動態類型的樹不就可以了？這是沒錯，但這實際上有兩個問題。第一個是著顯著的增加了你的測試成本，不過對于充滿了廉價勞動力的web行業來說這好像也不是什么大問題。第二個更加本質——HTML可以這么做，并不代表所有的東西都可以裝怎么做事吧。
?
那在靜態類型的前提下，要如何解決這個問題呢？很久以前我們的《設計模式》就給我們提供了visitor模式，用來解決這樣的問題。如果把這個Dom Tree修改成visitor模式的代碼的話，那原來FormatToText就會變成這個樣子：
?
classDomText;
classDomImg;
classDomA;
classDomDiv;
?
classDomBase
{
public:
????virtual ~DomBase();
????staticshared_ptr<DomBase> Parse(constwstring& htmlText);
?
????classIVisitor
????{
????public:
????????virtual ~IVisitor();
?
????????virtualvoid Visit(DomText* dom) = 0;
????????virtualvoid Visit(DomImg* dom) = 0;
????????virtualvoid Visit(DomA* dom) = 0;
????????virtualvoid Visit(DomDiv* dom) = 0;
????};
?
????virtualvoid Accept(IVisitor* visitor) = 0;
};
?
classDomText : publicDomBase
{
public:
????void Accept(IVisitor* visitor)override
????{
????????visitor->Visit(this);
????}
};
classDomImg : publicDomBase
{
public:
????void Accept(IVisitor* visitor)override
????{
????????visitor->Visit(this);
????}
};
classDomA : publicDomBase
{
public:
????void Accept(IVisitor* visitor)override
????{
????????visitor->Visit(this);
????}
};
classDomDiv : publicDomBase
{
public:
????void Accept(IVisitor* visitor)override
????{
????????visitor->Visit(this);
????}
};
?
classFormatToTextVisitor : publicDomBase::IVisitor
{
private:
????ostream& o;
public:
????FormatToTextVisitor(ostream& _o)
????????:o(_o)
????{
?
????}
?
????void Visit(DomText* dom){} // 直接輸出文字
????void Visit(DomImg* dom){} // 輸出img的tag內容
????void Visit(DomA* dom){} // 默認實現，把所有subtree的結果合并
????void Visit(DomDiv* dom){} // 默認實現，把所有subtree的結果合并
?
????staticvoid Evaluate(DomBase* dom, ostream& o)
????{
????????FormatToTextVisitor visitor(o);
????????dom->Accept(&visitor);
????}
};
?
看起來長了不少，但是我們驚奇地發現，這下子我們可以通過提供一個Visitor，來在不修改原有代碼的前提下，避免dynamic_cast，實現判斷一顆Dom Tree是否包含超鏈接的功能了！不過別高興得太早。這兩種做法都是有缺陷的。
?
虛函數的好處是你可以在不修改原有代碼的前提下添加新的Dom類型，但是所有針對Dom Tree的操作緊密的耦合在了一起，并且邏輯還分散在了每一個具體的Dom類型里面。你添加一個新功能就要修改所有的DomBase的子類，因為你要給他們都添加你需要的虛函數。
?
Visitor的好處是你可以在不修改原有代碼的前提下添加新的Dom操作，但是所有的Dom類型卻緊密的耦合在了一起，因為IVisitor類型要包含所有DomBase的子類。你每天加一個新的Dom類型就得修改所有的操作——即IVisitor的接口和所有的具體的Visitor。而且還有另一個問題，就是虛函數的默認實現寫起來比較鳥了。
?
所以這兩種做法都各有各的耦合。
?
?
看了上面對于虛函數和Visitor的描述，大家大概知道了虛函數和Visitor其實都是同一個東西，只是各有各的犧牲。因此他們是可以互相轉換的——大家通過不斷地練習就可以知道如何把一個解法表達成虛函數的同時也可以表達成Visitor了。但是Visitor的代碼又臭又長，所以下面我只用虛函數來寫，懶得敲太多代碼了。
?
虛函數只有一個this參數，所以他是single dynamic dispatch。對于碰撞系統來說，不同種類的物體之間的碰撞代碼都是不一樣的，所以他有兩個"this參數"，所以他是multiple dynamic dispatch。在接下來的描述會發現，只要遇上了multiple dynamic dispatch，在現有的架構下避免dynamic_cast，無論你用虛函數還是visitor模式，做出來的solution全都是不管操作有沒有偶合在一起，反正類型是肯定會偶合在一起的。
?
現在我們面對的問題是這樣的。在物理引擎里面，我們經常需要判斷兩個物體是否碰撞。但是物體又不只是三角形組成的多面體，還有可能是標準的球形啊、立方體什么的。因此這顯然還是一個繼承的結構，而且還有一個虛函數用來判斷一個對象跟另一個對象是否碰撞：
?
classGeometry
{
public:
????virtual ~Geometry();
?
????virtualbool IsCollided(Geometry* second) = 0;
};
?
classSphere : publicGeometry
{
public:
????bool IsCollided(Geometry* second)override
????{
????????// then ???
????}
};
?
classCube : publicGeometry
{
public:
????bool IsCollided(Geometry* second)override
????{
????????// then ???
????}
};
?
classTriangles : publicGeometry
{
public:
????bool IsCollided(Geometry* second)override
????{
????????// then ???
????}
};
?
大家猛然發現，在這個函數體里面也不知道second到底是什么東西。這意味著，我們還要對second做一次single dynamic dispatch，這也就意味著我們需要添加新的虛函數。而且這不是一個，而是很多。他們分別是什么呢？由于我們已經對first（也就是那個this指針）dispatch過一次了，所以我們要把dispatch的結果告訴second，要讓它在dispatch一次。所以當first分別是Sphere、Cube和Triangles的時候，對second的dispatch應該有不同的邏輯。因此很遺憾的，代碼會變成這樣：
?
classSphere;
classCube;
classTriangles;
?
classGeometry
{
public:
????virtual ~Geometry();
?
????virtualbool IsCollided(Geometry* second) = 0;
????virtualbool IsCollided_Sphere(Sphere* first) = 0;
????virtualbool IsCollided_Cube(Cube* first) = 0;
????virtualbool IsCollided_Triangles(Triangles* first) = 0;
};
?
classSphere : publicGeometry
{
public:
????bool IsCollided(Geometry* second)override
????{
????????returnsecond->IsCollided_Sphere(this);
????}
?
????bool IsCollided_Sphere(Sphere* first)override
????{
????????// Sphere * Sphere
????}
?
????bool IsCollided_Cube(Cube* first)override
????{
????????// Cube * Sphere
????}
?
????bool IsCollided_Triangles(Triangles* first)override
????{
????????// Triangles * Sphere
????}
};
?
classCube : publicGeometry
{
public:
????bool IsCollided(Geometry* second)override
????{
????????returnsecond->IsCollided_Cube(this);
????}
?
????bool IsCollided_Sphere(Sphere* first)override
????{
????????// Sphere * Cube
????}
?
????bool IsCollided_Cube(Cube* first)override
????{
????????// Cube * Cube
????}
?
????bool IsCollided_Triangles(Triangles* first)override
????{
????????// Triangles * Cube
????}
};
?
classTriangles : publicGeometry
{
public:
????bool IsCollided(Geometry* second)override
????{
????????returnsecond->IsCollided_Triangles(this);
????}
?
????bool IsCollided_Sphere(Sphere* first)override
????{
????????// Sphere * Triangles
????}
?
????bool IsCollided_Cube(Cube* first)override
????{
????????// Cube * Triangles
????}
?
????bool IsCollided_Triangles(Triangles* first)override
????{
????????// Triangles * Triangles
????}
};
?
大家可以想象，如果還有第三個Geometry參數，那還得給Geometry加上9個新的虛函數，三個子類分別實現他們，加起來我們一共要寫13個虛函數（3^0 + 3^1 + 3^2）39個函數體（3^1 + 3^2 + 3^3）。
?
?
為什么運行期的類型擴展就那么多翔，而靜態類型的擴展就不會呢？原因是靜態類型的擴展是寫在類型的外部的。假設一下，我們的C++支持下面的寫法：
?
bool IsCollided(switchGeometry* first, switchGeometry* second);
bool IsCollided(caseSphere* first, caseSphere* second);
bool IsCollided(caseSphere* first, caseCube* second);
bool IsCollided(caseSphere* first, caseTriangles* second);
bool IsCollided(caseCube* first, caseSphere* second);
bool IsCollided(caseCube* first, caseCube* second);
bool IsCollided(caseCube* first, caseTriangles* second);
bool IsCollided(caseTriangles* first, caseSphere* second);
bool IsCollided(caseTriangles* first, caseCube* second);
bool IsCollided(caseTriangles* first, caseTriangles* second);
?
最后編譯器在編譯的時候，把所有的"動態偏特化"收集起來——就像做模板偏特化的時候一樣——然后替我們生成上面一大片翔一樣的虛函數的代碼，那該多好啊！
?
Dynamic dispatch和解耦這從一開始以來就是一對矛盾，要徹底解決他們其實是很難的。雖然上面的作法看起來類型和操作都解耦了，可實際上這就讓我們失去了本地代碼的dll的功能了。因為編譯器不可能收集到以后才動態鏈接進來的dll代碼里面的"動態偏特化"的代碼對吧。不過這個問題對于像CLR一樣基于一個VM一樣的支持JIT的runtime來講，這其實并不是個大問題。而且Java的J2EE也好，Microsoft的Enterprise Library也好，他們的IoC（Inverse of Control）其實也是在模擬這個寫法。我認為以后靜態類型語言的方向，肯定是朝著這個路線走的。盡管這些概念再也不能被直接map到本地代碼了，但是這讓我們從語義上的耦合中解放了出來，對于寫需要穩定執行的大型程序來說，有著莫大的助。
from: http://www.cnblogs.com/geniusvczh/p/3416833.html
總結
以上是生活随笔為你收集整理的如何设计一门语言（十二）——设计可扩展的类型的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 如何设计一门语言（十一）——删减语言的功
- 下一篇： 伴随我成长的编程书