Clever Geek Handbook

三目並べ：コンパイラと人間-極端なメタプログラミング

「-反乱の後、銀河連邦は高次のメタ機能に厳しい制限を課しました。そして、倫理的な理由だけでなく、当局は誇大妄想の出現を恐れています...」

（ Google検索結果から ）
tic-tac-toeをコンパイラでプレイすることをお勧めします。 ゲームにはc ++の知識は必要ありません。cmake、python、c ++コンパイラが適切であれば十分です（gcc-3.3のような古いものでもそれを引き出せます）。 Pythonは、ユーザーデータの入力、各移動後のコンパイラの起動、および結果を取得するためのコンパイル済みプログラムにのみ使用されます。 すべての計算（次の動き、勝者の決定、または抽選の開始）は、コンパイル段階で実行され、実行時には結果のみが出力されます。



それがどのように機能するかを理解したい人のために：すべてが正直で、トリッキーなトリック、ハッキング、およびスクリプトによるコード生成はありません（まあ、ほとんど）。 スクリプトの出力では、2つのファイルがあります。最初の位置は、e、x、e、o、e、e、e、e、xの形式の行です。ここで、eは空のフィールドで、2番目のファイルでは番号0、1または2です。難易度。 3つの難易度レベルがあり、コンパイラの動きはこのレベルに応じてランダムになります。 また、コンパイラーにさまざまな難易度で自分自身と遊ぶことを教えます。



コードはほとんどありません-faslibライブラリに既に実装されているものを使用します。 このライブラリは、タイプリストに基づくテンプレートを使用して、アスペクト指向の概念を実装するように設計されています。 AOPトピックについては、今回は触れませんが、タイプリストとメタアルゴリズムを扱うためにパッケージを使用します。



再生するために、githubからプロジェクトをロードします（faslibはサブモジュールとして接続されています）： 

git clone https://github.com/migashko/tictactoe.git cd tictactoe/ git submodule init git submodule update


cmakeとc ++が使用可能であることを確認し、ゲームを実行します。 

 ./tictactoe.py


最初の起動時に、スクリプトはビルドディレクトリ自体を作成し、cmakeを実行します。 何か問題が発生した場合は、手動で実行します 

 mkdir build cd ./build cmake .. make tictactoe


ゲームの1ラウンドの例 
 Level [0,1,2]: 2 Figure [X,x,1,O,o,0]: o compiling... - - - - X - - - - Move [0..8, a1..c3]: a2 compiling... - O - - X - X - - Move [0..8, a1..c3]: a3 compiling... XOO - X - X - - Move [0..8, a1..c3]: b2 BUSSY Move [0..8, a1..c3]: b1 compiling... XOO OX - X - X X winner (compiler)




ゲームの開始時のスクリプトは、難易度レベルを設定するユーザーが入力した数値をlevel.inlファイルに書き込み、board.inlファイルに移動するたびに、新しい配置（クロスまたはゼロ）をコンパイラが移動することを分析します。 これらのアクションは手動で実行でき、コンパイラを実行して結果を確認できます。 例として、level.inlに2番目の難易度を記述します。 

 echo 2 > level.inl


そしてboard.inlでテキストエディターを使用して開始位置を設定します（改行を挿入できます）。 

 e,e,e, x,o,e, e,e,e


または： 

 echo "e,e,e,x,o,e,e,e,e" > board.inl


makeをビルドして実行し、次に./tictactoeに移動します。

複数コンパイルの例 
 $> make $> ./tictactoe - - - XO - - - X $> make $> ./tictactoe - - X XO - - - - $> make $> ./tictactoe X - - XO - - - -




tictactoeに加えて、ゲームを最後まで（また、コンパイル段階で）実行するtictactoe_itsプログラムがあります。 Board.inlは、図の初期配置に使用されます。 最初からゲームをプレイする必要がある場合は、このファイルを削除してください。

2つの動きがある開始位置の例 
 $> ./tictactoe_its - - - XO - - - - X - - XO - - - - X - - XO - O - - X - X XO - O - - XOX XO - O - - XOX XO - OX - Draw




コンパイラが使用するアルゴリズムは完全ではないため、2番目のレベルの複雑さであっても、この場所で死が保証されることはありません。



Win-Winアルゴリズム：

  1. 私たちは勝利に導く立場に行く
  2. 敵の勝利を阻止する
  3. フォーク
  4. 中心へ
  5. 相手がコーナーに行った場合、反対側のコーナーに移動します
  6. 隅々まで
  7. 任意の自由な位置へ


