2017-10-19

内蔵ストレージが破損した Mac で USB メモリに Ubuntu 16.04 LTS をインスコしてブート

久しぶりに日記的な内容。

序章

ついにその日が来てしまった。いつもと変わらず Mac の電源ボタンを押すと、フォルダのアイコンに ? のマーク。一旦再起動してオプションキーを押しながら起動するも、起動ディスクが一切一覧に現れない。Apple diagnostics を実行すると Reference code VDH002、的確に内蔵ストレージに問題があることを示した。この Mac は購入してから三年を経過していたので、もはやこれは物理的に逝ってしまったのだろう...などと思いつつアップルに電話を掛けると、やはりそのようであった。
失ったデータとしては、コードや執筆中のドキュメントなどは全て更新があるたびに Github に push していたため然程問題はなかったが、その他のデータとはおさらばする事になってしまった(また探せば良いのだが、分かりやすかった論文やドラフトが消えてしまったのが痛い。)。SSD を付け替えることも考えたが、そろそろ時期も時期なのでいっその事新規で購入してしまおうと思い、それは断念した。しかし、買い換えるまでの間何もできないというのは辛い。家にはデスクトップ機があるが、彼女が映像編集等でグラフィックボードが搭載された PC を必要としているので、まぁそれを使うのも頂けない。さらに出先では、ノート PC がなくては授業の間などの時間がとても無駄になってしまう。こういう場合、どうにかして使えないか考えて行き着くのは、やはり外部ストレージに OS を突っ込んで起動する事だろう。という事で、USB に Ubuntu 16.04 LTS を突っ込んでそれを Mac からブートすることにした。現在は、その Ubuntu からこの記事を書いている。個人的には、最近よく Arch Linux を利用しているので、それを導入しようかと考えたが、Ubuntu のコミュニティが充実していたので Ubuntu を利用する事とした。また、このエントリを書く本日から二日後に Ubuntu 17.10 がリリースされる事は把握しているが、17.10 特有の不具合などに遭遇したくはなかったので、最新の LTS である 16.04 を利用する事としている。

本題

