型クラスで tagless DSL メタプログラミング

これは Haskell Advent Calendar 2011 の5日目の記事です。 去年も書きましたが、その記事はこちら → Haskell厨を6年やってる俺がOCamlを仕事で2ヶ月使ってみた - keigoiの日記

先日の記事 Haskell＋タグレスな型付きDSLで楽々！C言語コード生成 - keigoiの日記 をちょっとブラッシュアップした。前回はコードについては全く説明しなかったので、改めて解説する。

おさらい

HaskellやOCamlなどの関数型言語は、プログラミング言語の処理 ― 構文解析とコード生成 ― がとても得意だ。 大手のソフトウェア企業として知られる NTTデータも既存コードの処理 (構文解析〜リバースエンジニアリング) のために Haskell を使っているそうだ。 (函数プログラミングの集い2011より。インドに外注する部分もあるそう togetter 1, 2, 3)
ソフトウェア設計でホットな話題の一つは、ドメイン特化言語 (DSL) による抽象化である。 ある問題領域（ドメイン）の語彙をDSLにうまくまとめて、そのDSLからコードを生成するコンパイラを書けば、より迅速に、かつスケールする形で（例えば多人数で）効率的にソフトウェアを開発できる。
特にプログラマにとって面白いのは、 EDSL (Embeded DSL) という、ライブラリの形で言語に「埋め込んで」提供する形のDSLだ。利用者側にとってはホスト言語 (Haskellなど) の型や関数定義などの抽象化機能を利用できる点で便利であり、また実装者にとっては、かかる手間がより少なく済む(構文解析や型チェッカが不要)。

今回のソース

今回の記事で使ったHaskellのソースコードを http://proofcafe.org/~keigoi/Advent2011.hsに置いた。長さは180行弱。

純粋関数的（簡易）EDSLの設計

今回は、ごく簡単な四則演算とループのみを備えた、純粋関数的なEDSLを実装する。 このEDSLでプログラムを記述し、実行すると、記述内容をC言語にコンパイルしたソースコードが出力される。そのコードをgccなどのコンパイラに与えれば、実行形式が得られる。
別の見方をすると、 C言語の「マクロ」をHaskellで書くと思えばいい。 HaskellはCの標準のプリプロセッサと違って、強力な型システムを備えている。 例としては非常に小さいが、それでも Haskellの高階関数を効果的に利用すれば、C言語では不可能な抽象化も簡単にできる。

タグレスDSL

前回書いた通り、実装はタグレスにする。 これはつまり、中間データ表現を介さないということだ。 ただ中間表現を廃止してまうと、その中間表現から得られたであろう様々な柔軟性が失われ、一つの用途にしか使えなくなる。これを回避するために、変換先の型を型クラスで抽象化する（今回の記事ではC言語コード生成しかしないのだが）。

まず、対象言語の「式」を表す型構築子Expを与える。

newtype Exp l a = Exp {unExp::l a}

ここでaは式の型、lは変換先の型を抽象化した型構築子だ。

次に、対象言語の関数プリミティブを導入する。

data FunName = Op String | Name String
newtype Func1 a b = Func1 (FunName, a -> b)
newtype Func2 a b c = Func2 (FunName, a -> b -> c)

FunNameは、その関数のC言語における名前（または演算子）を表す。 Func1は１引数関数、Func2は2引数関数だ。それぞれ中身は関数名と関数のペアになっている。前者はC言語のコード生成に使われる。後者はHaskellの式を評価するときに使い、Cのコード生成には関係ない。
構文は、次の型クラスで与える。Langという名前は、このEDSLがC言語ソースを生成するだけでなく、Haskellの式としても評価でき、他さまざまなプログラミング言語を出力できる可能性を表しているつもりだ。*1

