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

型推論は間に合わなかったので違うお話を書きます。まあ今年のカレンダーでも10日目、12日目、16日目、20日目と型推論の情報はいっぱいあるのでいいよね？（？

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

レイアウト規則について

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

例

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が実装したコードなのでそっちを見てもらったほうが早いのですが、コメントが少なくてあまりにも読みにくいので簡単な解説をします。

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

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

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

ここでenum Leftmostを導入します。見てもらえばわかるとおり

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

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

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

1. まずinfix_exprをLeftmost::Nothingで呼び出したとします。最初はそのままprefix_exprに制御を渡し、prefix_exprもまたterm_exprに、term_exprもfactor_exprに制御をそのまま渡します。ここまでで以下のようになっています。
   

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に変換するものです(それ以外は通過)。例のセクションで示したとおり、先頭が同じインデントの場合は別の式として認識されてほしいので以降の解析では先頭以降のトークンのみ含めるようにしています。
   

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

最後に

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

---

1. HaskellライクなAltJSのひとつ http://www.purescript.org/ ↩

2. たとえばinfix_exprはほぼ先頭を含むけど、factor_exprは「a + bのような場合、aの解析では先頭を含むがbの解析では含まない」など呼び出し元に依存する ↩

3. Haskellではlet { a = 1; b = 2 } in a + bのように{}や;を使ってブロックを明示することができる ↩

4. https://www.haskell.org/onlinereport/haskell2010/haskellch10.html ↩

5. パーサにインデント規則を盛り込む今回の方法と違って、事前にインデントによって{}や;を挿入するモジュールを通す方法をとる ↩