elm/parserのbacktrackableを理解する

Elm0.19になって、Elm0.18時代の elm-tools/parser も elm/parserとして新しく生まれ変わりました。
基本文法は Elm0.18時代 とほぼ同じなので、去年@jinjorさんが書いた Elm0.18の elm-tools/parser に関する記事の「基本文法」までを読めば理解できますが、Elm0.19から新たに加わった変更がいくつかあります。

そんな変更の1つ "backtrackable" は、elm/parser からリンクが貼られているドキュメントに説明がありますが、あまり親切とは言えません。
そこでこの記事ではより詳しく「そもそも backtrackable とはなにか」「どうやったらうまく使えるか」などをまとめました。

backtrackable とは

ざっくり説明すると「ひとかたまりのParse処理において、途中でParse処理が失敗した際に、文字列の最初に戻って別のParse処理をやり直せるかどうか」が backtrackable の意味するところです。

以下のparserを見てください。

parser : Parser (Maybe Int)
parser =
  oneOf
    [ succeed Just
        |. spaces
        |. symbol ","
        |. spaces
        |= int
    , succeed Nothing
        |. spaces
        |. symbol "]"
    ]

2つの「ひとかたまりのParse処理」が oneOf の引数としてリストで渡されています。

• 最初の succeed Just から始まる処理が成功したらその結果を返し
• それが失敗したら次の succeed Nothing から始まる処理を試す

ように見える Parserです。
(後で述べますが、残念ながら実際にはその意図どおりにはなっていません)

さて、この Parser に対して、" , 4" を渡したらどうなるでしょうか？
1つ目のParse処理:

succeed Just
    -- スペースが0個以上あって
    |. spaces
    -- その後 "," があって
    |. symbol ","
    -- スペースが0個以上あって
    |. spaces
    -- 数字がある
    |= int

に合致するため、int の部分が抜き出されて Just 4 を得ることができます。

では、" ]" を渡したらどうでしょうか？
1つ目のParse処理には合致しませんが、2つ目のParse処理:

succeed Nothing
    -- スペースが0個以上あって
    |. spaces
    -- その後 "]" がある
    |. symbol "]"

に合致しています。
では、このパターンが処理されて Nothing を得ることができるのでしょうか？

いえ、残念ながらそうはなりません

実際に " ]" がどのように処理されるか上から順に見ていきましょう。

oneOf
  [ succeed Just
      -- まずスペースがあるから残りは "]" だな？
      |. spaces
      -- おおっと！ ここで "," を期待されても、今残っているのは "]" だからこの Parse処理は失敗だ！
      |. symbol ","
      |. spaces
      |= int
  -- お、Parse処理失敗したの？ 特に何も言われてないからこれでParse処理は終わりにするね！
  -- じゃあね〜👋
  , succeed Nothing
      |. spaces
      |. symbol "]"
  ]

ということで、 Nothing を得られずに Parsing が失敗してしまうのです...

実はParse処理の「失敗」には2種類あり、"backtrackable" な失敗のときにしか oneOf は次の候補のParserを試してくれないのです！
「失敗」を "backtrackable" にするための関数がずばり backtrackable です。

実は上記の parser を以下のように書き換えると、目的通り " ]" を Nothing としてParseできます。

oneOf
  [ succeed Just
      -- |. spaces
      |. backtrackable spaces
      |. symbol ","
      |. spaces
      |= int
  , succeed Nothing
      |. spaces
      |. symbol "]"
  ]

spaces というParserに対して backtrackable という関数

backtrackable : Parser a -> Parser a

を適用することで、処理結果が backtrackable になるParserに変身させているだけですね！

elm/parser の backtrackable についてもう少しくわしく

backtrackable の「ふんいき」はわかりましたが、まだこれだけの情報では使いこなせる気がしません...
先ほどの例も、なぜ spaces だけに backtrackable を付けたらうまくいくのかがわかりません。

oneOf
  [ succeed Just
      |. backtrackable spaces
      |. symbol ","
      |. spaces
      |= int
  , succeed Nothing
      |. spaces
      |. symbol "]"
  ]

