GHCでの中置演算子のパース

Haskellでは、中置演算子を自由に定義することができ、多くの中置演算子を活用してプログラムを書きます。

module Main where

(<=>) :: Ord a => a -> a -> Ordering
a <=> b = compare a b

abs' :: Int -> Int
abs' x = case x <=> 0 of
           LT -> -x
           _  -> x

answer :: Double
answer = 2 + 4 * 2 * 10 / 2

main :: IO ()
main = do
  print . abs' . read =<< getLine
  print answer
-- このmainはすこしやりすぎ

GHCは、すべての中置演算子を左結合と仮定して構文解析を行います。
その後、Renamerと呼ばれる層でinfix宣言に基づいた構文木の書き換えを行うことで、構文解析器の魔境化を防いでいます。
この処理について、一連の流れをまとめました。

構文解析

-ddump-parsedオプションを付けてコンパイルすると、以下のような出力を得られます。

==================== Parser ====================
module Main where
(<=>) :: Ord a => a -> a -> Ordering
a <=> b = compare a b
abs' :: Int -> Int
abs' x
  = case x <=> 0 of {
      LT -> - x
      _ -> x }
answer :: Double
answer = 2 + 4 * 2 * 10 / 2
main :: IO ()
main
  = do { print . abs' . read =<< getLine;
         print answer }

この出力からは中置演算子を含む式がどのようなASTになっているかがわかりませんが、
https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/Parser によると、

Infix operators are parsed as if they were all left-associative. The renamer uses the fixity declarations to re-associate the syntax tree.

実際にcompiler/parser/Parser.yを見てみると、

infixexp :: { LHsExpr GhcPs }
        : exp10 { $1 }
        | infixexp qop exp10  {% ams (sLL $1 $> (OpApp $1 $2 placeHolderFixity $3))
                                     [mj AnnVal $2] }

となっており、たしかに頭から左結合でASTを構築しているようです。

Renamer

-ddump-rnオプションを付けてコンパイルすると、以下の出力が得られます。

==================== Renamer ====================
(Main.<=>) :: Ord a_aRh => a_aRh -> a_aRh -> Ordering
a_a1S3 Main.<=> b_a1S4 = compare a_a1S3 b_a1S4
Main.abs' :: Int -> Int
Main.abs' x_a1S5
  = case x_a1S5 Main.<=> 0 of
      LT -> - x_a1S5
      _ -> x_a1S5
Main.answer :: Double
Main.answer = 2 + 4 * 2 * 10 / 2
Main.main :: IO ()
Main.main
  = do print . Main.abs' . read =<< getLine
       print Main.answer

見ての通り、renamerは識別子がどのモジュールに属すのかを解決し、ローカル変数にユニークな名前を付け直します。

この他にも、renamerは次のような処理を行います。

中置演算子を含む式のASTを正しい形へ組み替え
相互再帰関数の識別
スコープ外参照、未使用の宣言、未使用のimport、重複したパターンの検出

-ddump-rn-traceオプションで挙動を確認すると、

...
addUsedGRE
  + parent:Num
    imported from ‘Prelude’ at Main.hs:1:8-11
    (and originally defined in ‘GHC.Num’)
lookupFixityRn_either:
  looking up name in iface and found: +
                                      infixl 6
addUsedGRE
  * parent:Num
    imported from ‘Prelude’ at Main.hs:1:8-11
    (and originally defined in ‘GHC.Num’)
lookupFixityRn_either:
  looking up name in iface and found: *
                                      infixl 7
addUsedGRE
  * parent:Num
    imported from ‘Prelude’ at Main.hs:1:8-11
    (and originally defined in ‘GHC.Num’)
lookupFixityRn_either:
  looking up name in iface and found: *
                                      infixl 7
addUsedGRE
  / parent:Fractional
    imported from ‘Prelude’ at Main.hs:1:8-11
    (and originally defined in ‘GHC.Real’)
lookupFixityRn_either:
  looking up name in iface and found: /
                                      infixl 7
...

確かに優先順位を検索しているようです。

実際にrenamerの処理の本体であるRnExpr.rnExprのソース(compiler/rename/RnExpr.hs)を見てみると、

rnExpr (OpApp e1 op  _ e2)
  = do  { (e1', fv_e1) <- rnLExpr e1
        ; (e2', fv_e2) <- rnLExpr e2
        ; (op', fv_op) <- rnLExpr op

        -- Deal with fixity
        -- When renaming code synthesised from "deriving" declarations
        -- we used to avoid fixity stuff, but we can't easily tell any
        -- more, so I've removed the test.  Adding HsPars in TcGenDeriv
        -- should prevent bad things happening.
        ; fixity <- case op' of
              L _ (HsVar (L _ n)) -> lookupFixityRn n
              L _ (HsRecFld f)    -> lookupFieldFixityRn f
              _ -> return (Fixity NoSourceText minPrecedence InfixL)
                   -- c.f. lookupFixity for unbound

        ; final_e <- mkOpAppRn e1' op' fixity e2'
        ; return (final_e, fv_e1 `plusFV` fv_op `plusFV` fv_e2) }

最後から二行目で呼ばれているmkOpAppRnはcompiler/rename/RnTypes.hsに存在します。

mkOpAppRn :: LHsExpr GhcRn             -- Left operand; already rearranged
          -> LHsExpr GhcRn -> Fixity   -- Operator and fixity
          -> LHsExpr GhcRn             -- Right operand (not an OpApp, but might
                                       -- be a NegApp)
          -> RnM (HsExpr GhcRn)

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

  | associate_right = do
    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

---------------------------
--      (- neg_arg) `op` e2
mkOpAppRn e1@(L _ (NegApp neg_arg neg_name)) op2 fix2 e2
  | nofix_error
  = do precParseErr (NegateOp,negateFixity) (get_op op2,fix2)
       return (OpApp e1 op2 fix2 e2)

  | associate_right
  = do new_e <- mkOpAppRn neg_arg op2 fix2 e2
       return (NegApp (L loc' new_e) neg_name)
  where
    loc' = combineLocs neg_arg e2
    (nofix_error, associate_right) = compareFixity negateFixity fix2

---------------------------
--      e1 `op` - neg_arg
mkOpAppRn e1 op1 fix1 e2@(L _ (NegApp _ _))     -- NegApp can occur on the right
  | not associate_right                 -- We *want* right association
  = do precParseErr (get_op op1, fix1) (NegateOp, negateFixity)
       return (OpApp e1 op1 fix1 e2)
  where
    (_, associate_right) = compareFixity fix1 negateFixity

---------------------------
--      Default case
mkOpAppRn e1 op fix e2                  -- Default case, no rearrangment
  = ASSERT2( right_op_ok fix (unLoc e2),
             ppr e1 $$ text "---" $$ ppr op $$ text "---" $$ ppr fix $$ text "---" $$ ppr e2
    )
    return (OpApp e1 op fix e2)

なんだか単項の-演算子の処理に少し涙ぐましい努力が見られますが、ここで中置演算子を含む式のASTの変換が行われているのがわかります。

まとめ

GHCにおける中置演算子の処理についてまとめました。
GHCは内部仕様のドキュメントが整っているので、コードリーディングなどにおすすめです。

参考文献など

The GHC Commentary
- Compiling one module: HscMain コンパイルパスの俯瞰
- The Parser 構文解析器とGHCのフロントエンドにおける戦略
- The renamer 名前解決を含むもろもろの意味検査
GHCのソースコード(Githubのミラー)
Haskell GHC開発に関する情報源いろいろ