Rokiのチラ裏

学生による学習のログ

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

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_packTMPによるコンパイル時乱数アルゴリズムの実装TMPによる四則演算パーサ等を参照されたい

stack overflow からの小ネタメモ #3

前回

stackoverflow.com C++98(03) ではstd::vectorの fill コンストラクタのプロトタイプに初期化子のデフォルト値があるが C++11 では削除されている。 C++03 – ISO 14882:2003 23.2.4.1 vector constructors, copy, and assignment [lib.vector.cons] から一部引用。

explicit vector(size_type n, const T& value = T(),const Allocator& = Allocator());

続いて N3337 23.3.6.2 vector constructors, copy, and assignment [vector.cons] から一部引用。

vector(size_type n, const T& value,const Allocator& = Allocator());

C++98(03) はプロトタイプオブジェクトを取り出し、それをn回コピーした。C++11では、n個のデフォルトオブジェクトが構築されるようになった事で、n個のコピーが削除され、n個のデフォルト構成に置き換えられる事となった。また、copy-constructible を要求する必然性はないのでそれが排除された。

stackoverflow.com

他のコンストラクターが有効でない場合にのみ呼び出される、variadic forwarding reference constructor の SFINAE 定義において以下のような解決策が講じられた。gcc 5.2.0 と clang 3.7.0 では意図した通りに動くが、これはどのように動作するのか、また合法か否か。

template <typename... T,typename = std::enable_if_t<!std::is_constructible<C, T&&...>::value>>
C(T&&... ) { }

現在の作業草案では、デフォルトのテンプレート引数がインスタンス化されるタイミングは記述されていない*1*2。興味深いのは、LWG 2452 でもあるようにそのセマンティックスを無視するかのような動作をする事だ。

struct C {
  C(const char*, size_t) {}
  template <class... Ts,
    typename = std::enable_if_t<!std::is_constructible<C, Ts&&...>::value>
  >
  C(Ts&&... ) { }
};

int main() {
  int a = 0;
  C x{a};
  std::cout << std::is_constructible<C, int&>{} << '\n'; // 0
}

これは、上述の理由により UB を引き起こす。LWG 2452 には Library specification でその旨を明記するよう呼びかけられている。

stackoverflow.com C++17 で<new>ヘッダに追加されたstd::launderの目的とは何か。コンパイラC++ のライフタイム規則*3に基づく最適化を行えるが、定数メンバでオブジェクトを再初期化する(placement new)と、それらの規則と上手く両立できない。std::launderは、ライフタイムルールとは無関係に、同じアドレスに以前存在したオブジェクトではなくアドレスが新しいオブジェクトのみを参照することができるコンパイラへのヒントである。オブジェクトモデルの観点からは、あるアドレスのある潜在的に寿命の長いオブジェクトへのポインタから、そのアドレスの現在有効なオブジェクトへのポインタへのポインタをマッピングする。実装の観点から見ると、コンパイラは、返されたポインタのバージョンが指すオブジェクトのアイデンティティについて何も知らないと仮定することを防ぐ事で最適化の障壁となる*4N4659 [ptr.launder] では*5、これを pointer optimazation barrier と称している。N4659 21.6.4 Pointer optimization barrier [ptr.launder] から引用。

template <class T> constexpr T* launder(T* p) noexcept;
Requires: p represents the address A of a byte in memory. An object X that is within its lifetime and whose type is similar to T is located at the address A. All bytes of storage that would be reachable through the result are reachable through p (see below).

Returns: A value of type T * that points to X.

Remarks: An invocation of this function may be used in a core constant expression whenever the value of its argument may be used in a core constant expression. A byte of storage is reachable through a pointer value that points to an object Y if it is within the storage occupied by Y, an object that is pointer-interconvertible with Y, or the immediately-enclosing array object if Y is an array element. The program is ill-formed if T is a function type or cv void.

[ Note: If a new object is created in storage occupied by an existing object of the same type, a pointer to the original object can be used to refer to the new object unless the type contains const or reference members; in the latter cases, this function can be used to obtain a usable pointer to the new object. See [basic.life]. — end note ]

[ Example:
struct X { const int n; };
X *p = new X{3};
const int a = p->n;
new (p) X{5};                       // p does not point to new object ([basic.life]) because X<200b>::<200b>n is const.
const int b = p->n;                 // undefined behavior
const int c = std::launder(p)->n;   // OK
— end example ]

尚引用にもある通り T が関数型または(及びcv修飾された)voidの場合、ill-formed である。引数の値が core constant expression で使用される場合、std::launderを core constant expression で使用することができる。また、constメンバーまたは参照メンバーを持たないオブジェクトの場合、lifetime ルールに基づきポインタと参照を再利用できるためstd::launderは必要ない。 続いて p0636r0 から Examples, notes を引用

A language support tool (an “optimisation barrier”) to allow libraries to reuse storage and access that storage through an old pointer, which was previously not allowed. (This is an expert tool for implementers and not expected to show up in “normal” code.)

ライブラリが以前許可していなかった古いポインタを使用してストレージを再利用し、そのストレージにアクセスできるようにする言語サポートツール(“最適化バリア”)。 これは実装者のための専門ツールであり、"通常の"コードでは見られないとある。続いて関連項目を引用。N4659 4.5 The C++ object model [intro.object] paragraph 1 から。

