• 作成:
  • 更新:

HaskellのAlternative, MonadPlus, StateT, Logicを使ってパーサーコンビネータのようにツリー構造を処理するための初歩知識

この記事は何?

これは、 logict :: Stackage Server とそれを組み合わせたパターンを使うための入門文書です。

具体的に行いたい処理としては、事前にある程度トークン分割などが処理されている、自然言語もしくはプログラミング言語などの人工言語の処理を想定しています。

ゼロから平坦なテキストをパースしていきたい場合は、 Megaparsec tutorial from IH book (翻訳) という名記事を読んだほうが良いと思いますし、そもそもこの記事を読んでもMegaparsecのチュートリアルは読むとためになるでしょう。

私の場合は、既に単語がトークン分けされていて、しかもそのトークンが単純なテキストじゃなくしかもツリーなので、パーサコンビネータじみたものを自作しなければいけなかったのでそれで処理実装を行って、それが他の人にも使えるように前提知識を解説する記事を書いています。

前提知識段階では汎用的な話なのでいっそのこと全世界に公開しています。

想定読者の知識

必要なこと

  • Haskellがある程度読み書きできる
  • モナド変換子を使ったコードが書ける

不要なこと

  • モナド変換子を理解している(私も本当に理解しているか怪しい)
  • 自然言語処理の知識

LogicT以前

まずはLogicT以前の汎用的な型クラスなどの話から開始します。

AlternativeとMonadPlusの有用性

型クラス、 Alternative は便利です。最近の実務ではRIOがemptyをexportしないので、面倒なのでmzeroを使ってAlternativeMonadの制約を付け加えたMonadPlusが型制約になってしまうことが多いですが。

この型クラスの具体的なインスタンスにはMaybe, [], そしてLogicTがありますが、話を簡単にするためにとりあえずMaybeで話を進めます。

Alternativeをパッと見ると、

Prelude Control.Applicative> Nothing <|> Just 1 <|> Just 2
Just 1

とかが出てきて、そんなことは退屈だし、 Monoidを使う場合などと比べてちょっと短く書けるのは良いけど、他のnull不安全な言語で||で書くとか、 Swiftで??とか書くのと同じではないか? Haskellで自分で面倒を作り出して自分で解決しているマッチポンプだ。などと言うことを思うかもしれません。

しかしこれが言語機能ではなく関数で実現されているのにも利点があります。

例えば、

choose :: Alternative f => [a] -> f a
choose = foldr ((<|>) . pure) empty

https://www.stackage.org/haddock/nightly-2022-12-07/logict-0.8.0.0/Control-Monad-Logic-Class.html#v:once

のようにListAlternativeな汎用的なものに変換する処理が自然に合成できたりすることですね。これでListLogicTに変換したりすることが出来ます。

またプリミティブに一つの型のみに対象を限定することなく型クラスの関数であることで拡張性を確保出来るので、後述のようにStateTなどのモナド変換子などと組み合わせることが出来て非常に便利です。 MegaparsecやattoparsecのParser型もAlternativeのインスタンスであることでAlternativeに対する汎用的な関数を使うことが出来ます。実際attoparsecパッケージで定義してある汎用的なAlternative関数が使いたいがために、 attoparsec本体を使わないのに依存してしまうことがたまにあります。

many :: Alternative f => f a -> f [a]Control.Applicative本体に定義されてある標準の関数ですが、とても汎用的で便利です。

manyの便利性をStateを使わずに説明しようとしましたが、 MaybeT IOとか余計にややこしいのでStateの説明に行きます。 Alternative単体で便利な例を考えると「それListMonad機能だけでで良くない?」ってなってしまったので、 AlternativeMonadPlusにしてモナド変換子などを使うと輝いて見えるタイプの型クラスなのかもしれません。

なお言語機能じゃないから短絡評価にならないとかはHaskellは遅延評価なので基本的には問題ないです。

少し脱線すると、 Scala Catsでは、 AlternativecombineKとかは値渡しです。なんで名前渡しにしてないんだろう…不便…ってScala書いてる時に思ってて、名前渡しにするラッパーを作っていました。 Eval とかで自分で制御しろってことなんでしょうか、でも、 scala.OptiongetOrElseはちゃんと名前呼び出しだし、実用性を重視してほしい。

Stateの有用性

何故純粋関数型言語のHaskellでわざわざStateを使うのかは過去に書いたことがあります。 HaskellのStateの必要性が, プログラミング言語の処理系を書いた時にわかったので, Stateの良さを語ります - ncaq