まず必要となってくるのが、他のインターネットに接続できる PC と3つ以上の USB または、外付け HDD などのストレージだ。Ubuntu の iso ファイルを入手するために当然インターネットは必要だ。また、サードパーティー製のプロプライエタリなネットワーク機器のモジュールは、Ubuntu のデフォルトインストールでは導入されない事もあるので、それらを導入するのに手動でオンライン状態にある PC でパッケージを入手し、物理的にブートとは別の USB ストレージを利用してデータを転送しなければならない。3つの外付けメディアは前述した用途と、Ubuntu のライブメディアを作るために必要となる。macOS の入った外付けメディアと Ubuntu のライブメディアとなる外付けメディア、また Ubuntu の iso ファイルを外部から持ち込むためのメディアの合計3つだ。
前述した通り状況として内蔵ストレージは一切認識されない。しかし、まず Ubuntu の Live ブートを行うためには macOS(diskutil) で書きこんだブートメディアが必要だ(そうでなくても可能かもしれないが、EFI のブートに最も手っ取り早く対応させる事ができるだろうとの事から[要出展]）。このような状態でも、セーフモードで macOS を起動することはできる。option + command + R または shift + option + command + R からインターネット経由で macOS を起動する。
そして新規で USB ストレージに一旦 macOS をインストールする。これがそこそこ時間がかかる。
無事インストールが終わると USB ブートのできる macOS が出来上がりだ。これを起動し、もう一つの USB ドライブに iso ファイルを入れておき、それを hdiutil などで iso ファイルから img ファイルに変換する。私は以下のようにした。

$ hdiutil convert -format UDRW -o target.img ubuntu-ja-16.04-desktop-amd64.iso

作成されたイメージをデバイスに対して書き込む。私は以下のようにした。書き込むディスクの指定を間違えると、それなりに面倒な事となるので注意しなければならない。

$ diskutil unmountDisk /dev/disk2
$ sudo dd if=target.img.dmg of=/dev/rdisk2 bs=1m
$ diskutil eject /dev/disk2
$ sudo reboot

再起動したら EFI Boot を選択し Live Ubuntu を起動させる。
次に、Ubuntu の本インストールとなるのだが、その前にパーティションを必ず作成する必要がある。Mac で起動させるためには UEFI モードで起動させなければならないが、そのために、EFI のシステムパーティションが構成されていなければならない。しかし Ubuntu 16.04 LTS を UEFI環境で、パーティションが一つもないストレージに対してデフォルトでインストールをしようとすると、インストーラーがフリーズする不具合が報告されており、続行する事ができない*1。fdisk または GParted でパーティションを作成する。パーティションテーブルを gpt にしてその上に任意のサイズ(200MB程度が推奨されていたためそれに習った)で fat32 のファイルシステムを作成し、それに Esp と Boot フラグを設定しておく。これで、ESP のパーティション設定が完了した。
後はそのままインストールを行うだけだ。インストールメディアの設定部分でその他を選択し、先ほど作成したパーティションに任意のファイルシステムを追加していく。今回は、USB ブートでかつ Mac の RAM が 8GB 程搭載されていたためスワップ領域を一切設けずに ext4 ファイルシステムのみを作成した。これまた少し時間がかかるが、再起動して無事 Ubuntu が起動した。
しかし、無線LAN機器がどうやら正常に動作していないようだった。ifconfig などで状況を見るも、やはり認識すらされていない。
まずは Mac に乗っている無線LAN機器を特定する必要がある。

$ lspci | grep Wireless

私の環境では broadcom 802.11 というデバイスが載っていたのでそれに合うドライバモジュールを導入する。しかしそのためにはパッケージが必要で、服を買うための服がないの如くインターネットへの接続が必要となるので、他の PC でダウンロードして物理的に外部ストレージを差込み、この Ubuntu に移してやる必要がある。broadcom 802.11 である場合は、以下のリンクからパッケージ(amd64)を入手できる。

二つ目の dkms というパッケージは上記 broadcom 802.11 の導入の際に必要となる依存パッケージで、ドライバの自動ビルドツールである。私の環境だと、broadcom 802.11 のモジュールの導入時にこのパッケージが必要である旨を示すメッセージと共に失敗したので恐らく同じケースである場合は必要になるのではないかと思われる。
両者とも、dpkg コマンドで導入し、再起動して、インターネットに接続した。
というわけで無事 Mac の内臓ストレージなしで USB から Ubuntu を起動してそこそこの作業ができるようにはなったのだが、やはりインストールしたストレージが USB 3.0 であるとは言え、体感で分かるほどに遅い。まぁ早く買い換えたいところだが、私のような貧乏学生は、少しの間はこれでやり過ごす必要があるようだ。

*1:どうやら Ubuntu 15.10 でもこの不具合は報告されていたようだが、16.04 LTS では修正されていないようだ

2017-09-30

C++17 structured bindings で [ ] が使われる事情

C++

C++17 から導入される structured bindings は、複数の変数をタプルのようなオブジェクトから初期化する事ができる言語機能であるが、同機能における宣言では { } ではなく [ ] が使われる。
そもそも structured bindings の元々の提案では宣言の構文において { } が使われていた*1。しかしそれが後に変更されて*2 [ ] を使うようになったという事実がある。変更の理由としては P0144r2/p3 によると "because it is more visually distinct from the existing syntax for declaring multiple variables of the same type." と述べられており、これと同じ内容を説明する動画もある。この変更には賛否両論あったようで、中には以下のような NB コメントも挙げられた。

Nested decomposition declarations can’t work, as they clash with the attribute syntax. --- p0488r0/p4

The “structured bindings” proposal originally used braces “{}” to delimit binding identifiers. Those delimiters were changed to brackets “[]” under the assertion that they didn’t introduce any syntactic problem. However, they turned out to introduce syntactic ambiguity with attributes and lambdas. In the light of various suggested fixes, it appears the original syntax is more adequate. --- p0488r0/p6

また、Botond Ballo 氏の trip report によると[ ]は attribute と競合する可能性があり、また{ }は auto の代わりにコンセプト名を使用できるようにする(!)と、Uniform initialization と競合する可能性があるため、両者に技術的な問題があるとしている。しかし clang の実装者は両方を試した結果、[ ] を利用した方が実装上の曖昧さを回避するのに容易である事を発見したと報告しており、結果的には{ }への変更の合意はなかったため、[ ]を使う構文が残ったという。
個人的には、既存の資産を持つ言語に対して機能を付け加える時、"ユーザーの混乱を最小限に抑える"と"パースを簡単にする"という相互に矛盾したリスクをどのように捉えて設計するかが言語そのものになると私は考えているのだが、その点においてこの仕様は、良くも悪くも何となく C++ らしいなと思った。

*1:P0144R0

*2:P0217R1 + P0144R2

2017-09-23

Usage of void() in a comma-separated list

C++

,で連結されたリストにおけるvoid()がどのような意味を持つのか。

a(), void(), b();

これは単純にオーバーロードされたoperator ,の呼び出しを防ぎ、言語による sequencing guarantees を保証するためのものである。void型のパラメータを持ったオーバーロードを定義する事はできないのでそれを防ぐ事ができる。例えば、variadic pack の展開ではよく用いられる。

template <class...> struct FirstType;
template <class Head, class... Tail>
struct FirstType <Head,Tail...> : std::enable_if<true, Head>{};

template <class T, class Allocator = std::allocator<T>>
struct X : std::vector<T, Allocator>{
    using std::vector<T,Allocator>::vector;
    
    template <class ValueType, std::enable_if_t<std::is_same<std::decay_t<ValueType>, X>::value, std::nullptr_t> = nullptr>
    ValueType&& operator,(ValueType&& x)
    {
        std::cout << "hoge" << std::endl;
        return std::forward<ValueType>(x);
    }
};

template <class Head, class... Tail>
Head&& do_something(Head&& head, Tail&&...)
{
    return std::forward<Head>(head);
}

template <class... Ts>
void f(Ts&&... ts)
{
    [[maybe_unused]] X<std::decay_t<typename FirstType<Ts...>::type>> a{X<int>{}, (do_something(std::forward<Ts>(ts)), void(), X<int>{})...}; // no hoge
}

2017-09-14

aggregate, aggregate initialization まとめ

C++

C++ における aggregate と aggregate initialization についてのメモ。
まずバージョンごとの aggregate の定義から。

aggregate

C++03

aggregate とは*1

配列または
以下の要件を満たすクラスである
- ユーザー定義コンストラクタがない
- private または protected な非 static data member がない
- 基底クラスがない
- 仮想関数がない

C++11

aggregate とは*2

配列または
以下の要件を満たすクラスである
- ユーザー定義コンストラクタがない(明示的にデフォルト、または削除されたコンストラクタを除く)
- 非 static data member に対する brace-or-equal-initializer*3 がない
- private または protected な非 static data member がない
- 基底クラスがない
- 仮想関数がない

C++11 から default member initializer が導入されたが、同機能を用いた場合そのクラスは aggregate ではない。

C++14

aggregate とは*4

配列または
以下の要件を満たすクラスである。
- ユーザー定義コンストラクタがない(明示的にデフォルト、または削除されたコンストラクタを除く)
- private または protected な非 static data member がない
- 基底クラスがない
- 仮想関数がない

C++14 では非 static data member に対する brace-or-equal-initializer があっても(default member initializerを用いても) aggregate と見なされる。

struct X{ // aggregate
    int x = 42;
};

C++17

aggregate とは*5

配列または
以下の要件を満たすクラスである。
- ユーザー定義の明示的、または継承されたコンストラクタがない(明示的にデフォルト、または削除されたコンストラクタを除く)
- private または protected な非 static data member がない
- 仮想関数がない
- 仮想、private 及び protected な基底クラスがない

C++17 では基底クラスを持っていてもそれを public で継承しているのであれば aggregate であると見なされる。この時、aggregate initialization では、protected または private な基底クラスの member またはコンストラクタへのアクセスは許可されない。

struct X{
    int a;
};
struct Y:X{ // aggregate
    int b;
};

またこの仕様により、ある aggregate クラスの基底型と convertible であるオブジェクトBで aggregate クラスDのオブジェクトの初期化を行える。

struct B{};
struct D:B{};
struct A{
    operator B() { return {}; }
};

D{B{}}; // OK: C++17
D{A{}}; // OK: C++17

この機能を利用して例えば aggregate クラスが基底クラスを持つかどうか検出する事ができる。

stackoverflow.com

まずテンプレートパラメータの適切な基底クラス型に変換できるクラステンプレートを作成する。

template<class T>
struct any_base{
    operator T() = delete;
    template<class U, class  = std::enable_if_t<std::is_base_of_v<U,T>>>
    operator U();
};

次にテンプレートパラメータTがany_base型の値から constructible な aggregate であるかどうかを検出する。

template<class, class = void>
struct has_any_base : std::false_type{};

template<class T>
struct has_any_base<T, std::void_t<decltype(T{any_base<T>{}})>> : std::true_type {};

以下に動作の概要を示す

implicit conversion によってTの初期化を試みる
any_base をTそのものに変換する implicit conversion の member function は削除されているため any_base から T の値は取得できない。
any_base から Tの値は取得できないためTのそれ以外の初期化方法を考慮する必要があるが、返される型はstd::is_base_ofによって継承関係が要求されているため、その要件を唯一満たすのは、aggregate クラスの基底型のオブジェクトでその aggregate クラスの派生型のオブジェクトを初期化する事である。
- それが不可能である場合、推論から外れる
- それが可能である場合、Uは aggregate クラスTの基底型に推論される
候補がある場合、substitution に成功、候補がない場合、substitution に失敗する。

C++20

C++17 と変わらない*6。

aggregate initialization

aggregate 型のオブジェクトは、braced-init-list を使って初期化する事ができる。構文は以下の通りである。

T object = { arg1, arg2, ...};

C++11 で uniform initialization が導入されたため、C++11 以降では以下の構文も適用できる。

T object{arg1, arg2, ...};

C++20 で Designated initializers が導入されたため、C++20 以降では以下の構文も適用できる。

T object = { .designator = arg1, .designator{arg2}...};
T object{ .designator = arg1, .designator{arg2}...};

Designated initializers

C++20 から追加される Designated initializers の構文を以下に示す。n4687 11.6 Initializers [dcl.init] から抜粋

$initializer:\\ \hspace{8pt}brace-or-equal-initializer\\ \hspace{8pt}( expression-list )$

$brace-or-equal-initializer:\\ \hspace{8pt} = initializer-clause\\ \hspace{8pt}braced-init-list$

$initializer-clause:\\ \hspace{8pt}assignment-expression\\ \hspace{8pt}braced-init-list$

$braced-init-list:\\ \hspace{8pt}\{initializer-list ,_{opt} \} \\ \hspace{8pt}\{designated-initializer-list ,_{opt} \}\\ \hspace{8pt}\{ \}$

$initializer-list:\\ \hspace{8pt}initializer-clause\ldots_{opt}\\ \hspace{8pt}initializer-list, initializer-clause\ldots_{opt}$

$designated-initializer-list:\\ \hspace{8pt}designated-initializer-clause\\ \hspace{8pt}designated-initializer-list, designated-initializer-clause$

$designated-initializer-clause:\\ \hspace{8pt}designator\hspace{2pt}brace-or-equal-initializer$

$designator:\\ \hspace{8pt}. identifier$

$expr-or-braced-init-list:\\ \hspace{8pt}expression\\ \hspace{8pt}braced-init-list$

各 $designator$ はTの direct non-static member に名前を付ける必要があり、式で使用される全ての $designators$ はTの data member と同じ順序で現れなければならない。

struct X{ int x; int y; int z; };
A a{.y = 2, .x = 1}; // エラー！ designator の順序が宣言の順序と一致しない
A b{.x = 1, .z = 2}; // OK: b.y は 0で初期化される

$designated-initializer-list$ を用いて初期化する時、それらは $designator$ の後に続く、それぞれが対応する $brace-or-equal-initializer$ によってコピー初期化される。もし $initializer$ が $assignment-expression$ または $= assignment-expression$ の形式であり、式を変換するために narrowing conversion*7 が必要である場合プログラムは ill-formed となる。designated initializer を利用して、union を以下のように最初の状態以外の状態に初期化する事ができる。union に対しては、 $initializer$ を1つだけ指定できる。

union U{ int a; const char* b; };
U f = {.b = "abcd"}; // OK: f の active member は b
U g = {.a = 1, .b = "abcd"}; // エラー！1つの initializer のみ利用できる

非 union aggregate である場合、明示的に初期化された要素ではない各要素は次のように初期化される。

要素にデフォルトの default member initializer がある場合、要素はその initializer から初期化される。
それ以外の場合、要素が参照できない場合、要素は空の initializer list からコピー初期化される。
それ以外の場合、プログラムは ill-formed である。

struct A {
  int x;
  struct B {
    int i;
    int j;
  } b;
} a = { 1, { 2, 3 } }; // initializes a.x with 1, a.b.i with 2, a.b.j with 3

struct base1 { int b1, b2 = 42; };
struct base2 {
  base2() {
    b3 = 42;
  }
  int b3;
};
struct derived : base1, base2 {
  int d;
};

derived d1{{1, 2}, {}, 4}; // initializes d1.b1 with 1, d1.b2 with 2, d1.b3 with 42,d1.d with 4
derived d2{{}, {}, 4}; // initializes d2.b1 with 0, d2.b2 with 42, d2.b3 with 42, d2.d with 4

union aggregate であり、initializer list が空の場合

任意の variant member が default member initializer を持つ場合、その member はその default member initializer から初期化される。
それ以外の場合は、共用体の最初のメンバー(存在する場合)が空の初期化子リストからコピー初期化される。

指定された $designated initializer clause$ で初期化された aggregate が匿名の union member を持つ場合、対応する designated initializer は、その匿名化された union の member の1つに名前を付ける必要がある。また、順序が不定である初期化、ネストされた designated initialization、指定された initializer と通常の initializer の混合、および配列の指定された初期化は全てC99でサポートされる機能であるが、C++20では許可されない。

struct A { int x, y; };
struct B { struct A a; };
struct A a = {.y = 1, .x = 2}; // valid C, invalid C++ (out of order)
int arr[3] = {[1] = 5};        // valid C, invalid C++ (array)
struct B b = {.a.x = 0};       // valid C, invalid C++ (nested)
struct A a = {.x = 1, 2};      // valid C, invalid C++ (mixed)

*1:C++ Standard - ANSI ISO IEC 14882 2003 8.5.1 Aggregates [dcl.init.aggr]/paragraph 1

*2:n3337 8.5.1 Aggregates [dcl.init.aggr]/paragraph 1

*3:= assignment-expression または = braced-init-list または braced-init-list

*4:n4140 8.5.1 Aggregates [dcl.init.aggr]/paragraph 1

*5:n4660 11.6.1 Aggregates [dcl.init.aggr]/paragraph 1

*6:執筆時現在では不確定要素を含むため後に変更される可能性がある

*7:11.6.4 List-initialization [dcl.init.list]/paragraph 7

2017-09-06

n4687 C++ extensions for Concepts

C++

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

コンセプト

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

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

constraint-expression、constraint-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 である*8 → constraint の元の定義の意味は変更できない。以下のいずれの場合も、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-clause と primary-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-clause は constraint-logical-or-expression のみ受け付ける構文となっており、constraint-logical-or-expression は constraint-logical-and-expression と primaty-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-requirement が trailing-return-type の場合、Eは trailing-return-type で指定された型に暗黙的に変換可能であるか。変換が失敗した場合、包含する requires-expression は false である。
- return-type-requirement が constraint-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が有効な型であり、*xがtypename 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_i$ は $Q_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_1$ と $Q_1$ を比較した時、 $P_1$ 内の conjunction における left operand $A$ は $Q_1$ 内の disjunction における left operand $A$ と atomic constraint の同一性規則([temp.constr.atomic]/paragraph 2])に則って同一であるため $P_1$ は $Q_1$ を包含(subsume)する。また、 $P_2$ と $Q_1$ を比較した時、 $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_1$ が $A$ 、 $P_2$ が $C$ であり、conjunctive 節 $Q_1$ が $A$ 、 $Q_2$ が $(B \lor C)$ である。
$P_1$ と $Q_1$ を比較した時、 $P_1$ 内の $A$ は $Q_1$ 内の $A$ と atomic constraint の同一性規則([temp.constr.atomic]/paragraph 2])に則って同一であるため、 $P_1$ は $Q_1$ を包含(subsume)する。また、 $P_1$ と $Q_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)という。

