chainl の正体

山本さんの「chainl と左再帰」( d:id:kazu-yamamoto:20110127:1296098875 )を読んでいて(ほんの)少々混乱したのと、Parsec の chainl は、結局どうやって使ったらいいのよ、というのを簡単にまとめておく。背景説明はどうでもいい人は最後のサンプルまで飛ばしてくれてよい。

用語1: 「左再帰の文法」とは

その意味を反映した構文木で表現した場合に、左側の枝のほうが深くなる再帰になる文法を「左再帰の文法」と言う。
たとえば普通の算術の式 "12 - 3 + 45 - 6" は、"((12 - 3) + 45) - 6" という意味なので、左再帰の文法を持っている。

用語2: 「左再帰の除去」とは

再帰の文法を、ナイーブに文脈自由文法の BNF で表現すると、<expr> = <expr> ('+'|'-') <num> | <num> のように、右辺の先頭に自分自身が現れる。これをやはりナイーブに再帰下降パーサに実装すると、評価(実行)が無限再帰(無限ループ)に陥るものになってしまう。これのワークアラウンドを「左再帰の除去」と呼んでいるが、それが具体的に指すものは一定していないようである。(なお、ここで例として示した構文定義には、トークンを一つ先読みしただけではどちらの展開をすべきかわからないので、左再帰と同様にLL(1)パーサにできない、という問題もあるが、そちらの対策は「左くくりだし」という本質的には似ているが、別のものとして分類されている変換であることに注意すること。)

再帰の除去1: 左再帰の無い再帰的定義への変換

教科書的には、こちらが「左再帰の除去」とされていることが多い(と思う)。
\[A = A\alpha | \beta\]
というような規則を、
\begin{eqnarray}
A = \beta A^{\prime} \\
A^{\prime} = \epsilon \ | \alpha A^{\prime}
\end{eqnarray}
のように変換する(詳細はここでは略す)。
ここでひとつ注意が必要なのは、この変換によって文法が「右再帰の文法」に変換されてしまっていることである。つまり、「言語」の外部定義すなわち「構文規則が(受け入れる|生成する)終端記号列」としては等価な変換だと言えるが、「言語」の内部定義として「構文規則によって作られる構文木」というものを考えるならば、違うものに変換されてしまっているわけである。

再帰の除去2: ループへの変換

実用的には、こちらのほうが重要なことが多い。なぜなら手続き型のルーチンではループは自然なものであるし、実際 Haskell(Parsec)でも do 記法内での再帰によるループを使ってこちらの形で書ける。
BNF でループを表現するには、拡張 BNF であれば * を使って書ける。前述の算術の式は、次のどちらかになる。
<expr> = (<num> ('+'|'-'))* <num>
<expr> = <num> (('+'|'-') <num>)*

chainl の正体

以下に、chainl と chainl1 の型を並べてみる。

  • chainl :: Parser a -> Parser (a -> a -> a) -> a -> Parser a
  • chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a

(chainr と chainr1 も同様)
~1 の付いているほうがわかりやすいが、fold の型を持ち上げたような(順序とかちょっと違うが)型であることが見てとれると思う。

  • foldl :: (a -> b -> a) -> a -> [b] -> a
  • foldl1 :: (a -> a -> a) -> [a] -> a

ここで foldl1 と foldr1 を使って ((1-2)-3)-4 と 1-(2-(3-4)) を計算してみよう。

> foldl1 (-) [1, 2, 3, 4] :: Int
-8
> foldr1 (-) [1, 2, 3, 4] :: Int
-2

このように foldl1 と foldr1 は、リストの要素の間に、第1引数の演算子を左結合で入れたり、右結合で入れたりする演算子だと見ることができる。
これと、その型から連想するならば chainl1 は、第1引数にリスト的な構文で要素になるもののパーサを、第2引数に演算子を消化して二分木を合成する関数を返すパーサを渡してやることにより、「左再帰の文法のパーサ」を返すコンビネータだとわかる。具体例として簡単だが動作するサンプルを示す。

実行例:

Prelude> :l sample.lhs
*Main> run "1+2+3+4"
((NumI 1 :+ NumI 2) :+ NumI 3) :+ NumI 4

(コメント内は chainl1 と同等のものを、chainl1 を使わず直接書きくだしたもの)
以上のように chainl(chainl1)は、左再帰ユースケースのほとんどの場合である、算術式のようなパターンについて、無限ループになったりすることのない左再帰のパーサ、を簡単に作れるようになっているものである、と言える。

余談

ウィキペディアには、文法の左再帰性を保ったまま変換する方法があるかのような感じで書かれているが、文献で読んだ記憶がない&ちょっと検索したぐらいでは出てこない。(意味規則を含んだ定義を、意味を壊さないように意味規則ごと変換するという手法は論文が見つかる。日本語版の編集者の問題ではなく、英語版に書かれていたものが引き継がれている*1

余談2

こうして考えてみると、Yacc で \left や \right のように記述して演算子の結合性を指定できるのは、複数の規則にまたがって再帰的定義をして煩雑になったり、ループを指定する構文を作って意味アクションの指定をややこしくしたりすることなく、シンプルな定義だけでたいていのユースケースをカバーする、うまい設計だということがわかる。

*1:なお、要出典タグを付けたのは私である。