Parsecのソースちら見

教科書的なパーサーと言えばStateT s []モナドをよく見るけど、今のParsecって全然そんな雰囲気ないんだなあ。
https://twitter.com/hiratara/status/297541496217927683

モナド本体は継続モナド×4的な構造をしている。継続となる関数を4本渡せば、結果を得ることができる。

Text-Parsec-Prim.html

newtype ParsecT s u m a
    = ParsecT {unParser :: forall b .
                 State s u
              -> (a -> State s u -> ParseError -> m b) -- consumed ok
              -> (ParseError -> m b)                   -- consumed err
              -> (a -> State s u -> ParseError -> m b) -- empty ok
              -> (ParseError -> m b)                   -- empty err
              -> m b
             }

起動用に用意されている関数では、最終的にどの継続を経由して結果を得たのかわかるようにラップをしている。ラップは各2項目×2段階。

Text-Parsec-Prim.html

runParsecT :: Monad m => ParsecT s u m a -> State s u -> m (Consumed (m (Reply s u a)))
runParsecT p s = unParser p s cok cerr eok eerr
    where cok a s' err = return . Consumed . return $ Ok a s' err
          cerr err = return . Consumed . return $ Error err
          eok a s' err = return . Empty . return $ Ok a s' err
          eerr err = return . Empty . return $ Error err

ラップの1段階目。パーサが入力を消費したか否か。

Text-Parsec-Prim.html

data Consumed a  = Consumed a
                 | Empty !a

ラップの2段階目。パースが成功したか否か。これで2*2=4通りのパターンを表せた。

Text-Parsec-Prim.html

data Reply s u a = Ok a !(State s u) ParseError
                 | Error ParseError

逆にこのラップされた型からParsecT型を復元する関数も定義されている。ラップされた型を展開して、4つ渡された継続のどれをキックするか判別するだけ。

Text-Parsec-Prim.html

mkPT :: Monad m => (State s u -> m (Consumed (m (Reply s u a)))) -> ParsecT s u m a
mkPT k = ParsecT $ \s cok cerr eok eerr -> do
           cons <- k s
           case cons of
             Consumed mrep -> do
                       rep <- mrep
                       case rep of
                         Ok x s' err -> cok x s' err
                         Error err -> cerr err
             Empty mrep -> do
                       rep <- mrep
                       case rep of
                         Ok x s' err -> eok x s' err
                         Error err -> eerr err