brainf**k LLVM IR トランスパイラ(コンパイラ)ジェネレータ
以前 brainf**k インタプリタジェネレータのようなものを書いたが、LLVM IR を使ってオブジェクトファイル吐けたら良いかなと思ったので、取り敢えず作った。レキシカルアナライザ*1は、インタプリタで書いたものを呼び出して再利用している。
こんな感じに使う。
以下のようにビルドする(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"); }
量子力学と量子コンピューターについての学習メモ #4
シリーズとしては少し間が空いてしまったが前回の続き
ショアのアルゴリズム
ショアのアルゴリズムは、有名な因数分解の量子計算アルゴリズムである。因数分解したい数を とする。
まず
に対して、お互いに約数を持たないような
より小さい数
を決める。
を用いて、
のあまりが 1 を満たす自然数
を探す。
この時に求まった
- この段階で
のあまりは 1 となっているはずである。つまり、
は
と
を掛け合わせたものであり、その二つのどちらかと
と
とすると、
はすなわち
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つの部分に分割される： これらのメソッドはすべて互いに一致するように実装される（コピーの後、operator==はtrueを返す）。そして、これは全て値メタクラスを使うことで簡単に表現できる。value PersonName { std::string firstName; std::string lastName; };namespace_class メタクラス
ライブラリの実装の詳細に属するテンプレートタイプまたは関数を定義するための現在の規約は、それらをdetailと呼ばれるサブネームスペースに配置することである。実際、テンプレートとしてライブラリのクライアントに含まれるヘッダーに置く必要があるため、.cppファイルでこれらを隠すことはできない。 Boostはこの規約を広く使用している。この規約は、機能はしているが、 これら2つの問題の解決策の1つは、名前空間の代わりにクラスを使用し、実装の詳細にプライベートメソッドを使用することであるが、これにより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 などのメタクラスを含む多くのサンプルは執筆時現在コンパイルできない。
しかし見てわかる通り、メタクラスは型に関するコードそのものがドキュメントやコーディング規約、しきたりの役割を果たす程の強力な表現力をもたらす事が言える。個人的には、この提案の動向に目が離せない。
JPEG デコーダ書いた
以前 JPEG エンコーダをフルスクラッチで書いたが、今度は JPEG デコーダを書いて見た。該当するコミットはこちら。
プロジェクト全体はこちら。
量子化テーブルの要素数を間違えて指定していて、少しハマった瞬間もあったが今回は割とサクサクと一日ほどで作り終えた。次は画像処理としては、巷で流行っている HEIF 関係の処理系を書ければと思っている。
#追記・諸々のアップデート
元々は C++1z 標準の[[fallthrough]]attribute を使っていたがコンパイラの対応状況になるべく依存しないようその辺りを吸収してくれるライブラリを作ったのでそれを使うように変更。
github.com
エンコード、デコード処理で用いるコサインテーブルは、元々実行時に生成されていたが、コンパイル時にコサインテーブルを生成するライブラリを作ったので、それを使うように変更。 github.com
order of eval
Because my memory was a little vague, I learned about C++ order of eval again and wrote it in Japanese to my reference book.
The document of built version is here and for list of grounds and references of this document, consult this page. This beginning of thing is from these tweets so I am grateful for yohhoy’s polite response.
Why an access to a volatile glvalue is considered a side effect by [intro.execution] ?
side-effect についてドラフトで再確認していたところ、その定義として “Reading an object designated by a volatile glvalue” という文面があったのでタイトルの内容をメモ。執筆時現在、side-effect については [intro.execution]/14/sentence-1 にて以下のように述べられている。
Reading an object designated by a volatile glvalue, modifying an object, calling a library I/O function, or calling a function that does any of those operations are all side effects, which are changes in the state of the execution environment.
タイトルに答える内容は、同セクションの3つ目のセンテンスで述べられている。
When a call to a library I/O function returns or an access through a volatile glvalue is evaluated the side effect is considered complete, even though some external actions implied by the call (such as the I/O itself) or by the volatile access may not have completed yet.
ライブラリ I/O 関数への呼び出しが返されるか、volatile glvalue によるアクセスが評価されると、呼び出しによって暗黙の外部操作(I / O自体など)や volatile なアクセスをまだ完了していない可能性がある。
stackoverflow にも分かりやすい回答が載っていたので一部引用。
Hardware registers, which is the normal use-case for volatile (typically in conjunction with pointers, but doesn't have to be), the read of a register will potentially have actual side-effects on the hardware - for example reading a fifo-register on a serial port [or network card, hard disk, or whatever], will affect the state of the hardware, since the fifo has now "moved on" one step. Skipping over, duplicating, caching the result of, or some other such optimisation would definitely cause a piece of driver code and hardware to behave in a different way than the programmer wanted - which would be the case if volatile wasn't considered as having a side-effect.
普段使いのコンパイル環境の整備
私は普段ちょっとしたコードに対してコンパイルを行う時、GCC と Clang のどちらかを使う。使うたびにコンパイルオプションを付与するのは面倒なので、これまでは単にオプションを含めた文字列をそのまま .zshrc のエイリアスとして設定していたのだが、あんまり管理の仕方としてはよろしくないなと思ったので、make で管理したいと思った。しかし、毎度 Makefile を作業ディレクトリごとに移動させたりパスを通したり何なりするのは元も子もないので、それに加えて zsh を使ってちょっとした環境整備をした。
で、これを呼び出す zsh スクリプト。--versionと-Sは割と使うのでそれだけ用意した。
そして .zshrc には以下のように指定。これで、gcc, g++, clang, clang++ がこの Makefile の設定で実行される。
alias g++="$HOME/build_setting/make.zsh GXX" alias clang++="$HOME/build_setting/make.zsh CLANGXX" alias gcc="$HOME/build_setting/make.zsh GCC" alias clang="$HOME/build_setting/make.zsh CLANG"
もっと良い管理法などはあるだろうか。個人的にはこれで満足しているので特別問題はないのだが。
