2009年9月23日 星期三

Design Pattern 與 Double Dispatching

為了寫 Design Pattern 作業,所以上網查了一下。不過我覺得以這個作業而言,Double Dispatch 好像也沒有什麼用,如果不偷用 RTTI(不管是用 instanceof、getClass 或自己加上一個回傳型別的 Virtual Function),好像就沒有辦法確認 object 的真正的 class。

--

在談 Double Dispatch 之前我們必需先從 Polymorphism 說起。Polymorphism 有兩種:
  1. Subtype Polymorphism: 前者就是指繼承類別之間的多型。例如:人和狗同時繼承動物類別,二者都會進食,不過二者的吃飯方式不同。我們會在動物宣告一個 Virtual Method,人和狗類別會各自 Override 自己的吃飯方式,利用 Virtual Method Invocation,在執行期喚起正確的函式。 (Method Overriding)
  2. Type Polymorphism (Ad-hoc Polymorphism): 有一個同名的函式,編譯器會依據傳入參數的不同,選擇不同的函式,例如:同樣是 + operator,你把數字加數字與字串加字串就會有不同的結果。(Function Overloading)
值得一提的是 Virtual Method Invocation 的效率略低於一般的函式呼叫,所以 C++ 要求希望被 Virtual Invoke 的函式應該要額外加上 virtual 關鍵字。而 Function Overloading 因為是在編譯期決定呼叫的函式,所以不會影響效率。

我們先看一下什麼是 Type Polymorphism (Function Overloading):

class A;
class B;

class A {
public:
    void interact(A const &a) { cout << "class A vs A" << endl; }
    void interact(B const &b) { cout << "class A vs B" << endl; }
};

class B : public A {
public:
    void interact(A const &a) { cout << "class B vs A" << endl; }
    void interact(B const &b) { cout << "class B vs B" << endl; }
};

int main() {
    A a;
    B b;

    a.interact(a); // Invoke A::interact(A const&)
    a.interact(b); // Invoke A::interact(B const&)
    b.interact(a); // Invoke B::interact(A const&)
    b.interact(b); // Invoke B::interact(B const&)
    return 0;
}

我們可以注意到,透過 Function Overloading,我們可以在不同的時候喚起不同的函式。例如:a.interact(b) 就會喚起 void A::interact(B const &) 這個函式。

如果因為某些原因我必需使用類別 A 的 Reference 來指稱其子類別的 Instance,我把上面的程式改成這樣呢?

int main() {
    A &aa = a;
    A &ba = b;

    a.interact(aa); // Invoke A::interact(A const&)
    a.interact(ba); // Invoke A::interact(A const&)
}

我們就會發現 Type Polymorphism 完全幫不了我們!為什麼?因為類別 A 的 Reference 所指向的物件的 Type 是可以隨 Runtime 的不同而有所變動,所以一般來說編譯器只能假定這個 Reference 只會是類別 A 的實例。從而只能喚起 A::interact(A const&) 函式。那我們該怎麼做呢?

此時我們會想聯想的 Subtype Polymorphism (Method Overriding) 的 Late Binding。首先我們要為上述的函式加上 virtual 關鍵字,使其可以動態地決定要喚起哪個函式。我分別 class A, class B 的 interact 函式的前面都加上了 virtual 關鍵字(雖然一日 Virtual Method 終身 Virtual Method,所以加在 class A 裡面的 Method 就可以了,不過為了方便閱讀,我是建議在 class B 裡面的 Method 也加上 virtual)

class A {
public:
    virtual void interact(A const &a) { cout << "class A vs A" << endl; }
    virtual void interact(B const &b) { cout << "class A vs B" << endl; }
};

class B : public A {
public:
    virtual void interact(A const &a) { cout << "class B vs A" << endl; }
    virtual void interact(B const &b) { cout << "class B vs B" << endl; }
};

這下問題解決了嗎?我們看看:

int main() {
    aa.interact(aa); // Invoke A::interact(A const&)
    aa.interact(ba); // Invoke A::interact(A const&)
}

很顯然地,雖然 interact 是 Virtual Function,但是因為只有 this 會透過 Late Binding 而被延遲到執行期,編譯器還是會在編譯期施行 Method Overloading Resolution 從眾多 Overloaded Method 當中挑選特定版本生成程式碼,讓我們的程式於執行期呼叫 Virtual Method(進而依據 this 所屬類別進行 Dynamic Dispatch),所以這裡 Subtype Polymorphism 似乎幫不上忙。

不過,事實上 Subtype Polymorphism 是可以幫上忙的!只是我們需要一個小技巧!這就是所謂的 Double Dispatching,我們可以再寫一個函式叫作 apply,它固定傳入一個類別 A 的 Reference,不過我們會在函式的本體上動手腳!

