January 2022 – wp.drmn.jp

『コンピュータシステムの理論と実装』に取り組むなかで、Jack という高級言語のコンパイラを Haskell で書いた。該当する章は 10 章と 11 章。このなかで、自分で作ったモナドをあとから mtl スタイルのトランスフォーマーに書き換えるという作業を行った。おかげでモナドおよびトランスフォーマーのイメージを少しつかむことができた気がする。

Parser モナド

まず 10 章で構文解析を行い、次の 11 章でコード生成という流れでプログラムを作成した。10 章では純粋に Jack の構文を解析するために、以下のような構成になった。

トークナイザ (10 章のメイン)
- ソースをパースしてトークンのリストを作る
- tokenize :: Text -> [Token]
- (パーサには attoparsec を使った)
パーサ
- トークンのリストをパースしてその階層構造をダンプする
- parse :: [Token] -> Text

本からのサンプルそのままだけど、以下のような入力が与えられたとき:

class Bar {
  method Fraction foo(int y) {
      var int temp; // a variable
  }
}

以下のような XML を出力するのが 10 章の内容。

<class>
  <keyword>class</keyword>
  <identifier>Bar</identifier>
  <symbol>{</symbol>
  <subroutineDec>
    <keyword>method</keyword>
    <identifier>Fraction</identifier>
    <identifier>foo</identifier>
    <symbol>(</symbol>
    <parameterList>
      <keyword>int</keyword>
      <identifier>y</identifier>
    </parameterList>
    <symbol>)</symbol>
    <subroutineBody>
      <symbol>{</symbol>
      <varDec>
        <keyword>var</keyword>
        <keyword>int</keyword>
        <identifier>temp</identifier>
        <symbol>;</symbol>
      </varDec>
...

ここで 2 番目のパーサ、[Token] をパースするために使えるパーサライブラリが見つからなかったので自分で作ることにした。おそらく自分のレベルだと、適当なライブラリが見つからなかったというのは以下のいずれかを示しているのだと思う。

探し方が悪い
ライブラリは目の前にあるけれどそれが適用可能であることを理解していない
リストをパースするというアプローチが悪い

とはいえ、自分で作ることは理解の最高の方法であるということで、今回はパーサ作りに挑戦した。自分で作ると言っても山本氏のブログ記事 (https://kazu-yamamoto.hatenablog.jp/entry/20080920/1221881130) を写しただけのものである。

import           Control.Applicative

newtype Parser s a = Parser { parse :: [s] -> [(a, [s])] }

item :: Parser s s
item = Parser $ \ss -> case ss of
                           []      -> []
                           (s:ss') -> [(s, ss')]

instance Functor (Parser s) where
    -- fmap :: (a -> b) -> f a -> f b
    fmap f p = Parser $ \ss -> [(f a, ss') |  (a, ss') <- parse p ss ]

instance Applicative (Parser s) where
    -- pure :: a -> f a
    pure a = Parser $ \ss -> [(a, ss)]
    -- (<*>) :: f (a -> b) -> f a -> f b
    f <*> p = Parser $ \ss ->
        [ (f' a, ss'') | (f', ss') <- parse f ss
                       , (a, ss'') <- parse p ss'
        ]

instance Monad (Parser s) where
    -- (>>=) :: forall a b. m a -> (a -> m b) -> m b
    p >>= q = Parser $ \ss ->
        concat [parse (q a) ss' | (a, ss') <- parse p ss]

これと Alternative の実装くらいで 10 章のパーサに必要な機能は実装することができた。余談だけど、これを自分で書くことでようやくモナドのイメージをつかむことができた気がする。あと「リストは非決定性計算を表す」というのも。

Parser モナドのトランスフォーマー化

ここからが本題。11 章ではコードを生成するにあたり、パーサに追加の機能が必要になってくる。たとえば以下のようなもの。

宣言された変数を記録するシンボルテーブルを持つ
一意のラベル名を生成するためのカウンタを持つ
パース中のクラス名 (= ソースファイル名) を使う

これはもう明らかに State だ Reader だ、となるのだけれど、この Parser はすでにモナドだから合成しないといけない。ということでこちらもよくわかってなかったトランスフォーマー化に取り組んだ。実際に取り組んだときには主に StateT の実装を参考にした: https://hackage.haskell.org/package/transformers-0.6.0.2/docs/src/Control.Monad.Trans.State.Strict.html

まずはトランスフォーマー対応版として ParserT を定義する。

newtype ParserT s m a = ParserT { parseT :: [s] -> m [(a, [s])] }

意味合いとしては前の Parser のと違いはもちろん m の部分で、「ある他のモナド m の文脈において使用可能な Parser」ということになると思う。ParserT におけるアクションは、型が示すとおりに m [(a, [s])] を返す関数を ParserT で包んでやれば良いはず。以下はリストの最初の要素を取る item の実装。

item :: (Applicative m) => ParserT s m s
item = ParserT $ \ss -> case ss of
                            []      -> pure []
                            (s:ss') -> pure [(s, ss')]

ParserT の中で使用している pure は m としての pure である。

これをモナドにしていく。まずは Functor のインスタンス実装。

instance (Functor m) => Functor (ParserT s m) where
    -- fmap :: (a -> b) -> f a -> f b
    fmap f m = ParserT $ \ss ->
        fmap (map (\(a, ss') -> (f a, ss'))) $ parseT m ss

さて、これを書いたは良いものの意味はまったくわかっていなかった。そもそもどうしてこのコードに辿りついたかというと、StateT からの類推である。StateT では Functor インスタンスが以下のように実装されている。

instance (Functor m) => Functor (StateT s m) where
    fmap f m = StateT $ \ s ->
        fmap (\ (a, s') -> (f a, s')) $ runStateT m s

runStateT m s は m (a, s), parseT m ss は m [(a, [s])] であるから、fmap に渡している関数を map すれば型が合うだろう……と試したところ、コンパイラの型チェックが通った。実装しているときは何がなんだかわからないまま次に進んだ。

今振り返ってみるとわかってきた気がする。まず少し書き方を変えて見やすくする。

fmap の型注釈に出てくる f は ParserT s m のこと。なので型宣言をより具体的に書くと (a -> b) -> ParserT s m a -> ParserT s m b. もしくは (a -> b) -> ([s] -> m [(a, [s])]) -> [s] -> m [(b, [s])]
引数の m の型は ParserT s m a. 注釈の型とまぎらわしいので p に変える

instance (Functor m) => Functor (ParserT s m) where
    -- fmap :: (a -> b) -> ParserT s m a -> ParserT s m b
    fmap f p = ParserT $ \ss ->
        fmap (map (\(a, ss') -> (f a, ss'))) $ parseT p ss

少しわかりやすくなった気がする。結局のところやろうとしていたことは以前の Parser モナドと同じで、p を適用して出てきた結果の [(a, ss')] を [(f a, ss')] にしようとしている。違いはこれが m の文脈に入っていることなので、この適用する部分の関数を fmap で m の文脈に持ち上げてやる必要があった、ということであった。Parser の実装を以下のように書き直してみたらわかりやすかった。

-- Parser
fmap f p = Parser $ \ss ->
    map (\(a, ss') -> (f a, ss')) $ parse p ss

-- ParserT
fmap f p = ParserT $ \ss ->
    fmap (map (\(a, ss') -> (f a, ss'))) $ parseT p ss

さて次は Applicative.

import           Control.Monad

instance (Functor m, Monad m) => Applicative (ParserT s m) where
    -- pure :: a -> ParserT s m a
    pure a = ParserT $ \ss -> pure [(a, ss)]

    -- (<*>) :: ParserT s m (a -> b) -> Parser s m a -> Parser s m b
    f <*> p = ParserT $ \ss -> do
        fs <- parseT f ss
        fmap concat . forM fs $ \(f', ss') ->
            fmap (map (\(a, ss'') -> (f' a, ss''))) $ parseT p ss'

pure は良いとして、 (<*>) はもうちょっとなんとかならんのかと自分でも思うくらいわかりづらい。これも StateT を参考に頑張って型を合わせた結果。ひとつずつ見ていくと以下のようになるだろう。

f <*> p = ParserT $ \ss -> do    -- m の文脈で

    -- f は ParserT s m (a -> b) なので parseT すると m [((a -> b), [s])] を得る
    fs <- parseT f ss

    -- forM: 上で得たそれぞれの (関数, 残り) に対して実行
    -- fmap concat :: m [[(b, [s])]] -> m [(b, [s])]
    fmap concat . forM fs $ \(f', ss') ->

        -- この部分は fmap と同じ。m [(b, [s])] が返る
        fmap (map (\(a, ss'') -> (f' a, ss''))) $ parseT p ss'

fmap が 2 回出てくるようなところはもう少しすっきりできそうな気がするのだけど、とりあえず動いたので先に進む。

最後に Monad. これは Applicative と似ている。

instance (Monad m) => Monad (ParserT s m) where
    -- (>>=) :: forall a b. ParserT s m a -> (a -> ParserT s m b) -> ParserT s m b
    p >>= q = ParserT $ \ss -> do
        ps <- parseT p ss
        fmap concat . forM ps $ \(a, ss') ->
            parseT (q a) ss'

これで ParserT をモナドにすることができた。

この時点で、ParserT をもとにした Parser を作っておこう。m に Identity モナドを使うだけ。

import           Control.Monad.Identity

type Parser s a = ParserT s Identity a

parse :: Parser s a -> [s] -> [(a, [s])]
parse p = runIdentity . parseT p

ここまでやると、最初にトランスフォーマー非対応の Parser を使うコードがそのまま動いた! 期待していたことであったが実際コンパイルが通って動いたときはすごい爽快感だった。

さて、実際にこれを他のモナドと合成して使うためには関連する関数をうまく取り扱えるように定義する必要がある。まず lift を使うために MonadTrans のインスタンスにする。このあたりも StateT を参考にしながら進めた。

import           Control.Monad.Trans.Class

instance MonadTrans (ParserT s) where
    -- lift :: Monad m => m a -> ParserT s m a
    lift act = ParserT $ \ss -> do
        a <- act
        pure [(a, ss)]

つまり合成対象 m モナドのアクション act を、ParserT の文脈で使えるようにするラッパーである。act から取り出した値 a を、ParserT の文脈においても <- で取り出したりできるようにセットしてやる。

おそらく、この段階で transformer スタイルの合成は可能なのではないか (試していないので推測のみ)。transformer スタイルだと明示的に lift を使用してアクションの持ち上げをするので、MonadTrans のインスタンスになっていれば他のモナドとの合成が可能であるような気がする。対して mtl スタイルではもう少し仕事が必要で、合成対象のモナドのアクションをあらかじめインスタンスとして実装しておくことで、この lift の手間を省いている、と理解している。

ということでまずは StateT から。MonadState のインスタンスとするのだが、実装はいたって単純。

{-# LANGUAGE FlexibleInstances     #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE UndecidableInstances  #-}

import           Control.Monad.State.Strict

instance (MonadState t m) => MonadState t (ParserT s m) where
    get = lift get
    put = lift . put
    state = lift . state

これらの関数は単純に lift するだけで良いようだ。get を例に取って見てみる。左辺の get は ParserT のアクション。右辺の get が合成対象モナド m のアクションで、それを lift で持ち上げることで ParserT のアクションとしている。言語拡張についてはまったく理解していなくて、コンパイラに言われるがまま追加した。Control.Monad.State.Class でもこれらの拡張が使われているので間違いではないだろう。

次に ReaderT を使えるようにする。

import           Control.Monad.Reader

instance (MonadReader r m) => MonadReader r (ParserT s m) where
    ask = lift ask
    local f p = ParserT $ local f . parseT p
    reader = lift . reader

local が他とは少し違うが、これもやはり他のモナドの実装を参考にした。他の処理と同じように、ParserT の中身、m の文脈で local を適用するということ。

これで、ParserT は StateT および ReaderT と合成可能である。以下のように利用できる。

type TokenParser a = ParserT Token (StateT ParseState (Reader Env)) a

compile :: Env -> [Token] -> Text
compile env tokens = fst . head $    -- 雑
    runReader (execStateT (parseT parseClass tokens) initialState) env

parseClass :: TokenParser Text
parseClass = ...

これで 11 章で必要なシンボルテーンブル等の状態やその他パラメータを TokenParser 内で使えるようになった。めでたし。

付記

StateT を例にとると、今回作ったのは ParserT s (StateT t Identity) a という形の合成モナドである。これは StateT t (ParserT s Identity) a とは違う。モナドの入れ子の順番は処理の結果に影響して、例えば try などでバックトラックが発生した時に状態が巻き戻るか否かという違いが出るらしい。なお、後者を実現しようとする場合には StateT に手を入れる必要が出てくる。ParserT を中に入れるための型クラス、たとえば MonadParser と使いたいアクションを定義したうえで、StateT を MonadParser のインスタンスにすることになる。

今回オリジナルの Parser をトランスフォーマー対応の ParserT にするにあたり、型を合わせる程度の自然な修正ではあるものの、それなりに多くの箇所に手を入れる必要があった。なので、もともとトランスフォーマーに対応していないモナド (例: attoparsec) を他のモナド (例: State) と合成して使う、というのは骨の折れる作業になると思った。

参考

モナディック・パーサー – あどけない話: https://kazu-yamamoto.hatenablog.jp/entry/20080920/1221881130
transformers: Concrete functor and monad transformers: https://hackage.haskell.org/package/transformers
mtl: Monad classes, using functional dependencies: https://hackage.haskell.org/package/mtl

Month: January 2022

モナドトランスフォーマー

Parser モナド

Parser モナドのトランスフォーマー化

付記

参考