The constructs in a C++ program create, destroy, refer to, access, and manipulate objects. An object is created by a definition, by a new-expression, when implicitly changing the active member of a union, or when a temporary object is created ([conv.rval], [class.temporary]). An object occupies a region of storage in its period of construction ([class.cdtor]), throughout its lifetime, and in its period of destruction ([class.cdtor]). [ Note: A function is not an object, regardless of whether or not it occupies storage in the way that objects do. — end note ]

続いて N4659 [intro.object] paragraph 2

Objects can contain other objects, called subobjects. A subobject can be a member subobject ([class.mem]), a base class subobject ([class.derived]), or an array element. An object that is not a subobject of any other object is called a complete object. If an object is created in storage associated with a member subobject or array element e (which may or may not be within its lifetime), the created object is a subobject of e's containing object if

the lifetime of e's containing object has begun and not ended, and

the storage for the new object exactly overlays the storage location associated with e, and

the new object is of the same type as e (ignoring cv-qualification).

[ Note: If the subobject contains a reference member or a const subobject, the name of the original subobject cannot be used to access the new object ([basic.life]). — end note ] [ Example:
struct X { const int n; };
union U { X x; float f; };
void tong() {
  U u = {{ 1 }};
  u.f = 5.f;                          // OK, creates new subobject of u ([class.union])
  X *p = new (&u.x) X {2};            // OK, creates new subobject of u
  assert(p->n == 2);                  // OK
  assert(*std::launder(&u.x.n) == 2); // OK
  assert(u.x.n == 2);                 // undefined behavior, u.x does not name new subobject
}
— end example ]

以下は例。

#include <new>
 
struct X {
  const int n; // note: X has a const member
  int m;
};
int main()
{
  X *p = new X{3};
  const int a = p->n;
  new (p) X{5};       // p does not point to new object because X::n is const
  const int b = p->n; // undefined behavior
  const int x = p->m; // undefined behavior (even though m is non-const, p can't be used)
  const int c = std::launder(p)->n; // OK, std::launder(p) points to new object
}
#include <iostream>

int main() 
{
   alignas(int) char data[sizeof(int)];
   int *myInt = new (data) int;
   *myInt = 34;

   std::cout << *reinterpret_cast<int*>(data); // dereferencing type-punned pointer will break strict-aliasing rules 
   std::cout << *std::launder(reinterpret_cast<int*>(data)); // OK
}

std::launderにおける feature test macro は __cpp_lib_launder である。

*1:CWG 2008

*2:尚この問題は、is_constructible + default 関数/テンプレート引数の唯一の問題ではない。例えば、LWG2452を参照されたい。

*3:[basic.life]/paragraph 8

*4:https://groups.google.com/a/isocpp.org/forum/#!topic/std-discussion/ko5ceM4szIE

*5:http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4430.htmlによる追加

C++ Standard Library Active Issues List Issue Status 和訳

C++ Standard Library Active Issues List の Issue Status の和訳。和訳されているのを見たことがなかったので、まとめておく。

