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

ソフトウェアのアーキテクチャについて（その２）～ ドメイン駆動設計から得られる知見

以下の記事の続きです。

threecourse.hatenablog.com

参考文献

以下の本でドメイン駆動設計について学んだところ、小〜中規模のプログラムの設計・記述についてもなかなかの知見・示唆が得られたので、まとめてみます。

以下も良い本らしいですが、まだ読んでないです

ドメイン駆動設計とは何か？

そもそもドメイン駆動設計とは何か？ということなのですが、私の理解では以下です。

  • ソフトウェアを開発する対象となる領域の知識に焦点を当てた設計方法
    ドメインの概念や事象を理解し、その中から問題解決に役立つものを抽出して得られた知識をソフトウェアに反映する。
  • ドメインとは、ソフトウェアの対象とする知識、影響、または活動の領域
  • 例えば会計システムであれば、金銭や帳票といった概念、その関係性や操作を適切にモデリングして設計する

ソフトウェアの対象とする領域を理解してモデリングしなきゃいけないのは当たり前だと思うので、これだけであればそれはそう、という感じ。

以下、「ドメイン駆動設計入門 ボトムアップでわかる！ドメイン駆動設計の基本 」をもとに具体的なパターンをまとめてみます。筆者の勝手な解釈が入っているため、元の書籍と記述が同じとは限りません。

概要

「ドメイン駆動設計入門 ボトムアップでわかる！ドメイン駆動設計の基本 」では、ドメイン駆動設計のパターンが以下に分けられています。

知識を表現するパターン

  • 値オブジェクト
  • エンティティ
  • ドメインサービス

アプリケーションを実現するためのパターン

知識を表現する、より発展的なパターン

  • 集約
  • 仕様

1. 知識を表現するパターン

1.1 値オブジェクト

「値」をクラスや構造体とするなどしてオブジェクトとして定義したもの

例
  • 氏名を表すクラス（姓、名をフィールドとして持つ）
  • 通貨を表すクラス（量、種類をフィールドとして持つ）
性質
  • 不変である・交換が可能である
    値を変えたい場合には代入によって変更する、それ自身の値が変わることはない
  • 等価性によって比較される
    姓と名が同じであれば同じものであるとする、通貨の量と種類が同じであれば同じものとする
メリット
  • 表現力を増す
    値オブジェクトのクラスの定義のコード自体によって、氏名は姓と名から構成されるということが示される。
  • 不正な値を存在させない
    コンストラクタで判定するなどして不正な値を除外できる
  • 誤った代入を防ぐ
    ユーザIDに商品IDを代入するようなことをできなくする
  • ロジックの散在を防ぐ
    値オブジェクトに関連する処理をそのクラスにまとめて記述することができる
感想

上手く使うと便利。つい文字列で素朴に持ちがちな値も、構造体やクラスにまとめると見通しが良くなることがある。

1.2 エンティティ

同一性によって識別されるオブジェクト

例
  • ユーザ（姓、名、ユーザID、ユーザ種別などのフィールドを持つ）
性質
  • 可変である
    再代入ではなく自身のフィールドの値を変えることで、ユーザ名などを変更できる
  • 同じ属性であっても区別される
    姓や名といった属性が同じだけでは同一であるとは言えない。ユーザIDのような識別子で同一性を表す
  • 同一性を持つ
    ユーザ名などを変更したとしても同一のユーザとして認識される
メリット
  • コードのドキュメント性が高まる・ドメインにおける変更をコードに伝えやすくなる
    エンティティに関連するルールはそのクラスにまとめて記述することができる
感想
  • エンティティは値オブジェクトとの対比で理解するのがよさそう。
  • 値オブジェクトはクラス化するのは自然ではない（氏名は文字列として持ってしまうことはありそう）なのだが、エンティティはクラス化するのは自然なので、これらのメリットはオブジェクト指向のメリットといえる
  • エンティティはライフサイクルを持つというのは大きな特徴といえる

1.3 ドメインサービス

値オブジェクトやエンティティに関連するが、値オブジェクトやエンティティに記述すると不自然なふるまいを定義するクラス

例

ユーザの重複を確認するメソッドはユーザクラス自体に定義するとちょっと変。 UserServiceクラスを定義し、そこにExistsメソッドで確認するようにすると自然になる

感想

値オブジェクトやエンティティに記述すると不自然なメソッドをどう書こう・・と悩んだことがあるのでなるほどという感じ。名前もManagerとかUtilとかで悩んでいたが、Serviceを使えば良さそう。

2. アプリケーションを実現するためのパターン

