2006/08/19

swap using Concepts

延續從《HasSwap》到《Concepts vs. Type Traits (vs. Reflection)》的討論,我擔心的事情果然成真:後面一篇文章所提的 template overloading 會形成歧義(ambiguity)。以下使用 N2042 所述的語法和語意(也就是 ConceptGCC 所實作的 concept system),建議搭配該篇 paper 閱讀本篇(因為這篇是非常典型的跳躍式邏輯 XD)。

auto concept MemberSwappable<typename T> {
  void T::swap(T&);
};

上述宣告引進一個新的 concept MemberSwappable,此類型別必須擁有一個 member function swap,signature 如 concept declaration 所示。ConceptGCC 使用偏向 pseudo-signature 的 concept 表述方式,但應該只是為了實作方便,pseudo-signature vs. usage pattern 的討論應該還沒定案。auto 代表這個 concept 採用 implicit model,省略的話,欲匹配這個 concept 的型別必須用 concept_map 明確宣稱。

Standard library 已經預先定義了 Swappable concept。我們可以用 concept map template 表述「所有為 MemberSwappable 的型別 T 都為 Swappable」:

template <MemberSwappable T>  // for every MemberSwappable T
concept_map Swappable<T> {
  void swap(T& a, T& b) { a.swap(b); }
};

如上述程式碼所示,使用 concept map 時可以把 concept 所要求的語法(e.g., non-member swap)對映到實際型別的操作(e.g., member swap)。這很像 OOP 的 virtual functions,例如:

template <Swappable T>
void f(T& a, T& b) {
  swap(a, b);
}

T 單純是個 Swappable,那麼會喚起 Swappable 所指定的 non-member swap;但若 T 是個 MemberSwappable,則 Swappable 所指定的 non-member 呼叫語法(i.e.,介面)會被轉換為 MemberSwappable 所指定的 member 呼叫語法(i.e.,實作):行為正與 virtual functions 類似。

故事還沒完。事實上,到此編譯器會抱怨 "ambiguous class template instantiation for 'concept std::Swappable<Test>' ",因為在 concept-enabled STL 中,std::swap 乃如此定義:

template <typename T>
  where Assignable<T> && CopyConstructible<T> {
inline void swap(T& a, T& b) {
  T tmp = a;
  a = b;
  b = tmp;
}

template <typename T>
  where Assignable<T> && CopyConstructible<T>
concept_map Swappable<T> { };

因為 STL 為所有「既為 Assignable 又為 CopyConstructible」的型別提供了 non-member swap,所以用 concept map template 宣稱「所有AssignableCopyConstructible 的型別均為 Swappable」很合理。但這在定義 f、實施 concept-checking 而試圖(自動)檢驗 Test 是否為 Swappable 時,卻發生麻煩:編譯器不知道應該把 Test 歸類為 Assignable && CopyConstructible 還是 MemberSwappable(而不知道該喚起 std::swap 還是 Test::swap)!

我試著解釋目前我理解(猜測)的內幕:auto concepts 事實上是由編譯器暗自產出 concept maps,然後所有操作再根據 concept maps 進行(無論是由編譯器暗自產出的還是使用者明確宣告的)。兩個 concept maps 所指明的關係如下面這個集合圖所示:

而且左右側兩個子集所對應的實際操作不同,所以匹配時必須獨一無二地讓型別落在其中一個子集內。如果,例如,把 Test 的 copy ctor 放在 private 區段,使 T 不為 CopyConstructible,那麼對 f 的呼叫就會成功,喚起 Test::swap。但現在 Test 剛好位於兩個子集的交集內,無法判斷從通用介面呼叫時,要的是哪個子集所定義的操作。喔,這不正是惡名昭彰的鑽石型多重繼承的 compile-time version 嗎?!真是糟糕啊,感覺上沒有比較好的一般解決方案。

--
一篇文章還沒看完就忍不住了 XD。

Anonymous 遊客8/19/2006 6:19 pm 說:

還有一個疑問, 不知道算不算問題?

f 說它要 Swappable, 而身為 Swappable
的人必須用 concept_map 說 "Yes, I am"

但 MemberSwappable 說只要你有 T::swap
那麼你就是 MemberSwappable

問題來了, 某個人有 T::swap 但沒有說它是
Swappable, 但結果它確實會是 Swappable
所以它可以呼叫 f, f 或許不會納悶, 但是
T 自己不覺得奇怪嗎?

 
Blogger Josh Ko8/19/2006 6:51 pm 說:

好問題!這感覺上和 concept 的(新)本質有關,我一時難以直接推導或類推。

我先把那堆 papers 看完好了,看看有沒有解答或得到一點 insight :)。

 
Anonymous 遊客8/19/2006 7:45 pm 說:

在下想到 function template overloading
又要增添新成員, 實在是滿恐怖的一件事!!

這個讓人說法不一個例子:
http://phpfi.com/142595

以前 VC 跟 g++ 持不同意見, 現在不知怎樣
還有更複雜的例子, 通常應該會讓 cpper 放棄跟 overloading 搏鬥 =.=+

 
Blogger Josh Ko8/19/2006 8:09 pm 說:

哈,同意 :)。

我在去年 12 月一篇 blog 裡面寫了一些初探 C++0x 的感想,其中像

「程式語言從 typeless B/BCPL 走到 typed C,算是一個極大的 evolution。而現在 C++ 即將演化出 type of types,又是一次 evolution。」

這句已經值得商榷。而另一句

「多了一個層級出來,不僅新層級裡面的東西要處理好,新舊層級間的互動也要注意。例如以後 function template overloading 可能就要同時考慮 template-parameter-based overloading 和 function-parameter-based overloading,不知道會產生什麼樣的 overload resolution rules 出來。」

就如你所言 :)。現在光 plain function overloading 和 function templates 兩者個別出現,程式員就有點招架不住(讓我想到《C++ Primer》每次都被抓住裡面的 overload resolution 部份當作它很難讀的證據 XD),兩者結合起來真的很嚇人 :P。

把 N2036 ~ N2042 全印出來了。這種東西當睡前讀物最好 :P。

 
Blogger Josh Ko8/19/2006 9:03 pm 說:

我自己的問題先解決了 :P。太急著發文,往下多看一段就知道該怎麼做了 XD。

我們現有兩個 concept maps,分別對映到圖中兩個子集,同具兩邊陣營特性的型別會搖擺不定,不知該倒向哪邊好(該使用哪個 concept map)。

解法事實上很簡單:只要再造出第三個陣營(即中間那個交集部份)就行:

template <typename T>
  where MemberSwappable<T> && Assignable<T> && CopyConstructible<T>
concept_map Swappable<T> {
  void swap(T& a, T& b) { a.swap(b); }
};

如此兼具兩邊特性的型別就有家可歸了。

這樣的東西似乎就沒辦法和 OOP 平行類推了?

 
Blogger Josh Ko8/19/2006 10:51 pm 說:

睡不著,試著提出一些解釋 XD。

剛剛看 N2042 後面的規格部份,p.23 提到

"Whenever a constrained template is used, there must be a concept map corresponding to each concept-id requirement in the where clause."

並在 p.16 說

"a concept with a preceding auto specifier is an implicit concept. When a concept map is required for an implicit concept but no concept map can be found through concept map lookup, it shall be implicitly generated."

所以一個 type 能否與一個 concept 匹配(whether a type matches a concept),取決於能否找到那個 type 與那個 concept 之間的 concept map ─ auto concepts 只是特例而已。(有 concept map 存在 ==> 這個 type 就匹配那個 concept)

當一個 concept 為 explicit concept 時(即未受 auto 修飾),這個 concept 需要由 type 那邊明確寫出 concept map 宣稱匹配。所以若 Swappable 為 explicit concept,則僅具有「可通過型別檢查的 non-member swap」尚且不足,還必須由 type 那邊明確宣稱(語意符合)才行,如先前所討論。而 implicit concept 就代表「只要語法符合,就保證語意符合」,所以編譯器型別檢驗通過後,就直接產出 concept map。(implicit concept ==> [語法符合 ==> 產出 concept map(因為語意也符合)])

