substring-parserで「タイプセーフプリキュア!」を移行した話

~タイプセーフプリキュア!を支える技術 その3~

Posted by Yuji Yamamoto(@igrep) on September 4, 2018

先日私はプリキュアハッカソン NewStageというちょっと変わったイベントで、「タイプセーフプリキュア!」の最近の更新について発表いたしました。
今回はその際使用したスライドを、ブログ記事として拡大して共有させていただきたいと思います!

Link to
here
予告編(はじめにまとめ)

  • Haskell界に伝わる伝説のアイテム「パーサーコンビネーター」を応用して、「タイプセーフプリキュア!」の古いソースコードを半自動で変換しました。
  • 「パーサーコンビネーター」は正規表現よりいいところたくさんですが、文字列の先頭からのマッチしかできないのがつらいです。
    • substring-parserというライブラリーを書いて、対応しました。
  • パーサーコンビネーター最高! ✌️😆✌️

Link to
here
これまでのあらすじ

Link to
here
「タイプセーフプリキュア!」とは?

rubicureACME::PrettyCureのような「プリキュア実装」の1つです。
詳しくはこれから挙げる過去の記事をご覧ください、と言いたいところですが、よくよく見たら「プリキュア実装」が何かを明記してる記事ではないようなので😅、ここで軽く説明しましょう。
「プリキュア実装」とは一言で言うと「プリキュアやプリキュアに変身する女の子たち、変身時の台詞など諸々のプリキュアの設定をソースコードに収録したライブラリー」です。

例えば、今回取り上げます私の「タイプセーフプリキュア!」は(もちろん)Haskellで書かれたプリキュア実装で、次のように書くことで、キュアアンジュが変身する際の台詞を取得することができます。
(出力されるリストは、手で整形しています)

GHCiで上記のコードを試す場合は、下記のコードでtypesafe-precureunicode-showをインストールした上で起動するとよいでしょう。

その他の機能や、使っているGHCの拡張などについては下記の記事をご覧ください。

Link to
here
cure-index.jsonとは?

そんな「タイプセーフプリキュア!」ですが、前述のQiitaの記事の最後で「typesafe-precureは現状非常に冗長で、非実用的な実装になってしまっています」と述べているとおり、ほかのプリキュア実装と異なり、実用性を度外視して「設定の正しさ」を最優先事項とした結果、変身時の台詞や浄化技(「必殺技」ともしばしば呼ばれます)の台詞を取得するのに、非常に冗長なコードが必要になってしまいました。
それではせっかくYouTubeやらWikipediaやらBlu-rayやらを見直してせっせと集めた情報が勿体ないので、集めた情報を、コンパイル時にJSONとして出力することにしました。
そうして生まれたのがcure-index.jsonとそれをプリティープリントしたpretty-cure-index.jsonです。
将来的には、かつてrubicureで作ったユナイトプリキュアを書き直すのに使用しようかと考えています。

作るに当たって新たに「タイプセーフプリキュア!」のソースコードに仕込んだ仕組みについては、去年のHaskell Advent Calendarの記事をご覧ください。
Template HaskellGHCANNという機能を濫用することで達成しました。😎

Link to
here
今回のプリキュアハッカソンに向けて行ったこと

従来のcure-index.jsonには、最新作である「HUGっと!プリキュア」と、その一つ前の作品である「キラキラ☆プリキュアアラモード」の情報しか収録されていませんでした。
前述の去年のHaskell Advent Calendarの記事でも触れましたが、収録のためにはプリキュアの設定の書式を大幅に変更しなければならず、面倒なのでひとまず後回しにしていたのです。

そこで今年のプリキュアハッカソンにて発表するのによいネタだろうと思い、あの手この手を使って、全シリーズをcure-index.jsonに含める対応を行いました1🎉。

Link to
here
🔴修正の書式

それでは、具体的にどんな修正を行ったのか紹介しましょう。
修正前は、プリキュアの設定を収録した各モジュール(ACME.PreCure.Textbook以下にあるので、今後は「Textbookモジュール」と呼びます)には👇こんな感じのTypes.hsがたくさんありました。