様々なステータスを通じてLWG移行に報告された問題で、解決への進捗状況を示す。通常、ほとんどの問題は次の段階を流れる

  • New - この問題は、まだLWGによってレビューされていません。いかなる提案された決議も、問題提出者からの示唆であり、LWGの見解と解釈すべきではありません。
  • Open - LWGは問題について話し合ったが、問題を先に進める準備はできていない。公開ステータスにはいくつかの理由が考えられる。
    • この問題に対処する方法についてまだ合意に達していない可能性がある。
    • 非公式な合意に達したかもしれないが、LWGはレビューのために正確な提案された分限を待つ。
    • LWGは、先に進む前に追加の技術専門家に相談したい。
    • この問題には、さらなる研究が必要な場合がある。 未解決の問題に対する提案された解決策は、依然としてLWGの見解として解釈されるものではない。議論の現状に関するコメントは、公開されている問題の終わりにイタリック体で記載されることが多い。そのようなコメントは情報提供のみを目的としており、過度の重要性を与えるべきではない。
  • Review - LWGが以前に非公式な合意に達した問題について、提案された決議の正確な文言を検討することができるようになった。
  • Ready - LWGは、問題が標準の欠陥であり、提案された決議が正しいと合意に達し、問題が欠陥報告書(DR)としてのさらなる行動のために全委員会に転送する用意がある。 通常、問題はLWGレビュー中に変更されない文言が現在公開されている Issues List に提案された解決策を持っていなければならず、Ready状態に移行する必要がある。
  • Voting - このステータスは、公開されている Issues List には表示されないが、会議前のメールで問題が発生したことを示すためのマーカーで、提案された解決策は正しい。問題はワーキンググループに提供されます。現在の作業用紙(WP)に適用するか、または他の適切な方法でクローズされる。これにより、ミーティング自体の間に Ready 状態に移行する物と、それを次のミーティングまで転送してはならない物との区別が容易になる。問題に対する進捗がない場合は、次のリストが公開される前に、Open 状態に戻る。
  • Immediate - このステータスは、発行済みの Issues List には表示されない。会議前のメールで問題の準備が完了していなかったことを示すために会議中に使用するためのマーカーであるが、提案された解決策は正しい。また現在の作業用紙(WP)に適用するか、またはその他の適切な方法でクローズするために、現在の会議の終わりにワーキンググループに提出される。このステータスは、ごくまれにしか使用されない。通常、小規模で明白な fix であり、リリース予定の会議で使用される。問題に対する進捗がない場合は、次のリストが公開される前に、 Open 状態に戻る。
  • Deferred - LWGは問題を議論したが、まだ問題を進める準備はできていないか、標準や Technical Report の発行を遅らせるほど重要であるとは考えていない。一般的には、文面は技術的には正しいかもしれないが、ミスリーディングできてしまう言葉遣いを明確にすることに費やされる。 延期された問題の解決案は、依然としてLWGの見解として解釈されるべきではない。議論の現状に関するコメントは、公開されている問題の終わりにイタリック体で記載されることが多い。そのようなコメントは情報提供のみを目的としており、過度の重要性を与えるべきではない。
  • Core - LWGはこの問題について話し合い、問題解決の重要な部分は、標準のコア部分での言語のクリーンアップによってうまく処理されると感じている。この問題は、コアワーキンググループに渡され、理想的には、ライブラリの問題からリンクできる問題を Open しなければならない。このような問題は、コアが変更を行った後(または変更を拒否した後)に再確認される。
  • EWG - LWGはこの問題について話し合い、問題解決の重要な部分は、言語の拡張(上手くいけば小さな)によって処理されることがある。この問題は、Evolutionワーキンググループに渡される。このワーキンググループは、理想的には、ライブラリの問題からリンクできる問題を Open しなければならない。このような問題は、Evoltion が何らかの勧告を行った(または却下した)後に再確認される。
  • LEWG - LWGはこの問題について議論し、その問題が拡張されているとはいえないと考えているか、または fundamental でライブラリデザインを変更しているため、初期の作業を Library Evolution ワーキンググループに委任した。
  • DR - (Defect Report) - WG21 / PL22.16委員会は、潜在的な欠陥報告として処理するために問題をプロジェクトエディタに転送するよう投票した。プロジェクトエディタは問題をレビューし、それを WG21 Convenorに転送し、WG21 Convenor はそれを最終的な処分のために全委員会に返す。この Issues List は、プロセスのどこに関係なく、DRのステータスをこれらのすべての欠陥レポートに一致させる。
  • WP - (Working Paper) - 提案された決議は Technical Corrigendum として受け入れられていなかったが、WG21 / PL22.16委員会は、不具合報告書の提案された決議をワーキングペーパーに適用するよう投票した。
  • C++17 - (C++ Standard, as revised for 2017) - WG21 / PL22.16委員会は、C++標準、ISO / IEC IS 14882:2017(E) への 2017 改訂版に不具合報告書の提案された決議案を受け入れることに賛成した。
  • C++14 - (C++ Standard, as revised for 2014) - WG21 / PL22.16委員会は、C++標準、ISO / IEC IS 14882:2014(E) への 2014 改訂版に不具合報告書の提案された決議案を受け入れることに賛成した。
  • C++11 - (C++ Standard, as revised for 2011) - WG21 / PL22.16委員会は、C++標準、ISO / IEC 14882:2011(E) への 2011 改訂版に不具合報告書の提案された決議案を受け入れることに賛成した。
  • CD1 - (Committee Draft 2008) - WG21 / PL22.16委員会は、2008年秋の委員会草案に不具合報告書に提案された決議を受け入れることを表明した。
  • TC1 - (Technical Corrigenda 1) - WG21 / PL22.16委員会は、不具合報告書の提案された決議を Technical Corrigenda として受け入れることに賛成した。この問題に対するこれ以上のアクションは、ISOルールに基づき不可能である。
  • TRDec - (Decimal TR defect) - LWGは、不具合報告書の提案された決議を Decimal TR に受け入れることに賛成した。この問題に対する行動はこのように完全であり、それ以上の行動は期待されない。
  • TS - (TS - various) - WG21 / PL22.16委員会は、不具合報告書の提案された決議を公表された Technical Corrigenda に受け入れることに賛成した。
  • Resolved - LWGは、この問題が標準の欠陥であるという合意に達したが、問題を解決するために採択された決議は、リストのこの問題以外のメカニズムを介して行われた。
  • Dup - LWGは、この問題が別の問題と重複しているとの合意に達したため、今後は対処しない。
  • NAD - LWGは、この問題が標準の欠陥ではないという合意に達している。
  • NAD Editorial - LWGは、問題が編集上の扱いを受けることができるか、論文によって取り扱われるという合意に達している。
  • Tentatively - これはステータスへの修飾子である。この問題は、オンラインで、または非公式の会議でレビューされているが、公式の会議ではレビューされておらず、資格を取得するためのサポートがいくつか作成されている。暫定資格の問題は、同じ会議内の完全な委員会(準備ができている場合)に転送される可能性がある。Ready の問題とは異なり、小さな委員会で審議されてから完全な委員会に転送されます。一時的にステータスが認定されている場合でも、問題は引き続きアクティブと見なされる。
  • Pending - これはステータスへの修飾子である。これはステータスが前に付いたときに、問題が委員会によって処理されたことを示し、関連する不適合なステータスに問題を移行することが決定される。しかし、 logistical な理由から、問題の示された結果は、最新の作業記録にまだ現れていない。
  • NAD Future - LWGは、この問題が次回の改訂時に再検討されるべきだと考えている。これは現在、Library Evolutional ワーキンググループによって管理されている進行中の課題であり、このステータスのほとんどの問題はLEWGのステータスで再開された。
  • NAD Concepts - このステータスは、C++11の開発中の言語の進化を反映している。コンセプトと呼ばれる新しい機能に言語が移行し、テンプレートの指定と書き方が根本的に変わった。この言語機能はC++11プロジェクトの終わりに近づくにつれて削除されたが、この部分の言語設計を再検討する意思が明確に示されている。その開発中に、その機能の使用に関連する更新されたライブラリに対して、またはコンセプト機能の明示的な使用を必要とする修正を要求するいくつかの問題が開かれた。このような問題はすべてこのステータスで解消されており、この機能または類似の言語機能が将来の標準に戻った場合に再確認される可能性がある。
  • NAD Arrays - このステータスは、C++14/17の開発中の言語の進化を反映していた Arrays TS と呼ばれる技術仕様に関する作業が始まったが 2016年の初めにこの作業は放棄され、作業項目は正式に取り下げられた。 TSの開発中に、TSの機能がいくつか公開された。このような問題はすべてこのステータスで解消されており、この機能または類似の言語機能が将来の標準に戻った場合に再確認される可能性がある。