class A {
public:
    virtual void apply(A &obj) { obj.interact(*this); }
};

class B : public A {
public:
    virtual void apply(A &obj) { obj.interact(*this); }
};

int main() {
    aa.apply(aa); // Finally invoke A::interact(A const&)
    ba.apply(aa); // Finally invoke A::interact(B const&)

    aa.apply(ba); // Finally invoke B::interact(A const&)
    ba.apply(ba); // Finally invoke B::interact(B const&)
}

對,這裡我用了 *this,*this 的型別是什麼呢?對!就是擁有 apply 函式的類別。注意:我們必需要在每個類別加上相同的 apply 函式。因為每個 apply 函式中的 *this 型別是不一樣的。當我們用 object1.apply(object2) 呼叫時,apply 會幫我們找出 object1 的確切類別,再使用 object2.interact((THISCLASS &)object1) 來呼叫 interact 函式,因為 object1 的型別已經確定,所以第二次呼叫 interact 就是找出 object2 的確切類別,喚起正確的函式。

這大概是 Double Dispatch 的內容。

--

不過壞消息是:這個作業中我們不能碰原有的 class 也就不能為原有的 class 加上 virtual method,所以這樣寫似乎沒有什麼用。

2009年9月16日 星期三

C++ 與 instanceof

C++ 本身是沒有提供 instanceof 關鍵字,不過我們可以利用簡單地實作出該語意:

template <class Class, typename T>
inline bool
instanceof(T const &object)
{
    return dynamic_cast<class const *>(&object);
}

不過我發現如果要用 dynamic_cast,我們的 class 至少要有一個 virtual function,因為 C++ 的 RTTI 實作是依賴 vtable 的。

以下是整個範例程式:

#include <iostream>
#include <cstdlib>

using namespace std;



template <class Class, typename T>
inline bool
instanceof(T const &object)
{
    return dynamic_cast<Class const *>(&object);
}



class A
{
public:
    virtual ~A() {}
};

class B : public A { };
class C : public A { };
class D : public B, public C { };

class E
{
public:
    virtual ~E() {}
};



int
main()
{
    A a;
    B b;
    C c;
    D d;
    E e;

    A& aa = a;
    A& ab = b;
    A& ac = c;
    A& ad = *static_cast<B *>(&d);

#define CHECK(CLASS, REF) \
    do \
    { \
        if (instanceof<CLASS>(REF)) \
        { \
            cout << #REF " is an instance of " #CLASS << endl; \
        } \
        else \
        { \
            cout << #REF " is NOT an instance of " #CLASS << endl; \
        } \
    } \
    while (0);

    CHECK(A, aa);
    CHECK(A, ab);
    CHECK(A, ac);
    CHECK(A, ad);
    CHECK(A, e);

    CHECK(B, aa);
    CHECK(B, ab);
    CHECK(B, ac);
    CHECK(B, ad);
    CHECK(B, e);

    CHECK(C, aa);
    CHECK(C, ab);
    CHECK(C, ac);
    CHECK(C, ad);
    CHECK(C, e);

    CHECK(D, aa);
    CHECK(D, ab);
    CHECK(D, ac);
    CHECK(D, ad);
    CHECK(D, e);


    return EXIT_SUCCESS;
}

2009年9月9日 星期三

類別的抽象意涵

到底基於什麼樣的誤會會讓人讓 Point3d 繼承 Point2d?有人會說「空間的點」是一種「平面的點」嗎?

class Point2d {
private:
    int x;
    int y;
public:
    Point2d(): x(0), y(0) {}
    Point2d(int x_, int y_) : x(x_), y(y_) {}

    int get_x() const { return x; }
    int get_y() const { return y; }

    void set_x(int x_) { x = x_; }
    void set_y(int y_) { y = y_; }
};

class Point3d : public Point2d {
private:
    int z;
public:
    Point3d(): Point2d(0, 0), z(0) {}
    Point3d(int x_, int y_, int z_): Point2d(x_, y_), z(z_) {}

    int get_z() const { return z; }
    void set_z(int z_) { z = z_; }
};

上面的程式碼看似可以重復使用 Point2d 的部分,基於「儘可能重複使用原則」,這樣寫好像沒有錯。可是如果今天我有一個函式長這樣呢?

int dist(Point2d const &a, Point2d const &b) {
    return sqrt(pow((double)(a.get_x() - b.get_x()), 2) +
                pow((double)(a.get_y() - b.get_y()), 2));
}

然後假設經過很久的時間,你早已忘記你的 Point3d 還有 dist 是怎麼寫得。有一天我們忽然必需要計算空間中的二點的距離,於是你很自然地寫下下面的程式碼:

Point3d pa(0, 0, 0);
Point3d pb(0, 0, 10);