上記はキュアミラクルを表す型の定義と、その日本語での名前、変身時の名乗りといったプロフィールを設定しているコードです。
このほかにも、プリキュアに変身する女の子の設定や、変身の際に必要な変身アイテムなどの型定義がたくさんあります。
transformedInstanceで始まる行は、Template Haskellを使った、型クラスのインスタンス宣言です。
transformedInstanceというマクロが、Transformedという型クラスのインスタンスを生成することで、プリキュアを表す型と、日本語での名前、変身時の名乗りを実際に紐付けているのです。
(実際の日本語での名前はご覧のとおりcureName_Miracleといった変数に束縛されております。Words.hsというファイルから参照しています)

修正前はこのように、あくまでもHaskellのソースコードとして、プリキュアの設定を書いていたため、このままではcure-index.jsonのデータとして扱うのが難しい状態でした。

Link to
here
🔵修正の書式

そのため、今回修正した後の各Textbookモジュールでは、👇こんな感じのProfiles.hsで、各種の設定を宣言することにしました。

mkTransformee関数で作っているTransformee型の値は、cure-index.jsonの一部として、JSONに変換する中間データです。もちろんToJSONのインスタンスになっております。
このように新しい各Textbookモジュールでは、直接Haskellのソースコードとしてプリキュアの設定を書く代わりに、一旦JSONに変換する用の中間データを設けることで、cure-index.jsonに収録しやすい状態にしています。

こうして作られたTransformeeなどの中間データ用の値は、各Textbookモジュールのルートに当たるモジュールで、型クラスのインスタンス宣言を行ったり、ANNという機能でモジュールに紐付けられます。
以下は「魔法つかいプリキュア!」のルートに当たるモジュールMahoGirls.hsからの抜粋です。

Profiles.hsで定義したtransformeesというリストを、ANNMahoGirlsモジュールに紐付け、declareTransformeesというTemplate Haskellのマクロで型宣言やインスタンス宣言を生成するのに使っています。
ANNについては前回の「タイプセーフプリキュア!を支える技術」をご覧ください2

修正前との違いにおける要点を繰り返しましょう。修正後の各Textbookモジュールでは、

  • プリキュアの情報を、
    • cure-index.jsonとして書き出すためのデータ
    • Template Haskellで型や型クラスのインスタンスとして生成するためのデータ
  • 両方で扱えるようにするために、専用の型の値として保存

するようにしています。

Link to
here
どうやって修正する?

それではここからは、各Textbookモジュールの書式を、どうやって前節で説明したような、「修正前」から「修正後」の書式に移行したのか説明します。

当然、手で修正するには大変な量です。
従来より「タイプセーフプリキュア!」ではTVシリーズ15作品に加えてキュアエコーが出てくる映画もサポートしているため、各Textbookモジュールは16作品分存在しています。
すでに「修正後」の書式に移行済みの「HUGっと!プリキュア」と「キラキラ☆プリキュアアラモード」を除いても、14作品分書き換えないといけません。
シリーズごとに定義されている型やインスタンス宣言の数にはばらつきがありますが、すべて移行してから数えてみたところ、型の数だけで313個、変身や浄化技のインスタンス宣言だけで211個ありました。
プリキュアやプリキュアに変身する女の子、変身アイテムだけでなく、それぞれの変種も別の型として定義しているため、実際のプリキュアの数よりも遙かに多いのです😵。
Vimのマクロなどを駆使すれば決して人間の手でも移行できない規模ではありませんが、そこは「タイプセーフプリキュア!」です。
始まって以来私がGHCの拡張を始めいろいろな技術を試すための実験場としても機能していたので、ここは是非ちょっと凝ったことをしてぱーっと書き換えてみたいものでしょう😏。
そこで思いついたのがパーサーコンビネーター、並びに拙作のライブラリーsubstring-parserだったのです💡!

Link to
here
パーサーコンビネーターとは