Issues List に最初に表示されるときに、問題のステータスは常にNewになる。 LWGが積極的に取り組んでいる間、それらは Open または Review に進むかもしれない。 LWGが問題の処理に関して合意に達すると、状態はDupNAD、または Ready に変更される。 PL22.16委員会が Ready の問題をプロジェクトエディタに転送すると投票すると、不具合報告書(DR)のステータスが与えられる。これらは、更新された標準(C++11、C++14)であるテクニカルコリレンダ(TC1)の基礎となる可能性がある。この LWG によるプロセスの目的は、スタンダードの真の欠陥である問題のみが正式なISO DRステータスに移行するためである。

non-type template parameter のシーケンス生成におけるプレースホルダなど

執筆時現在、C++1z(17)から追加される、non-type template parameter でのautoを使ってゴリゴリとコンパイルを行うと、コンパイル時間が型を指定している場合と比較して圧倒的に伸びる事があるので*1、この機能を使わずに C++14 までの機能だけで任意の型のシーケンス*2を生成できるように、以下のようなものを書いた記録。

github.com

これは、機能的にはstd::make_index_sequenceの上位互換であると言える。std::make_index_sequenceは、std::index_sequenceにシーケンスを溜め込む。つまりstd::size_tの値を持つシーケンスしか生成できない*3。これに対して、non-type template parameter が許容する任意の型を指定する事ができたり、値の適用時にプレースホルダのようなものが使えたりするようにした。

#include<srook/mpl/constant_sequence/algorithm/make_sequence.hpp>

まず、普通のシーケンス生成は以下のようにできる。これは、std::make_index_sequenceと変わらない。

 using type = srook::constant_sequence::make_sequence<10>;

生成される型は以下となる。

std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul, 6ul, 7ul, 8ul, 9ul>

これを例えばint型のシーケンスにしたければ、以下のようにする。

using type = srook::constant_sequence::make_sequence<10,srook::constant_sequence::make_sequence_utility::cast<int>>;

この時生成される型は以下となる。

std::integer_sequence<int, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9>

また、同じ値で埋めたくなる事もあるだろう。以下のようにする。

using type = srook::constant_sequence::make_sequence<10,srook::constant_sequence::make_sequence_utility::initialize<int,42>>;

生成される型は以下となる。

std::integer_sequence<int, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42>

任意の操作をしたい事もあるだろう。その場合は、コンパイル時にデフォルトコンストラクトが可能でありかつコンパイル時に呼び出しが可能である operator() を持つクラスを渡す事で適用される*4

struct Plus2char{
        explicit constexpr Plus2char() = default;
        constexpr char operator()(std::size_t x) const noexcept
        {
                return char(x * 2);
        }
};

using type = srook::constant_sequence::make_sequence<10,Plus2char>;

生成される型は以下となる。

std::integer_sequence<char, (char)0, (char)2, (char)4, (char)6, (char)8, (char)10, (char)12, (char)14, (char)16, (char)18>

引数にシーケンスの値が渡ってくる。また、戻り型を変えれば、その値でシーケンスに溜め込むようにしてある。ここまではまぁ普通だと思うのだが、少し実験的な部分が以下の機能。

using namespace srook::constant_sequence::make_sequence_utility;

using type = srook::constant_sequence::make_sequence<10,decltype(std::integral_constant<int,2>() * placeholders::_val)>;

生成される型は以下となる。

std::integer_sequence<int, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18>

+-*/ をそれぞれこの機能向けに定義していて、呼び出されるとその演算処理の内容が埋め込まれた型を生成するだけなのだが、少し表現力豊かになったりする。
最後に、シーケンスのリバース機能。

using namespace srook::constant_sequence::make_sequence_utility;

using type = srook::constant_sequence::make_sequence<10,decltype(std::integral_constant<int,2>() * placeholders::_val),Reverse>;

以下のように生成される。

std::integer_sequence<int, 18, 16, 14, 12, 10, 8, 6, 4, 2, 0>

*1:原因究明中

*2:勿論浮動小数点数型などは non-type template parameter に渡せないので不可能

*3:std::make_index_sequence はそもそも”インデックス”のシーケンス生成を目的としているので、その用途としては十分に満たしている。

*4:以前大体同じような事をしているが、今回は auto を使っていない点で若干異なる

brainf**k LLVM IR トランスパイラ(コンパイラ)ジェネレータ

以前 brainf**k インタプリタジェネレータのようなものを書いたが、LLVM IR を使ってオブジェクトファイル吐けたら良いかなと思ったので、取り敢えず作った。レキシカルアナライザ*1は、インタプリタで書いたものを呼び出して再利用している。