double d1 = dist(pa, pb); // d1 = 0

這時你會得到一個讓你意外的結果!為什麼是 0?沒有任何的機制阻止你犯下錯誤。當然,當你發現數值不對的時候,也許會認為在多補一個 Point3d 的 dist 函式就可以了(事實上你也應該這麼做)。但是事情有這麼簡單嗎?

Point2d pc(0, 0);
Point3d pd(0, 0, 10);

double d2 = dist(pc, pd);

上面的程式出了什麼問題?對,沒有錯,dist 又把 Point3d 的 instance 當成 Point2d 的 instance。然後就是你的程式怎麼死得都不知道!

這組 class 的設計有個根本的問題就是隨便使用繼承的語意,看到「重複的程式碼」就開槍!結果反而寫出意想不到的程式碼。根本的解決方式就是抄一次 int x, y ... 等程式碼,而且多抄一次錯誤的機會反而會更少。

當然我知道有人會反駁說我應該使用 private inheritance。對,private inheritance 的確有 has-a 的語意,可是你認為這樣的程式碼比較直觀嗎?

class Point3d : private Point2d {
private:
    int z;
public:
    Point3d(): Point2d(0, 0), z(0) {}
    Point3d(int x_, int y_, int z_): Point2d(x_, y_), z(z_) {}

    using Point2d::get_x;
    using Point2d::get_y;
    int get_z() const { return z; }

    using Point2d::set_x;
    using Point2d::set_y;
    void set_z(int z_) { z = z_; }
};

不要自欺欺人了,要是「重複使用」這麼重要,你也應該使用 composition 與 delegation 來完成 has-a 的語意。
class Point3d {
private:
    Point2d xy;
    int z;
public:
    Point3d(): xy(0, 0), z(0) {}
    Point3d(int x_, int y_, int z_): xy(x_, y_), z(z_) {}

    int get_x() const { return xy.get_x(); }
    int get_y() const { return xy.get_y(); }
    int get_z() const { return z; }

    void set_x(int x_) { xy.set_x(x_); }
    void set_y(int y_) { xy.set_y(y_); }
    void set_z(int z_) { z = z_; }
};

我今天看書的時候還看到更扯的例子:橢圓是圓形的子類別,因為橢圓要二個參數來描述,圓只需要一個,同理矩形是正方形的子類別。還有,因為向量表示法很相似,所以三角形是一種矩型。照這種亂七八糟繼承法推演下去,所有的形狀都可以是正方形的一種(is-a-kind-of),你看正方形所需的參數最少嘛!?

這樣為了重複使用而重複使用對嗎?明明是毫不相干的類別我們應該讓他們互相繼承嗎?原本是超集的集合現在要變成別人的子集對嗎?敝人不才,我不懂這些聰明絕頂的人在想什麼。

書評: 多型與虛擬

多型與虛擬: 物件導向的精髓
侯俊傑
1998

--

今天在圖書館看書的時候,不小心把這本書拿起來看。因為看得很順,所以大概四個小時就看完了。結果正事都沒有做...。(話說有點奇怪的是總圖的二本明明就被借走了,為什麼我在架上還看得到書呢?)

--

這本書很大一部分是取材自 Inside C++ Object Model深入淺出 MFC。前者侯俊傑為該書的譯者,後者為侯捷(侯俊傑的另一筆名)的作品。

本書在第一章花了不少篇幅用以講解 C++ 中 class 的語意,第二章則用以講述 class 的佈局(在記憶體中的 layout),第三章是在說明轉型的語意(semantics)。這三章的內容大多與 Inside C++ Object Model 的內容重疊,惟作者所使用的 C++ 實作(編譯器)不同,故研究之方法與得出的結論有些許差異,然而其中心思想是雷同的。

第四章與第五章則是介紹 RTTI(Runtime Type Information執行期型別資訊),與動態物件生成(Unserialize)。這二章我相信是取材自深入淺出 MFC 一書,範例的設計與 MFC 的設計如出一轍。只不過範例程式碼已經大量簡化以方便理解。

第六章則是介紹 COM,這個 COM 並非 C++ Object Model 的縮寫,而是 Component Object Model 的縮寫。Component Object Model 是微軟提出來的一個技術,用以讓 C++ 的 class 變成一個 library 讓多數程式可以共享同一個類別庫(Class Library)。然而要把 class 匯出為一個介面不是易事,撇開 C++ 標準沒有限制 binary 的設計,C++ 本身的 Object Model 很大的程度就限制了類別庫的「重用性」。本章提出了一些解法,用以作為學習 COM 的墊腳石。

--