現在の実装では、第2レベルの複雑さで、コンパイラはポイント3と5を無視します。ポイント3と5を考慮に入れてこのアルゴリズムに従う場合、コンパイラはゲームを引き分けに減らします。 最初のレベルでは、4番目のポイントは考慮されませんが、最も単純なゼロ、6番目は考慮されます。



2番目の難易度でコンパイラーに勝つチャンスを得るには、最初の移動を最も「間違った」位置（サイドセル）に行う必要があります。 コンパイラはつま先を中央に移動します。 次の動きは、最初の動きに対して、反対側の角の1つである必要があります。 アルゴリズムに従って、コンパイラーは自由なコーナーのいずれかに移動します。最初の移動の近くにない角度を選択した場合、プラグを差し込んで勝つことが保証されます。

難易度2のコンパイラフォーク 
 e> ./tictactoe.py Level [0,1,2]: 2 Figure [X,x,1,O,o,0]: x Move [0..8, a1..c3]: b1 compiling… - - - XO - - - - Move [0..8, a1..c3]: c3 compiling... - - O XO - - - X Move [0..8, a1..c3]: c1 compiling... - - O XO - XOX Move [0..8, a1..c3]: a1 compiling... X - O XO - XOX X winner (you)




このゲームで私たちは終了し、最も興味深いものに進みます。 次に、C ++、特にテンプレートに関連するすべての知識が必要です。 最初にfaslib（ゲームを実装するために必要なパッケージのみ）の簡単な概要を説明し、コンパイラーに1つの動き、勝者の特定、引き分けの決定を教えます。 そして最後に、ゲーム全体を自分でプレイするように彼に教えます。



Faslibの概要



ライブラリをナビゲートするのは簡単です-各デザイン（最も単純なものでも）を個別のファイルに。 ファイルのリストを見て、使用可能な機能を判別してください。 faslibはメタライブラリです。実際にはランタイムコードはありません。そのため、関数とアルゴリズムでは、メタ関数とメタアルゴリズムを意味します。



いくつかのライブラリがfaslibの設計に影響を与えました。 タイプのリスト（ fas / type_list ）、およびタイプに対するすべての種類の操作（ fas / typemanip ）は、もちろんLokiです。 typemanipの多くの構成体は、c ++ 11の<type_traits>の対応するものに置き換えることができます。 パッケージfas / mp （プレースホルダー式とラムダメタ関数）およびfas / Integral （整数型のラッパーとそれらの操作）のアイデアは、boost :: mplから取られています。 STLアルゴリズムに似たメタアルゴリズムのインターフェイスを作成しようとしました。



整数型から始めましょう。 テンプレートを使用する場合、数字を使用するのが常に便利であるとは限りません;これらの目的には、次のような特別なラッパーがより便利です。 

 typedef fas::int_<2> level;


このコンストラクトの定義と、fas / integralパッケージの他の整数型の定義。 そこで、追加などの基本的な操作を見つけることができます。 

 std::cout << fas::int_<1>::value << std::endl; // 1 std::cout << fas::plus< fas::int_<1>, fas::int_<2> >::value << std::endl; // 3


ここでは、コンパイル段階で最小公倍数を見つける方法の例を調べることができます 。



fas / typemanipパッケージには、さまざまなデータ型を操作するための一連の構成体が含まれています。 2つの型が同じかどうかを判断するには、same_typeが必要です。 

 std::cout << fas::same_type<int, long>::value; // 0 std::cout << fas::same_type<int, int>::value; // 1


特定の位置から型を取得するための型と関数のペアとタプル： 

 typedef fas::pair< fas::int_<1>, fas::int_<2> > pair; typedef fas::tuple< fas::int_<3>, fas::int_<4>, fas::int_<5> > tuple; std::cout << fas::first<pair>::type::value << std::endl; // 1 std::cout << fas::second<tuple>::type::value << std::endl; // 4 std::cout << fas::third<tuple>::type::value << std::endl; // 5


タプルは最大5つのタイプを取ることができます。 さらに必要な場合は、タイプリストを使用する方が便利です。 4番目と5番目のタイプを取得するための関数：4番目と5番目。



条件付き操作： 

 std::cout << fas::if_< fas::true_, fas::int_<42>, fas::int_<24> >::type::value << std::endl; // 42 std::cout << fas::switch_< fas::case_< fas::false_, fas::int_<24> >, fas::case_c< 1, fas::int_<42> >, fas::default_< fas::int_<44> > >::type::value << std::endl; // 42


