中年からのメタプロデビュー

2006-08-27

近況

また余暇コードを書きはじめた. 挫けないようゴールは小物をえらぶ. こんどは C++ を使っている. 趣味での C++ はちょっと久々. ほどよくモダンに書きたい.

作業をすすめると, ある整数値の二進対数を計算したくなった. lg(512) -> 9 みたいなやつ. 端数は切り上げたい. (ex. lg(100) -> 7) 想像のつくとおり, ビットシフトでせこく計算を端折ったり, メモリをけちる都合で適当にデータやメモリブロックの大きさを揃えるような目的に使う. だから対数を求めたら逆に 2 の指数も計算したい (ex. pow(2, 7) -> 128)

モダン界に生きる以上, このサイズ計算はコンパイル時にやる必要がある. こんなかんじ.

typename<typename S>
struct PoormansContainer {
  enum {
    block_size  = ... sizeof(S)を使った式 ..., // ここで指数を計算
    block_power = ... sizeof(S)を使った式 ...  // ここで対数を計算
  };
  ...
};

...
PoormansContainer<MyData> data_list;

C++ でコンパイル時計算といえば template meta programming. せっかくだからここらでメタプロデビューをしてみようと思い Boost MPL のドキュメントを眺めてみる. が, むずかしい. よくわかんない. 眠い. 挫けた...

私が最初にテンプレートを使った MP を知ったのは, 学生の頃 Generative Programming という本を読んだ時のこと. たぶんこのころ瞬間的に boost をウォッチしていて, この本がメーリングリストか何かで紹介されていたのだった気がする. (よっぽどヒマだったんだね...) こいつはすごいとさっそく手元の VC++6.0 で書いてみたらさっぱり動かなかった. ひどくがっかりしたのを覚えている. それ以来 MP には近づいていない.

その時の記憶が確かなら, テンプレートの MP とはテンプレートの特殊化で分岐を, enum で変数を, 再帰的なテンプレートクラスのインスタンス化で関数を表現する手法だった気がする. boost MPL はもっと色々やっていそうだが, 私の知る素朴な MP はそんなものだった. まあ分岐と変数と関数があればなんとかなりそうだ.

ということで書いてみた:

#include <iostream>

/*
 * conditional
 */
template<bool P, size_t X, size_t Y>
struct select_t { enum { value = 0 }; };
template<size_t X, size_t Y>
struct select_t<true,  X, Y> { enum { value = X }; };
template<size_t X, size_t Y>
struct select_t<false, X, Y> { enum { value = Y }; };

/*
 * binary logarithm (with round-up)
 */
template<size_t N, size_t M=30u> struct lg_t {
  enum {
    X = N &  (1<<M),
    Y = N & ((1<<M)-1),
    value = select_t<(0 != X),
	             (M + select_t<(0 != Y), 1, 0>::value),
                     lg_t<N, M-1>::value
	             >::value
  };
};

template<size_t N> struct lg_t<N, 0> {
  enum { value = 0 };
};

/*
 * power function
 */
template<size_t N, size_t M> struct pow_t {
  enum {
    X = M-1,
    value = select_t<(0 == X),
                     N,
                     (N*pow_t<N, M-1>::value)
	             >::value
  };
};

template<size_t N> struct pow_t<N, 0> {
  enum { value = 1 };
};

int main() {
  std::cout << lg_t<100>::value << std::endl;
  std::cout << pow_t< 2, lg_t<100>::value >::value << std::endl;
  return 0;
}

結果:

7
128

なんとなく動いてる気がする. 最近のコンパイラ(gcc-4.0)はエライ.

それにしても, このくらい誰かが既に作っているとおもうんだどなあ. boost MPL の難しさを考えると, この程度なら MP な人には当たり前すぎる話なんだろうか. 本も出ていることだし勉強しておいた方がいいのかもと思うも食指の動きは鈍くカート投入には至らず... それにこの再帰に満ちた界隈で生きていくには, MP 以前に関数型言語の一つもやっておいた方がよさそう. 先は長い.