2.1 リポジトリ

データの永続化と再構築の処理を抽象的に扱うためのオブジェクト

例およびメリット

アプリケーションを作る上では、ユーザの生成・変更といった処理をデータベースなどに反映し、「永続化」する必要がある。また、永続化されたデータから、ユーザーIDで検索するなどしたユーザをオブジェクトとして「再構築」する必要がある。

ここで、直接ユーザからデータベースを叩くコードを書いてしまうと、具体的なデータベースの操作を記述することになり、分かりづらく密結合なコードとなってしまう。 そこで、ユーザはIUserRepositoryインターフェイスに対して操作を行い、データベースとの接続等の処理はIUserRepositoryを実装したUserRepositoryクラスで行うことにする こうすることで、テストも行いやすくなる。リポジトリの実装をテスト用のものに差し替えることで、いちいちデータベースをセットアップする必要が無くなる。

感想

これもなるほど。知らないと直接データベースを叩いてしまうことがありそう。リポジトリだけでなく、一歩抽象化する思考を身に着けておくと応用が効きそう

2.2 アプリケーションサービス

ユースケースを実現するオブジェクト

例

ユーザの登録処理、ユーザ情報取得処理、ユーザ情報更新処理、退会処理といった処理を記述するクラス

論点
  • アプリケーションサービスはあくまでドメインオブジェクトのタスク調整に徹するべきであり、ドメインのルールを記述すべきでない

  • データ転送用オブジェクト
    ドメインオブジェクトを公開するかどうかという論点がある。

    • ドメインオブジェクトを公開する場合、ユーザ情報取得処理でユーザを直接返してしまう方法をとる。これは楽であるが、アプリケーションサービス以外がドメインオブジェクトを自由に操作できてしまうリスクがある。
    • 別の方法として、DTO（データ転送用オブジェクト）にデータを移し変えるという方法がある。つまり、IDと名前というフィールドを持つUserDataオブジェクトを返すようにする。

  • コマンドオブジェクト
    更新処理を定義するときに、ユーザ名だけを変更したいときもあれば、メールアドレスだけを変更したいこともある。このとき、引数で制御する方法もあるが、追加のたびにメソッドの引数が変わってしまう。この対処法として、コマンドオブジェクトを定義し、更新処理の引数としてコマンドオブジェクトを渡すという方法がある。

2.3 ファクトリ

生成を責務とするオブジェクトのこと

例

採番処理機能を実装したユーザ生成を行うため、IUserFactoryインターフェイスを実装したUserFactoryクラスを用いる

3. 知識を表現する、より発展的なパターン

3.1 集約

データを変更するための単位として扱われるオブジェクトの集まり

例

自動車とその要素である車輪・位置・タイヤがある場合に、自動車オブジェクトおよびそのフィールドとなる車輪・位置・タイヤのオブジェクトを定義する。 外部からは直接に車輪・位置・タイヤを参照せず、自動車オブジェクトに定義したメソッド経由で扱うようにする。このときの自動車オブジェクトを集約ルートという。

3.2 仕様

オブジェクトの評価を行うオブジェクト

オブジェクトの評価は単純なものであればメソッドとして定義すればよい。しかし、複雑な評価を仕様オブジェクトとすることで、評価のルールを切り出すことができる。 例えば、CircleFullSpecificationというクラスにサークルが満員かどうかという判定を定義し、それをアプリケーションサービスで呼び出すような方法がある また、仕様オブジェクトに対するAND/OR演算を定義するようなこともできる。

感想
  • Strategyパターンに似ているように思えた。評価・戦略といった抽象的な概念をオブジェクトとすることで見通しが良くなることがある。

その他

CQS/CQRS（コマンドクエリ分離原則、コマンドクエリ責務分離原則）

状態を変更するメソッドとそうでない単に問い合わせをするメソッドを区別すると良い。

フロントエンド何もわからない（その５）〜 React Hooks + Redux + TypeScriptでいいんじゃね

去年から悩んで来ましたが、React (React Hooks + Redux) + TypeScript に落ち着きそうな気がしてきました。

前提

Webページの制作よりは、ヒューリスティックコンテストや数理最適化などのビジュアライザをさくっと作るのが主な目的です。

メインのフレームワーク

React (React Hooks + Redux) + TypeScript としました。

React Hooks + Reduxの使い方はこんな感じでシンプルです。

  • ReduxのReducerやActionを定義
  • Providerを定義し、Reduxのストアをコンテキストとして情報を伝える
  • useSelectorで状態を取得、useDispatchで状態を更新