symbol "," のところで失敗するんだから、symbol "," にも backtrackable をつけないとうまくいかないのでは？
そんな疑問を解消するために、ここでは以下のような新しい記法を導入してより詳しく説明していきます。

OK{true}
OK{false}
ERR{true}
ERR{false}

これは、何らかの文字列に対してParserを適用した結果を示しています。

• OK/ERR はそのParse処理が成功したか/失敗したか
• {true}/{false} は backtrackableか/そうではないか (backtrackability)

たとえば特定のキーワードが対象の文字列に含まれるかどうかをチェックするParserを作る keyword 関数をつかって

keyword : String -> Parser ()

keyword "import" というParserを作ると、その結果は以下のようになります。

対象文字列	結果
"import"	OK{false}
"imp"	ERR{true}
"export"	ERR{true}

どうやら keyword 関数は最初から「Parse処理に失敗したら backtrackable にする」という仕様になっているようです。

symbol の backtrackability

では、先ほどの oneOf の例で使われていた symbol の挙動を見てみましょう。
symbol "," に様々な文字列を渡した結果が以下です。

対象文字列	結果
","	OK{false}
",."	OK{false}
"."	ERR{true}

このように、失敗したときにのみ backtrackable になる仕様のようです。

spaces の backtrackability

次に、同じく oneOf の例で使われていた spaces の挙動を見てみます。

対象文字列	結果
",."	OK{true}
""	OK{true}
" "	OK{false}
" ,."	OK{false}

spaces は「0個以上の空白文字」のためのParserなので、常に成功します。
ただし

• 空白文字が対象文字列の最初に1つも含まれていない時は backtrackable
• 1つ以上含まれている時は backtrackable ではない

という仕様になっているようです。

succeed の backtrackability

succeed a の結果は常に OK{true} になります。

map2 の backtrackability

次に、|. や |= の backtrackability を調べたいのですが、実はこれらは map2 を使って以下のように定義されています。

map2 : (a -> b -> c) -> Parser a -> Parser b -> Parser c

(|.) a b = map2 (\keep ignore -> keep) a b
(|=) a b = map2 (\func arg -> func arg) a b

そのため、map2 の backtrackability を調べることで |. や |= の backtrackability も知ることができます。

map2 func parserA parserB の結果は以下のようになります。

parserA の結果	parserB の結果	map2 func parserA parserB の結果
OK{b}	OK{b'}	OK{b && b'}
OK{b}	ERR{b'}	ERR{b && b'}
ERR{b}	(処理されない)	ERR{b}

先ほどの説明の通り、|. や |= の定義にも map2 が使われているため、
parserA |. parserB や parserA |= parserB の場合もこの表と同じ結果になります。

先行する Parser (parserA) が失敗した場合、後続のParser は実行されずに先行する Parser の結果の backtrackability がそのまま採用されます。
それ以外の場合、両者のうちどちらか1つでも backtrackable でなければ、結果も backtrackable ではなくなってしまいます。

backtrackable

最後に backtrackable parser の結果は次のようになります。

parserの結果	結果
OK{b}	OK{true}
ERR{b}	ERR{true}

つまり、Parse処理の成功/失敗の結果はそのままに、常に backtrackable な結果に強制的に書き換えてしまいます。

あらためて例を見てみよう！

これで先ほどの例を理解するための材料がそろいました。
まずは backtrackable 関数を使う前の最初の例を見てみましょう。

succeed Just
  |. spaces
  |. symbol ","
  |. spaces
  |= int

これに " ]" を渡してみます。¹

succeed Just -- `succeed` だから無条件に OK{true}
  |. spaces -- 最初に空白があるから OK{false} / 対象文字列の残りは "]"

  -- OK{true} と OK{false} を `|.` で結合しているので OK{true && false} => OK{false}

  |. symbol "," -- 対象文字列の残りは "]" なので ERR{true}

  -- OK{false} と ERR{true} で ERR{false && true } => ERR{false}

  -- ERRになったのでこれ以降は処理されず、全体の結果は ERR{false}

  |. spaces
  |= int