substring-parserの紹介の前に、パーサーコンビネーターについて簡単に紹介しておきましょう。
(「すでに知ってるよ!」という方はこの節は飛ばした方が良いかと思います)
パーサーコンビネーターは、例えば正規表現のような、文字列を解析する技術の一つです。
Haskellmegaparsecattoparsecをはじめ、多くのプログラミング言語にライブラリーとして提供されています。

実装はいろいろありますが、本質的にパーサーコンビネーターは「文字列を受け取って『文字列を解析した結果』と、『残りの文字列』を返す関数」として表現されます。
加えて、それらを簡単に組み合わせるためのAPIを提供することで、複雑な文字列から複雑なデータ構造を抽出できるようにしてくれます。

実際のパーサーコンビネーターのライブラリーを単純化して例を挙げましょう。
例えば、通例パーサーコンビネーターのライブラリーはdecimalという、「10進数の文字列を受け取って、整数を返すパーサー」を提供していることが多いです。

parse関数に、解析したい文字列と一緒に渡すことで、「文字列を解析した結果」と、「残りの文字列」を取得することができます。

👆上記の例では「解析したい文字列」として123abcを渡したので、パースした結果の整数123と、その残りの文字列"abc"を返しています。

これだけではつまらないので、ほかのパーサーの例も挙げましょう。
👇今度は「文字 セミコロン ; を受け取って、そのまま返すパーサー」です。

「パースした結果」がセミコロン ; で、「残りの文字列」が"aaa"となっていますね。

それでは以上2つのパーサーを組み合わせて、10進数の文字列を受け取った後、セミコロンを受け取り、整数を返すパーサーを作ってみましょう。

Haskellにおけるパーサーコンビネーターのライブラリーは、パーサーをMonadとして提供することで、上記のようにdo記法でパーサーを組み合わせることができるようになっています。
ここでは詳細は割愛しますが、

  1. decimalで整数をパースしたあと、
  2. char ';' で文字セミコロン ;をパース(でも結果は無視)し
  3. パースした結果として「decimalがパースした整数」nを返す

という処理を行っているのがわかるでしょうか?

ちなみに、パーサーコンビネーターに慣れた読者の方なら、いわゆるApplicativeスタイルを使って、次のようにも書けると気づくでしょう。

これならパースした結果をいちいち変数に束縛する必要もなく、より簡潔に書くことができますね!

パーサーコンビネーターのパワーを実感していただくために、もう一つ例を紹介します。
manyという関数にパーサーコンビネーターを渡すと、「受け取ったパーサーコンビネーターで失敗するまで繰り返しパースして、その結果をリストとして返す」パーサーが作れます。
例えば先ほどの「10進数の文字列を受け取った後、セミコロンを受け取り、整数を返すパーサー」から、「セミコロンが末尾に着けられた整数のリストを返すパーサー」を作ることができます。

このようにパーサーコンビネーターは、小さなパーサーをどんどん組み合わせることで、複雑な文字列から複雑なデータ構造を取り出すパーサーを、クールに作れるようにしてくれます。

Link to
here
パーサーコンビネーターが正規表現より良いところ・悪いところ

そんなパーサーコンビネーターについて、正規表現と比べた場合の長所短所を明確にしておきましょう。
まずはよいところから。

Link to
here
👍パーツとしてパーサーを組み合わせるのが簡単

前節で示したように、複雑なパーサーも、小さなパーサーの組み合わせからコツコツと作れるようになっています。

Link to
here
👍パースした結果を、文字列から複雑なデータ構造に割り当てるのが簡単

さっきのdecimalは、パースした結果を直接整数(Int)として返していたことにお気づきでしょうか?
正規表現で欲しい文字列からデータ構造を取り出したい際は、通常グルーピング機能を使うことになりますが、必ず一旦文字列として取り出すことになります。
それに対してパーサーコンビネーターには、取り出した文字列を対象のデータ構造に変換する仕組みが組み込まれています。
再帰的なパーサーを書いて再帰的なデータ構造に割り当てるのも楽ちんです。

