Rokiのチラ裏

学生による学習のログ

n4687 C++ extensions for Concepts

このエントリは、ドラフト入りしたコンセプト仕様全体を網羅するためのものである。尚、このエントリは P0734R0 と同提案が drafting された n4687 に基づいており、注釈などで付けられるセクション名は特に指定のない限り n4687 を示しているものとする。

コンセプト

コンセプトとはテンプレート引数に制約を定義するテンプレートである*1concept キーワードは entity として追加され*2、以下のようにして定義する*3。これを concept-definition という。

template<template-parameter-list> concept concept-name = constraint-expression;

constraint-expressionconstraint-parameter は以下の通り。

template<typename T>
requires C<T>     // C は constraint-expression f1(T) を制約する
T f1(T x) { return x; }

template<C T>       // C は constraint-parameter として f2(T) を制約する
T f2(T x) { return x; }
  • concept-definition はコンセプトを宣言する。その識別子は、そのコンセプトの範囲内でそれを参照する concept-name となる*4
  • concept-definition名前空間のスコープ([basic.scope.namespace])に現れなければならない*5
  • 再帰的に自分自身を参照することはできない。
template<typename T>
concept C = C<T*>; // エラー: recursive concept
  • associated constraint を持たない*6
template<class T> concept bool C1 = true;

template<C1 T> 
concept C2 = true; // エラー: C1 Tは associated constraint を宣言する

template<class T> requires C1<T>
concept C3 = true; // エラー: requires節は associated constraint を宣言する
  • コンセプトの特殊化を示す id-expression(コンセプト名に対して型を指定した形式)は、コンパイル時に normalize を行い、その constraint が満たされていれば真、そうでなければ偽 の bool 型の prvalue を結果としてもたらす*7
template<typename T> concept C = true;
static_assert(C<int>); // OK
  • コンセプトによる constraint は、template name と overload resolution を使用する場合にも考慮され、constraint の partial order 中に比較される
  • インスタンス化する事はできない。明示的にインスタンス化したり、明示的に特殊化したり、部分的にコンセプトを特殊化するプログラムは ill-formed である*8constraint の元の定義の意味は変更できない。以下のいずれの場合も、fの constraint は満たされない。
void f(int) requires false;

f(0); // error: cannot call f

void (*p1)(int) = f; // error: cannot take the address of f

decltype(f)* p2 = nullptr; // error: the type decltype(f) is invalid
// fが評価されていないオペランドであってもそれらの constraint を満たさなければならない
  • concept-definition の最初に宣言されたテンプレートパラメータは、prototype parameter という。variadic concept は、その prototype parameter がテンプレートパラメータパックであるコンセプトである*9

requires

以下の内容は特に指定のない限り 8.1.7 Requires expressions [expr.prim.req] を参照している。キーワードrequiresは、テンプレートファミリの requires-clauseprimary-expression として追加される

  • requires-clause はテンプレート引数または関数宣言の constraints を指定する事ができる。
  • require-expression は、テンプレート引数に関する要件を簡潔に表現する方法を提供する。

要件は、name lookup でチェックするか、型と式のプロパティをチェックすることで確認できる*10。キーワード、requiresに対する構文定義は以下の通りである。

requires-expression:
    requires requirement-parameter-listopt requirement-body
requirement-parameter-list:
    ( parameter-declaration-clauseopt )
requirement-body:
    { requirement-seq }
requirement-seq:
    requirement
    requirement-seq requirement
requirement:
    simple-requirement
    type-requirement
    compound-requirement
    nested-requirement

requires-clause

requires-clause の構文定義は以下の通りである。

requires-clause:
    requires constraint-logical-or-expression
constraint-logical-and-expression:
    primary-expression
    constraint-logical-and-expression && primary-expression
constraint-logical-or-expression:
    constraint-logical-and-expression
    constraint-logical-or-expression || constraint-logical-and-expression

このように requires-clauseconstraint-logical-or-expression のみ受け付ける構文となっており、constraint-logical-or-expressionconstraint-logical-and-expressionprimaty-expression を内包する設計になっている。また、requires-clause は以下のような箇所に記述できる。

