C++テンプレートでFizzBuzz

これは、1月20日に北海道にて行われた日本野望の会で披露したネタのまとめと解説のエントリーです。

そもそも

こんなしょーもないネタを思いついたのは、このブログの昨年の検索キーワードトップ3が

1. C++
2. FizzBuzz
3. テンプレート

だったから。それぞれのキーワードについては、

• C++ - Wikipedia
• Fizz Buzz - Wikipedia
• テンプレート（プログラミング）- Wikipedia

あたりを見てちょうだい。

特に、会場には「テンプレートって知らなーい」って人が2,3人いたのでテンプレートについてちゃんと説明したかったのですが、いかんせん時間が足りなすぎでした。テンプレートをまじめに語ると本が一冊書けてしまうので、端折りました。当然、ここでも端折ります。

上述のリンク先とかを見るか、テンプレートをまじめに語った本を一冊読んでくだせえ。

とりあえず、おいらのFizzBuzzコードwithC++テンプレートを読むに当たって、次の点だけでもおさえておくと理解が早く進むかも。

操作すべき対象は型（クラス,構造体etc...）であり、クラス（構造体）テンプレートは関数である

たとえば、f(x,y)=G(P(x),Q(y))な関数は次のように書けます。

template<class X, class Y> struct F {
  typedef Q<Y> q;
  typedef typename G<P<X>, q>::ev ev;
};

ev*1というtypedefされたメンバ型があるけど、これを参照するとテンプレートがインスタンス化されます。このテンプレートのインスタンス化は即ち関数Fの評価に相当し、インスタンスが評価値となります。テンプレートは実際に使うまでインスタンス化されないので、evを参照するタイミングを適切に設定すると、遅延評価もできます。

部分特殊化(partial specialize)を使うと分岐が書ける

部分特殊化とはなんぞやという解説はしません。とりあえず次のコードを見てください。

template<class C, class E1, class E2>
  struct IF { typedef typename E1::ev ev; };
template<class E1, class E2>
  struct IF<FALSE, E1, E2> { typedef typename E2::ev ev; };

この定義に対し、

IF<foo,T1,T2>::ev

としたとき、fooがFALSE以外だとT1の評価値が、FALSEだとT2の評価値がIFの評価値になるのね。これはまさに分岐。実際の実装にはもうワンクッションの工夫が必要だけど、とりあえずそれは実コードを見てもらえればいいです。

さて、C++はオブジェクト指向言語ですが、ここでやっていることは関数プログラミングです。Lispとかでのプログラミング経験があるとかなり有利！

ついでに言うと、C++テンプレートはチューリング完全であることが分かっているので、理論上は全てのアルゴリズムが計算可能なのです*2。

さて、これを踏まえてFizzBuzzをやります。

FizzBuzzの設計と実装

FizzBuzzを作るには次の順序で実装します。

1. 任意の整数のうち、3の倍数、5の倍数、15の倍数をそれぞれFizz,Buzz,FizzBuzzに変換できるようにする
2. 任意の連続した整数列にこの変換を適用できるようにする

Fizz,Buzz,FizzBuzzへの変換

でわまず、任意の整数のうち、3の倍数、5の倍数、15の倍数をそれぞれFizz,Buzz,FizzBuzzに変換できるようにするところ。Fizz,Buzz,FizzBuzzはそれぞれ同名の構造体を定義しておきます。また、整数関数Nも定義しておきます。Fizz,Buzz,FizzBuzz,Nはいずれも評価値は自分自身になります*3。

すると、こんなコードになります。

struct Fizz     { typedef Fizz ev; };
struct Buzz     { typedef Buzz ev; };
struct FizzBuzz { typedef FizzBuzz ev; };

template<int n> struct N {
    typedef N<n> ev;
    static const int vl = n;
  };

N::vlはNの値をint型にして返すためのものです。

続いて、FizzBuzzへの変換に必要な演算用の関数を定義します。剰余、論理否定、そして分岐です。

template<class N1,class N2>
  struct MOD { typedef N<N1::ev::vl % N2::ev::vl> ev; };

template<class _T> struct _NOT        { typedef N<0> ev; };
template<>         struct _NOT<N<0> > { typedef N<1> ev; };
template<class T>  struct NOT {
  typedef typename _NOT<typename T::ev>::ev ev;
};

template<class _C, class _T1,class _T2>
  struct _IF { typedef typename _T1::ev ev; };
template<class _T1,class _T2>
  struct _IF<N<0>,_T1,_T2> { typedef typename _T2::ev ev; };
template<class C,class T1,class T2>
  struct IF { typedef typename _IF<typename C::ev,T1,T2>::ev ev; };

NOTとIFが先の分岐のサンプルよりも若干複雑になっています。これは、第一引数の評価値を使って、関数の評価値を決める必要があるためです。サンプルのコードでは、第一引数が既に評価済みである必要があるんだけど、実際のコードでは、第一引数は評価前の関数をそのまま与えることが可能になってて、明示的な評価操作が不要。

以上を用い、整数が与えられたときにFizz,Buzz,FizzBuzzが評価値となるConvFizzBuzzを定義します。3の倍数でも5の倍数でもなければ、元の整数に評価されます。

template<class T>
  struct ConvFizzBuzz {
    typedef typename
      IF<NOT<MOD<T,N<15> > >, FizzBuzz,
      IF<NOT<MOD<T,N< 5> > >, Buzz,
      IF<NOT<MOD<T,N< 3> > >, Fizz,
                              T
    > > >::ev ev;
  };

以上で整数からFizz,Buzz,FizzBuzzへの変換の記述は完了。