余談

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

https://t.co/UwzaPKw12H vs. https://t.co/WzBIKbXWG3 ﾌｧｲｯ!
— roκi (@530506) 2017年8月8日

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$ ) との混同を防ぐために敢えて"かつ"としている

2017-09-04

Can non-type template parameters in c++17 be decltype(auto)?

C++ reading English

stackoverflow.com

template <decltype(auto)> // Is this legal by standard?
struct X {};

結論：
合法である。

n4659 17.1 Template parameters [temp.param]/paragraph 4 に non-type template parameters が持てる型について示されている(下線部は強調)。

A non-type template-parameter shall have one of the following (optionally cv-qualified) types:
- integral or enumeration type,
- pointer to object or pointer to function,
- lvalue reference to object or lvalue reference to function,
- pointer to member,
- std::nullptr_t, or
- a type that contains a placeholder type.

“a type that contains a placeholder type” に関する記述同ドラフト 10.1.7.4 The auto specifier [dcl.spec.auto]/paragraph 1

The auto and decltype(auto) type-specifiers are used to designate a placeholder type that will be replaced later by deduction from an initializer. The auto type-specifier is also used to introduce a function type having a trailing-return-type or to signify that a lambda is a generic lambda ([expr.prim.lambda.closure]). The auto type-specifier is also used to introduce a structured binding declaration.

