TL; DR
tailRecM は, Alternative あるいは MonadPlus でもあるパーサ (ParsecT) において,
再帰的なパーサの定義をする際にも有効.
パーサコンビネータは便利
例として文字列リテラルのパーサを書いてみます.
BNF で書くと (character はいい感じにやるとして),
stringHead ::= '"' stringTail ::= '"' | character stringTail stringLiteral ::= stringHead stringTail
Parsec (Haskell) なら, このような文字列リテラルの簡易的なパーサを, 以下のように BNF の定義に近い形で簡潔に書けます.
import Text.Parsec import Text.Parsec.String stringHead :: Parser () stringHead = char '"' >> return () stringTail :: [Char] -> Parser [Char] stringTail xs = (char '"' >> return (reverse xs)) <|> (noneOf "\"\r\n" >>= \x -> stringTail (x : xs)) stringLiteral :: Parser [Char] stringLiteral = stringHead >> stringTail ""
実行は (例えば GHCi で) こんな感じに.
λ> parse stringLiteral "" "\"foobar\"" Right "foobar"
さて, 同じことを loquat (JavaScript) でもやってみましょう. 以下は見た目が少しごちゃついていますが, 大体 Parsec のものと同じことをやっています.
const lq = require("loquat")(); const stringHead = lq.char("\"").void(); const stringTail = xs => lq.char("\"").return(xs) .or(lq.noneOf("\"\r\n").bind(x => stringTail(xs + x))); const stringLiteral = stringHead.and(stringTail(""));
実行はこんな感じ.
console.log(lq.parse(stringLiteral, "", "\"foobar\"")); // { success: true, value: "foobar" }
うまく動きました. 便利ですね〜.
JavaScript での問題点
さて, 次のような場合はどうでしょう.
const veryLongString = "\"" + "A".repeat(10000) + "\""; console.log(lq.parse(stringLiteral, "", veryLongString)); // RangeError: Maximum call stack size exceeded
はい. コールスタックが溢れて死にました.
一方 Parsec はどれだけ文字列を長くしても (たぶん) うまく動きます (出力が長くなるので結果は捨てている).
λ> let veryLongString = "\"" ++ replicate 10000 'A' ++ "\"" λ> parse stringLiteral "" veryLongString >> return "ok" Right "ok"
なぜ JavaScript では死んでしまうのかというと,
stringTail が stringTail を使って再帰的に定義にされているためです.
stringTail xs = (char '"' >> return (reverse xs)) <|> (noneOf "\"\r\n" >>= \x -> stringTail (x : xs))
const stringTail = xs => lq.char("\"").return(xs) .or(lq.noneOf("\"\r\n").bind(x => stringTail(xs + x)));
Haskell では末尾呼び出しの除去が行われて, かつ Parsec はそれがうまく行われるようパーサを定義しているので, コールスタックが溢れずに済むのですが, JavaScript は末尾呼び出しが除去されず *1, しかも loquat ではそれがうまく動くようにも定義していない*2ので, コールスタックが溢れてしまいます.
問題を整理するために以下のように書き換えます (stringTail → f).
e x = char '"' >> return (reverse x) s x = noneOf "\"\r\n" >>= \y -> y : x f x = e x <|> (s x >>= f)
このような f の形は, 文字列リテラルだけでなく, 他にも頻繁に登場するので,
一般的な話をするためにこの形の f について考えることにします.
問題は, このような再帰的定義を JavaScript で,
const f = x => e(x).or(s(x).bind(f));
と愚直に書くと, 繰り返しが多すぎた場合, コールスタックが増えすぎると死んでしまう, ということですね.
一応, 手作業で再帰的定義をループに書き換えてやることで解決できることもあり,
実際に many などのコンビネータの定義はそのようにやっています.
ただ, この書き換えにはパーサコンビネータの内部構造に関する知識が必要になる上に,
なによりとても面倒なので, 内部で使うのであればともかく,
簡単にパーサを書くためのライブラリのはずなのに簡単に書けない,
ということになってしまっていて大変不便です.
tailRecM
というわけで何か解決方法はないかと適当な単語で検索していたら, 以下のページを見つけました.
- 猫番 — 末尾再帰モナド (FlatMap)
- Stack Safety for Free (参照されている論文)
これは Scala のライブラリ Cats の話だけれど, 元は PureScript *3 で, コールスタックが溢れないように Free モナドを実装するにはどうしたら良いか, という話らしい.
以下では論文に倣って, 「コールスタックが溢れない (スタック消費が定数となる)」ことをスタック安全と呼ぶことにします.
あまり詳しくは読んでいないので適当なことを言っているかもしれませんが,
内容をかいつまんで紹介すると,
まず tailRecM を以下のように定義します.
tailRecM :: Monad m => (a -> m (Either a b)) -> a -> m b tailRecM f a = f a >>= go where go (Left a) = f a >>= go go (Right b) = return b
繰り返し処理 (再帰的定義) はこれを使うことで (おそらくある範囲内では) 実現できそうです.
この定義は一般の Monad のインスタンスに対するものですが, このままではスタック安全ではありません.
これを各 Monad のインスタンスに対してスタック安全な形で定義しなおしてやれば,
繰り返しや再帰を tailRecM を使うことでスタック安全に書くことができるようになります.
要するに, 上で書いた面倒な書き換えを tailRecM についてさえ行っておけば,
あとはそれを使って様々なことが出来るだろう, という話です.
(もっとも, PureScript や Scala は自己再帰であればコンパイラが最適化してくれるので,
手作業でループに書き直すほど面倒ではなさそう.
あなたはコンパイラですか?)
tailRecM を使ってみる
実際に tailRecM を使って, 上で見たような再帰的定義されたパーサを書き換えられるのかを考えてみます.
まずは元の定義はこれ.
f x = e x <|> (s x >>= f)
対称性が悪いのでまた定義を書き換えます.
e' x = Right <$> e x s' x = Left <$> s x f' (Left a) = (e' a >>= f') <|> (s' a >>= f') f' (Right b) = return b f x = f' (Left x)
さらに書き換えるために, Haskell/Alternative and MonadPlus - Wikibooks, open books for an open world にあるような分配法則が成り立つかどうかを考える必要があります.
(m >>= k) <|> (n >>= k) = (m <|> n) >>= k
これは MonadPlus 一般について成り立つわけではなく, さらに運の悪いことに,
今考えているパーサに対しては成り立ちません.
ところがほとんどの場合にはこれを使って書き換えることができます.
どういうことかというと, まず, パーサを実行すると得られる結果は 4 通り (入力を消費したか, パースが成功したかで 2 × 2 = 4) あります.
ここでは Parsec での関数名に従って cok, cerr, eok, eerr と呼ぶことにしましょう.
これらの結果の各組み合わせについて分配法則が成り立つかを確認してみると, 実は「m が eok になり得て, かつ k が返すパーサが eerr になり得る」場合のみ成り立ちません
*4.
今考えているのは m = e' a, k = f' なので, 分配法則が成り立たないのは e' a が eok で Left 値を返し得る場合のみです
*5.
この場合では e' a は常に Right 値を返すので問題ありませんし,
仮に e' a が Left 値を返しうる一般の場合についても, (よほど特殊な場合でない限りは) 入力を消費せずにパース処理が継続する, つまりパース処理が無限ループとなってしまうはずなので,
そもそも元のパーサの定義が正しくありません (無限にパースし続けたいのであれば別だけれど).
したがって, 正しく定義されているパーサについては, 分配法則が成り立つと言って良いでしょう.
というわけで分配法則を使って書き換えます.
f' (Left a) = (e' a <|> s' a) >>= f' f' (Right b) = return b
かなり tailRecM の定義にある go に近い形になりました.
実際, 以下の tailRecM の定義の f に (\x -> e' x <|> s' x) を代入すると go = f' となることがわかります.
tailRecM f a = f a >>= go where go (Left a) = f a >>= go go (Right b) = return b
さて, 元の f (tailRecM の引数ではない方) はどうなるでしょうか.
f x = f' (Left x)
先ほど書き換えた f' を代入して適用してみます.
f x = (e' x <|> s' x) >>= f'
おや, これは,
f a = (\x -> e' x <|> s' x) a >>= f'
と等価ですね.
もう一度 tailRecM の定義を見れば明らかなように,
結局 f は tailRecM を用いて以下のように書けます.
f = tailRecM (\x -> e' x <|> s' x)
めでたしめでたし.
JavaScript の話をしましょう
JavaScript の話をしているつもりだったんですけどねぇ……
というわけで loquat にも tailRecM を実装してみました.
Scalaz / Cats の tailRecM と同じ引数の順番の tailRecM(val, func) と,
カリー化されていて PureScript の tailRecM と同じ ftailRecM(func)(val) があります.
(なんでこんな命名になっているのかというと,
JS っぽい引数順で定義した map(parser, func) と,
オリジナルの fmap(func)(parser) が混在しているのに対応するようにしたため.)
const lq = require("loquat")(); const stringHead = lq.char("\"").void(); const stringTail = lq.ftailRecM(xs => lq.char("\"").return(xs).map(x => ({ done: true, value: x })) .or(lq.noneOf("\"\r\n").map(x => xs + x).map(x => ({ done: false, value: x }))) ); const stringLiteral = stringHead.and(stringTail("")); console.log(lq.parse(stringLiteral, "", "\"" + "A".repeat(10000) + "\"")); // { success: true, value: "AAA..." }
これだと少々煩雑なので以下のようなメソッド .done(), .cont() を定義しようかしらん.
const stringTail = lq.ftailRecM(xs => lq.char("\"").return(xs).done() .or(lq.noneOf("\"\r\n").map(x => xs + x).cont()) );
npm には今週末にでも publish します.
まとめ
というわけで JS でもいい感じに再帰的にパーサを書けるようになりました.
どんどんいい感じにしていっているので, 急に DSL が作りたくなったりした場合は是非お試しください. github.com
