レイアウト規則を独自実装してしまったお話

型推論は間に合わなかったので違うお話を書きます。まあ今年のカレンダーでも[10日目](http://fetburner.hatenablog.com/entry/2017/12/13/234953)、[12日目](https://qiita.com/h_sakurai/items/ef04224975a7506b2901)、[16日目](http://rhysd.hatenablog.com/entry/2017/12/16/002048)、[20日目](https://qiita.com/uint256_t/items/7d8c8feeffc03b388825)と型推論の情報はいっぱいあるのでいいよね？（？

というわけでちょっと変わった構文解析を実装した話です。
現在、シェーダ(GPUプログラム)をHaskellライクな構文でほぼ純粋に書けるようにする「PureShader(仮名)」を製作しているので、そこの実装を交えての記事となります。名前はまんまPureScript[^purescript]に乗っかった感じです。

## レイアウト規則について

Haskellの構文における特徴的なものとして**「インデントを重視する(レイアウト規則)」**というものがあります。これはHaskellに限ったものではなくて、Pythonなんかもインデントを構文のルールの一つとして取り入れているわけですが、Haskellの場合はPythonのそれに加えて式を複数行に分けることが可能なので少しだけ複雑になります。今回は後者を実装しました。

### 例

```haskell
main =
  if f 1 == True then do
    putStrLn $ "2"      -- *1
      ++ show 3         -- *2
     ++ show 4          -- *2
    putStrLn "---"      -- *1
 else putStrLn "false"  -- *2
```

`do`以降の２つの`putStrLn`(\*1の行)はインデントが揃っています。ここはPythonと同様です。
重要なのは式のインデント規則(\*2の行)で、ここも二行目以降は揃っている必要があるかと思えば、`if`より`else`のほうがインデントが浅かったり`++ show 3`より`++ show 4`のほうがインデントが浅かったりしています。両者に共通しているのは**式の先頭(`if``else`は`main =`、`++ show 3``++ show 4`は`putStrLn $ "2"`)のインデントよりはいずれも深い**ということです。

## 実装

[Pctg-x8/shading_descriptor:src/parser](https://github.com/Pctg-x8/shading_descriptor/tree/master/src/parser)が実装したコードなのでそっちを見てもらったほうが早いのですが、コメントが少なくてあまりにも読みにくいので簡単な解説をします。

基本方針は「あるインデントレベルより深ければ(つまり右側にあれば)連接するトークンとして消費する」です。

```
※検査の起点はトークンの左端です
putStr "hello, "  | "hello, "はputStrより右側なのでつながる
putStrLn $ "wo"
  ++ "rl"
 + "d"            | すべてputStrLnより右側にあるのでつながる
putStrLnはputStrより右側にないので繋がらない
```

再帰下降パーサの一種として実装しているため式や各種構文ルールをそれぞれ関数化しています。ルール内でレイアウトについて検査するとき「ルールの先頭だけ同一インデントを含めたり含めなかったりして、以降は含めない」という場合[^complex-rule]があるため、基準インデントレベルとして単純に`usize`を渡すだけでは役不足です。

ここで[`enum Leftmost`](https://github.com/Pctg-x8/shading_descriptor/blob/master/src/parser/utils.rs#L95)を導入します。見てもらえばわかるとおり

- `Nothing`(インデントなし、もしくは明示的なブロック[^exp-block]に入っている状態)
- `Inclusive(usize)`(インデント状態で、判定するときに同じインデントのトークンを**含める**。暗黙的なブロックの開始で使われることが多い(`do`の後ろとか))
- `Exclusive(usize)`(インデント状態で、判定するときに同じインデントのトークンは**含めない**)

という3状態を取るものです。トークンを検査する際に`Leftmost::satisfy`を使って対象トークンが要求されたインデント規則を満たしているかを検査します。

ステップバイステップで、式`f 2 + f 3`を例に解析してみます。

1. まず[`infix_expr`](https://github.com/Pctg-x8/shading_descriptor/blob/master/src/parser/expr.rs#L28)を`Leftmost::Nothing`で呼び出したとします。最初はそのまま[`prefix_expr`](https://github.com/Pctg-x8/shading_descriptor/blob/master/src/parser/expr.rs#L48)に制御を渡し、`prefix_expr`もまた[`term_expr`](https://github.com/Pctg-x8/shading_descriptor/blob/master/src/parser/expr.rs#L56)に、`term_expr`も[`factor_expr`](https://github.com/Pctg-x8/shading_descriptor/blob/master/src/parser/expr.rs#L85)に制御をそのまま渡します。ここまでで以下のようになっています。  
![pass.png](https://qiita-image-store.s3.amazonaws.com/0/94115/9997f48b-9950-dd57-b178-ad6320d53f36.png)

2. まず`leftmost.satisfy(stream.current(), true)`でチェックを行います。現在のトークンが要求インデントを満たさない場合に解析結果として「消費しなかった(`NotConsumed`)」を返します。第二引数の`true`は`Leftmost::Nothing`の場合に返却する値です。今回は`Leftmost::Nothing`なのでここのチェックは通過します。
3. `factor_expr`は式の中で最も基本的なものを解析するので、今回は一番目の`f`が消費されてシンボルとして返ります。
4. `term_expr`に戻って、次は`let leftmost = leftmost.into_nothing_as(Leftmost::Exclusive(lhs.position().column)).into_exclusive();`となります。
`Leftmost::into_nothing_as`は`Leftmost::Nothing`を指定のものに変換するものです。
`Leftmost::into_exclusive`は`Leftmost::Inclusive`を`Leftmost::Exclusive`に変換するものです(それ以外は通過)。例のセクションで示したとおり、先頭が同じインデントの場合は別の式として認識されてほしいので以降の解析では先頭以降のトークンのみ含めるようにしています。
![leftmost_intos.png](https://qiita-image-store.s3.amazonaws.com/0/94115/604ce39b-00d3-b2c7-be8f-e6b81c1c2c5d.png)

5. 以降、構文規則に沿って繰り返しです

## 最後に

別にこんなこと考えなくてもHaskellの構文はレイアウト規則も入れてすべて公開されている[^synrule]のでそれをそのまま実装すればできます。そこにあるレイアウト規則(トークン挿入規則)[^insertion]もそこまで難しくはないですが、ブロックを自動で閉じる際などで構文に依存する部分があってちょっとだけ面倒です。あとうちではトークナイザを`Iterator`として実装していた時期があって、挿入操作が面倒すぎてとりやめたというのもあります。

---

[^purescript]: HaskellライクなAltJSのひとつ http://www.purescript.org/
[^synrule]: https://www.haskell.org/onlinereport/haskell2010/haskellch10.html
[^insertion]: パーサにインデント規則を盛り込む今回の方法と違って、事前にインデントによって{}や;を挿入するモジュールを通す方法をとる
[^exp-block]: Haskellでは`let { a = 1; b = 2 } in a + b`のように{}や;を使ってブロックを明示することができる
[^complex-rule]: たとえば`infix_expr`はほぼ先頭を含むけど、`factor_expr`は「`a + b`のような場合、`a`の解析では先頭を含むが`b`の解析では含まない」など呼び出し元に依存する