template<typename T>
void f(T&&) requires Eq<T>; // 関数宣言子の最後の要素として利用できる
 
template<typename T> requires Addable<T> // またはテンプレートパラメータリストの直後に利用できる
T add(T a, T b) { return a + b; }

この場合、キーワードrequiresに対して何らかの定数式が続かなければならない。例えばrequires true;と書くこともできる。定数式は上記構文の通り、以下のいずれかでなければならない。

  • primary-expression
  • 演算子 && で結合された primary-expression のシーケンス
  • 演算子 || と結合された前述の式のシーケンス

尚、仮想関数が requires-clause を持つ事はできない。

struct A {
    virtual void f() requires true; // error: constrained virtual function
};

requires-expression

requires-expressionは、以下で述べられる bool 型の prvalue である。requirement-body に現れる式は評価されないオペランドである。

simple-requirement

simple requirement:
    expression;

simple-requirement は、式の妥当性を主張できる。テンプレート引数の式への置換に失敗した場合、包含する requires-expression は false に評価される。

template<typename T> concept C =
requires (T a, T b) {
a + b; // C<T> is true if a + b is a valid expression
};

type-requirement

type-requirement:
    typename nested-name-specifieropt type-name ;

type-requirement は、型の妥当性を主張できる。テンプレート引数の式への置換に失敗した場合、包含する requires-expression は false に評価される。

template<typename T, typename T::type = 0> struct S;
template<typename T> using Ref = T&;
template<typename T> concept C =
    requires {
        typename T::inner; // required nested member name
        typename S<T>; // required class template specialization
        typename Ref<T>; // required alias template substitution, fails if T is void
     };

compound requires

compound-requirement:
    { expression } noexceptopt return-type-requirementopt ;
return-type-requirement:
    trailing-return-type
    -> cv-qualifier-seqopt constrained-parameter cv-qualifier-seqopt abstract-declaratoropt

compound-requires は式Eの特性をアサートする。テンプレート引数の置換(もしあれば)と意味論的特性の検証は、以下の順序で進行する。

  • テンプレート引数(存在する場合)を式に substitution する。
  • noexcept 指定子が存在する場合、Eは potentially-throwing な式ではないか。
  • return-type-requirementが存在する場合、
    • テンプレート引数(ある場合)をreturn-type-requirementに substitution する。
    • return-type-requirementtrailing-return-type の場合、Eは trailing-return-type で指定された型に暗黙的に変換可能であるか。変換が失敗した場合、包含する requires-expression は false である。
    • return-type-requirementconstraint-parameter で始まる場合、式は 17.8.2.1*11 の規則を使用して生成された関数テンプレート Fに対して演繹される。F は、単一の型のテンプレートパラメータTが constraint-parameter で宣言された void 関数テンプレートである。constrained-parameter から constと volatile 指定子の和集合を取って、新しい cv-qualifier-seq cvを作成する。 F にはtype-specifierが cv T で、その後に abstract-declarator が続く単一のパラメータがある。演繹が失敗した場合、含包する requirement-expression は false である。
template<typename T> concept C1 =
    requires(T x) {
        {x++};
    };

C1 の compound-requirement は、式x++が有効であることを要求する。これは、同じ式を持つ simple-requirement に相当する。

template<typename T> concept C2 =
    requires(T x) {
        {*x} -> typename T::inner;
    };

C2 の compound-requirement には、*xが有効な式であり、typename T::innerが有効な型であり、*xtypename T::innerに暗黙的に変換可能である事を要求する。

template<typename T, typename U> concept C3 = false;
template<typename T> concept C4 =
    requires(T x) {
        {*x} -> C3<int> const&;
    };

template<C3<int> X> void f(X const&); // #1

C4 の compound-requirement は、*xが生成された関数の引数として演繹される事を要求する。この場合、C3 は常に false であるため、演繹は常に失敗する。