github.com

こんな感じに使う。

以下のようにビルドする(Makefile が雑なのは悪しからず)。

実行すると、IR コードがダンプされると同時にオブジェクトファイルが生成される。 尚、キーワードはbrainf**k インタプリタジェネレータと同じく好き勝手に設定できるので、brainf**k の亜種であるインタプリタ/コンパイラは、これらを用いてキーワードをただ単に変えるだけで完結する*2

#include <srook/brainfk/llvm/brainfk_compiler.hpp>

int main()
{
    using namespace std::string_literals;
    namespace br_keywords = srook::brainfk::label;

    const auto ponkotsu_keywords = srook::brainfk::make_keywords((
        br_keywords::_INCREMENT_THE_POINTER = L"ブラック企業かよ"s,
        br_keywords::_DECREMENT_THE_POINTER = L"アイスうめー"s,
        br_keywords::_INCREMENT_THE_BYTE_AT_THE_POINTER = L"ヒョウド! "s,
        br_keywords::_DECREMENT_THE_BYTE_AT_THE_POINTER = L"ドルファヘキセンダー  "s,
        br_keywords::_OUTPUT = L"おもらひ"s,
        br_keywords::_INPUT = L"おねひ"s,
        br_keywords::_JUMP_FORWARD = L"労災はおりない"s,
        br_keywords::_JUMP_BACKWARD = L"ハンマー"s));

    srook::brainfk::brainfk_syntax_llvm_compiler<std::wstring> bk_syn(ponkotsu_keywords);
    if(!bk_syn.file_open("../sample_bf/fizzbuzz.ponque")){
        return EXIT_FAILURE;
    }
    if(!bk_syn.analyze()){
        return EXIT_FAILURE;
    }
    bk_syn.exec();
    bk_syn.output_object("output.o");
}

上記のように設定した fizzbuzz のコードは以下のようになる。

*1:ご存知の通り brainf**k はそれほど大それた構文ではないので通常1バイトずつ進んで行けば勝手にトークンに分割されるが、今回はキーワードを任意に変更できるようにしてある分、ほんの少し面倒ではある。

*2:キーワードを変えただけで新しい言語であるとは到底思えない。

量子力学と量子コンピューターについての学習メモ #4

シリーズとしては少し間が空いてしまったが前回の続き

ショアのアルゴリズム

ショアのアルゴリズムは、有名な因数分解の量子計算アルゴリズムである。因数分解したい数を  N \in \mathbb{N} とする。

  1. まず N に対して、お互いに約数を持たないような  N より小さい数 x を決める。 xN が互いに約数を持つかはユークリットの互除法で判定する。

  2.  N x を用いて、 \frac{x^{r}}{n} のあまりが 1 を満たす自然数 r を探す。

    • x^{r} \in \mathbb{N} で、 たまたま  x^{r}  \bmod N= 1 だったとした時、  x^{r+m} \pmod N = x \bmod N ( m \in \mathbb{N}を満たす)であり、横軸にxの累乗の指数( yとする)、縦軸に x^{y} \bmod N を表すと、 y が 1 から始まり r に至るまで、 x^{y} \bmod Ny に応じて様々な値となるが、  y = r となる部分であまりが 1 となり、グラフは周期的にそのパターンを繰り返す。この周期がわかれば r が求められるため、量子フーリエ変換量子ビットの確率振幅に行う。
  3. この時に求まった r が奇数だった場合、手順 1. に戻り x を選び直してやり直す。この場合、r は偶数なので、次の手順に進む。

  4. この段階で \frac{x^{r}}{N} のあまりは 1 となっているはずである。つまり、 (x^{r}-1)N の整数倍となっているはずだ。一方で  (x^{r}-1) は、(x^{\frac{r}{2}} + 1)(x^{\frac{r}{2}} - 1) を掛け合わせたものであり、その二つのどちらかと  N は公約数を持っているはずである。今 (x^{\frac{r}{2}} +1) N の最大公約数を  z とすると、 z はすなわち N の因数なので、これで N因数分解ができたことになる。

C++ メタクラス提案の要約

元記事:http://www.fluentcpp.com/2017/08/04/metaclasses-cpp-summary/, Jonathan Boccara氏

[訳注 + メモ:

  • Herb Sutter 氏による P0707R0 Metaclasses の提案文書の要約がまとまった記事。分かりやすく要約されていたため個人的理解のため翻訳 + メモ。
  • メタクラスのプロトタイプは執筆時現在、github.com/asutton/clang(source)とcppx.godbolt.org(ライブコンパイラ) にて利用する事ができる。この辺りの諸々の更新情報は、Herb 氏によるドキュメントによって案内されるはず。
  • 尚、執筆時現在メタクラスの提案書における最新のリビジョンは P0707R1 である。 このリビジョン間での差分*1で特に大きいものは、P0707R1で述べられている以下の一文の通り、
The current prototype implementation will change “for...” to “for” per EWG direction in Kona, but in the meantime this paper still uses “for...” to stay in closer sync with the compiler. The current prototype implementation does not yet allow a source_location, so that has been temporarily removed from this paper’s examples to make it easier to cut-and-paste examples from here into the prototype compiler. The source_location will be added so that diagnostics can have precise source line and column information.

現在のプロトタイプの実装では、KonaのEWG方針に応じてfor...forに変更されるが、その間、この文書ではfor ...を使用してコンパイラとの緊密な同期を維持している(コピペでのテストを容易にするため)事と、source_locationに関する諸々が述べられている。
訳注 + メモここまで]