Link to
here
👍パースした結果に基づいて、パーサーの挙動を変えることができる

今回の例にはありませんでしたが、例えばパースして取り出した整数の数だけ、続きの文字列を繰り返しパースする、といったことも簡単にできます。

一方、正規表現と比べて悪いところもあります。

Link to
here
👎記述が冗長

正規表現はいわゆる「外部DSL」、すなわちプログラミング言語から独立した構文で提供されています。
PerlRubyなどの構文で言えば、/.../の中は別世界ですよね。
パーサーコンビネーターは、本質的に「文字列を受け取って『文字列を解析した結果』と、『残りの文字列』を返す関数」であるとおり、あくまでプログラミング言語標準の関数(のうち、文字列の解析に特化したもの)として提供されます。「内部DSL」なんて呼ばれることもあります。

そのため、正規表現とは異なり、あくまでもプログラミング言語の構文の中で使えなければならないため、使用できる文字列に限りがあり、必然的に長くなります。
例えば先ほどのmanyは正規表現で言うところの*0回以上の量指定子)とちょっと似てますが、正規表現の方が3文字も短いですよね。

しかしながら、冗長であることはメリットにもなり得ます👍。
*をはじめ、正規表現の特殊な機能を使うには、専用の記号(メタキャラクター)をその数だけ覚えなければなりません。
片やパーサーコンビネーターはmanyのような機能も普通の関数として提供されるため、冗長である分分かりやすい名前をつけやすいのです。

Link to
here
👎ユーザーからの入力として直接受け取ることは難しい。

パーサーコンビネーターは先ほども触れた「内部DSL」です。
つまり、プログラミング言語の普通の関数として使用されるものです。
したがって、例えば正規表現をエディターの検索機能に利用すると言ったような、「ユーザーからの入力として受け取る」と言ったことは、不可能ではないものの、正規表現に比べれば難しいです。

Link to
here
👎正規表現でいうところの * にあたるmanyが、必ず強欲なマッチになる

こちらについてはちょっと難しいので後述します。

Link to
here
👎文字列の先頭からのマッチしかできない

この問題は、パーサーコンビネーターをベター正規表現として使おうと思った場合に、しばしばパーサー作りを面倒くさくします。
パーサーコンビネーターは、原理上必ず文字列の先頭から解析するよう作られています。
例えば先ほど紹介したパーサーdecimalの場合、

と書いても、"abc123"は先頭が「10進数の文字列」ではないので、失敗してしまいます(実際の戻り値はライブラリーによって異なります。試してみましょう!)

パーサーコンビネーターはそもそもの用途が0からプログラミング言語などのマシンリーダブルな構文を作るところにあるので、妥当と言えば妥当な制限です。
その場合は必ず、文字列を頭から読んでパースすることになるでしょうから。

とはいえ、これは正規表現で例えるなら、常に先頭に\A (あるいは ^)を付けなければならない、あるいは自動的に付いてしまう、というような制限です。
正規表現は行の中にある一部の文字列を抽出したり置換したりするのによく使われるので、役に立たないケースがたくさん出てきてしまいます。

パーサーコンビネーターでこの問題に対応するには、マッチさせたい文字列に到達するまで、スキップするための処理を書かないといけません。
残念ながらこれは、正規表現で言うところの \A.*(本当にマッチさせたい文字列) と書けばよい話ではありません
\A(マッチさせたくない文字列)*(本当にマッチさせたい文字列) という書き方をしなければならないのです。
なぜなら、先ほど触れた「正規表現でいうところの * にあたるmanyが強欲なマッチになる」という問題があるためです。
正規表現で言うところの\A.*(本当にマッチさせたい文字列)を書くと、.*が「マッチさせたくない文字列」だけでなく「本当にマッチさせたい文字列」までマッチしてしまい、結果肝心の「本当にマッチさせたい文字列」を扱うことができなくなってしまうのです。

Link to
here
ソースコードの書き換えとsubstring-parser

