型レベルプログラミングの会
- 型レベルプログラミングの会 ATND
東京駅から丸の内線に乗ったが、溜池山王駅が屈指の地下ダンジョンであることをすっかり忘れていて、丸ノ内線国会議事堂前駅の最後尾車両を降りてから、ATTの最寄り出口まで20分も歩く羽目になってしまった。しかも途中で２回引き返しをしている。ふんがー。
C++ テンプレートでカレンダー
で、このさいなので一昨年の夏プロシンのショートセッションでしゃべったネタを再版。論文にはなっていないので、一般には初公開？
セッションは好きなプログラミング言語でカレンダーを実装する、というお題で、おいらはC++テンプレートを使った。
他に、竹内先生がLispで宇宙カレンダーを作ったり（ref:竹内郁雄＠Lispハッカーは、日本のゲルトミューラーだ／Tech総研）、ささださんがRubyVMにカレンダー命令を組み込んだり、にしおくんがpythonワンライナーっぽい正方形プログラムを書いたりしていた。
C++ テンプレートでカレンダー
概要
C++テンプレートによるメタプログラミングで、コンパイルタイムにカレンダーを計算し、オブジェクトプログラムへ結果を組み込むプログラムを作成する。またそのプログラムの記述方法から、C++テンプレートと関数型言語との類似点を紹介する。
はじめに
C++テンプレートはコンパイルタイムで駆動する型ベースの計算システムで、マルチパラダイムプログラミング言語C++の総称性プログラミング部分を担う。[1]
C++テンプレートはチューリング完全性を備えていることが分かっており[2]、総称性プログラミングの範囲を超えてアルゴリズムを記述することができる。これをテンプレートメタプログラミングと呼ぶ。
本稿ではC++のテンプレートメタプログラミングを使い、お題であるカレンダー作成をコンパイルタイムで行うプログラムを作成する。
テンプレートによるメタプログラミング
関数の記述
C++のテンプレートメタプログラミングでは型をオブジェクトに、型を引数とするクラステンプレートを関数に見立てる。そして、テンプレートをインスタンス化する操作が関数適用に相当する。
例えば、f(x,y) = g(p(x),q(y))のような関数fは次のように記述する。
template<class X, class Y> struct F { typedef Q<Y> q; typedef typename G<P<X>,q>::ev ev; };関数に見立てたテンプレートには全て、評価(evaluation)を意味するevという名前のメンバ型を持たせ、関数の評価値に相当する型をtypedefしておく。このevを参照することで評価値を得ることができる。この記述は一種のダックタイピングであり、typedef操作は変数の宣言および束縛に相当すると言える。
関数の評価とパターンマッチ
テンプレートはそのインスタンスが実際に必要とされるまでインスタンス化されない。そのため、evを参照する位置によって評価のタイミングをコントロールでき、遅延評価を行うことも可能である。また、テンプレートは参照透過性が確保されており、一度評価されると後はパターンマッチにより評価が省略される。
テンプレートにはifステートメント相当の記法が無く、テンプレートメタプログラミングではテンプレートの部分特殊化を多用する。テンプレートの部分特殊化とは引数の一部が特定の場合のテンプレートを定義しておくことで、インスタンス化の際に引数のパターンマッチで適切なテンプレートが選択される。
このように、C++テンプレートは関数型言語に類似した側面を持つが、λ関数に相当する記法が無いこと、テンプレートそのものをオブジェクトとして扱えないことなどが関数型言語とは決定的に異なる。
実装
暦計算プログラム
アルゴリズムにZellerの合同式[3]をC++テンプレートメタプログラミングで実装した、暦計算プログラムを以下に示す。
基本の整数型N
を定義した後、各関数を定義する。全ての関数は最終的にN に評価される。N ::vlで対応するint型整数nを取り出す。 template<int n> // 全てのevの基底 struct N { typedef N<n> ev; static const int vl = n; }; template<class N1, class N2> struct ADD { typedef N<N1::ev::vl + N2::ev::vl> ev; }; template<class N1, class N2> struct SUB { typedef N<N1::ev::vl - N2::ev::vl> ev; }; template<class N1, class N2> struct MUL { typedef N<N1::ev::vl * N2::ev::vl> ev; }; template<class N1, class N2> struct DIV { typedef N<N1::ev::vl / N2::ev::vl> ev; }; template<class N1, class N2> struct MOD { typedef N<N1::ev::vl % N2::ev::vl> ev; }; template<class N1, class N2> struct LT { typedef N<(N1::ev::vl < N2::ev::vl)?1:0> ev; }; template<class C, class N1, class N2> struct IF { template<class _C, class _N1, class _N2> struct _IF { typedef typename _N1::ev ev; }; template<class _N1, class _N2> struct _IF<N<0>, _N1, _N2> { // 部分特殊化 typedef typename _N2::ev ev; }; typedef typename _IF<typename C::ev,N1,N2>::ev ev; }; template<class Y, class M, class D> struct Z { static const int a = DIV<Y,N<100> >::ev::vl; static const int b = MOD<Y,N<100> >::ev::vl; static const int m = M::ev::vl; static const int d = D::ev::vl; typedef N<(static_cast<int>(m*2.6-0.2)+d+b+b/4+a/4+5*a)%7> ev; }; template<class Y, class M, class D> struct ZELLER { typedef Z<SUB<Y,N<1> >,ADD<M, N<10> >,D> E1; typedef Z<Y, SUB<M, N<2> >, D> E2; typedef typename IF<LT<M,N<3> >, E1, E2>::ev ev; }; template<class Y, class D> struct DIF { typedef typename DIV<SUB<DIV<Y,D>,SUB<Y,N<1> > >,D>::ev ev; }; template<class Y> struct LEAP { typedef DIF<Y,N<4> > E1; typedef DIF<Y,N<100> > E2; typedef typename ADD<SUB<E1,E2>,E2>::ev ev; }; template<class Y, class M> struct DS { template<class _Y, class _N> struct _DS {}; template<class _Y> struct _DS<Y0, N<1> > { typedef N<31> ev; }; template<class _Y> struct _DS<_Y, N<2> > { typedef typename ADD<N<28>,LEAP<_Y> >::ev ev; }; template<class _Y> struct _DS<_Y, N<3> > { typedef N<31> ev; }; template<class _Y> struct _DS<_Y, N<4> > { typedef N<30> ev; }; template<class _Y> struct _DS<_Y, N<5> > { typedef N<31> ev; }; template<class _Y> struct _DS<_Y, N<6> > { typedef N<30> ev; }; template<class _Y> struct _DS<_Y, N<7> > { typedef N<31> ev; }; template<class _Y> struct _DS<_Y, N<8> > { typedef N<31> ev; }; template<class _Y> struct _DS<_Y, N<9> > { typedef N<30> ev; }; template<class _Y> struct _DS<_Y,N<10> > { typedef N<31> ev; }; template<class _Y> struct _DS<_Y,N<11> > { typedef N<30> ev; }; template<class _Y> struct _DS<_Y,N<12> > { typedef N<31> ev; }; typedef typename _DS<Y, typename M::ev>::ev ev; };|カレンダーを出力
テンプレートはコンパイルタイムの計算システムなので、計算結果はコンパイラの出力を媒体とする。ここではオブジェクトファイルにカレンダーを出力する。いわば、コンパイラはテンプレートのインタプリタである。
出力コード
以下に、オブジェクトファイルの定数セクションに曜日方向の日付配列を曜日名で出力するコードを示す。
template<class Y, class M, class E> struct DATE { typedef SUB<N<1>, ZELLER<Y,M,N<1> > > Z; typedef typename IF<LT<ADD<E,Z>, N<0> >, N<0>, IF<LT<DS<Y,M>, ADD<E,Z> >, N<0>, ADD<E,Z> > >::ev ev; }; typedef N<_YEAR> Y; typedef N<_MONTH> M; #define DAY(D,DD) extern const char D[] = { DATE<Y,M,N<DD> >::ev::vl, DATE<Y,M,N<DD+7> >::ev::vl, DATE<Y,M,N<DD+14> >::ev::vl, DATE<Y,M,N<DD+21> >::ev::vl, DATE<Y,M,N<DD+28> >::ev::vl, DATE<Y,M,N<DD+35> >::ev::vl, } DAY(su,0); DAY(mo,1); DAY(tu,2); DAY(we,3); DAY(th,4); DAY(fr,5); DAY(sa,6);|出力操作
最後に計算結果の確認操作を行う。以下はx86 Linuxでの操作例であるが、環境毎のオブジェクトファイルの形式に合わせるため、nmコマンドなどbinutilsを併用するとよい。
% c++ -o -D_YEAR=2007 -D_MONTH=8 cal.cpp %% objdump -x cal.o % od -tdC -j 064 -N 42 --width=6 cal.o 0000064 0 5 12 19 26 0 0000072 0 6 13 20 27 0 0000100 0 7 14 21 28 0 0000106 1 8 15 22 29 0 0000114 2 9 16 23 30 0 0000122 3 10 17 24 31 0 0000130 4 11 18 25 0 0おわりに
C++のテンプレートメタプログラミングを使って、コンパイルタイムでカレンダーを計算した。
Stroustrap曰く「テンプレートを総称型以外にやたらと使うなよ」。しかし現実には、Boost.MPLのようなテンプレートメタプログラミングライブラリが普及し、C++ 0xやD言語の標準化にも影響を与えている。
コンパイルタイム計算はデバッグが大変だが、ぜひテンプレートメタプログラミングを楽しんで欲しい。