我個人覺得這本書的定位很特別,他前三章的內容不若 Inside C++ Object Model 詳細,而第四五章則不若 深入淺出 MFC 詳儘。不過就「多型與虛擬」這個主題而言,這樣的剪裁恰到好處。對於一個只是想要簡單地了解 Visual C++ 如何實作各種 C++ class 的語義的人,這樣的一本書已經足夠。而且這本書和侯俊傑譯得《C++ 物件模型》相比好讀許多,至少這本書是原文書,自然也不會有誤譯。第二三章的範例也多出自 Inside C++ Object Model 一書,不過大部分都有再做修改並附上 Visual C++ 編譯後的數據。而第四五章則把心力放在 RTTI 與物件動態生成上,展示了 MFC 在處理物件執行期型別資訊(RTTI)、儲存(Persistence)的方法。即使時至今日 C++ 早已有許多改變,但我認為了解 RTTI 與 Persistance 的實作方法仍是相當重要的。想想看你還有多少的 *.doc?而最後一章的可以當作學習 COM 的「導論」(如果你對 COM 還是很有興趣的話),它簡單的說明了為什麼以 C++ 設計類別庫是如此的困難,以及當時流行的一些 Work Around。

總體來說,如果你想要了解 Visual C++ 對 class 所施加的黑魔法,這本書是一門不錯的入門書,雖然年代久遠,仍有其參考價值。不過如果你已經讀過 Inside C++ Object Model (你的功力已經很強了),就不要把時間浪費在第一二三章;如果已經讀過 深入淺出 MFC,第四五章也可以稍加斟酌。

2009年9月1日 星期二

xrandr 與筆電的 VGA 輸出

之前在 R219 做 C++ 演講的時候,發現 Ubuntu 沒有辦法使用 VGA 輸出,臨時改用 Windows Vista 結果我覺得用起來很不順,而且有些範例沒有辦法展示,覺得相當捥惜。今天我用桌機的螢幕測試看看,結果發現 Ubuntu 是可以自動偵測螢幕,雖然結果不是很令人滿意(自動選用的解析度對二個螢幕而言都不是最佳解析度),但也還算是堪用。

那之前的演講是怎麼一回事呢?我在想有可能是因為投影機的解析度和我的筆電的解析度八字不合,所以 Ubuntu 沒有辦法自動選出最合適的解析度組合,所以當天就沒有辦法正常使用投影機。

早期要更改解析度,一定要修改 xorg.conf 然後重新開啟 X server。不過現在我們可以用 xrandr 來重新設定解析度,而且可以像 Windows 那樣立刻生效,甚至還可以做一些特別的設定。

首先我們要下面的指令來觀察目前的設定:
xrandr --current

在我的電腦會看到有 VGA 與 LVDS 二種輸出方式,前者是 VGA 輸出端子,後者是筆電本身的螢幕;同時 xrandr 也會顯示每種輸出方式可以使用的解析度與更新頻率。

如果我想要調整 LED panel (筆電內建) 的解析度我們可以使用 --mode 來設定:
xrandr --output LVDS --mode 1280x800

當然如果我要調整 VGA output 的解析度我們可以用下面的指令:
xrandr --output VGA --mode 1024x768

如果我們要關閉一種輸出,我們可以用 --off 來關閉。off 很重要,因為二種輸出有時候會互相干擾,我們可以先關閉一個,調整好再開啟不同的輸出。

接下來,我們可以讓不同的螢幕有不同的解析度。之所以會有這樣的需求是因為 LCD 螢幕的解析度是不能動態調整的,所以對於「非出廠內定值」通常只是把輸入訊號用內差法放大,效果都不甚理想,所以我希望可以讓筆電的螢幕是「出廠內定值」。

我的做法是:
xrandr --output LVDS --mode 1280x800 --output VGA --off

先把 LCD panel 的解析度調整好,再開啟 VGA output 的解析度:

xrandr --output VGA --mode 1024x768

此時,我們還可以稍做修改,例如我不想要顯示 GNOME 上層的選單,我就可以用 --pos 來移動我的 VGA output 的顯示區:

xrandr --output VGA --mode 1024x768 --pos 0x25

我想在一般的演講,這些指令就很夠用了。不過我在研究 xrandr 的時候發現了一個有趣的參數:panning。我們可以用 panning 模擬比較大的螢幕。有人可能會很好奇它是如何「模擬」的?事實上使用了 panning 就有點像顯微鏡,我們的「可視區」還是只有螢幕的大小,隨著滑鼠的移動,「可視區」的範圍也會隨之移動。也就是說如果我剛才修改一下 VGA 的設定,VGA output 就可以隨著滑鼠的移動看到不同的部分。

xrandr --output VGA --mode 1024x768 --panning 1280x800

當然 xrandr 的功能不止如此,他還可以把二個螢幕串起來,一左一右,不過我就懶得試了,因為還要修改 xconf 的 Virtual 值以加大 Virtual Screen 的大小。