数週間前、Herb Sutter氏はメタクラスに関する提案を発表し、正当な理由でC++コミュニティの熱意を引き出した。彼の提案は、メタクラス潜在的な可能性と、特に現在のC++のイディオムの表現力を向上させるための方法を読者に紹介している。私は誰もがこの提案の内容を知っているべきであると思う。何故、特別これを知っているべきなのかとあなたは思うかもしれない。その理由は、これを読むことで、言語がどこに向かうのか、そして今日利用可能な機能がどのようにその絵*2に収まるのかが示されるからである。それは今日C++がもたらす力の上に、さらなる言語に関する多くの視点を与える。

1つの詳細:その提案は37ページの長さであり、それぞれの内容が濃密である。

あなたがその種の文書を読む時間があれば、それをするべきだ。それ以外の場合は、私があなたのために読んで作成したこの概要を読む事で、どのようなメタクラスが何であるかを理解できる。また、私はあなたがメタクラスの感覚を体験できるように、私が発見した最も驚いたコンポーネントをいくつか追加した。

この記事をレビューしてくれた Herb Sutter 氏に感謝します。

構造体やクラスは不十分

今日のC++において構造体とクラスは、型を定義する2つの主要な方法である。技術的な観点からは、時差しには同じように動作するが、コード内で異なる意味を表現するために、使用するものを選択するための規則がある
しかし、それは単なるしきたりである。言語は、与えられた文脈で正しいものを選択するように強制するものではない。しきたりを尊重しないのは、コードの読者を間違った方向へ送り出すので、しきたりを全く持たないよりもさらに悪い事である。また、構造体やクラスのために、言語は、特定の条件下でコピーコンストラクタやその他のメソッドを生成するなど、すべての型のいくつかの規則を固定する。しかし、これらの規則はすべてが一応のものであり、特定の種類に適合しない場合もある。これは、= delete= defaultを使用してルールの効果を修正する必要がある。また、標準委員会の決定を難しくする(すべての型の既定の比較演算子を組み込む必要があるか?)。

さらに、構造体、クラスのどちらも良い選択ではない型もある。純粋な仮想関数のみを含み、派生することを意図したインタフェースの例を考える。それは構造体か、それともクラスか?いずれも適合しないので、誰もが時には不合理な推論を持って1つを選ぶ必要がある。

最後に、C++イディオムの中には重複したコードがある。インタフェースの例をもう一度考えると、インタフェースには常に純粋な仮想パブリックメソッドと仮想デストラクタがあるが、毎回これらがあることを確認する必要がある。今日、そのような共通の機能を除外する方法はない。

メタクラス

メタクラスは、上記の各問題を構造体とクラスで修正することを目的としている。これらの二つの型を自身の型の型(つまり、メタクラス)で補う事ができる。つまり、クラスのようなものは、実行時にオブジェクトをインスタンス化できるモデルであり、メタクラス( Herb 氏の提案でキーワード $class で定義されている)は、コンパイル時にクラスを生成できるモデルである。これらのクラスは、言語のほかのすべての通常のクラスと似ている。つまり、実行時にオブジェクトをインスタンス化する事ができる。例として、クラスとオブジェクトの関係は常にこのようになっている。:

(図略)

これに対してメタクラスはどのように見えるべきか:

(図略)

ここで提案されたメタクラスの構文を示す。Herb Sutter 氏がメタクラスを説明するために使用するインタフェースの例を示す。メタクラスを定義する方法は次の通りである。
$class interface
{
    // インタフェースが何であるかを記述するコード
    // 仮想デストラクタを持つ、コピーコンストラクタを持たない
    // すべての public と pure virtual など
    
    // 実装のための次のセクションを参照
}
インスタンス化する方法は次の通りである。構造体またはクラスの代わりにメタクラスの名前を使用するだけだ。
interface Drivable
{
    void speedUp(int acceleration);
    void brake();
    void turn(int angle);
};
これを解析するとき、コンパイラはこれら全てのメソッドを純粋仮想にし、仮想デストラクタを追加することによって Drivable クラスを生成する。これは、インタフェースを記述するための前例のない表現力を持つ(この例では、主題とは異なる強い型付けを無視している)。 メタクラスはテンプレートの引数としても使われ、コンセプトのために提案された構文と同じ構文で使われることに留意されたい。
template<interface I>
...

リフレクションとコンパイル時プログラミング

インタフェースのメタクラスを実装する方法とはどのようなものか。メタクラスの実装は、リフレクションとコンパイル時のプログラミングという2つのC ++の提案に基づいている。リフレクションは、メタクラスがクラス自体の機能を操作することを可能にする(クラスのように、オブジェクトの機能を操作する)。例えば、リフレクションでは、クラスのメソッドの機能を検査できる($を使用して現在の提案でリフレクションを認識できる):
for (auto f : $interface.functions())
{
    if (!f.has_access())
    {
        f.make_public();
    }
}
これを次のように読む:クラスの各関数(メソッド)がインタフェースメタクラスからインスタンス化されている場合、このメソッド(public、protected、private)のスコープがコードで明示的に指定されていない場合は、リフレクションでは、メタクラスは、インタフェースメタクラス用の純粋な仮想デストラクタである。

