完成C++不能做到的事 - Visitor模式
昨晚做完了一個非常困難的任務並送給美國同事Review，因此今天只需要根據他們提出的意見適當修改代碼並提交，一周的任務就完成了。剩下的兩三天裡，我就可以有一些空余的時間看看其它資料來繼續充實自己了。
打開Review Board，可以看到我的代碼已經被標記為可以提交，但是下面所留的注解引起了我的注意：
“Great job! With this solution, we can start our integration work and perform testing earlier. One thing is that we have used several “instance of” in the overrided function. That’s double dispatch, an obvious signature for using Visitor pattern. We can switch to that pattern in our future work.”
Visitor模式我知道，但是Double Dispatch是什麼意思？我打開了搜索引擎，找了幾篇有關Double Dispatch的介紹性文章開始讀了起來。
Double Dispatch
當然，對Double Dispatch描述最為清晰和准確的還是在Wikipedia上：
In software engineering, double dispatch is a special form of multiple dispatch, and a mechanism that dispatches a function call to different concrete functions depending on the runtime types of two objects involved in the call. In most object-oriented systems, the concrete function that is called from a function call in the code depends on the dynamic type of a single object and therefore they are known as single dispatch calls, or simply virtual function calls.
而在該段文字的最後，我看到了一個再熟悉不過的名詞“virtual function”。一看到這個詞，我腦中就開始回憶對虛函數進行調用的步驟：在調用虛函數的時候，C++運行時將首先查找對象所對應的虛函數表，然後根據虛函數表中所記錄的地址來調用相應的虛函數實現。由於虛函數表是與類型相關聯的，因此對虛函數進行調用所執行的邏輯就與對象本身的類型相關。
而Double Dispatch則需要和參與函數調用的兩個對象相關。於是我想：那通過為類型添加一個函數重載，不就可以實現Double Dispatch了麼？我打開Visual Studio，並在其中寫下了如下的代碼：
1 // 普通汽車，折扣為0.03
2 class Vehicle
3 {
4 public:
5 virtual double GetBaseDiscountRate() { return 0.03; }
6 };
7
8 // 由於是奔馳特銷商，因此可以得到更大的折扣
9 class Benz : public Vehicle
10 {
11 public:
12 virtual double GetBaseDiscountRate() { return 0.06; }
13 };
14
15 // 普通的銷售人員，只能按照公司規定的折扣進行銷售
16 class Sales
17 {
18 public:
19 virtual double GetDiscountRate(Vehicle& vehicle)
20 {
21 return vehicle.GetBaseDiscountRate();
22 }
23
24 virtual double GetDiscountRate(Benz& benz)
25 {
26 return benz.GetBaseDiscountRate();
27 }
28 };
29
30 // 銷售經理，可以針對奔馳提供額外的優惠
31 class SalesManager : public Sales
32 {
33 public:
34 virtual double GetDiscountRate(Vehicle& vehicle)
35 {
36 return vehicle.GetBaseDiscountRate();
37 }
38
39 virtual double GetDiscountRate(Benz& benz)
40 {
41 return benz.GetBaseDiscountRate() * 1.1;
42 }
43 };
44
45 int _tmain(int argc, _TCHAR* argv[])
46 {
47 // 有兩輛車需要銷售，一輛是普通轎車，而另一輛則是奔馳
48 Vehicle& vehicle = Vehicle();
49 Vehicle& benz = Benz();
50
51 // 向普通銷售詢問這兩輛車的折扣
52 Sales* pSales = new Sales();
53 double rate = pSales->GetDiscountRate(vehicle);
54 cout << "Sales: The rate for common vehicle is: " << rate << endl;
55 rate = pSales->GetDiscountRate(benz);
56 cout << "Sales: The rate for benz is: " << rate << endl;
57
58 // 向銷售經理詢問這兩輛車的折扣
59 SalesManager* pSalesManager = new SalesManager();
60 rate = pSalesManager->GetDiscountRate(vehicle);
61 cout << "Sales Manager: The rate for common vehicle is: " << rate << endl;
62 rate = pSalesManager->GetDiscountRate(benz);
63 cout << "Sales Manager: The rate for benz is: " << rate << endl;
64
65 return 0;
66 }
點擊運行，答案卻不是我想的那樣：
啊，銷售經理並沒有提供額外的折扣。這可是個大麻煩。啟動Visual Studio的調試功能，我看到了語句“pSalesManager->GetDiscountRate(benz)”所調用的是SalesManager類中定義的為普通汽車所定義的重載：
1 class SalesManager : public Sales
2 {
3 public:
4 virtual double GetDiscountRate(Vehicle& vehicle) <----傳入的參數的運行時類型是Benz，卻調用了為Vehicle定義的重載
5 {
6 return vehicle.GetBaseDiscountRate();
7 }
8 ……
9 };
難道我對函數重載的理解不對？在搜索引擎中鍵入“C++ overload resolution”，我打開了C++標准中有關函數重載決議的講解。其開始的一段話就給了我答案：
In order to compile a function call, the compiler must first perform name lookup, which, for functions, may involve argument-dependent lookup, and for function templates may be followed by template argument deduction. If these steps produce more than one candidate function, then overload resolution is performed to select the function that will actually be called.
哦，對！函數重載決議是在編譯時完成的。也正因為我們傳入的是Vehicle類型的引用，編譯器並沒有辦法知道在運行時傳入GetDiscountRate()這個函數的參數到底是Vehicle實例還是Benz實例，因此編譯器只可能選擇調用接受Vehicle類型引用的重載。如果傳入參數benz的類型不再是Vehicle的引用，而是更具體的Benz的引用，那麼編譯器將會正確地決定到底其所需要調用的函數：
但這就不再是根據參數的類型動態決定需要調用的邏輯了，也就不再是Double Dispatch了。要如何達到這種效果呢？我苦苦地思索著。
“你在想什麼？”身邊的同事遞給我今天公司派發的水果，一邊吃著一邊問我。我就把我剛剛寫出的程序以及我現在正在考慮的問題告訴了他。
“既然你要動態決定需要調用的邏輯，那麼就把這些邏輯放到動態運行的地方去啊，比如說放到你那些汽車類裡面然後暴露一個虛函數，就可以根據所傳入的汽車類型決定該汽車所需要使用的折扣率了啊。”
“哦對”，我恍然大悟。C++在運行時動態決議的基本方法就是虛函數，也就是一種Single Dispatch，如果依次在對象和傳入參數上連續調用兩次虛函數，那麼它不就是Double Dispatch了麼？在銷售汽車這個例子中，我希望同時根據銷售人員的職稱和所銷售的汽車類型一起決定需要執行的邏輯。那麼我們首先需要通過Sales類型的指針調用一個虛函數，從而可以根據銷售人員的實際類型來決定其在銷售時所需要執行的實際邏輯。而在執行這些邏輯的過程中，我們還可以繼續調用傳入參數實例上定義的虛函數，就可以根據傳入參數的類型來決定需要執行的邏輯了！
說做就做。我在Vehicle類中添加一個新的虛函數GetManagerDiscountRate()，以允許SalesManager類的函數實現中調用以獲得銷售經理所能拿到的折扣，並在Benz類中重寫它以返回針對奔馳的特有折扣率。而在Sales以及SalesManager類的實現中，我們則需要分別調用GetBaseDiscountRate()以及新的GetManagerDiscountRate()函數來分別返回普通銷售和銷售經理所能拿到的折扣率。通過這種方式，我們就可以同時根據銷售人員的職務以及所銷售車型來共同決定所使用的折扣率了。更改後的代碼如下所示：
1 // 普通汽車，折扣為0.03
2 class Vehicle
3 {
4 public:
5 virtual double GetBaseDiscountRate() { return 0.03; }
6 virtual double GetManagerDiscountRate() { return 0.03; }
7 };
8
9 // 由於是奔馳特銷商，因此可以得到更大的折扣
10 class Benz : public Vehicle
11 {
12 public:
13 virtual double GetBaseDiscountRate() { return 0.06; }
14 virtual double GetManagerDiscountRate() { return 0.066; }
15 };
16
17 // 普通的銷售人員，只能按照公司規定的折扣進行銷售
18 class Sales
19 {
20 public:
21 virtual double GetDiscountRate(Vehicle& vehicle)
22 {
23 return vehicle.GetBaseDiscountRate();
24 }
25 };
26
27 // 銷售經理，可以針對某些車型提供額外的優惠
28 class SalesManager : public Sales
29 {
30 public:
31 virtual double GetDiscountRate(Vehicle& vehicle)
32 {
33 return vehicle.GetManagerDiscountRate();
34 }
35 };
36
37 int _tmain(int argc, _TCHAR* argv[])
38 {
39 // 需要銷售的兩輛車
40 Vehicle& vehicle = Vehicle();
41 Benz& benz = Benz();
42
43 // 向普通銷售詢問這兩輛車的折扣
44 Sales* pSales = new Sales();
45 double rate = pSales->GetDiscountRate(vehicle);
46 cout << "Sales: The rate for common vehicle is: " << rate << endl;
47 rate = pSales->GetDiscountRate(benz);
48 cout << "Sales: The rate for benz is: " << rate << endl;
49
50 // 向銷售經理詢問這兩輛車的折扣
51 SalesManager* pSalesManager = new SalesManager();
52 rate = pSalesManager->GetDiscountRate(vehicle);
53 cout << "Sales Manager: The rate for common vehicle is: " << rate << endl;
54 rate = pSalesManager->GetDiscountRate(benz);
55 cout << "Sales Manager: The rate for benz is: " << rate << endl;
56
57 return 0;
58 }
再次運行程序，我發現現在已經可以得到正確的結果了：
也就是說，我自創的Double Dispatch實現已經能夠正確地運行了。
你好，Visitor
“你說為什麼C++這些高級語言不直接支持Double Dispatch？”我問身邊正在和水果奮斗的同事。
“不需要呗。”他頭也不抬，隨口回答了一句，又拿起了另一只水果。
話說，他可真能吃。
“真的不需要麼？”我心裡想，就又在搜索引擎中輸入了“why C++ double dispatch”。
在多年的工作中，我已經養成了一種固定的學習習慣。例如對於一個知識點，我常常首先了解How，即它是如何工作的；然後是Why，也就是為什麼按照這樣的方式來工作；然後才是When，即在知道了為什麼按照這樣的方式來工作後，我們才能在適當的情況下使用它。
幸運的是，在很多論壇中已經討論過為什麼這些語言不直接支持Double Dispatch了。簡單地說，一個語言常常不能支持所有的功能，否則這個語言將會變得非常復雜，編寫它的編譯器及運行時也將變成非常困難的事情。因此到底支持哪些功能實際上由一個語言的目標領域所決定的。在一個語言可以通過一種簡單明了的方式解決一種特定問題的時候，該語言就不再必須為該特定問題提供一個內置的解決方案。這些解決方案會逐漸固定下來，並被賦予了一個特有的名字。例如C++中的一種常用模式就是Observer。該模式實現起來非常簡單，也易於理解。而在其它語言中就可能提供了對Observer的原生支持，如C#中的delegate。而Visitor模式實際上就是C++對Double Dispatch功能的標准模擬。
接下來，我又搜索了幾個Visitor模式的標准實現並開始比較自己所實現的Double Dispatch與Visitor模式標准實現之間的不同之處。這又是我的另一個習慣：實踐常常可以檢驗出自己對於某個知識點的理解是否有偏差。就像我剛剛所犯下的對重載決議的理解錯誤一樣，形成自己解決方案的過程常常會使自己理解某項技術為什麼這麼做有更深的理解。而通過對比自己的解決方案和標准解決方案，我可以發現別人所做的一些非常精巧的解決方案，並標准化自己的實現。
我仔細地檢查了自己剛才所寫的有關銷售汽車的實例與標准Visitor模式實現之間的不同。顯然Visitor模式的標准實現更為聰明：在Sales和SalesManager的成員函數中，編譯器知道this所指向的實例的類型，因此將*this當作參數傳入到函數中就可以正確地利用C++所提供的函數重載決議功能。這比我那種在實現中調用不同函數的方法高明了不知多少：
1 class SalesManager : public Sales
2 {
3 public:
4 virtual double GetDiscountRate(Vehicle& vehicle)
5 {
6 return vehicle.GetDiscountRate(*this); <----編譯器知道*this是SalesManager類型實例，因此可以正確地選擇接受SalesManager類型參數的重載
7 }
8 };
那麼在Vehicle類以及Benz類中，我們只需要創建接收不同類型參數的函數重載即可：
1 class Benz : public Vehicle
2 {
3 public:
4 virtual double GetDiscountRate(Sales& sales) { return 0.06; }
5 virtual double GetDiscountRate(SalesManager& salesManager) { return 0.066; }
6 };
而在Visitor模式的標准實現中，我們則需要使用Visit()及Accept()函數對替換上面的各成員函數，並為所誘得汽車及銷售人員定義一個公共接口。因此對於上面的銷售汽車的示例，其標准的Visitor模式實現為：
1 class Sales;
2 class SalesManager;
3
4 // 汽車接口
5 class IVehicle
6 {
7 public:
8 virtual double Visit(Sales& sales) = 0;
9 virtual double Visit(SalesManager& sales) = 0;
10 };
11
12 // 普通汽車，折扣為0.03
13 class Vehicle : public IVehicle
14 {
15 public:
16 virtual double Visit(Sales& sales) { return 0.03; }
17 virtual double Visit(SalesManager& salesManager) { return 0.03; }
18 };
19
20 // 由於是奔馳特銷商，因此可以得到更大的折扣
21 class Benz : public IVehicle
22 {
23 public:
24 virtual double Visit(Sales& sales) { return 0.06; }
25 virtual double Visit(SalesManager& salesManager) { return 0.066; }
26 };
27
28 class ISales
29 {
30 public:
31 virtual double Accept(IVehicle& vehicle) = 0;
32 };
33
34 // 普通的銷售人員，只能按照公司規定的折扣進行銷售
35 class Sales : public ISales
36 {
37 public:
38 virtual double Accept(IVehicle& vehicle)
39 {
40 return vehicle.Visit(*this);
41 }
42 };
43
44 // 銷售經理，可以針對某些車型提供額外的優惠
45 class SalesManager : public ISales
46 {
47 public:
48 virtual double Accept(IVehicle& vehicle)
49 {
50 return vehicle.Visit(*this);
51 }
52 };
53
54 int _tmain(int argc, _TCHAR* argv[])
55 {
56 // 需要銷售的兩輛車
57 Vehicle& vehicle = Vehicle();
58 Benz& benz = Benz();
59
60 // 向普通銷售詢問這兩輛車的折扣
61 Sales* pSales = new Sales();
62 double rate = pSales->Accept(vehicle);
63 cout << "Sales: The rate for common vehicle is: " << rate << endl;
64 rate = pSales->Accept(benz);
65 cout << "Sales: The rate for benz is: " << rate << endl;
66
67 // 向銷售經理詢問這兩輛車的折扣
68 SalesManager* pSalesManager = new SalesManager();
69 rate = pSalesManager->Accept(vehicle);
70 cout << "Sales Manager: The rate for common vehicle is: " << rate << endl;
71 rate = pSalesManager->Accept(benz);
72 cout << "Sales Manager: The rate for benz is: " << rate << endl;
73
74 return 0;
75 }
“那Visitor模式該如何進行擴展呢？”我自己問自己。畢竟在企業級應用中，各組成的擴展性可以很大程度上決定系統的維護性和擴展性。
我注意到上面的Visitor模式實現中主要分為兩大類類型：IVehicle和ISales。在該Visitor實現中添加一個新的汽車類型十分容易。從IVehicle派生並實現相應的邏輯即可：
1 class Fiat : public IVehicle
2 {
3 public:
4 virtual double Visit(Sales& sales) { return 0.05; }
5 virtual double Visit(SalesManager& salesManager) { return 0.06; }
6 };
但是添加一個實現了ISales接口的類型則非常困難：需要更改所有已知的汽車類型並添加特定於該接口實現類型的重載。
那在遇到兩部分組成都需要更改的情況該怎麼辦呢？經過查找，我也發現了一種允許同時添加兩類型的模式：Acyclic Visitor。除此之外，還有一系列相關的模式，如Hierachical Visitor Pattern。看來和Visitor模式相關的各種知識還真是不少呢。
我再次打開搜索引擎，繼續我的自我學習之旅。而身邊的同事也繼續和水果奮斗著。