昔の記事では既にASTを構築してから実行する時の優位性を書いていますが、パース段階では特にStateは有用です。ソースがリストだろうがツリーだろうが、パースしたものとその残りははっきりと区別する必要があります。

特に入力元をツリーとする場合は、パースしてない残りを表す場合ために、 TextのようにIntなどでカーソル位置を表すわけにもいけないので、ツリー自体を持って、それを削っていくような実装が自然でしょう。

また一時的にサブツリーをトップレベルにしてコンビネータを実行して解析してもらうことで問題を分割することが出来ます。 Zipperに似てますね。

我々はMwbTreeという独自のツリーと、それを補助するwithLogicNewRootのような関数を作り、一時的にサブツリーを全体状態に変えコンビネータを実行して解析結果を手に入れ、サブツリーは抹消する方法を使っています。

そのうちこのツリーと関連関数をFLOSSとして配布したいなあと思っています。

よって現在のStateは自由自在に変えられて、なおかつ過去の履歴が残ると都合が良いわけです。

MonadPlusとStateを組み合わせてトイコンビネータを作る

StateTと組み合わせることでAlternativeMonadPlusの良さが発揮されます。

極めて単純化した説明をします。

トイコンビネータを作りましょう。

例えば、

import           Control.Applicative
import           Control.Monad
import           Control.Monad.Trans.State.Strict
import           Data.Char
import           Data.Text as T

type Parser = StateT [Text] Maybe

-- | 先頭の単語を取得する。
popToken :: Parser Text
popToken = do
  s <- get
  case s of
    [] -> mzero
    (x : xs) -> do
      put xs
      return x

parseDigitOrAlpha :: Parser Text
parseDigitOrAlpha = digit <|> alpha

digit :: Parser Text
digit = do
  t <- popToken
  guard $ T.all isDigit t
  return t

alpha :: Parser Text
alpha = do
  t <- popToken
  guard $ T.all isAlpha t
  return t

のようなパーサがあるとします。

このパーサに["a"]を食わせてみましょう。

λ> runStateT parseDigitOrAlpha ["a"]
Just ("a",[])

のような結果になります。最初にdigitでtokenを消費したように見えるのに、 alphaでtokenを取得できています。

バックトラックが発生しています。

これはStateTAlternativeの実装を見れば一目瞭然です。

 StateT m <|> StateT n = StateT $ \ s -> m s `mplus` n s

https://www.stackage.org/haddock/lts-20.3/transformers-0.5.6.2/src/Control.Monad.Trans.State.Strict.html#line-212

2つのコンビネータにその時点での状態引数を2つに分けて渡しています。 Stateの持つ状態が可変に見えても実態は不変であるからこそ出来る技ですね。不変参照のためパフォーマンスの多大な問題にはなりません。多分。

これにより他のコンビネータで状態がぐちゃぐちゃになってわけわからんと泣きながらプリントデバッグをする必要が少し減ります。

やっとmanyの有用性を示すことが出来ます。

λ> runStateT parseDigitOrAlpha ["a", "0", "b"]
Just ("a",["0","b"])
λ> runStateT (many parseDigitOrAlpha) ["a", "0", "b"]
Just (["a","0","b"],[])

のようにmanyとコンビネータを修飾してやるだけで繰り返しを表現できて汎用性もあります。 someなら空リストは許さず一つの要素を要求するとか、そういうAlternative向けの汎用関数は他にも色々あります。 Data.Attoparsec.ByteString あたりから引っ張ってきても良いかもしれませんね。これが使えるならだいたいAttoparsecそのまま使っても良いんですが… とりあえず自前のwithLogicNewRootとその派生にmanysomeは便利に使えてます。

ちなみにこれ、後述するLogicTでは、

StateT (MwbTree word) Logic

のような入れ子になっている必要があります。

LogicT (State (MwbTree word))

のような入れ子になっているとStateが共有されてしまいます。

これはMegaparsecでは注意が必要です。 tryコンビネータをコンビネータに付与してやらないとこのような動作にはならないことがあります。そもそもpopTokenのような雑な実装ではなく条件付きで取得していれば消費も起きないので次のAlternative要素を選ぶこともありますが。パフォーマンスを追求するためにこのような設計になっているようです。

我々は前処理でニューラルなもっと重い処理をしているのと、後処理でメチャクチャ計算負荷のかかるアルゴリズムを回しているのと、まだまだ開発途中なので今最適化を気にしても仕方ないと早すぎる最適化を危惧して、今のところあまり気にしていません。