タイプのリスト。 概念の詳細は説明せず、実装の機能のみを示します。 だから、基本的な構造： 

 struct empty_list { typedef metalist::empty_list metatype; }; template< typename L, typename R = empty_list > struct type_list { typedef metalist::type_list metatype; typedef L left_type; typedef R right_type; };


4つのタイプのリスト： 

 typedef fas::type_list<A, fas::type_list<B, fas::type_list<C, fas::type_list<D > > > > list_abcd; // [A,B,C,D,empty_list]


無効なリスト： 

 typedef fas::type_list<A, B > list2_ab_invalid;


faslibでは、Lokiとは異なり、型のリストは常に型fas :: empty_listで終わる必要があります。 この規則が順守されない場合、そのようなリストは未編成と呼ばれます。 fas ::組織機能は、たとえば次のような状況を修正するのに役立ちます。 

 typedef fas::type_list< A, B > list_ab_invalid; // [A,B] typedef fas::type_list< C, D > list_cd_invalid; // [C,D] typedef fas::type_list< list_ab_invalid, list_cd_invalid> list_abcd_invalid; // [[C,D],[C,D]] typedef fas::organize<list2_abcd_invalid>::type list_abcd; // [A,B,C,D,empty_list]


Alexandrescuと彼のフォロワーが#defineを使用して型のリストを作成する理由を私は心から理解していません。 

 typedef fas::type_list_n<A,B,C>::type list; // [A,B,C,empty_list]


C ++ 11より前は、type_list_nは最大26個のパラメーターを受け入れますが、その後は制限されません（さまざまなテンプレート）。

型リストの詳細
type_list_nは、タイプリストの作成に加えて、fas :: organizeを使用してそれらを整理できます。たとえば、次のようにパラメーターの数の制限を削除します。 

 typedef fas::type_list_n< fas::type_list_n<A,B>::type, // [A,B,empty_list] fas::type_list_n<C,D>::type // [C,D,empty_list] >::type list; // [A,B,C,D,empty_list]


faslibのタイプリストの次の優れた機能は、次のような構造体でリストをエスケープできることです。 

 struct list_bc: fas::type_list<B, fas::type_list<C> > {}; // [B,C,empty_list] struct list_abc: fas::type_list<B, list_bc > {}; // [A,list_bc]


タイプリストで動作するすべての操作とアルゴリズムは、シールドを検出し、可能であればそれらを再構築しないように設計されています。 リストを組み合わせて説明しましょう： 

 typedef fas::merge< list_bc, // [B,C,empty_list] list_abc // [A,list_bc] >::type list; // [B,C,A,list_bc]


この操作を簡単に実装すると、[B、C、A、B、C、empty_list]のリストが再構築されます。 faslibでの実装はそれほど複雑ではありませんが、コンパイル時間の最適化とリストの末尾をスクリーニングするときにエラーが発生した場合のログの実際的な削減という点で実質的な利益はありません。 ただし、次のように、エスケープする機能はリストの作成に役立ちます。 

 template<int A, int B, int C> struct list123: fas::type_list_n< fas::int_<A>, fas::int_<B>, fas::int_<C> >::type {};


さらに、シールドされたリストは、テンプレートパラメーターとして任意のクラスに渡されると、エラーログを読みやすくします。 

 #include <fas/integral.hpp> #include <fas/type_list.hpp> typedef fas::type_list_n< fas::int_<1>, fas::int_<2> , fas::int_<2> >::type list1; struct list2: list1 {}; template<typename L> class test {}; int main() { // test<list2> tst; test<list1> tst; tst.doit(); }


このバージョンでは、コンパイラは次のようなものを生成します。 

 error: 'class test<fas::type_list<fas::int_<1>, fas::type_list<fas::int_<2>, fas::type_list<fas::int_<2>, fas::empty_list> > > >' has no member named 'doit'


およびlist2の場合： 

 error: 'class test<list2>' has no member named 'doit'


リストに12個以上のアイテムがある場合、違いを感じるでしょう。 リストの長さを決定する関数を定義する例を使用して、エスケープの仕組みの秘密を明らかにしましょう。 シールドなしの実装： 

 template<typename L, typename R> struct length; template<typename L, typename R> struct length< type_list<L, R> > { enum { value = 1 + length<R>::value }; }; template<> struct length< empty_list > { enum { value = 0 }; };


