Template Haskell を使ってメタプログラミングをやってみた

こんにちは。アドベントカレンダー18日目の記事を担当させて頂きます、エンジニアの澤田です。

普段の業務ではJavaScript やPython などでプログラムを書くことが多いですが、今回はあえて、普段使用していない関数型プログラミング言語Haskell に触れてみつつ、以前から興味があったメタプログラミングを実際にやってみようと思います。

Haskell にはメタプログラミングを行うためのTemplate Haskell という言語拡張があり、これを使えば簡単にメタプログラミングができるのではないか？という期待を胸に手を出してみました。

では、早速始めていきましょう！

なお、GHC はバージョン8.0.2を、Template Haskell はバージョン 2.11.1.0を使用しています。

メタプログラミングとは

メタプログラミングとは、プログラムを生成するプログラムを書くことで、マクロやテンプレートメタプログラミングによって行われることが多いようです。
このプログラム生成は、プログラムが処理されるどの過程で行われるのでしょうか？少し見てみましょう。

プログラムのコードは言語処理系によって、基本的に以下の段階を経て実行プログラムに変換される(コンパイル型)か直接実行されます(インタプリタ型)。

1. 字句解析: 文字列を字句(トークン)列に変換する
2. 構文解析: 字句列の文法を解析して抽象構文木(AST: Abstract Syntax Tree)に変換する
3. 意味解析: 抽象構文木に対して意味的な解析を行い中間コードに変換する
4. 最適化: 中間コードを計算量・メモリ使用量などの観点から効率化する
5. コード生成: オブジェクトプログラム(アセンブリ言語、機械語)を生成する

上記のどの段階に対してメタプログラミングを行えるかは、言語ごとの拡張機能によって異なっていて、C のプリプロセッサマクロは「字句解析」の段階で変換され、Lisp マクロは「構文解析」で、D テンプレートは「意味解析」で変換されます。

Template Haskell は、上記の「構文解析」で変換されるマクロで、抽象構文木を組み替えたり合成したりすることができます。
抽象構文木を直接操作できるなんてワクワクしませんか？

では、やっていきましょう！

Template Haskell で抽象構文木を眺めてみる

Template Haskell には、クォート式(Quotation)という特別な括弧で囲われた式などを、抽象構文木に変換して出力する機能があります。
この式の抽象構文木はどうなっているのかな？と思ったら簡単に確認できるわけです。すごいですね。
見てみましょう。

まず、-XTemplateHaskellオプションを付けて ghci を起動します。
そして Language.Haskell.TH モジュールを読み込みます。

$ ghci -XTemplateHaskell
Prelude> :module + Language.Haskell.TH
Prelude Language.Haskell.TH>

1 + 2 の抽象構文木を見てみます。

Prelude Language.Haskell.TH> runQ [e| 1 + 2 |]
InfixE (Just (LitE (IntegerL 1))) (VarE GHC.Num.+) (Just (LitE (IntegerL 2)))

おお、出ましたね！図にするとこんな感じです。

変数への束縛の場合はどうなるでしょうか。

Prelude Language.Haskell.TH> :{
Prelude Language.Haskell.TH| runQ [d|
Prelude Language.Haskell.TH|     x = 1
Prelude Language.Haskell.TH|     y = 2
Prelude Language.Haskell.TH| |]
Prelude Language.Haskell.TH| :}
[ValD (VarP x_1) (NormalB (LitE (IntegerL 1))) [],ValD (VarP y_0) (NormalB (LitE (IntegerL 2))) []]

こちらも図にしてみます。

面白いですね！
今度はこの抽象構文木を元の式などに戻してみましょう。

抽象構文木を元の式などに戻してみる

抽象構文木を元の式などに戻すには、基本的にppr関数に抽象構文木を渡すだけでOKですが、GHC.Num.+ などは、そのままでは名前として解釈してくれないので、先頭にシングルクォートを付けて、 '(GHC.Num.+) などのように書き直す必要があります。

それでは先の 1つ目の例を出力してみましょう。

Prelude Language.Haskell.TH> ppr (InfixE (Just (LitE (IntegerL 1))) (VarE '(GHC.Num.+)) (Just (LitE (IntegerL 2))))
1 GHC.Num.+ 2

おお、元に戻りました！
続いて先の2つ目の例です。2つ目の例では、新しい変数 x と y を導入していますので、名前として解釈させてもそんな変数は無い、と怒られてしまいます。
そんなときは mkName "x" などのように記述して名前を作る必要があります。

それでは先の2つ目の例も出力してみましょう。

Prelude Language.Haskell.TH> ppr [ValD (VarP (mkName "x")) (NormalB (LitE (IntegerL 1))) [],ValD (VarP (mkName "y")) (NormalB (LitE (IntegerL 2))) []]
x = 1
y = 2

できました！
次はいよいよ抽象構文木を書き換えてみましょう。

抽象構文木を書き換えてみる

これまで、式などを抽象構文木にしたり、抽象構文木から式などを復元する方法を見てきました。
この相互の行き来ができるなら、抽象構文木を直接書き換えることもできなくはなさそうです。

しかし1 + 2 のような単純な式でも、抽象構文木は、
InfixE (Just (LitE (IntegerL 1))) (VarE GHC.Num.+) (Just (LitE (IntegerL 2)))
のように複雑な記述になってしまいます。
これを間違えずに書き換えるのはかなり大変そうですよね･･･。

そこで、先ほど出てきたクォート式(Quotation)を使います。このクォート式には全部で 4種類あります。
(各クォートの型のところに書かれている Q は Quotation Monad の略です )

• 式クォート(Expression quotations)
  • 構文: [| ... |] または [e| ... |]
  • 型: Q Exp
• 宣言クォート(Declaration quotations)
  • 構文: [d| ... |]
  • 型: Q [Dec]
• 型クォート(Type quotations)
  • 構文: [t| ... |]
  • 型: Q Type
• パタンクォート(Pattern quotations)
  • 構文: [p| ... |]
  • 型: Q Pat

そして、上記のクォート式を接合(Splice)する、$( ... )という特別な括弧があります。
この接合用の括弧を使うと、Q Exp 型などの抽象構文木を通常のHaskellのコードに埋め込むことができます。

1 + 2 の 2 の部分だけ抽象構文木で記述した 3 に書き換えて接合してみます。

Prelude Language.Haskell.TH> runQ [| 1 + $(return (LitE (IntegerL 3))) |]
InfixE (Just (LitE (IntegerL 1))) (VarE GHC.Num.+) (Just (LitE (IntegerL 3)))

接合して抽象構文木を書き換えることができました！！
そしてクォート式を使わない場合、以下のように書かないといけません。

Prelude Language.Haskell.TH> runQ (return (InfixE (Just (LitE (IntegerL 1))) (VarE '(GHC.Num.+)) (Just (LitE (IntegerL 3)))))
InfixE (Just (LitE (IntegerL 1))) (VarE GHC.Num.+) (Just (LitE (IntegerL 3)))

これはしんどいですね･･･。

さいごに

この記事を書くにあたって、メタプログラミングについて勉強して、実際の業務に役に立つ何かを見つけ出そうと意気込んでいましたが、抽象構文木を実際に見るだけでも面白くなってしまい、通常のコードと抽象構文木を行ったり来たりするのに終始してしまいました･･･。
「これが具体的に何の役に立つのか？」と聞かれると困ってしまいますが、抽象構文木を操作するという新鮮な体験をすることができました :)

皆さんも新しいプログラミング言語に興味を持った際には、新しいプログラミング手法も試してみてはいかがでしょうか。