[C++] Type Erasure (型別抹除) - A Technique of Behavior Abstraction

    其實我真正要寫的是這篇XD 只是剛好有例子會用到 Functor，所以就順道寫了那兩篇 functor 的介紹。Type erasure (後面都會簡寫成 TE) 其實不算是 C++ 語言中的特性，應該算是一種技巧，用來避開 C++ 在編譯過程中型別檢查造成的麻煩 (所以才會叫型別抹除)。這項技巧其實在 C 也有，只是 C++ 因為引入了 OO，所以 C 的型別抹除技巧不能完全套用在 C++ 上，就如同 qsort 在 class 上會撞牆是一樣的情況 [2]。另一方面，C++ 因為有了 template 可以使用，所以這項技巧可以有了更好的發揮空間。同時，TE 也扮演了 template 跟 OO 之間的接合劑 (聽起來好像有點奇怪...) [3]。一個最顯而易見的例子就是 std::sort 的第三個參數就是運用了 TE 的技巧，所以他可以吃進任何可以像 function 般操作的東西，而不管你扔進來的東西的型態為何。

       首先讓我們回歸 qsort 的例子，先把 qsort 如何排序這件事情放一邊，先來看看他的介面設計：
1. 排序的對象是個陣列，由第一個參數指定，且其型態須轉為 void*
2. 排序的陣列總大小 (以 byte 表示)，由第二個參數指定
3. 每個 element 的大小 (以 byte 表示)，由第三個參數指定
4. 兩個 element 之間如何定義其順序，由第四個參數指定

C 雖然不是個 strong-type language，但是能比對的型態還是會比對的，然而正是此點會造成介面設計上的困擾：我希望這個 sorting function 可以套用在任何形態上。畢竟我們不可能為每種型態都重新寫一個內容幾乎一模一樣的 sorting function，更何況 C 沒有提供 function overloading，也沒有 template 可以用，更不可能提供使用者利用 struct / union 自定義的型別的 sorting function。而 qsort 之所以能做到此點的原因在於："所有的型別都可以轉成 void"。而這，正是 C 所提供的 TE 的功能，藉著把所有 type 都轉成 void，我只須寫出一個可以在 void 陣列上排序的演算法，接下來就可以套用在任何 C 的陣列上。

當然，因為型別被拿掉了，本來我們可以利用的型別特性也就此消失了，所以需要其他的方法來補足所需要、但遺失了的資訊，在 qsort 上是利用其他參數來補足這些資訊，這就是 C 版本的 TE。然而，當我們把目標轉向 OO 時，因為其設計概念與 C 是截然不同的，C 的 TE 已然不再適用。在 C++ 裡，TE 的做法主要是利用 template 的特性。

       首先我們先來看 std::sort 的 signature：

default (1):
template <class RandomAccessIterator>
void sort (RandomAccessIterator first, RandomAccessIterator last);

default (2):
template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

default (1) 跟 (2) 的差別只在有沒有第三個參數，而 default (1) 的排序是利用 operator< 來達成的。而 std::sort 的 TE 的精神就在那些 template parameters 裡：我不管你是丟什麼東西給參數，只要他滿足 random access iterator 的特性就好 (何謂 random access iterator 請參考 STL)。而 std::sort 的實作中就奠基於這項事實去撰寫 sorting algorithm，從而忽略所要排序的東西的型態究竟為何。

       因此所謂的 C/C++ 的 TE 簡單來說是這樣：針對想要實做的東西 (比如說是 sorting algorithm)，去除型態，專心在描述其行為。也因此我對 TE 的副標題 "behavior extraction" 及是來自於此。因為當我們把型態的問題從實作中去除後，剩下的就是如何描述其行為。所以我認為 TE 得一個重點在於 "介面設計"，找出各種型態間的共通行為，設計出一個將來可在任何型態上使用的介面就是 TE 最大的困難點也是基礎。

       網路上有很多 TE 的文章，大部分看到的例子是用 iterator 當示範，不過我覺得那其實頗難抓到 TE 的概念，但是會比較精確的描述 TE 在做的事。另外 C++ 的 TE 跟 JAVA 的 TE 似乎有不同的意涵，這點仍有待查證。

Reference:
[1] http://www.cplusplus.com/articles/oz18T05o/
[2] http://shininglionking.blogspot.tw/2014/01/c-functor-function-like-object-part-ii.html
[3] http://www.artima.com/cppsource/type_erasure.html
[4] http://en.wikipedia.org/wiki/Type_system