Tempale meta-programing for Haskell
久しぶりにHaskellを勉強した。
せっかくなのでだらだらと。
Template Haskell
- はじめに
Template Haskell というものを勉強してみた。
そういうわけで、資料を探してみたのだが、
日本語の資料は見事なまでに皆無だったので、
(Haskellで、しかも試験的な機能だから止む無しか)
英語の論文を読むことになった。
10ページほど読むのに3日かかったけど…。
- Template Haskell とは…?
大雑把に言うとコンパイル時にプログラムを生成するためのもののようである。
- 概要
コンパイル時に指定した式を実行させ、その値をコードの中に展開させることが出来る。
展開できる式の値は"プログラム式"等の型をもつ。
要するに、任意の方法で構文木を組み立てて、それを実行することが出来ると。
- 大雑把なアイデア
構文木はExpQという型を持つ。
Template Haskell においてはこのExpQ型の何かを扱えば良い。
ExpQというのは実際にはQ Expのシノニムであり、
Expは単にHaskellのデータ型、
QはQuotationモナドというように説明されている。
Quotationモナドであるが、これはほぼIOモナドと同じだろう。
実際のところQモナドとIOモナドは相互変換可能である。
IOに加え、コンパイラの内部状態にアクセスするためにこのように
なっていると思われる。
構文木の構築においてExpQという型を持ち出すのは
構築の際に任意のIOを行わせるためだろう。
Exp型には VarE :: String -> Exp や
AppE :: Exp -> Exp -> Exp などのコンストラクタがあり、
これらはそれぞれ変数参照、関数適用を表している。
全容はLanguage.Haskell.THSyntaxに定義されている。
これとモナド演算だけを用いてプログラムを構築することも出来るのだが、
それはあまりにも冗長で煩雑であるので、利便性のために
もっと別な方法で記述できるようになっている。
Template Haskellの記述方法には3つのやり方がある。
それぞれ順番に記述力が下がり、利便性が上がる。
まず、最初は、先に書いたExp型等をそのまま扱う方法。
次に、それのモナディック版を使う方法。
VarEに対してvarE、AppEに対して、appEなど、先頭が小文字な
関数バージョンが定義されており、
これらはいずれもExpQ上の関数として定義されている。
これらを用いることにより、明示的なモナド操作が減少する。
最後に、quasi-quote記法というものを用いる方法。
これはSchemeにあるquasi-quoteに大体で似ている。
[| |] で囲った部分の式をExpQな型として扱える。
途中に$(式)と書くことにより、その中の式を実行したものを
埋め込むことが出来る。
tfact :: Int -> ExpQ tfact 0 = [| 1 |] tfact n = [| $(lift n) * $(tfact $ n-1) |]
適当な例として階乗を。
tfact 5 が 5 * 4 * 3 * 2 * 1 * 1 に展開される。
なお、quasi-quote記法では色々と記述しきれない部分があるので
これら3つの手法を組み合わせて目的のコードを作成することになる。
これらの手法はシームレスに混合可能である。
作成したものをコンパイル時に実行させるには(unquoteと同様に)
$を頭につければよい。
> $(tfact 10) 3628800
式として書かれるべき場所でトップレベルな展開が発生した場合、
その計算したものの型がExpQであった場合、そこにコードが
挿入されるような感じであろうか。
定義を書くべき場所であれば、DecQ型を返せばそこに宣言を挿入することも出来る。
- 例1 printf
普通なHaskellではprintfのような関数を定義しようと思っても
型を付けることが出来ない。
というのも、
printf "%s : %d" "hello" 123
等のようなコードで、printf の型は引数の文字列によって変わるからなのである。
上の例では String -> String -> Int -> IO () になるだろうか。
しかし、Template Haskellなら可能である。
コンパイル時に文字列を解析して
printf "%s : %d" を \s n -> s ++ " : " ++ show n なる式に
してしまうことが出来るからである。
(以下、都合上 printfでは無くてsprintfを作る)
{-# OPTIONS -fglasgow-exts #-} module Printf( sprintf ) where import Language.Haskell.THSyntax data Format = D | S | L String deriving (Eq,Show) sprintf :: String -> ExpQ sprintf = flip toExp [| "" |] . parse parse :: String -> [Format] parse [] = [] parse ('%':x:xs) | x=='d' = D : parse xs | x=='s' = S : parse xs | otherwise = error "invalid input" parse xs = L l : parse rest where (l,rest) = span (/='%') xs toExp :: [Format] -> ExpQ -> ExpQ toExp [] x = x toExp (D : xs) x = [| \n -> $(toExp xs [| $x ++ show n |]) |] toExp (S : xs) x = [| \s -> $(toExp xs [| $x ++ s|]) |] toExp (L s : xs) x = toExp xs [| $x ++ $(lift s) |]
まず、StringをFormatのリストに変換し、
それをExpQに構築する。
なお、GHCではなぜかtop-levelなspliceはローカルな定義ではなくて
importしたものじゃないと駄目だといわれるので、Printfモジュールを作成している。
{-# OPTIONS -fglasgow-exts #-} module Main where import Printf main = putStr $ $(sprintf "error %s on line %d.\n") "Hoge.hs" 123
このように使用することが出来る。
sprintfは左記の通り変換されるので、型チェックも
問題なく行えるようだ。
- 例2 タプルからのパラメータ化されたセレクト
pairからの要素選択はfst、sndという関数が用意されているが、
triple以上のものから選択しようと思うと、
case x of (a,b,c) -> b
のようなものを書かなければならない。
Template Haskellを用いると、
$(sel 1 3) (1,'a',[]) => 1 $(sel 2 3) (1,'a',[]) => 'a'
のような、自動的にそのような式を生成するものを
記述することが出来る。
{-# OPTIONS -fglasgow-exts #-} module Select( sel ) where import Language.Haskell.THSyntax sel :: Int -> Int -> ExpQ sel a b = lamE [varP "x"] (caseE (varE "x") [alt]) where alt = match pat (normalB rhs) [] pat = tupP (map varP xs) rhs = varE (xs !! (a-1)) xs = ["x"++show i | i <- [1..b]]
上記、sel関数は、quasi-quoteだけでは書けない。
sel a b = [| \x -> case x of ...
と、ここでb要素のタプルが書けないのである。
上のように必要に応じてモナディックな関数で構成すれば
定義できる。
- 例3 任意個のzip
タプルは帰納的な型でないためか
Template Haskellの格好の題材のようであるが、次はzipである。
zipにはzip,zip3,zip4,... と個数に応じたバージョンのzipが定義されているが
zip3 = $(zipN 3)
と書ければ嬉しいという話。
{-# OPTIONS -fglasgow-exts #-} module Zips( zipN ,tfact ) where import Language.Haskell.THSyntax zipN :: Int -> ExpQ zipN n = [| let zp = $(mkzip n [| zp |]) in zp |] mkzip n f = lamE pys (caseE (tupE eys) [m1,m2]) where (pxs ,exs) = genPE "x" $ toInteger n (pys ,eys) = genPE "y" $ toInteger n (pxss,exss) = genPE "xs" $ toInteger n pcons x xs = conP "GHC.Base::" [x,xs] b = [| $(tupE exs) : $(appsE (f:exss)) |] m1 = match (tupP (zipWith pcons pxs pxss)) (normalB b) [] m2 = match (tupP (replicate n wildP)) (normalB [| [] |]) []
lexical scopingのためにzpという名前の扱いが
ややトリッキー(…でもないか)になっているが、
まぁ、こんな感じで。
conP "GHC.BASE::" という部分があるが、これは
(x:xs) なるパターンを生成したかった。
論文中では [p| $x : $xs |] というようにパターン用クオート表記が
使われていたのだが、これがなんだか使えなかったので、
上のような感じになってしまった。
GHC.Baseのようなものを直接書くのは正直忍びないが、
他にやり方がわからなかった。
- まとめ?
参考文献 http://www.haskell.org/th/papers/meta-haskell.ps
率直な感想…構文木を作るコード書くのめんどくさすぎ…
自分で書こうと思っても全然書けない。
慣れの問題なのだろうか…?
http://www.haskell.org/ghc/docs/latest/html/libraries/haskell-src/Language.Haskell.THSyntax.html
ここにもほとんど説明が付いていないし、
いろいろ大変だ。