autoとdecltype(auto)型指定子は、後で初期化子から差し引かれる placeholder type を指定するために使用され、同セクション/paragraph 5

A placeholder type can also be used in the type-specifier-seq in the new-type-id or type-id of a new-expression and as a decl-specifier of the parameter-declaration's decl-specifier-seq in a template-parameter.

placeholder type はテンプレートパラメータ内のパラメータ宣言 decl-specifier-seqの宣言指定子として使用できる。

2017-09-01

non-type template parameter におけるデータの受け渡しから TMP で実数を含む value computing を行う

C++

push してからしばらく経っているが記録もかねて。C++ の non-type template parameter には浮動小数点型などの数値を直接与えることはできない。しかし、型の内部に内包させて Expression templates のようにその値を取り出そうとした瞬間に型情報に紐付いている式の形を展開させられれば実質 template arguments を利用してでも浮動小数点数値を受け渡し、かつ value computing を行う事ができる。基本的に、TMP はそれを純粋関数型言語とみなして記述するので*1、式の形を保持しておき遅延評価を行うという解はまぁ当然と言える。実装そのものはそこそこ小さくまとまっていると思われる。これを利用すると、以下のように浮動小数点などの値を non-type template parameter 経由で扱うことができる。

一応 Polish Notation と infix notation 的な両記法をサポートしているようなつもりでいる。上記のコードは特別意味のある計算をしていないが、例えばこれを使えば理論的には TMP によるコンパイル時マンデルブロ集合を得る事ができたりする(コンパイル時Cコンパイラがあるので不思議な事ではないが)。