この実装では、シールドされたリストが長さ関数の入力に来ると、コンパイル段階でエラーが発生します。 型のリストを他の構造と区別するために、構造fas :: type_listおよびfas :: empty_listで定義されているマジックメタタイプを使用して、さらに宣言します： 

 template<typename L> struct length : length_impl<typename L::metatype, L> {}; template<typename L> struct length_impl<metalist::type_list, L> { typedef typename L::right_type tail; enum { value = 1 + length< tail>::value }; }; template<typename L> struct length_impl<metalist::empty_list, L> { enum { value = 0 }; };


つまり、fas :: type_listまたはfas :: empty_listによる長さの特殊化が機能しない場合、入力パラメーターで定義されているメタタイプタイプに基づいた特殊化が必要になります。 定義されていないか、型fas :: metalist :: type_listまたはfas :: metalist :: empty_listでない場合、コンパイルエラーが発生します。 長さ<type_list <L、R >>および長さ<empty_list>の特殊化を削除すると、コードは機能しますが、コンパイルが遅くなります。 コンパイラー（この場合はg ++）は、入力タイプを「オープン」せずに特殊化を実行するのがはるかに簡単です。



さらに、すべての操作で入力タイプリストの有効性を確認できます。 このオプションは、デフォルトでは無効になっています。 コンパイル時間が長くなります。 型リストを試してみたい場合は、FASLIB_TYPE_LIST_CHECKを有効にして、CMakeLists.txtの行のコメントを外すことをお勧めします。



#add_definitions（-DFASLIB_TYPE_LIST_CHECK）



そこで、type_listによる操作とアルゴリズムの特殊化を無効にして、メタタイプによる特殊化のみを残し、コンパイル時間の観点から効果を評価できます。



#add_definitions（-DDISABLE_TYPE_LIST_SPEC）



さらに、コメントでは、タイプのリストを説明するときに、簡潔にするためにempty_listを示していません。 正しいタイプリストのみを使用します。

type_list_nはどのように機能しますか？
わずかに簡素化されたが機能する実装： 

 template< typename T1 = empty_list, typename T2 = empty_list, typename T3 = empty_list, typename T4 = empty_list, typename T5 = empty_list, typename T6 = empty_list, typename T7 = empty_list, typename T8 = empty_list, typename T9 = empty_list, typename T10 = empty_list, typename T11 = empty_list, typename T12 = empty_list, typename T13 = empty_list, typename T14 = empty_list, typename T15 = empty_list, typename T16 = empty_list, typename T17 = empty_list, typename T18 = empty_list, typename T19 = empty_list, typename T20 = empty_list, typename T21 = empty_list, typename T22 = empty_list, typename T23 = empty_list, typename T24 = empty_list, typename T25 = empty_list, typename T26 = empty_list > struct type_list_n { typedef type_list< T1, type_list< T2, type_list< T3, type_list< T4, type_list< T5, type_list< T6, type_list< T7, type_list< T8, type_list< T9, type_list< T10, type_list< T11, type_list< T12, type_list< T13, type_list< T14, type_list< T15, type_list< T16, type_list< T17, type_list< T18, type_list< T19, type_list< T20, type_list< T21, type_list< T22, type_list< T23, type_list< T24, type_list< T25, type_list< T26 > > > > > > > > > > > > > > > > > > > > > > > > > > bar; typedef typename organize<bar>::type type; };


26個すべてのテンプレートパラメーターから型のリストを作成します。明示的に指定されたパラメーターはリストの先頭にあり、リストの末尾はfas :: empty_listのセットで構成されます-これはfaslibのコンテキストでの型の誤ったリストです。 fas :: organize操作は、不要なfas :: empty_listを削除し、その結果、必要な要素数から型のリストを取得します。



C ++ 11のオプション： 

 template<typename Head = fas::empty_list, typename ...Args > struct type_list_n { typedef typename fas::organize< fas::type_list< Head, typename type_list_n<Args...>::type > >::type type; }; template<> struct type_list_n<> { typedef fas::empty_list type; };


また、簡素化された実装-fas :: organiseは、その形成の各段階でリストに適用されます。 良い方法では、最初にリストを作成し、それを一度整理する必要があります。 パラメータfas :: type_list_nで型のリストを渡すには、fas :: organiseが必要です。





タイプリストの操作



型リストを操作するために、型Lのリストに加えて、型Tを取り、インデックスIが整数型である操作のセットがあります。 インデックスを使用する操作の場合、接尾辞_cの代替があります。この代替では、インデックスは番号で指定されます。たとえば、 

 typedef fas::erase< fas::int_<0>, fas::type_list<char> >::type empty; typedef fas::erase_c< 0, fas::type_list<char> >::type empty;


タイプリストで利用可能なすべての操作のリスト：



More articles:


All Articles