セルの値をボタンやクリックで変更するだけの簡単なサンプルを作成しました。
https://threecourse.github.io/app-cells-react (Github Pages）
https://github.com/threecourse/app-cells-react (ソースコード）

以下、雑感です。

  • 用いる方法によっては、メソッドや状態をコンポーネントの親子関係に沿って受け渡すバケツリレーが発生するが、このやり方ではその心配がない
  • 関数コンポーネント + React Hooksで書く方がクラスコンポーネントで書くより良い様子
    クラスの方が「ちゃんとしていて拡張性が高い」イメージがあったが、Reactはどうもそういう訳ではないらしい。　
  • TypeScriptは入れない選択肢もあるが、型が付くのはやはり強力
  • 型をより精緻に書いたり、useMemoなどを使って高速化したり、非同期を上手く処理するのは今後の課題
  • 初心者が作る場合Nuxt.js/Vue.jsで開発するほうが悩む場所が少ないかもしれない。 ただ、コンポーネントの再利用性やTypeScriptとの親和性を考えると、Reactが優位に思えた

参考文献

TypeScriptは以下の本が良くまとまっています。Kindle Unlimited対象ですが普通に買っても良いと思いました。
速習 TypeScript 第2版 速習シリーズ
https://www.amazon.co.jp/dp/B086JKVGPB

React/Reduxは公式ドキュメントが良さそう。
https://ja.reactjs.org/
https://ja.reactjs.org/docs/hooks-intro.html
https://redux.js.org/
https://react-redux.js.org/
https://react-redux.js.org/api/hooks

Linter設定

Linterおよびその他の環境構築は以下を参考にしました。
create-react-app Lint構築よくばりパック(ESLint + TypeScript + airbnb + Prettier + lint-staged & husky + VSCode拡張)
https://qiita.com/jonakp/items/7d9f47c613c16cbf95aa

create-react-app + TypeScript + eslint + prettier によって導入し、airbnb/huskyなどは入れませんでした。
なお、vscodeでなくWebStormを使っているので、WebStormの保存時に自動Prettierを適用する設定としました。

CSSフレームワーク

CSSフレームワークはreactStrapを使いました。
https://reactstrap.github.io/

AtCoder Problemsの真似です。
https://github.com/kenkoooo/AtCoderProblems

ナーススケジューリング問題を焼きなましで解いて可視化する

この記事は、数理最適化 Advent Calendar 2020 の17日目の記事です。遅刻してすみません・・。

qiita.com

今回は、ナーススケジューリング問題と呼ばれる勤務シフト作成問題を焼きなまし法で解いてみました。*1

Reactで可視化したので、以下リンクをご参照下さい。
https://threecourse.github.io/nurse-scheduling-simulated-annealing/

焼きなまし法とは何ぞや、という方は以下を見ていただけると分かりやすいかと思います。

kumagallium.hatenablog.com

shindannin.hatenadiary.com

最近の自分が追っているテーマの一つは、最適化などの技術をGUIと組み合わせることでさらなる価値を産み出すことです。 アルゴリズムもフロントエンドも両方学ぶのは自分の頭のリソースが厳しいので、同じような問題意識を抱えている方と協力したいですね。

*1:出典：
池上 敦子 (2018) ナース・スケジューリング：問題把握とモデリング 21P Millarsの論文の2交代制ナーススケジューリング問題
Millar, Harvey H., and Mona Kiragu. "Cyclic and non-cyclic scheduling of 12 h shift nurses by network programming." European journal of operational research 104.3 (1998): 582-592.

poetry publishでPyPIに勝手に公開されないのかどうか

poetry publishをうっかり実行してしまい、privateなファイルが全世界に公開されると困るので。。 自分だけならまだ注意すれば良いけど、人に薦めることを考えると気になります。

結論

poetry new <package-name> からpoetry publishをしてみたところ、以下のようにまー大丈夫っぽい。

他の言語

C#の.NET Coreでは、dotnet publish コマンドは違った位置づけで、あくまでローカルに発行するだけ（のはず）。
https://docs.microsoft.com/ja-jp/dotnet/core/tools/dotnet-publish

Rustのcargo publishでは、publish = falseオプションがある。
opt-inにすべきでは？というIssueがある。
https://doc.rust-lang.org/cargo/reference/manifest.html#the-publish-field
https://github.com/rust-lang/cargo/issues/6153

ソフトウェアのアーキテクチャについて

最近、小〜中規模のプログラムを保守性高く記述するにはどうすればよいかが気になっていて、 ソフトウェアのアーキテクチャについて調べていました。

本を読んでみる

