Template Haskell - mad日記

計算を静的に表す手段としてArrowが使えるという事をid:MaD:20070816で書いたわけですが、もっと強烈な手段としてTemplate Haskellがあります。

以前作ったOpというArrowでは(>>>)演算によって繋がれたArrowを一旦構文木としてデータ化し、最適化をした後に関数を合成するということをしました。

一方、Template Haskellを使うとHaskellのコード片から直接Haskellの内部表現を得られます。Template Haskellについてはhttp://haskell.org/haskellwiki/Template_Haskellのチュートリアルがとてもわかりやすいです。

% ghci -fth                                                                                                    
Prelude> :m +Language.Haskell.TH
Prelude Language.Haskell.TH> runQ [| 1 + 2 |] >>= print
InfixE (Just (LitE (IntegerL 1))) (VarE GHC.Num.+) (Just (LitE (IntegerL 2)))

[| ... |]で囲まれた部分のコードの内部表現を得る事ができます。
これを利用すれば、Template Haskellでも計算を実行する前に最適化を行うということが実現できます。

例えば以前やったreverse.reverseのidへの簡約は以下のように行う事ができます。
Arrowの場合と決定的に違うのは、この最適化はコンパイル時に行われるということです。

% cat test.hs
{-# OPTIONS_GHC -fth #-}
import Language.Haskell.TH

optimize :: Q Exp -> Q Exp
optimize q = q >>= return.opt

opt :: Exp -> Exp
opt (InfixE (Just (VarE e1)) (VarE op) (Just (VarE e2)))
    | op == '(.) && e1 == 'reverse && e2 == 'reverse = VarE 'id
opt e = e

% ghci
Prelude> :load "test.hs"
*Main> runQ [| reverse . reverse |] >>= print
InfixE (Just (VarE GHC.List.reverse)) (VarE GHC.Base..) (Just (VarE GHC.List.reverse))
*Main> runQ (optimize [| reverse . reverse |]) >>= print
VarE GHC.Base.id
*Main> (reverse . reverse) [1..]
Interrupted.    (処理が返ってこない)
*Main> $(optimize [| reverse . reverse |]) [1..]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22

簡単に説明すると、$演算子は$( ... )の中をコンパイル時に評価し、計算結果からHaskellの実際のコードを生成します。
[| ... |]の記法によってQ Expという型のデータが生成されますので、optimizeによってそれを処理して新しい式へと書き換えています。
QはQuotation Monadというモナドで、Expが実際の式を表すデータ型です。

InfixE (Just a) op (Just b)で a op bを表します。Maybe型を利用しているのはこれを利用して関数の部分適用を表現する為です。

InfixE (Just 'x) (VarE '(+)) (Just 'y) == x + y
InfixE (Just 'x) (VarE '(+)) Nothing   == (x +)
InfixE Nothing (VarE '(+)) (Just 'y)   == (+ y)

クオート(')はHaskellのコード上の識別子を、内部表現での識別子に変換する記法です。
reverse . reverseという形の式であればidに置き換えるということをしています。

Template Haskellの難しさ

という感じでTemplate Haskellはめちゃくちゃ強力なわけですが、扱うのは非常に困難です。
例えば(->)のArrowでは

f >>> g = g.f

と定義されていましたが

Prelude> :load "test.hs"
*Main> :m +Control.Arrow
*Main Control.Arrow> $(optimize [| reverse . reverse |]) [1..]
Loading package template-haskell ... linking ... done.
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,
*Main Control.Arrow> $(optimize [| reverse >>> reverse |]) [1..]
Interrupted.    (処理が返ってこない)

となってしまいます。これは

*Main Control.Arrow> runQ [| reverse . reverse |] >>= print
InfixE (Just (VarE GHC.List.reverse)) (VarE GHC.Base..) (Just (VarE GHC.List.reverse))
*Main Control.Arrow> runQ [| reverse >>> reverse |] >>= print
InfixE (Just (VarE GHC.List.reverse)) (VarE Control.Arrow.>>>) (Just (VarE GHC.List.reverse))

のように、reverse >>> reverseの構文木とreverse . reverseの構文木が異なる事が原因です。
他にも

*Main Control.Arrow> let f = reverse
*Main Control.Arrow> runQ [| f.f |] >>= print
InfixE (Just (VarE f_1627400287)) (VarE GHC.Base..) (Just (VarE f_1627400287))

の用に、ちょっと式が変われば解析対象が変わってしまいます。

また、$( ... )の部分をライブラリの使用者から見えないようにするとかいった事もできませんし、$( ... )の中に入る関数は外部からimportしたものでなければなりません。ファイルのコードを参照しつつコードを書き換えるということになってしまって、好ましくないからのようです。

なので、通常はDSL(ドメイン固有言語)を作り、特定用途に限定してTemplate Haskellを使用することが多いようです。
例えば、ライブラリ側で、基本的な部品となるQ Exp型のデータやQ Expを生成する関数と、Q ExpからQ Expを合成するoptimizeのような関数を提供し、使用者は直接[| ... |]の形のコードを書かなくても済むように設計するなどの方法をとったりします。