template<typename T> concept C5 =
    requires(T x) {
        {g(x)} noexcept;
    };

C5 における compound-requirement は、g(x)が有効な式であり、g(x)が nonthrowing である事を要求する。

用語の定義

constraint

constraint は、logical operands のシーケンスであり、テンプレート引数の要件を指定するオペランドである。また、logical operation(論理演算) のオペランドは constraints である。constraint は

  • conjunction
  • disjunction
  • atomic constraint

の 3種類である。

associated constraint

  • 関連づけられた constraint を associated constraint という。
  • constaint 付きのテンプレートをインスタンス化するには、関連づけられた constraint 条件を満たす必要がある。
  • “関連づけられた” constraint は以下のように定義される。
    • constraint-expression がない場合、宣言には associated constraint がない。
    • それ以外の場合で、導入された constraint-expression が1つだけ存在する場合、constraint-expression はその式の normal form となる。
    • それ以外の場合、associated constraint は、オペランドが次の順序にある​ logical and expression の normal form である。
      • 宣言の template-parameter-list 内の各 constraint 付きパラメータによって導入された constraint-expression が外観順に並べ替えられ
      • template-parameter-listに続くrequire-clauseによって導入された constraint-expression
      • 関数宣言末尾の requires-clause によって導入された constraint-expression
template<typename T> concept C1 = sizeof(T) == 1;
template<typename T> concept C2 = C1<T>() && 1 == 2;
template<typename T> concept C3 = requires { typename T::type; };
template<typename T> concept C4 = requires (T x) { ++x; }

template<C2 U> void f1(U);      // The associated constraints are sizeof(T) == 1 (with mapping T↦U) ∧ 1 == 2. 
template<C3 U> void f2(U);      // The associated constraints are requires { typename T::type; } (with mapping T↦U). 
template<C4 U> void f3(U);      // The associated constraints are requires (T x) { ++x; } (with mapping T↦U).

*12

優先順序関係

コンセプトはオーバーロード解決における順序関係の決定に対して作用する言語機能の1つである。主に [over.match] 等で定義されるオーバーロード解決の作用に加えてコンセプトの機能がその優先順序に影響を与える。

オーバーロード候補の関数を f1, f2 とする時、

  •  f1, f2 の両者とも constraints を持っていて、constraints  X を包含する constraints  P ( X \subset P または  P \supset X)を  f1 が、constraints  X f2 が持っている時、 P is more constrained than  X が成り立ち、 f1 が優先される。
  •  f1 のみ constraints を持っている時、f1 が優先される。
  • そうでない場合、どちらも優先されない → コンセプトによる順序関係は成り立たない。


constraint には、前述した通り conjunction と disjunction (合接と離接)という2つの二項論理演算*13、と1つの部類があり、それぞれの constraint ごとに規定が定められている。

