[コンパイラ][Haskell][OCaml] Haskellのinfixの仕組み

OCamlでは ＜ や | で始まる中置演算子は左結合になるため、|> はO.K.ですが、<| 演算子をつなげたときにカッコが必要になってしまいます。

http://d.hatena.ne.jp/mzp/20090105#c1231290114

なんだそれと思ったが,ほんとだった。

  | ['=' '<' '>' '|' '&' '$'] symbolchar *
            { INFIXOP0(Lexing.lexeme lexbuf) }
(* 略 *)
  | ['*' '/' '%'] symbolchar *
            { INFIXOP3(Lexing.lexeme lexbuf) }

とレキサの中で先頭文字だけ('**'のみ2文字)を見て演算子の種別分けをしている。
なんでこんな設計になっているんだろうか。(手抜き? 高速化の為?)

ところで,演算子の結合性を指定できる言語にSMLやHaskellがある。例えばHaskellでは

infixr 5 <+>   -- 右結合性で優先順位は5

などと指定できる。しかし, yaccなどのコンパイラコンパイラには動的に定義される演算子を扱う方法がないので一体どうやっているのかが気になった。
そこでghcを読んでみたところ,以下のようになっていた。

1. パース時には全て同一の結合性(全部左結合)としてパースする
2. 型検査時のα変換(異なる値の変数には違う名前を割り振る)のフェーズで, 結合性をチェックして組み換える

組み替えは,(e1 op1 e2) op2 e3 となっている部分で op1とop2の結合性を比較して,必要ならe1 op1 (e2 op2 e3)に直すというようにする.

以下が組み替え処理の一部。

-- (e11 `op1` e12) `op2` e2
mkOpAppRn e1@(L _ (OpApp e11 op1 fix1 e12)) op2 fix2 e2
  | nofix_error = do
    addErr (precParseErr (ppr_op op1,fix1) (ppr_op op2,fix2))
    return (OpApp e1 op2 fix2 e2)

    -- op2の方が結合性が高い
  | associate_right = do
    -- 新しく組み直した e12 `op2` e2 の再組み替え
    new_e <- mkOpAppRn e12 op2 fix2 e2
    return (OpApp e11 op1 fix1 (L loc' new_e))
  where
    loc'= combineLocs e12 e2
                                           -- 結合性のチェック
    (nofix_error, associate_right) = compareFixity fix1 fix2

-- nofix_error = False, associate_right = Falseの時は何もしない

何か面白いことをやっているかと思ったら想像通りでおもしろくなかった。もっと工夫したやり方はないだろうか。

ところで,Haskellでは型検査が終わるまで構文木は正しくない状態という事になるけれども,これは一年以上放置していたなぜ型検査は脱糖の前か?という疑問の解答の一つになった。