リフレクションを使うと、メタクラスは、インタフェースメタクラスの純粋仮想デストラクタなどの関数を定義することもできる。
~interface() noexcept = 0;
または
~interface() noexcept { }
for (auto f : $interface.functions())
{
    f.make_pure_virtual();
}
コンパイル時プログラミングは、コンパイル時にコードが実行される行の領域を定義することにあり、結果としてコンパイル時のデータが評価される。領域はconstexprブロックで区切られ、条件と結果はコンパイル時の評価 -> {結果}という構文で表される。次の例は、比較演算子についての別のメタクラスの例である。デフォルトの比較演算子がクラスによってまだ定義されていない場合、デフォルトの比較演算子を定義する:
constexpr
{
    if (! requires(ordered a) { a == a; }) ->
    {
        friend bool operator==(ordered const& a, ordered const& b)
        {
            constexpr
            {
                for (auto variable : ordered.variables())
                    -> { if (!(a.variable.name$ == b.(variable.name)$)) return false; }
            }
            return true;
        }
    }
}
上記の2つのconstexprブロックに着目する。requireは、「operator==がクラスにまだ実装されていない場合」を意味する。この文脈はちょっと変わっているが、それはコンセプトから成る自然な構文である。

最後に、メタクラスコンパイル時のチェックに依存して制約を適用し、制約が守られていない場合コンパイルエラーで適切なメッセージが表示される。例えば、インタフェースのすべてのメソッドがpublicになっていることを確認する方法は次の通りである。
for (auto f : $interface.functions())
{
    compiler.require(f.is_public(), "interface functions must be public");
}
インタフェースメタクラスの提案されている完全な実装は以下の通りである。
$class interface
    {
    ~interface() noexcept { }
    constexpr
    {
        compiler.require($interface.variables().empty(), "interfaces may not contain data");
        for (auto f : $interface.functions())
        {
            compiler.require(!f.is_copy() && !f.is_move(), "interfaces may not copy or move; consider a" " virtual clone() instead");
            if (!f.has_access()) f.make_public();
            compiler.require(f.is_public(), "interface functions must be public");
            f.make_pure_virtual();
        }
    }
};

メタクラスができる事

私は、上記のようにインタフェースと順序付けされたクラスを定義できる事の他にメタクラスができる3つのことを抽出した。それらは私を本当に驚かせた。

メタクラス

レギュラーな値*3型について聞いたことがあるだろうか。基本的にそれらはあなたが期待するように動作する。それらは、Alex Stepanov 氏による非常に人気のある Elements of Programming という書籍内で素晴らしい内容で開発されている。レギュラーな値型はメタクラスの値で表現でき、その定義は2つの部分に分割される:
  • すべてのデフォルトのコンストラクタ、デストラクタ、その他の代入演算子と移動演算子を定義するbasic_value
  • すべての比較演算子を定義するordered
これらのメソッドはすべて互いに一致するように実装される(コピーの後、operator==trueを返す)。そして、これは全て値メタクラスを使うことで簡単に表現できる。
value PersonName
{
    std::string firstName;
    std::string lastName;
};

namespace_class メタクラス

ライブラリの実装の詳細に属するテンプレートタイプまたは関数を定義するための現在の規約は、それらをdetailと呼ばれるサブネームスペースに配置することである。実際、テンプレートとしてライブラリのクライアントに含まれるヘッダーに置く必要があるため、.cppファイルでこれらを隠すことはできない。 Boostはこの規約を広く使用している。この規約は、機能はしているが、
  1. ライブラリユーザがdetail名前空間で何かを使用することを妨げるものは何もなく、ライブラリの下位互換性を危険にさらす。
  2. ライブラリのコード内でこの名前空間に出入りするのは面倒である。
これら2つの問題の解決策の1つは、名前空間の代わりにクラスを使用し、実装の詳細にプライベートメソッドを使用することであるが、これにより3つの新しい問題が生み出される。
  1. クラスはそれが私たちが本当に意味する名前空間であることを表現していない
  2. クラスは、メンバ変数のような名前空間には意味を持たない多数の機能を提供している
  3. 名前空間とは異なり、コード全体のいくつかの場所でクラスを再度定義することはできない
提案されたnamespace_classは、両方の世界のベストを保つことを可能にする。実装は次の通りである。
$class namespace_class : reopenable // see below for reopenable
{
    constexpr
    {
        for (auto m : $reopenable.members())
        {
            if (!m.has_access ()) m.make_public();
            if (!m.has_storage()) m.make_static();
            compiler.require(m.is_static(), "namespace_class members must be static");
        }
}
};
コード内の異なる場所で複数の部分を定義できるようにする:
$class reopenable
{
    constexpr
    {
        compiler.require($reopenable.member_variables().empty(), "a reopenable type cannot have member variables");
        $reopenable.make_reopenable();
    }
};
これは、detail名前空間を置き換えるために使用される。
namespace_class my_libary
{
public:
    // public interface of the library
 
private:
    // implementation functions and types
};

plain_struct メタクラス

最後に、plain_structは構造体を表現することを目的としているが、コンパイラが規約を尊重しているかどうかを確認する。より正確には、public関数とpublicネストされた型で不変なものがなく(ユーザー定義のデフォルトのコンストラクタ、コピー、代入またはデストラクタを意味しない)、メンバーを書くことができる最も強力な比較演算子のみを持つbasic_valueである。

更に知りたければ