當我們寫下一個 concept map 時,我們就明確宣稱這個 type 匹配那個 concept。同理,當我們寫下 concept map template 時,我們是明確宣稱一整族的 types 都匹配那個 concept。所以在此處,所有 MemberSwappable 的 types 都被「明確」宣稱為 Swappable,而沒違反「Swappable 要求明確宣稱」的規則 ─ 我們確實明確提供了所求的 concept maps。

也就是說,當我們寫下「宣稱所有 MemberSwappable types 都是 Swappable」的 concept map template 時,意思就是「只要是 MemberSwappable types 就必然匹配 Swappable(連同語意考慮在內)」,因為寫出 concept map 就一併保證語意符合,而我們的確寫出了。

而 MemberSwappable 的匹配條件就寬鬆一點,因為 MemberSwappable 是個 implicit concept,所以保證只要語法符合語意就符合。全部合起來,只要 T 具有 member swap,就一定(在語法、語意上)匹配 Swappable。

主要關鍵應該在於,我們寫出 implicit concept 時,就代表保證「語法符合時語意亦符合」,而非「不考慮語意」。

基本上我還滿喜歡這樣的設計:explicit & implicit concepts 並存 :)。

--
寫到後來覺得自己在寫天書,一堆 Swappable、concept map,快混淆在一塊了 XD。

 
Anonymous 遊客8/20/2006 4:20 am 說:

> 這樣的東西似乎就沒辦法和 OOP 平行類推了?

好像是這樣耶!!

這樣可以自己決定要用哪一個成品; 如果是一般
的多重繼承, 應該是語言會決定一個採用順序

像 Python 有什麼 __mro__ 好像滿複雜的
而 Ruby 的 mixin 也跟它的 include 順序有關

一個是自己決定, 一個是語言決定 (但使用者要學習認知)

 
Anonymous 遊客8/20/2006 4:45 am 說:

之前的疑問癥結是:

某 T 有 T::swap 就是 MemberSwappable
而後又明確宣稱 MemberSwappable 就是 Swappable

所以光看 f 的 prototype, 我以為要一個
explicit Swappable, 但是因為我有 T::swap
所以我隱然 (implicit) 是一個 Swappable
甚至我連 MemberSwappable 這個 concept
的存在也不知道, 就發生了


看起來滿像這個: Conversion Sequences =.=+

猶記得那一串吧?
standard conversion -> user-defined conversion -> standard conversion

不知道它有否限制轉換次數, 還是說這個問題在 concept 中有等於沒有? 某 T 有 A 的特徵, A 說他是 B, B 說他是 C, 所以 T 是 C


其實, 只要小心使用, 就沒有問題 =.=+

 
Blogger Josh Ko8/20/2006 12:35 pm 說:

我剛剛想試 namespace 能否解決問題,但因為 concept map 必須和所對映的 concept 處於同一個 namespace 裡面,似乎沒輒。至於「限制轉換次數」的問題,我覺得應該是以 concept map 的存在與否為準。

這種從客戶端觀之全然無異,但語意可能突然改變的情況,似乎在 C++98 裡面就有了?(例如,private section 裡面加個較為匹配的 member function 重載版本。)如果依照現況,恐怕真的只能「小心使用」了吧 :P。

 
Anonymous 遊客8/20/2006 1:04 pm 說:

之前我有無意間看到你回那篇, 我覺得那篇所
說的應該沒錯! 不過不知為何突然砍掉了?

以語法來說, 它這樣設計個人覺得算滿優的 ^^

 
Blogger Josh Ko8/20/2006 1:13 pm 說:

哎呀,我以為我刪得夠快了 XD。

我本來在實驗時,以為我的觀點正確。可是後來一想不對,又發現實驗裡少了個 const 而導致不正確結果(以及不正確推論),所以趕緊刪了那篇 XD。

想用 namespace 控制這問題,前提是 concept maps 必須能定義於任意 namespace,才不會在使用者未引用那個 namespace 時流瀉出去。不過這前提目前不成立 :)。

 
Anonymous 遊客8/20/2006 1:25 pm 說:

哦, 原來如此 :-D

(歹勢,事情就是那麼巧。)

 

<< 回到主頁