-- 'tagless' representation of the language
class Lang (l :: * -> *) where
  -- | true constant
  true :: Exp l Bool
  -- | false constant
  false :: Exp l Bool
  -- | constant of type Int
  int :: Int -> Exp l Int
  -- | func e1
  func1 :: Func1 a b -> Exp l a -> Exp l b
  -- | func e1 e2
  func2 :: Func2 a b c -> Exp l a -> Exp l b -> Exp l c
  -- | if-then-else
  ifThenElse :: Exp l Bool -> Exp l Int -> Exp l Int -> Exp l Int
  -- | loop
  loop :: Exp l Int -> Exp l Int -> Exp l Int
          -> (Exp l Int -> Exp l Int -> Exp l Int) -> Exp l Int
  -- | let-binding in the target language
  let_ :: Exp l Int -> (Exp l Int -> Exp l Int) -> Exp l Int

true,false,intは言語の定数だ。 func1, func2 は関数の呼び出しである。 ifThenElseは文字通りif文だ。loopはややわかりにくいが、 loop from to acc f でfromからtoまでaccにfを繰り返し適用する高階関数である。 let_ は、ターゲット言語におけるletである。Haskellのletだと式が複製されてしまうので、こちらのlet_を使うようにする（このように、式の共有を自然には扱えないのがEDSLの欠点のひとつだが、解決策もある(observable sharing)）。

C言語ソースコード生成部

型クラスLangのインスタンスとして、C言語のソースコードを生成する部分を与える。 つまり、型 Exp l a の l に相当する部分を与え、それへの変換をここで実装する。

名前生成モナド

まず、自動生成するコードに現れる変数どうしが衝突しないように工夫する必要がある。この名前管理をStateモナドで与える。

class Monad q => MonadQ q where
  newName :: String -> q String

instance MonadQ (State [(String,Int)]) where
  newName str = do
    varmap <- get
    let cnt = fromMaybe 0 $ lookup str varmap
    put $ (str,cnt+1):deleteBy (\(a,_)(b,_)->a==b) (str,0) varmap
    return $ str ++ show cnt

instance (Monoid w, MonadQ m) => MonadQ (WriterT w m) where
  newName = lift . newName

要するにnewNameは文字列fooからfoo0,foo1,..という名前を生成するだけだ(アホなバグがあったので直した)。 後で使うために、WriterTでリフトした場合にもMonadQのインスタンスになるようにしてある。

C言語ステートメントを運ぶWriterモナド

C言語は残念ながらHaskellのような式を中心とした言語ではなく、ifやforなど一部の制御構造は文（ステートメント）である (gcc拡張でブロックを式として扱えたりするが)。 そこで、コード生成モナドには「その式を計算する前に実行しなければならない文のリスト」を持たせるようにする。コード生成計算毎に副作用として文のリストが生成されてゆくことになる。 このような場合に適したモナドは何か？ そう、Writerモナドだ。 既にStateモナドを使っているので、それを WriterT で持ち上げるようにする。このモナドにWという名前をつける。

type W a = WriterT [C.BlockItem] (State [(String,Int)]) a

C.BlockItemはC言語の文を表すlanguage-c-quoteの型だ（Language.C.SyntaxをCと略している）。一方、C言語の式は C.Exp という型を持つ。
結局、EDSLの式に相当するC言語コードを表す型は、 W C.Exp という型になる。

ソースコード生成器

ここまでに見てきたように、コード生成結果の型は、Wモナドの型をもつ。 結局、型Exp l aのlに置く型 (CGenと名付ける) は次のようになる：

newtype CGen a = CGen {unCGen :: W C.Exp}

型 CGen a は、型aの値を計算するC言語の式(と文)であるが、 型aは コード生成に使わない幽霊型である*2。
いろいろな型を変換する便利関数も準備しておく。　

unExp_ :: Exp CGen a -> W C.Exp
unExp_ (Exp (CGen m)) = m

cgen :: C.Exp -> Exp CGen a
cgen = E. CG . return

cgenW :: W C.Exp -> Exp CGen a
cgenW = E . CG

実際にC言語のコードを生成する部分は、次のLangのインスタンス宣言だ。 CGen型がWモナドになっているので、コード生成器に必要な様々な副作用を入れられるようになっている。