しかし残念ながらこのコードは実際には動かない。コード中冒頭のコメントにもあるとおり、メモリを大量に食い尽くしてしまうからだ。浮動小数点計算を non-type template parameter 経由で行えるようにしたところで特別何か使い道も思いつかないのだが、例えばコンパイル時にコサインテーブルを生成するぐらいであれば容易にできる。実際フルスクラッチで以前に書いた JPEG エンコーダ/デコーダのコサインテーブルはそれを利用している。

*1:この辺りの C++ TMP における~~無駄な~~活用については any_pack や TMPによるコンパイル時乱数アルゴリズムの実装や TMPによる四則演算パーサ等を参照されたい

Rokiのチラ裏

学生による学習のログ

内蔵ストレージが破損した Mac で USB メモリに Ubuntu 16.04 LTS をインスコしてブート

序章

本題

C++17 structured bindings で [ ] が使われる事情

Usage of void() in a comma-separated list

aggregate, aggregate initialization まとめ

aggregate

C++03

C++11

C++14

C++17

C++20

aggregate initialization

Designated initializers

n4687 C++ extensions for Concepts

コンセプト

requires

requires-clause

requires-expression

simple-requirement

type-requirement

compound requires

用語の定義

constraint

associated constraint

優先順序関係

conjunction

disjunction

atomic constraint

順序関係の生成

normal form

conjunctive, disjunctive normal form

Partial ordering by constraints

例

at least as constrained

余談

Can non-type template parameters in c++17 be decltype(auto)?

non-type template parameter におけるデータの受け渡しから TMP で実数を含む value computing を行う