same_asコンセプトとSymmetric Subsumption Idiom

C++2a(C++20)ライブラリ提供の標準コンセプトstd::same_as、およびコンセプト定義における対称包摂イディオム(Symmetric Subsumption Idiom)についてメモ。

制約式std::same_as<X, Y>と制約式std::same_as<Y, X>は対称関係、つまり互いに一方が他方を包摂する(subsume)関係にある。これによりコンセプトへのテンプレートパラメータ指定順が一致していなくとも、制約式を用いた関数オーバーロード解決の半順序関係を表現できる。

// C++2a(C++20)
#include <concepts>

template <typename X, typename Y>
  requires std::same_as<X, Y>
constexpr int f() { return 1; }  // #1

template <typename X, typename Y>
  requires std::same_as<Y, X> && (1 < sizeof(X))
constexpr int f() { return 2; }  // #2

f<int, int>();  // OK: #2を呼び出す

もしsame_asコンセプトがこのような対称性をもたない場合、関数オーバーロード解決は曖昧になり上記コードはill-formedとなってしまう。*1

C++2a標準ライブラリ

標準コンセプトsame_as<T,U>の定義では動作説明用(exposition only)のコンセプトsame-as-implを用いて、型パラメータT, Uに対象関係が成り立つようにしている。ここではC++2a言語仕様上、メタ関数is_same_vの直接記述ではなくコンセプトsame-as-impl経由が必須となる。（詳細後述）
N4830*2 14.8.2より引用。

template<class T, class U>
  concept same-as-impl = is_same_v<T, U>;  // exposition only

template<class T, class U>
  concept same_as = same-as-impl<T, U> && same-as-impl<U, T>;

1 [Note: same_as<T, U> subsumes same_as<U, T> and vice versa. -- end note]

当初はナイーブな定義とNoteによる動作説明になっており、パラメータの対称性を実現にはコンパイラマジックが必要であった。LWG3182によりライブラリ定義のみで対称性が実現されるよう修正された経緯がある（下線部は強調）。*3

The specification of the Same concept in 18.4.2 [concept.same]:

template<class T, class U>
  concept Same = is_same_v<T, U>;

-1- Same<T, U> subsumes Same<U, T> and vice versa.

seems contradictory. From the concept definition alone, it is not the case that Same<T, U> subsumes Same<U, T> nor vice versa. Paragraph 1 is trying to tell us that there's some magic that provides the stated subsumption relationship, but to a casual reader it appears to be a misannotated note. We should either add a note to explain what's actually happening here, or define the concept in such a way that it naturally provides the specified subsumption relationship.

Given that there's a straightforward library implementation of the symmetric subsumption idiom, the latter option seems preferable.

コンセプト利用

コンセプトsame_as定義にコンセプトsame-as-implを利用するとき、2つの制約式[A]same_as<X, Y>, [B]same_as<Y, X>の関係は次のように説明できる。

template<class T, class U>
  concept same-as-impl = is_same_v<T, U>/*#0*/;

template<class T, class U>
  concept same_as = same-as-impl<T, U> && same-as-impl<U, T>;

それぞれの制約式を正規化(normalization)すると、原子制約(atomic constraint)導出時のパラメータマッピング(parameter mapping)を ↦ 表記して、次の正規形(normal form)が得られる：

• [A]same_as<X, Y>の正規形は is_same_v<T↦X, U↦Y>#0 ∧ is_same_v<T↦Y, U↦X>#0
• [B]same_as<Y, X>の正規形は is_same_v<T↦Y, U↦X>#0 ∧ is_same_v<T↦X, U↦Y>#0

制約P=[A]same_as<X, Y>, 制約Q=[B]same_as<Y, X>とおくと、PのDNF(選言標準形; disjunctive normal form)およびQのCNF(連言標準形; conjunctive normal form)の各項は次の通り：

