colunさんのMM Languageを学ぶ

colunさんの作成されたMM Languageを学んでみます。
https://github.com/colun/mmlang
https://github.com/colun/mmlang/blob/master/doc/introduction.md

マラソンマッチに勝とう！という目的というよりは、DSLや抽象化を考察することで何かに役立てられないかという視点で学んでいます。 ただ、革新的なアプローチであり、実力以上の上振れが出るかもしれないので、興味のある方はぜひ実戦に使ってみると良いのではないでしょうか。

試験的にnotionでも公開してみました。
https://www.notion.so/colun-MM-Language-01a3c5bf337149889888df0c947bb7f6

以下、私の理解なので誤りがある部分も含まれるかもしれません、ご注意下さい。

MM Languageの概要

いわゆるDSLで、独自形式の言語でコードを記述すると、C++コードに変換し実行することができます。
（注：ここではDSLとしていますが、私がそう解釈しただけであり、その呼び方が適切でない可能性はあります）

目玉機能として、ループ演算子とビームサーチがあります。

特にビームサーチについて、通常はロジックの本質でない状態管理のコードを書く必要がありますが、MM Languageのビームサーチでは状態管理を自動的に効率的に行ってくれるため、本質部分に集中できます。 https://github.com/colun/mmlang/blob/master/doc/introduction.md#ビームサーチ

入力例は以下です。
https://github.com/colun/mmlang/blob/master/examples/chokudai005a.m2

出力例は以下です。
https://github.com/colun/mmlang/blob/develop/examples_outputs/chokudai005a.cpp
出力は元の入力コード（これはコンパイルされない）＋ライブラリコード＋変換後コード で構成されます。

DSL

DSLの文法は、PythonとC++が混じっている感じです。

PythonのLarkというDSLのパーサが使われています。
https://github.com/lark-parser/lark

動かすときの流れは、

  1. MM Languageの文法に沿ったコードを書き、拡張子.m2で保存する
  2. コマンドラインからDSLのパーサを起動し、変換を行うと、C++に変換されたコードが出力される（—runオプションをつけると、自動的にコードが実行される）
  3. コンテストには、変換されたC++コードを提出できる。

（https://github.com/colun/mmlang#readmeを参照）

ここで、変換後のファイルは以下で構成されます。

  • 元の.m2の入力コード （確認用、ディレクティブによってコンパイルされないようになっている）
  • C++のライブラリコード
  • .m2をC++に変換したコード

ループ演算子

本家の説明は以下にあります。

https://github.com/colun/mmlang/blob/develop/doc/introduction.md#ループ演算子

「ある文中にループ演算子が出てきた場合、文の外側にループを作成し、ループ演算子の箇所をループ変数で置き換える」と理解するのが分かりやすいと思います。

なので、被代入側でも代入側でも利用することができます。

// 被代入側にループ演算子を適用する例 - 入力コード
A[0:3] = inputInt()

// 被代入側にループ演算子を適用する例 - 変換後C++コード
for(int $1=0; $1<3; ++$1) 
    A[$1] = inputInt();

// 代入側などにループ演算子を適用する例 - 入力コード
print(0:3)

// 代入側などにループ演算子を適用する例 - 変換後C++コード
for(int $1=0; $1<3; ++$1) 
    print($1);

（実際のコード変換とは異なります）

なお、

  • 文中にｎ個のループ演算子を使用した場合、ｎ重ループとなります。
  • ループ変数をバインドし、文の他の箇所で使用することができます。

ビームサーチ

本家の説明はこちらになります。

https://github.com/colun/mmlang/blob/develop/doc/introduction.md#ビームサーチ

使い方は以下のようになります。

  • ビームサーチのメインとなるロジックの関数に、@beamのようなデコレータをつける
    　（以下、更新関数ということにします）
  • 更新関数は、引数としてスコア・ハッシュ・操作などの情報をとる
  • 更新関数は、ある状態から開始し、操作を行い次の世代の状態に更新したのちに、更新関数を再帰することで次の世代の状態の作成を行う
  • 更新関数内で状態を管理する変数は、xarray, xvectorなどのメモリ自動管理型のデータ構造を利用する

通常はビームサーチを行う場合、状態の巻き戻し処理を行うか、盤面全体をコピーするかという処理が必要になります。MM Languageでは、ビームサーチクラスの機能およびメモリ自動管理型のデータ構造によって、自動で状態の巻き戻し処理が行われます。

ビームサーチの深み

では、上記のような挙動はどのような仕組みで実現されているのでしょうか？

ビームサーチの流れ

  • ビームサーチのノード（xbeam$node）は、状態およびスコア、親ノードなどの情報を持ちます。
  • ビームサーチクラス（xbeam）は、current_ranking, next_rankingという2つの変数を持ちます。これらは両端プライオリティキューであり、スコアとノードへのポインタを要素とします。
  • 最初はcurrent_rankingに初期状態のノードをセットします。

以下を繰り返すことで、ビームサーチを行うことができます。

  1. current_rankingのスコアの最も大きいノードを処理します。
  2. 処理対象のノードの状態に対して、更新関数が実行されます。 更新関数の中で再帰で更新関数が呼び出されたときに、next_rankingに次の状態のノードを追加します。 ただし、ビーム幅を超える数のノードがnext_rankingに存在する場合、スコアの最も小さいノードは除外されます。
  3. 1-2を繰り返します。 current_rankingが空になるか、時間が経過した場合は次の世代のノードの実行に移ります。 次の世代の実行は、current_rankingにnext_rankingをコピーし、next_rankingを空にすることで行います。

状態の自動管理の実現

上記を単純に行うと、状態がめちゃくちゃになってしまいます。自動的な状態の巻き戻しをどう実現しているかを以下で説明します。

  • xarray, xvectorなどのメモリ自動管理型のデータ構造は、その値が変更されるときに、変更点を記録する仕組みを持っている。 つまり、変更されるときに「変更箇所のポインタ、値のサイズ、変更前の値」を記録する。
    （xmemクラスの静的変数であるbufferに記録領域を確保している）
  • 更新関数は、更新の最初から最後までの操作履歴をpatchとして保存する。 つまり、メモリ自動管理型のデータ構造による変更をウォッチし、「変更箇所のポインタ、値のサイズ、変更前の値、変更後の値」のリストを保存する。
    （データ構造による変更のウォッチは、実際にはxmem::bufferの使用領域の増加分のみをみている）
  • patchの情報があれば、更新前の状態からredoして更新後の状態にすることも、更新後の状態からundoして更新前の状態にすることもできる。
  • ビームサーチのノードは、「世代（depth）、親ノードのポインタ、patchのポインタ」の情報を持つ
  • ビームサーチでは、ノードAを計算した後に別のノードBの計算を行うことになる。 このとき、状態をノードBの時点に変更してから計算する必要がある。
  • ノードAからノードBの状態への変更は、ノードAとノードBの共通の先祖であるノードCを見つけ、ノードAからノードCまでのpatchをundoしていき、ノードCからノードBまでのpatchをredoしていくことで実現できる。（以下はイメージ図）

f:id:threecourse:20210410020858p:plain:w500