Help us understand the problem. What is going on with this article?

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は内部仕様のドキュメントが整っているので、コードリーディングなどにおすすめです。

参考文献など

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away