• P₁=(is_same_v<T↦X, U↦Y>#0 ∧ is_same_v<T↦Y, U↦X>#0)
• Q₁=is_same_v<T↦Y, U↦X>#0, Q₂=is_same_v<T↦X, U↦Y>#0

項P₁は2つの原子制約 P_1,1=is_same_v<T↦X, U↦Y>#0, P_1,2=is_same_v<T↦Y, U↦X>#0からなり、QのCNF項に含まれる原始制約Q_j,bに対して同一(identical; ≡ 表記)な原子制約P_i,aが存在する：

• 原子制約Q_1,1=is_same_v<T↦Y, U↦X>#0 ≡ 原子制約P_1,2=is_same_v<T↦Y, U↦X>#0 つまり “項P₁ subsumes 項Q₁”
• 原子制約Q_2,1=is_same_v<T↦X, U↦Y>#0 ≡ 原子制約P_1,1=is_same_v<T↦X, U↦Y>#0 つまり “項P₁ subsumes 項Q₂

以上より、制約Pの全てのDNF項(P₁)は制約Qの全てのCNF項(Q₁, Q₂)を包摂する、つまり “[A]same_as<X, Y> subsumes [B]same_as<Y, X>” が導出される。

制約P, Qを入れ替えると、同様に対称な関係 “[B]same_as<Y, X> subsumes [A]same_as<X, Y>” が導出される。

メタ関数利用

コンセプトsame_as定義にメタ関数is_same_vを直接利用したとき、2つの制約式[A]same_as<X, Y>, [B]same_as<Y, X>の関係は次のように説明できる。

template<class T, class U>
  concept same_as = is_same_v<T, U>/*#1*/ && is_same_v<U, T>/*#2*/;

それぞれの制約式を正規化すると、次の正規形が得られる：

• [A]same_as<X, Y>の正規形は is_same_v<T↦X, U↦Y>#1 ∧ is_same_v<U↦Y, T↦X>#2
• [B]same_as<Y, X>の正規形は is_same_v<T↦Y, U↦X>#1 ∧ is_same_v<U↦X, T↦Y>#2

制約P=[A]same_as<X, Y>, 制約Q=[B]same_as<Y, X>とおくと、PのDNFおよびQのCNFの各項は次の通り：

• P₁=(is_same_v<T↦X, U↦Y>#1 ∧ is_same_v<U↦Y, T↦X>#2)
• Q₁=is_same_v<T↦Y, U↦X>#1, Q₂=is_same_v<U↦X, T↦Y>#2

項P₁は2つの原子制約 P_1,1=is_same_v<T↦X, U↦Y>#1, P_1,2=is_same_v<U↦Y, T↦X>#2からなるが、QのCNF項に含まれる原始制約Q_1,1やQ_2,1と “同じ式(the same expression)” かつ “同等のパラメータマッピング” をもつ原子制約が無い、つまりいずれの原子制約Q_j,bに対しても同一(identical)な原子制約P_i,aは存在しない。*4

つまり[A]same_as<X, Y>は[B]same_as<Y, X>を包摂しない。制約P, Qを入れ替えても同様に包摂関係は成り立たない。

関連URL

• コンセプト制約式の包摂関係とオーバーロード解決 - yohhoyの日記
• https://gist.github.com/yohhoy/a96021f1e0415d06bb8d4bd8eab94aec

*1:C++言語仕様を厳格に解釈すると 1 == sizeof(int) となる処理系が存在しうるため、該当コードでオーバーロード#1が選択される可能性もある。本記事ではそのような処理系の存在は無視する。

*2:http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/n4830.pdf

*3:N4820以前のコンセプト名は Same とされていたが、(PDF)P1754R1採択によって same_as へと改名された。詳細はC++標準コンセプトの名前付けガイドラインを参照。

*4:N4830 13.4.1.2/p2: "Two atomic constraints are identical if they are formed from the same expression and the targets of the parameter mappings are equivalent according to the rules for expressions described in 13.6.6.1."