任意の連続した整数列に変換を適用

続いて任意の連続した整数列に変換を適用して、任意の整数範囲のFizzBuzzをできるようにします。これはLispのConsセルのようなものを使った再帰リストで記述します。

template<class N1>
  struct INC { typedef N<N1::ev::vl + 1> ev; };

template<class T1,class T2> struct _EQ      { typedef N<0> ev; };
template<class T>           struct _EQ<T,T> { typedef N<1> ev; };
template<class N1,class N2> struct EQ {
  typedef typename _EQ<typename N1::ev, typename N2::ev>::ev ev;
};

struct FizzBuzzTerminal { typedef FizzBuzzTerminal ev; };

template<class T1, class T2>
  struct FizzBuzzList {
    typedef FizzBuzzList<INC<T1>, T2> ev;
    typedef typename ConvFizzBuzz<T1>::ev vl;
    typedef typename
      IF<EQ<T1,T2>, FizzBuzzTerminal, FizzBuzzList<T1,T2> >::ev next;
  };

FizzBuzzListはT1からT2までのFizzBuzzのリストで、メンバ型nextを使って再帰的に定義されてます。T1とT2が同じものだと、FizzBuzzListのnextはFizzBuzzListTerminalになって、再帰の基底になりここで再帰は終了。

以上で一応完成。

typedef FizzBuzzList<N<0>, N<20> >::ev fb20;

なんてやると、fb20はFizzBuzz,N<1>,N<2>,Fizz,...,Buzz,FizzBuzzListTerminalというクラスの連接構造を持ちます。

実際に計算をさせるには、

% c++ fizzbuzz.cpp

とコマンドを入力する必要があり。ちなみに、c++コマンドはC++テンプレートインタプリタのコマンドです。g++なんてのもあります。デバッガはありません。

ただ、これだと計算はできているのですが、実際に人間様の目に見えるようにFizzBuzzを出力してくれない。なのでランタイムで文字列を出力するようなコードを貼っておきますが、もう疲れたので解説はしません。ランタイムコードなので、C++を普通に知っていて、テンプレートでのFizzBuzzを理解できていれば読めるので、勝手に読んでちょーだい。

#include <iostream>
using namespace std;

template <int n>
  struct N {
    typedef N<n> ev;
    static const int vl = n;
    static void print() { cout << vl << endl; }
  };

template<class N1>
  struct INC { typedef N<N1::ev::vl + 1> ev; };
template<class N1,class N2>
  struct MOD { typedef N<N1::ev::vl % N2::ev::vl> ev; };

template<class T1,class T2> struct _EQ      { typedef N<0> ev; };
template<class T>           struct _EQ<T,T> { typedef N<1> ev; };
template<class N1,class N2> struct EQ {
  typedef typename _EQ<typename N1::ev, typename N2::ev>::ev ev;
};

template<class _T> struct _NOT        { typedef N<0> ev; };
template<>         struct _NOT<N<0> > { typedef N<1> ev; };
template<class T>  struct NOT {
  typedef typename _NOT<typename T::ev>::ev ev;
};

template<class _C, class _T1,class _T2>
  struct _IF { typedef typename _T1::ev ev; };
template<class _T1,class _T2>
  struct _IF<N<0>,_T1,_T2> { typedef typename _T2::ev ev; };
template<class C,class T1,class T2>
  struct IF { typedef typename _IF<typename C::ev,T1,T2>::ev ev; };

struct Fizz {
  typedef Fizz ev;
  static void print() { cout << "Fizz" << endl; }
};
struct Buzz {
  typedef Buzz ev;
  static void print() { cout << "Buzz" << endl; }
};
struct FizzBuzz {
  typedef FizzBuzz ev;
  static void print() { cout << "FizzBuzz" << endl; }
};

template<class T>
  struct ConvFizzBuzz {
    typedef typename
      IF<NOT<MOD<T,N<15> > >, FizzBuzz,
      IF<NOT<MOD<T,N< 5> > >, Buzz,
      IF<NOT<MOD<T,N< 3> > >, Fizz,
                              T
    > > >::ev ev;
    static void print() { ev::print(); }
  };

struct FizzBuzzTerminal {
  typedef FizzBuzzTerminal ev;
  static void print() { }
};

template<class T1, class T2>
  struct FizzBuzzList {
    typedef FizzBuzzList<INC<T1>, T2> ev;
    typedef typename ConvFizzBuzz<T1>::ev vl;
    typedef typename
      IF<EQ<T1,T2>, FizzBuzzTerminal, FizzBuzzList<T1,T2> >::ev next;
    static void print() {
      vl::print();
      next::print();
    }
  };

int main()
{
  FizzBuzzList<N<0>, N<20> >::print();
}

あー疲れた。

ちなみに、このコードを作るのに要した時間は2時間。

ちゃんとしたプログラマであれば、これを実行するプログラムを2分とかからずに紙に書き出せるはずだ。怖い事実を聞きたい? コンピュータサイエンス学科卒業生の過半数にはそれができないのだ。自称上級プログラマが答えを書くのに10-15分もかかっているのを見たこともある。

どうしてプログラマに・・・プログラムが書けないのか?

orz

関連エントリー

• 剰余を使わずにFizzBuzz
• FizzBuzz問題をC++とFIFOLでやる
• C++テンプレートでLisp
• C++テンプレートは計算完備

*1:評価"eval"の略、Lispのエバるとはちょっとちがう

*2:実際には、「チューリング機械の停止性判定問題」を回避するために、再帰の回数を言語仕様で最低17回までに制限しているんだけども...

*3:だって終端記号なんだから他のものに変換しようがないんだもん