elm/parserのbacktrackableを理解する

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

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

## backtrackable とは

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

![P_20180422_163624_vHDR_Auto.jpg](https://qiita-image-store.s3.amazonaws.com/0/16345/7124c8ac-506b-7dd2-e900-5fd36966fca7.jpeg)


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

```elm
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処理:

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

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

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

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

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

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

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

```elm
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できます。

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

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

```elm
backtrackable : Parser a -> Parser a
```

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

![P_20171223_154607_vHDR_Auto.jpg](https://qiita-image-store.s3.amazonaws.com/0/16345/8380589f-e2ab-4cdf-54e7-868f4e4ce22f.jpeg)

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

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

```elm
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` 関数をつかって

```elm
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` を使って以下のように定義されています。

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

```elm
(|.) 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` 関数を使う前の最初の例を見てみましょう。

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

これに `" ]"` を渡してみます。[^1]

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

```elm
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` を適用したものに `" ]"` を渡してみましょう。

```elm
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 のドキュメント](https://package.elm-lang.org/packages/elm/parser/latest/) には各関数の backtrackability が明記されていません。
これでは [backtrackable についてのドキュメント](https://github.com/elm/parser/blob/master/semantics.md)で紹介されていない関数の backtrackability がまるでわかりません...

そこで便利なのが [arowM/elm-parser-test](https://package.elm-lang.org/packages/arowM/elm-parser-test/latest/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` を使わなくても同等の処理を書くことができます。

```elm
-- 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 についてのドキュメント](https://github.com/elm/parser/blob/master/semantics.md)ではここまでで主張が終わっていますが、
逆に速度を気にしない場合は `backtrackable` を積極的に使ったほうが再利用性などの面で便利なのも事実です。

```elm
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 を作りましょう！


[さくらちゃんにご飯をあげる](https://www.amazon.co.jp/gp/registry/wishlist/20ZV2VC57615B/ref=nav_wishlist_lists_1)
[さくらちゃんをもっと見る](https://twitter.com/hashtag/%E3%81%95%E3%81%8F%E3%82%89%E3%81%A1%E3%82%83%E3%82%93%E6%97%A5%E8%A8%98?src=hash)
[他の記事を見る](https://qiita.com/arowM)
![DqQLSiUWsAMG9uw.jpg:large.jpeg](https://qiita-image-store.s3.amazonaws.com/0/16345/4382f943-2931-c322-13be-b401361bd5ed.jpeg)