conjunction

  • ある constraint  P Q の conjunction ( P \land Q) は、P && Qとして指定する。
  • 2つの constraint の conjunction は、両方の constraints が満たされる場合にのみ満たされる。conjunction は左から右に評価され、短絡される。例えば left constraint(左の制約) が満たされない(not satisfied)場合、right constraint(右の制約) へのテンプレート引数の置換は行われない*14
  • constraint conjunction における演算子&&のユーザー定義オーバーロードは許可されない。
  • (1  P \land Q is more constrained than  P (2  P \land Q is more constrained than  Q である時 (1 と (2 が成り立つ。
template<class T>
concept Arithmetic = std::is_arithmetic_v<T>;
template<class T>
concept SignedArithmetic = Arithmetic<T> && std::is_signed_v<T>;
template<class T>
concept UnsignedArithmetic = Arithmetic<T> && !SignedArithmetic<T>;
template<class T>
concept C = false && UnsignedArithmetic<T>; // The right constraint(UnsignedArithmetic<T>) is never substituted.

void f(Arithmetic); /* Never called because concept of SignedArithmetic is a <i>more constrained</i> than concept of Arithmetic.
 'Arithmetic ∧ std::is_signed_v<T> (SignedArithmetic)' is <i>more constrained</i> than 'Arithmetic'. */
void f(SignedArithmetic);
void f(UnsignedArithmetic);

*15

disjunction

  • ある constraint  P Q の disjunction ( P \lor Q) は、P || Qと指定する。
  • いずれかの constraints が満たされれば、2つの constraint の disjunction が成立する(satisfied)。離接は左から右に評価され、短絡される。例えば left constraint(左の制約) が満たされている場合、right constraint(右の制約) への template argument deduction は試行されない)。
  • constraint disjunction における演算子||のユーザー定義オーバーロードは許可されない。
  • (1  P is more constrained than  P \lor Q (2  Q is more constrained than  P \lor Q である時 (1 と (2 が成り立つ。
template<class T>
concept C = true || std::is_same_v<T,int>; // Template argument deduction into the right constraint(std::is_same_v<T,int>) is never attempted.

*16

atomic constraint

  • conjunction でも disjunction でもない constraint が atomic constraint である。
  • constraint expression は logical and または logical or でもない。
  • Atomic constraints は constraint normalization によって形成される。
  • 2つの atomic constraint が同じ式から形成され、パラメータマッピングのターゲットが [temp.over.link] の式の規則*17に従って同等である場合、2つの atomic constraint は同一の constraint である。それ以外の場合は、異なる constraint である。
template<typename T> concept C = sizeof(T) == 4 && !true;      // requires atomic constraints sizeof(T) == 4 and !true

template<typename T> 
struct S {
  constexpr operator bool() const { return true; }
};

template<typename T> requires (S<T>{})
void f(T);                      // #1
void f(int);                    // #2

void g() {
  f(0);                         // error: expression S<int>{} does not have type bool
}                               // while checking satisfaction of deduced arguments of #1;
                                // call is ill-formed even though #2 is a better match

順序関係の生成

各 constraint の強弱を比較するためには associated constraint を normalize して normal form を生成しある規則に則って constraint 間の subsume 関係を成立し、その関係性から順序関係を成り立たせるプロセスが必要である。

normal form

式 Eの normal form とは、次のように定義される constraint である。

  • 式(E) の normal form は、Eの normal form である。
  • normal form の式E1 || E2は normal form の E1 と E2 の disjunction である。
  • normal form の式E1 && E2は normal form のE1 と E2 の conjunction である。
  • id-expressionC<A1, A2, ..., An>の normal form は、Cがコンセプト名である時、CのそれぞれのテンプレートパラメータにA 1, A 2, …, A nを substituting した後のCの制約式の normal form であり各 atomic constraint の parameter mapping で使用される。そのような置換が無効である型または式になった場合、ill-formed; NDR
  • それ以外の任意の式 E の normal form は、式 E で構成された atomic constraint である。
  • normalization によって残るものは、predicate constraints, expression-constraints, type constraints, implicit conversion constraints などの atomic constraints に関する一連の conjunction および disjunction である。argument deduction constraints および exception constraints が含まれる。
  • normal form には以下の二つの種類があり、全ての constraint はどちらの normal form にも同時に解釈する事ができる。
    • conjunctive normal form → 各節が atomic constraint の disjunction である節の conjunction である形
    • disjunctive normal form → 各節が atomic constraint の conjunction である節の disjunction である形
conjunctive, disjunctive normal form

 A, B, C が atomic constraint であり、 A \land (B \lor C) という constraint-expression がある時、

  • constraint  A \land (B \lor C) は conjunctive normal form である。その conjunctive 節は A(B \lor C)である。
  • constraint  A \land (B \lor C) の disjunctive normal form は (A \land B) \lor (A \land C)である*18。その disjunctive 節は  (A \land B) (A \land C) である。

normalization は ill-formed を引き起こす場合がある*19

template<typename T> concept A = T::value || true;
template<typename U> concept B = A<U*>;
template<typename V> concept C = B<V&>;

T::valueがポインタ型Tに対して ill-formed であるにも関わらず コンセプトBの normalize は有効であり、T​::​value (with the mapping T↦U*) ∨ true (with an empty mapping)である。更に C の constraint-expression を normalize すると、パラメータマッピングに無効な型T&*が形成され、ill-formed NDR となる。

Partial ordering by constraints

partial ordering 関係における constraint 同士は以下のようにしてその constraint の強弱を定め(subsume するか否か)、more constrained 関係を構築する事ができる。
2つの constraint  P Q 間で more constrained 関係を定める時、constraint  P は、以下に述べられるように、 P Q を含み、 P および  Q の atomic constraint の同一性([temp.constr.atomic]/paragraph 2、atomic constraint の説明で前述した同一規則)までを決定することができる場合、別の constraint  Q を包含すると言われる(A constraint P is said to subsume another constraint Q)。

  • constraint  P を disjunctive normal form に normalize し、constraint  Q を conjunctive normal form に normalize する。
  •  P は、 P の disjunctive normal form の全ての disjunctive 節 P_i が conjunctive normal form  Q のすべての conjunctive 節  Q_j を包含(subsume)する場合にのみ、 Q を包含(subsume)する。
  • disjunctive 節  P_i 内の atomic constraint  P_{i_a} が存在し、 P_{i_a} が atomic constraint  Q_{j_b} を含む(subsume)ように conjunctive 節  Q_j 内に atomic constraint  Q_{j_b} が存在する場合に限り、P_iQ_j を包含(subsume)する。
  • atomic constraint  A, B は、[temp.constr.atomic] の同一規則において  A B が等価である場合にのみ、 B を包含(subsume)する。

     A, B を atomic constraint とした時、constraint  A \land B A を包含(subsume)するが、A A \land B を包含(subsume)しない。constraint  A A \lor B を包含(subsume)するが、 A \lor B A を包含(subsume)しない。また、すべての constraint がそれ自身を包含(subsume)している。

 P A \land (B \lor C) Q A \lor C とした時の P Q 間の順序関係を考える*20

  •  P を disjunctive normal form に normalize し  (A \land B) \lor (A \lor C) Q を conjunctive normal form に normalize し  A \lor C とする。この時、disjunctive 節  P_1 (A \land B) P_2 (A \land C) であり、conjunctive 節  Q_1 A \lor C である。
  •  P_1Q_1 を比較した時、 P_1 内の conjunction における left operand AQ_1 内の disjunction における left operand  A と atomic constraint の同一性規則([temp.constr.atomic]/paragraph 2])に則って同一であるため P_1 Q_1 を包含(subsume)する。また、 P_2Q_2 を比較した時、 P_2 内の conjunction における left operand A Q_1 の disjunction における left operand A と atomic constraint の同一性規則([temp.constr.atomic]/paragraph 2])に則って同一であるため、P_2 Q_1 を包含(subsume)する。
  • よって  P_1 subsume  Q_1 かつ*21  P_2 subsume  Q_1 より  P subsumes  Q

     P Q をそれぞれ入れ替え、 P A \lor C Q A \land (B \lor C) とする。

  •  P を disjunctive normal form に normalize し  A \lor C Q を conjunctive normal form に normalize し  A \land (B \lor C) とする。この時、disjunctive 節 P_1AP_2C であり、conjunctive 節 Q_1 AQ_2(B \lor C) である。

  •  P_1 Q_1 を比較した時、 P_1 内の  A Q_1 内の  A と atomic constraint の同一性規則([temp.constr.atomic]/paragraph 2])に則って同一であるため、P_1Q_1 を包含(subsume)する。また、P_1Q_2 を比較した時、P_1 内の  A Q_2 内の disjunction における left operand B 及び right operand C のどちらも atomic constraint の同一性規則([temp.constr.atomic]/paragraph 2])に則り同一ではないため、P_1 Q_2 を包含(subsume)しない。
  • よって  P_1 does not subsume  Q_2 より P does not subsume Q

    以上から  A \land (B \lor C) subsumes  A \lor C となり2つの constraints において  A \land (B \lor C) の優先順序が高いと言える。
    このように、これらの包含(subsume)関係は前述している通り constraint の partial order を定義しこの部分的な順序付けは、以下の5つの場合における決定に作用する。

  • 非テンプレート関数の中で最も有望な候補([over.match.best])の決定

  • 非テンプレート関数のアドレス([over.over])の決定
  • テンプレートテンプレート引数の一致
  • クラステンプレートの特殊化における partial order
  • 関数テンプレートにおける partial order

at least as constrained

以下の条件を満たす時、宣言 D1 は少なくとも宣言 D2 と同じくらい制約されている(A declaration D1 is at least as constrained as a declaration)と言う。

  • D1とD2は両方とも constraint 付きの宣言であり、D1 の associated constraint は D2 の constraint を包含(subsume)する。または、
  • D2 に associated constraint がない。

    また、宣言 D1 は、D1 が少なくとも D2 と同じくらい制約されていて(D1 is at least as constrained as D2)、D2 が少なくともD1 と同じくらい制約されていない(D2 is not at least as constrained as D1)場合、別の宣言D2よりも制約されている(A declaration D1 is more constrained than another declaration D2)という。

余談

コンセプトに対する反応諸々。

p0726r0 はコンセプトの理想と現実から始まり、SFINAEとstd::enable_ifが既にあるだろうとしている。尚、上記ツイートにあるもう一つのリンク p0724r0 には以下のように述べられている。

I am well aware of that, but I'm boldly suggesting that we take a brave step and send a message to the C++ community that we are serious about having Concepts in C++20. In fact, a leap so brave that we merge the current wording in and all commit to finishing it up design-wise, wording-wise and otherwise before C++20 goes out, without missing its schedule.

I'm also well aware that we don't usually merge new wording which has known issues (except when we do, but that happens much more rarely for Core than Library). Perhaps this facility is significant enough to make an exception.

*1:17.6.8 Concept definitions [temp.concept]/paragraph 1

*2:6.1 Basic concepts [gram.basic]

*3:17 Templates [temp]/paragraph 1

*4:17.6.8 Concept definitions [temp.concept]/paragraph 2

*5:17.6.8 Concept definitions [temp.concept]/paragraph 3

*6:17.6.8 Concept definitions [temp.concept]/paragraph 4

*7:8.1.4 Names [expr.prim.id]/paragraph 3

*8:17.6.8 Concept definitions [temp.concept]/paragraph 5

*9:17.6.8 Concept definitions [temp.concept]/paragraph 6

*10:8.1.7 Requires expressions [expr.prim.req]

*11:17.8.2 Explicit instantiation [temp.explicit]

*12:17.4.3 Constraint normalization [temp.constr.normal]/paragraph3

*13:これらの論理演算には対応するC++構文がないため、ドラフト文書では解説の目的で、記号  \land を使用して conjunction (合接) を示し、記号  \lor を使用して disjunction (離接) を示す事がある。これらのオペランドは、left operand または right operand と呼ばれる。制約 A ∧ B では、A が left operandであり、Bが right operand である。

*14:これにより immediate context 外での substitution による諸々の hard error とかを防止できる。諸々の hard error については https://twitter.com/530506/status/907423269417914368 などを参照

*15:17.4.1.1 Logical operations [temp.constr.op]/paragraph 2

*16:17.4.1.1 Logical operations [temp.constr.op]/paragraph 3

*17:[temp.over.link]/paragraph 5, 同セクション/paragraph 6, 同セクション/paragraph 7 等を参照

*18:conjunctive normal form に分配法則を適用する

*19:17.4.3 Constraint normalization [temp.constr.normal]/paragraph1.4

*20:一見して強い constraint が分かりうるパターンではあるが、例として17.4.4 Partial ordering by constraints [temp.constr.order]/paragraph 2/footer note 138 に記載されている  A \land (B \lor C) を流用している。これに特別な意味はない。

*21:ドラフト上で示されている logical and ( \land) との混同を防ぐために敢えて"かつ"としている