以下の本を浅めに読み通してみました。どの本もそれぞれ学ぶべき点があって興味深かったです。

学んだこと

疎結合の重要性

とにかく疎結合にすることが重要。分割すると脳のリソースにも優しいし、分担して作業できるし、テストもできる。

インターフェイス

インターフェイスは、振る舞いだけを定義し、基本的に実装を記述しない要素。
C#などの強い型付けの言語では使われるが、Pythonなどではあまり使われない印象がある（Pythonのabcモジュールはあるが）
インターフェイスを使うと、具体的なクラスでなく振る舞いに対して記述することが強く意識付けられ、 具体的なクラスに依存しづらくなるため、疎結合なプログラムを作りやすいように思える。

依存性の注入(Dependency Injection)

「依存オブジェクトの注入」と理解した方が良さそう。 依存オブジェクトを内部で生成するとテストがしづらいが、コンストラクタなどから与えるとモックなどを使ったテストができるようになる。
注入が必要な依存オブジェクトが増えると面倒になるが、その場合にはDIフレームワークを用いる選択肢がある。

（参考）SOLID原則

※各原則は私の要約です。（書籍などに明確に定義が記述されていないものもあるため）

S - 単一責務の原則

「クラスを変更する理由はひとつのみであるべき」
クラスの責務はひとつのみであるべき。それはそう。

O - 開放・閉鎖の原則

「拡張に対して開いており、変更に対して閉じているべき」
要するに、モジュールの振る舞いを拡張できるとともに、拡張したときに既存のコードに変更が発生しないということ。
これを満たすには、モジュールの機能をどう拡張するかの拡張ポイントを考えることになる。

L - リスコフの置換原則

「SがTの派生型であるとすれば、T型のオブジェクトをS型のオブジェクトと置き換えたとしても、プログラムは動作しつづけるはず」
要するに、あるオブジェクトを派生型のオブジェクトに置き換えたとしても動作しつづけるはずということ。 これもそれはそう。

I - インターフェイス分離の原則

「クライアントが使用しないメソッドに依存するよう強制されるべきではない」
上記「インターフェイス」参照

D - 依存性反転の原則

「上位レベルのモジュールは下位レベルのモジュールに依存すべきではない。両方とも抽象に依存すべき」
「抽象は詳細に依存してはならない。詳細が抽象に依存すべき」
確かにそれはそう。実現するには、インターフェイスを使った上で依存関係を上手くほぐしていく必要がありそう。

C#からC++を呼び出してポインタを使う

C#からC++を呼び出す方法を調べていたのですが、ポインタつかってごにょごにょできることを知って驚きました。 安全に使うには当然いろいろと気をつけなくてはいけないのですが、C++ではここまでできるのかと。

ソースコード

lib.hの記述

class Value
{
public:
    int v;
};

typedef void *Handle;
extern "C" int CreateValue(Handle *out, int x);
extern "C" int AddValue(Handle handle, int x);
extern "C" int GetValue(Handle handle, int *out);

lib.cppの記述

#include "lib.h"

int CreateValue(Handle *out, int v) {
    *out = new Value{v};
    return 0;
}

int AddValue(Handle handle, int v) {
    auto p = static_cast<Value*>(handle);
    p->v += v;
    return 0;
}

int GetValue(Handle handle, int *out) {
    auto p = static_cast<Value*>(handle);
    *out = p->v;
    return 0;
}

main.csの記述

ポイントは以下のとおり：

  • DllImportでC++ライブラリとのインターフェースを定義する
  • IntPtr型でC++のポインタを扱う
using System;
using System.Runtime.InteropServices;

class Program
{
    static void Main(string[] args)
    {
        External.CreateValue(out var ptr, 10000);
        int v;
        External.GetValue(ptr, out v);
        Console.WriteLine(v);
        for (int i = 0; i < 5; i++)
        {
            External.AddValue(ptr, 100);
            External.GetValue(ptr, out v);
            Console.WriteLine(v);
        }
        // おそらくメモリリークしている
    }
}

static class External
{
    private const string Path = "../../../lib.so";

    [DllImport(Path)]
    public static extern int CreateValue(out IntPtr ptr, int v);

    [DllImport(Path)]
    public static extern int AddValue(IntPtr ptr, int v);

    [DllImport(Path)]
    public static extern int GetValue(IntPtr ptr, out int v);

}

参考文献

アンマネージ コードとの相互運用

docs.microsoft.com

xgboostのAPI

github.com

実際ちゃんと使うのであれば、xgboostが行っているようにさまざまな用心をする必要がありそうです。