メタクラスがどのようなものかをより明確にしたので、このトピックをさらに深く掘り下げたい場合は、Herb Sutter 氏の提案を参照されたし。それはよく書かれており、多くの例が示されている。私がここに示したものの他に、表現力が向上したという点で最も印象的な部分は、
  • the .as operator (section 2.6.2 and 2.6.3)
  • safe_union (section 3.10)
  • flag_enum (section 3.8)
  • とにかくそれはすべて素晴らしいものである。 また、ACCU会議や提案を発表したブログ記事で、メタクラスに関するHerb 氏のトークを見ることもできる。メタクラスは私のC++の構造的変化のように思える。私たちのインタフェースにはこれまでにない表現力とコードへの堅牢性がもたらされる。それらのために、準備をしよう。

以降の内容は、翻訳元とは関係なく、私が記述したものである。
p0707r1 準拠のインタフェースメタクラスの実装は、以下の通り。

$class interface {
    constexpr {
        compiler.require($interface.variables().empty(),
                         "interfaces may not contain data");
        for... (auto f : $interface.functions()) {
            compiler.require(!f.is_copy() && !f.is_move(),
                "interfaces may not copy or move; consider a"
                " virtual clone() instead");
            if (!f.has_access()) f.make_public();
            compiler.require(f.is_public(),
                "interface functions must be public");
            f.make_pure_virtual();
        }
    }
    virtual ~interface() noexcept { }
};

これをShapeというクラスで派生する。

interface Shape{
    int area() const;
    void scale_by(double);
};

constexpr{
    compiler.debug($Shape);
}

現在のプロトタイプ実装では、debugメタクラスから成るクラスを指定して呼び出す事でその内容を出力する事ができるようになっている。例えば、Shapeに変数を持たせてみる。

interface Shape{
    int area() const;
    void scale_by(double);
    int i;
};

すると、コンパイルエラーとなり、エラー文はメタクラスで設定した文字列で構成される。

6 : <source>:6:5: error: interfaces may not contain data
    constexpr {
    ^

更にインタフェースメタクラスでインタフェースの要件としている条件に反して宣言すれば、

interface Shape {
    int area() const;
    void scale_by(double factor);
private:
    void g(); // インタフェースの関数をプライベートに設定する
};
interface Shape {
    int area() const;
    void scale_by(double factor);
    Shape(const Shape&); // インタフェースクラスにコピー、またはムーブを宣言する。
};

それぞれ同じようにメタクラスで設定されたエラー文が出力される。

6 : <source>:6:5: error: interface functions must be public
    constexpr {
    ^
6 : <source>:6:5: error: interfaces may not copy or move; consider a virtual clone() instead
    constexpr {
    ^

尚、執筆時現在のプロトタイプ実装では、メタクラス側で設定した複数の require に反した宣言をインタフェースクラス側で行った場合、一番先頭に当る違反箇所のエラーメッセージのみ出力されるようだ。
次に、basic_value メタクラスの実装。*4

$class basic_value {
    basic_value() = default;
    basic_value(const basic_value& that) = default;
    basic_value(basic_value&& that) = default;
    basic_value& operator=(const basic_value& that) = default;
    basic_value& operator=(basic_value&& that) = default;

    constexpr {
        for... (auto f : $basic_value.variables())
            if (!f.has_access()) f.make_private();
        for... (auto f : $basic_value.functions()) {
            if (!f.has_access()) f.make_public();
            compiler.require(!f.is_protected(), "a value type may not have a protected function");
            compiler.require(!f.is_virtual(),   "a value type may not have a virtual function");
            compiler.require(!f.is_destructor() || f.is_public(), "a value destructor must be public");
        }
    }
};

$class value : basic_value{};

これを使って二点の座標を意味する Point クラスが作れる。

value Point{
    int x = 0,y = 0;
    Point(int xx,int yy):x{xx},y{yy}{}
};

次に plain_struct の実装について。plain_struct は、構造体を表現する。パブリックオブジェクトと関数のみ、仮想関数なし、ユーザー定義コンストラクタ(つまり no invariants)、代入、デストラクタ、およびすべてのメンバでサポートされている最も強力な比較を持つbasic_valueである。

$class plain_struct : basic_value {
    constexpr {
        for... (auto f : $plain_struct.functions()) {
            compiler.require(f.is_public() || !f.is_virtual(),
                             "a plain_struct function must be public and nonvirtual");
            compiler.require(!(f.is_constructor() || f.is_destructor()
                                   || f.is_copy() || f.is_move())
                               || !f.is_defaulted() || !f.is_deleted(),
                             "a plain_struct can't have a user-defined "
                             "constructor, destructor, or copy/move");
        }
    }
};

これらの他に翻訳元でも取り扱われているものを含む base_class, final, orderd, copyable_pointer, namespace_class, enum_class, flag_enum, bitfield, safe_union メタクラスが提案されている。ただ、P0707R1 でも述べられている通りプロトタイプコンパイラに使っている clang がまだ concepts を持っていないため、order などのメタクラスを含む多くのサンプルは執筆時現在コンパイルできない。
しかし見てわかる通り、メタクラスは型に関するコードそのものがドキュメントやコーディング規約、しきたりの役割を果たす程の強力な表現力をもたらす事が言える。個人的には、この提案の動向に目が離せない。

*1:差分の確認には pdf-diffが役立った

*2:イメージだとか空想といったところだろうか...

*3:basic_value をこのように訳したが少し無理があるだろうか...

*4:翻訳文中ではレギュラーな値型と訳したが以下は basic_value という単語をそのまま使う。