-- generate C code!!
instance Lang CGen where
  true  = cgen $ [cexp| TRUE |]
  false = cgen $ [cexp| FALSE |]
  int i   = cgen $ [cexp| $int:i |]
  func1 fun e1 = cgenW $ do 
    x <- unExp_ e1
    return $ case fun of
      Func1(Name funname,_) -> [cexp| $id:funname( $x ) |]
      Func1(Op opname,_) -> (C.UnOp (toCUnOp opname) x noSrcLoc)
  func2 fun e1 e2 = cgenW $ do
    x <- unExp_ e1; 
    y <- unExp_ e2;
    return $ case fun of
      Func2(Name funname,_) -> [cexp| $id:funname( $x, $y ) |]
      Func2(Op opname,_) -> (C.BinOp (toCBinOp opname) x y noSrcLoc)
  ifThenElse cond then_ else_ = cgenW $ do
    tmp <- newName "tmp"
    cond' <- unExp_ cond
    (thenExp, thenStmts) <- lift $ runWriterT $ unExp_ then_
    (elseExp, elseStmts) <- lift $ runWriterT $ unExp_ else_
    -- 変数宣言を生成し、if文の内部で代入する
    tell [C.BlockDecl [cdecl|
            int $id:tmp;
          |], C.BlockStm [cstm| 
            if($cond') {
              $items:thenStmts
              $id:tmp = $thenExp;
            } else { 
              $items:thenStmts
              $id:tmp = $elseExp;
            } 
          |] ]
    return [cexp| $id:tmp |]

let_, loop については読者に委ねる（ifを参考にすればそう難しくないはずだ）。 toCUnOp, toCBinOpはFunc1,Func2からC言語の演算子に変換する関数である。

実行

次のようにモナドを走らせればよい：

toString :: Exp CGen Int -> String
toString exp = 
  case flip evalState [] $ runWriterT $ unExp_ exp of
    (exp, blocks) -> unlines (map show blocks) ++ "return " ++ show exp ++ ";"

時間がなくなってきたので非常につまらない例で恐縮だが、例えば ifThenElse (1 >. 0) 1 2 という式からC言語の式を生成すると

Main> putStrLn $ toString (ifThenElse (1 >. 0) (1*2) (3+4-5))
int tmp0;
if (1 > 0) {
    tmp0 = 1 * 2;
} else {
    tmp0 = 3 + 4 - 5;
}
return tmp0;

のようになる。ここで、 E CGen Int を Num のインスタンスにすることで、よりHaskellっぽい構文で書けるようになっている。

まとめ

この記事では、以前に引き続き、Oleg Kiselyov氏のtagless interpreterを応用して、C言語のソースコードを生成する例を示した。 ソースコードは http://proofcafe.org/~keigoi/Advent2011.hsにある。 以前よりはソースコード生成の具体的な方法に踏み込めたと思う。実装にモナド変換子を使ったりと、初心者にも面白い用例になっているかもしれない。
この言語を使って書ける計算は限られているが、Langクラスのメソッドを追加すればどんどん拡張できる。純粋関数に限定しなければ、もっと複雑で実用的なプログラムの生成も簡単だろう（その場合、EDSLの見た目が純粋関数的なHaskellの意味と乖離していくことになるが、モナドの記法などを流用してそれらしく見せることもできる）。
タグレスDSLを入り口として、Haskellを使ったプログラム生成でソフトウェア開発をより効率よく開発できるようになることを期待したい。

*1:私の手元にある実装では、これに加え タプル型や配列、構造体の一部を扱えるのだが、簡潔さのため割愛した。特にタプルの扱いはちょっと工夫したので、機会あればお披露目したい

*2:幽霊型なので、型はコード生成時に「捨てられる」ことになる。型を捨てているせいで、let_やifにおいてC言語の変数宣言における型がint一種類に決め打ちせざるを得なくなっている。後の拡張として、ifやletがint以外の型を返せるようにするには、型aの情報を使って変数宣言を生成することになる。これを実現するためには、実行時型情報を持ち運べるData.TypeableかGADTを使う。今はint型のみを相手にしているので、勝手にint型の宣言を生成している