このように、処理結果が ERR{false} で backtrackable ではないため、oneOf はここで処理を止めてしまいます。

次に、最初の spaces に backtrackable を適用したものに " ]" を渡してみましょう。

succeed Just -- `succeed` だから無条件に OK{true}
  |. backtrackable spaces -- 最初に空白があるから OK{false} だが、`backtrackable` が付いているので
                          -- OK{true} / 対象文字列の残りは "]"

  -- OK{true} と OK{true} を `|.` で結合しているので OK{true && true} => OK{true}

  |. symbol "," -- 対象文字列の残りは "]" なので ERR{true}

  -- OK{true} と ERR{true} で ERR{true && true } => ERR{ture}

  -- ERRになったのでこれ以降は処理されず、全体の結果は ERR{true}

  |. spaces
  |= int

このように ERR{true} となり、今度は backtrackable なので、oneOf がもとの対象文字列 " ]" に対して次の処理も試してくれます。

backtrackability の調べ方

さて、backtrackable の挙動について一通り見てきましたが、残念ながら elm/parser のドキュメント には各関数の backtrackability が明記されていません。
これでは backtrackable についてのドキュメントで紹介されていない関数の backtrackability がまるでわかりません...

そこで便利なのが arowM/elm-parser-test です。
elm repl で以下のように使うことで backtrackability を検査できます。

> import Parser.Test
> import Parser exposing (..)
> Parser.Test.run (keyword "import") "import"
(Ok (),False) : ( Result (List DeadEnd) (), Bool )
> Parser.Test.run (keyword "import") "imported"
(Err [{ col = 1, problem = ExpectingKeyword "import", row = 1 }],True)

Parser.Test.run の結果が以下のように backtrackability を示しています。

(OK ..., False)   <=> OK{false}
(OK ..., True)    <=> OK{true}
(Err ..., False)  <=> ERR{false}
(Err ..., True)   <=> ERR{true}

自分で作った parser のテストを書く際にも、このライブラリを使うことで想定どおりの backtrackability になっているかを簡単に確認できます。

backtrackable のつかいどころ

実はこれまであつかってきた例は backtrackable を使わなくても同等の処理を書くことができます。

-- backtrackable を使った書き方
parser : Parser (Maybe Int)
parser =
  oneOf
    [ succeed Just
        |. backtrackable spaces
        |. symbol ","
        |. spaces
        |= int
    , succeed Nothing
        |. spaces
        |. symbol "]"
    ]


-- backtrackable を使わない書き方
parser : Parser (Maybe Int)
parser =
  succeed identity
    |. spaces
    |= oneOf
        [ succeed Just
            |. symbol ","
            |. spaces
            |= int
        , succeed Nothing
            |. symbol "]"
        ]

backtrackable 関数を使うとParse処理の速度が低下してしまうため、速度を気にする場合はできるだけこのように工夫して backtrackable の使用を避けたほうが良いでしょう。

backtrackable についてのドキュメントではここまでで主張が終わっていますが、
逆に速度を気にしない場合は backtrackable を積極的に使ったほうが再利用性などの面で便利なのも事実です。

parser : Parser (Maybe Int)
parser =
  oneOf
    [ map Just parserA
    , map (\_ -> Nothing) parserB
    ]

parserA : Parser Int
parserA =
  succeed identity
      |. backtrackable spaces
      |. symbol ","
      |. backtrackable spaces
      |= int

parserB : Parser ()
parserB =
  succeed ()
      |. backtrackable spaces
      |. symbol "]"

backtrackable をうまく使って（あるいはあえて使わないようにして）思い通りの Parser を作りましょう！

さくらちゃんにご飯をあげる
さくらちゃんをもっと見る
他の記事を見る

1. 実際には |. と |= の結合順を考えるともっと複雑になりますが、基本的には上から評価していけば問題ないです。沼に足を踏み入れたいひとは結合順を考えてなぜ上からの評価でいいのかを考えてみてください。 ↩