Edited at
HaskellDay 6

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

More than 1 year has passed since last update.

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) }


最後から二行目で呼ばれているmkOpAppRncompiler/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は内部仕様のドキュメントが整っているので、コードリーディングなどにおすすめです。


参考文献など