ただこういう雑オートマトンを使う時は純粋関数で済んでも別スレッドに処理を移して、タイムアウトを設定しておいた方が良いでしょう。雑に無限再帰が発生するかもしれませんし、手軽にバックトラックしているのでReDoSみたいな問題が発生するかもしれません。 ReDoSから学ぶ,正規表現の脆弱性について - Qiita

MaybeよりListになっていると便利

先程の簡単なトイコンビネータではパーサの返り値をMaybeにしていましたが、特に結果が一意に定まらない可能性が高い自然言語処理ではListの方が便利なこともあります。

パーサの型を以下のように変更するだけで、

type Parser = StateT [Text] []

実行結果ではソースの取得数などがブレにブレてくれます。

λ> runStateT (many parseDigitOrAlpha) ["a", "0", "b"]
[(["a","0","b"],[]),(["a","0"],["b"]),(["a"],["0","b"]),([],["a","0","b"])]

これだけ見るとなんの役に経つんだという感じがしなくは無いですが、いわゆるNN NN問題(複合名詞の区切りがどこなのかイマイチ分からない)とかを、仕方ないので両方の解析結果を返すということがお手軽に出来ます。

もちろん結果は大量になるのでtakeなどで区切る必要がありますね。

ListよりLogicTの方が便利

LogicTの話を始めるまで6000文字近くかかってしまいました。

自然言語処理など曖昧性が必要な場合は、 ListよりlogictLogicLogicTを使った方が便利でしょう。

logictはProlog, Datalogで出来ることをHaskellで再現するためのパッケージです。

何故便利かというと、まずListはモナド変換子では無いので、 IOとかを仕込ませるのが面倒です。 ListTはあるにはありますが、それも結局別パッケージです。

またいくら曖昧な結果が欲しいと言っても典型的なケースは1つだけです。その場合無駄な計算をしないことをListのGHCの遅延評価だけに任せるには心もとないです。 LogicTはあんまり実装追ってないですが継続渡しスタイルで制御しているのである程度は信頼出来そうです。

また、 Control.Monad.Logic.Class には便利な関数がたくさんあります。まあこれらの関数を提供する型クラスはListもインスタンスになっているためListでも使えるんですが。

interleave がイチオシです。

もう疲れて良い感じの例を思いつかないのと、昔参考にしてたアメリカの大学の資料が消失してしまったので雑に説明すると、数式解析とか係り受け解析を再帰で解析していくとうっかり無限再帰になってしまい結果が出ないことがあります。つまり雑に述べると深さ優先探索ではなく幅優先探索的なことをしてほしいのですが、これはそれを実現してくれます。

雑に解決するの最高!

他にもソフトカットなど、 Prologで使えた処理が実装されてあります。

logictの課題

便利な関数を集めたMonadLogic型クラスはReaderT, StateTなどには対応しているが、 WriterTには対応していません。

WriterでもControl.Monad.Trans.Writer.CPSは典型的なスペースリークはしない - ncaq に書いた通り、 Writerを避ける合理的理由はあまり思いつかないので、対応させたいのでさっきほんの少しだけやってみたのですが、即座には解決出来ませんでした。多分出来るとは思うのですが。今度また暇が出来たら対応させたいなと思っています。誰かがやってくれても良いですが…

とりあえずCPS版のWriterはmtlのexportが不十分になっているのでそれを解消するPRを投げました。

2022-12-24追記: 作った

とりあえず実装しました。 feat!: instance MonadLogic for WriterT by ncaq · Pull Request #33 · Bodigrim/logict mtlのバージョン要求を引き上げているため本家に取り込まれるのかはまだ謎ですが。

ちなみにEgisonというものもあります

プログラミング言語Egison も強力なパターンマッチが表現がよく宣伝されてますが、実は幅優先探索をする簡単な関数も用意されています。

まあEgison本体はまだ実験的なため実装の都合で動的型なのと、エコシステムの成熟度的に真剣に使うのは私はまだ厳しいと判断しています。

しかし、 Template Haskellで埋め込むライブラリがあります。 egison/egison-haskell: Template Haskell Implementation of Egison Pattern Matching

私が何故これを使わずにlogictを採用したのかはQuasiQuoteを連発するのが個人的に好きじゃなかったからです。でも時々このパターンマッチが欲しくなりますね。以下のような関数を書いていると尚更です。

-- | 指定された関数に一致する一つの要素を取り出し、取り出された残りの要素も返す。
-- それを非決定的に複数の要素を対象に行う。
findN :: MonadPlus m => (a -> Bool) -> [a] -> m (a, [a])
findN _ [] = mzero
findN f (x : xs) =
  if f x
  then return (x, xs) <|> (second (x :) <$> findN f xs)
  else second (x :) <$> findN f xs