さて、今回の目的は「『タイプセーフプリキュア!』のソースコードの書式を書き換えることで、全シリーズのプリキュアの情報をcure-index.jsonに収録する」ことでした。
そのためには、各Textbookモジュールのソースコードにおいて途中に含まれている、プリキュアを表す型の定義や、型クラスのインスタンス宣言を集める必要があります。
しかもそれらは、一つの定義が行をまたいでいたりまたいでなかったりするので、よくある行単位で処理するツールを使うのも、なかなか難しいと思います。
また、抽出したいデータ構造も多様かつそこそこに複雑で、中には再帰的なデータ構造もあります。正規表現を用いてのパースも、かなり困難なことでしょう。
とはいえパーサーコンビネーターを通常のとおりに使うと、これまでに述べたとおり、「文字列の先頭からしかマッチできない」という制限が、考えることを複雑にします。

こうした状況は今回の問題に限らず、このように、ソースコードの多くの類似箇所を書き換える場面において、しばしば発生するでしょう。
そこで今回は3こうした問題全般に対応するライブラリーとして、substring-parserというライブラリーを作りました。

substring-parserを使えば、任意のパーサーコンビネーター4文字列の中間でもマッチさせることができます。
残念ながらドキュメントらしいドキュメントが全く書けてない状況ではありますが、一応動きます。
Spec.hsが動作を知る際の参考になるかも知れません。

Link to
here
substring-parserの仕組み

substring-parserはどのようにして、任意のパーサーコンビネーターを文字列の中間でもマッチできるようにしているのでしょう?
仕組みは単純です。
引数として受け取ったパーサーを、

  1. とりあえず先頭からマッチさせてみる。
  2. 失敗したら先頭の一文字をスキップして、次の文字からまたマッチさせてみる。

という手順を繰り返すだけです。 結果として文字列の先頭にある「マッチさせたくない文字列」をスキップすることができるのです。

⚠️残念ながら決して効率のいい方法ではないので、真面目なパーサーを書くときはおすすめしません!
あくまでも今回のような、書き捨てだけど、それなりに複雑な文字列を解析する必要がある場合のみ使うべきでしょう。

Link to
here
結果、できたもの

ここまで説明したsubstring-parserを駆使することで、私は無事、各Textbookモジュールを半自動で古い書式から新しい書式に書き換えることに成功しました。
(残念ながら古いTextbookモジュールには存在しない情報を補ったり、体裁を整えたりする必要があったため、完全に自動で書き換えられたわけではありません)
typesafe-precure#25という大きなPull requestに、移行したもののほぼすべてが刻まれています。

なお、上記のPull requestでは消してしまってますが、実際に実行した、移行用スクリプトはtypesafe-precure/app/migrate2cure-index.hsにあります。
ご興味のある方はご覧になってみてください。

また、もう少し小さいサンプルとして、プリキュアハッカソンの成果発表でデモをした時点のコミットも載せておきます。
👇のコマンドを実行すれば、こちらのコミット時点のパーサーで、同時点のTypes.hsから、cure-index.jsonで使用するGirlという型の値を取り出すことができます!

Link to
here
その他の似たソリューション

今回は、自前で作ったライブラリーと一から書いたパーサーを組み合わせることで「ソースコードの多くの類似箇所を書き換える」問題に対応しましたが、似たようなことを行うツールはほかにもあります。
いずれも私はほぼ使ったことがないので詳しい解説はできませんが、軽く紹介しておきます。

Link to
here
codemod

Facebook製の一括置換ツールです。指定したディレクトリーのファイル群を、正規表現で一括置換できます。
ここまで書くとperlsedawkなどで十分できそうにも聞こえますが、修正前後の状態を色つきで見ながら対話的に修正できるそうです。
正規表現での単純な修正が気に入らなければ、その場で該当箇所だけをエディタで修正できるとのこと。
Python 2に依存しているのがちょっとつらいところでしょうか…😨。

Link to
here
jscodeshift

同じくFacebookが作った、名前のとおりJavaScriptに特化したソースコードの修正ツールです。
こちらは正規表現は使用せず、「Transform module」と呼ばれる、JavaScriptASTを変換するための専用のスクリプトを実行することで修正するそうです。
様々な状況に特化した「Transform module」を別パッケージとしても提供しているようです。

📝以上の2つについては「JavaScript疲れに効く! codemodJSCodeshiftでリファクタリングが捗る - WPJ」も参考にしました。

Link to
here
refactorio

SuperPowers Corpという会社が開発中の、lensをはじめとするHaskellのパワーを集大成させた、ソースコードの一括置換ツールです。
ByteString -> ByteStringという型のHaskellの関数を渡すことで、指定したディレクトリーのファイルすべてに対して関数を適用し、書き換えます。

加えて、--haskell--html--javascriptなど、各言語に特化したオプションを渡すと、各言語のソースコードを修正するlensベースのmoduleimportした状態で、関数を作れるようにしてくれます。
具体的には、例えば--haskellオプションを渡すと、haskell-src-extshaskell-src-exts-prismsパッケージのモジュールをimportすることで、HaskellASTの各トークンに対応したPrismなどが使えるようになります。

後はbiplateなどlensライブラリーのコンビネーターと組み合わせれば、一気にHaskellのソースコードを編集することができます。 「任意のデータ構造に対するjQuery」とも言われるlensライブラリーのパワーを存分に生かしたツールなのです。

残念なところは、今でも開発中である点と、lensライブラリーに習熟していなければ使いこなせないという点でしょうか。
よく使うLens型やPrism型だけでなく、Traversalも使えなければなりません。
特にサンプルで紹介されているようなbiplateを使った場合において、指定したPrismがマッチしなかった場合、何事もなかったかのようにソースが書き換えられないため、デバッグが面倒なところもつらいです。

Link to
here
次のゴール

「タイプセーフプリキュア!」の開発は、これからもプリキュアハッカソンの前後とプリキュアAdvent Calendarの前後を中心に、今後も続ける予定です。
先にも触れましたが、次回は今回完成させたcure-index.jsonを使用することで、かつてrubicureで作ったユナイトプリキュアを「ユナイトプリキュア」を「ディナイトプリキュア」として書き直すかも知れません。
ただ、それ以外にももうちょっとHaskellで遊びたいことがあるので、後回しにするかも知れません。
Vim script、あんまり書きたくないんですよね…😥

Link to
here
まとめ

  • Haskell界に伝わる伝説のアイテム「パーサーコンビネーター」を応用して、「タイプセーフプリキュア!」の古いソースコードを半自動で変換しました。
  • 「パーサーコンビネーター」は正規表現よりいいところたくさんですが、文字列の先頭からのマッチしかできないのがつらいです。
    • substring-parserというライブラリーを書いて、対応しました。
  • パーサーコンビネーター最高! ✌️😆✌️

それではこの秋もパーサーコンビネーターでHappy Haskell Hacking!!✌️✌️✌️


  1. プリキュアハッカソンは「ハッカソン」の名を冠してはいるものの、実態としてはプリキュアの映画を観ながら好き勝手に開発するというゆるい会です。
    また、そもそもそれほど時間もないので、私は当日の34週間ほど前から今回の対応を始めておりました。「今回のプリキュアハッカソンに向けて行ったこと」なる見出しなのは、そのためです。

  2. 当時は各TextbookモジュールのTypes.hsというファイルでANNdeclareTransformeesなどを使っていましたが、現在は「ルートに当たるモジュール」で行うことにしました。ファイル数を減らすのと、exportする識別子を型に絞ることで、transformeesHugttoのような、あまりかっこよくない識別子を隠す、というのがその目的です。

  3. 実際には、前職時代に同様の問題に遭遇した際作成しました。今後も必要になったときにちょっとずつ開発していく予定です。

  4. 一応parsersパッケージを使って様々なパーサーコンビネーターのライブラリーをサポートするように作りましたが、現状attoparsecでのみテストしています。用途を考えれば多分十分じゃないかと思っています。