No Such Blog or Diary

八王子からの帰り，C++のテンプレートでコンパイル時にリストを使った計算をさせようとテンプレートでリストを表現する方法を考えていた．結論としては，値を直接使わずに，全てを型の上で処理してしまえばいい．ためしにリストを作って表示，foldr, map を書いてみた．まあ，int 限定にしているけど．一般化は容易でしょう．

#include <iostream>
using namespace std;
 
#define cons(x, y)      Cons< Int< x >, y >
#define nil             Nil
 
// nil  or []
struct Nil {};
 
// cons h t  or h:t
template <typename H, typename T>
struct Cons {
    typedef H head;
    typedef T tail;
};
 
// element of lists
template<int n>
struct Int{
    enum {val = n};
    static void print() { cout << n; }
};
 
// printer
template <typename L>
struct ListPrinter {
    static void print(){
        cout << '[';
        L::head::print();
        ListPrinter<typename L::tail>::print2();
        cout << ']';
    }
    static void print2(){
        cout << ',';
        L::head::print();
        ListPrinter<typename L::tail>::print2();
    }
};
template <>
struct ListPrinter<Nil> {
    static void print(){
        cout << '[' << ']';
    }
    static void print2(){
    }
};
 
// foldr function
// foldr f e [] = e
// foldr f e (h:t) = f h (foldr f e t)
// cons case:
template<template<typename,typename> class F, typename E, typename L >
struct Foldr{
    typedef typename F<typename L::head, typename  Foldr<F,E,typename L::tail>::val >::val val;
};
// nil case:
template<template<typename,typename> class F, typename E>
struct Foldr<F,E,Nil>{
    typedef E val;
};
 
// map function
// map f [] = []
// map f (h:t) = f h:(map f t)
// cons case:
template<template<typename> class F, typename L >
struct Map{
    typedef Cons< typename F<typename L::head>::val , typename Map<F, typename L::tail>::val> val;
};
// nil case:
template<template<typename> class F>
struct Map<F,Nil>{
    typedef Nil val;
};
 
//addition operator
template <typename X, typename Y>
struct Add {
    typedef Int<X::val + Y::val> val;
};
 
// zero
typedef Int<0> Zero;
 
//douoblring operator
template <typename X>
struct Double{
    typedef Int<X::val + X::val> val;
};
 
int main(int argc, char *argv[])
{
    typedef cons(4, cons(3, cons(2, cons(1, nil)))) l;
    typedef cons(5, l) l2;
    ListPrinter< l >::print();  cout << endl;
    ListPrinter< l2 >::print(); cout << endl;
     typedef Foldr<Add, Zero, l2>::val sum;
    sum::print(); cout << endl;
     typedef Map<Double, l2>::val l3;
    ListPrinter< l3 >::print(); cout << endl;
}

とまあ，考えてみたわけだけど，あとに別の用件で google で検索かけたらThe Boost C++ Metaprogramming Libraryとかいうものを見つけてしまった．boost に含まれいてるらしいが，上で考えたのと同じで全てを型で扱ってコンパイル時計算をしているらしい．いやぁ，やっぱ同じことを考える人はいるもんだなぁ．でも，こいつにはサイズに制限があるらしい（上限を上げるようにすればいいんだけど）．ということで，上の Cons/Nil は制限一切無いので捨てたもんじゃない（はず？）．

コンパイラが SGI の STL を満足にコンパイルできないのでしょうがなく string, pair, vector を自分で実装することに．vector は面倒なので arraylist にして実装，サイズは倍々にしか大きくなりません．string は char* のラッパクラスで pair はただのペアと．はじめからこうしておいたほうが速かったと本気で思う今日この頃．とはいえ，まだまだテンプレート周りでエラーでまくりだなぁ．

あほなコンパイラで SGI の STL をコンパイルしようと奮闘中．static_cast が無いから手前で用意してみたり，関数ポインタを返す関数がうまく解釈されないのでいろいろ書き方を変えてみたり．しまいにゃ「この関数使ってないから消してしまえ」で消しまくってみたり．いろいろやってみたけど何となくコンパイルは無理な気がしてきた…

友人曰く，gcc はテンプレート展開が遅いとのことで，VC++のコンパイラにて挑戦．しかし，なにやら何かがオーバーフローしたとかでコンパイルに失敗．しょうがないからインスタンス化されるTemplateのかずを減らすように全体を書き直し．

とりあえずジェネレータとできたやつ．これでも５時間1.3Gメモリで終わらない… やっぱTemplateでやるのは無謀だったのだろうか？　問題解決のひとつの方法は，最下位桁で分けて分割コンパイルすればいいのだけど…　何かそれも負けだよなぁと考える今日この頃．

覆面算のすべての条件分岐を Template で処理してしまうプログラムを考えた．ソースを書くのが面倒なのでソースジェネレータを書いて生成することに．とりあえず，ジェネレータとできたソースをおいておくとして…　Pen4 2.6C で８時間たってもコンパイルが終わらない…　メモリもすでに 1G 食ってるし．このソースをコンパイルできる環境ってどこかにあるのだろうか？　ちなみに，X*Y = ZZ という 4 進数での覆面算のプログラムは以下のとおり（答えなし）

#include <iostream>
using namespace std;
template <bool judge, typename T, typename F>
struct Selector{ typedef T val; };
 
template <typename T, typename F>
struct Selector<false, T, F>{   typedef F val; };
 
struct Nothing{ inline static void calc(){}};
 
template<unsigned int x, unsigned int y>
struct Printer{
  inline static void calc(){
    cout << x << " * " << y << " = " << x * y << endl;
    cout << y << " * " << x << " = " << x * y << endl;
  }
};
 
template<int x0, int y0>
struct Judge{
  const static bool val = ((x0==y0))&&((x0==y0))&& (x0!=0);};
 
template<int n, unsigned int x, unsigned int y, int x0, int x1, int x2, int x3>
struct Perms{   inline static void calc(){}};
 
template<unsigned int x, unsigned int y, int x0, int x1, int x2, int x3>
struct Perms<0, x, y, x0, x1, x2, x3>{
  inline static void calc(){
    Selector<true, Perms<1, x | (x0<< 0), y, x0, x1, x2, x3>, Nothing >::val::calc();
    Selector<true, Perms<1, x | (x1<< 0), y, x1, x0, x2, x3>, Nothing >::val::calc();
    Selector<true, Perms<1, x | (x2<< 0), y, x2, x1, x0, x3>, Nothing >::val::calc();
    Selector<true, Perms<1, x | (x3<< 0), y, x3, x1, x2, x0>, Nothing >::val::calc();
  }
};
template<unsigned int x, unsigned int y, int x0, int x1, int x2, int x3>
struct Perms<1, x, y, x0, x1, x2, x3>{
  inline static void calc(){
    Selector<(x0 > x1), Perms<2, x, y | (x1 << 0), x0, x1, x2, x3>, Nothing >::val::calc();
    Selector<(x0 > x2), Perms<2, x, y | (x2 << 0), x0, x2, x1, x3>, Nothing >::val::calc();
    Selector<(x0 > x3), Perms<2, x, y | (x3 << 0), x0, x3, x2, x1>, Nothing >::val::calc();
  }
};
template<unsigned int x, unsigned int y, int x0, int x1, int x2, int x3>
struct Perms<2, x, y, x0, x1, x2, x3>{
  inline static void calc(){
    Selector<(((x*y) >> 0)& 0x3) == x2, Perms<3, x, y, x0, x1, x2, x3>, Nothing >::val::calc();
    Selector<(((x*y) >> 0)& 0x3) == x3, Perms<3, x, y, x0, x1, x3, x2>, Nothing >::val::calc();
  }
};
template<unsigned int x, unsigned int y, int x0, int x1, int x2, int x3>
struct Perms<3, x, y, x0, x1, x2, x3>{
  inline static void calc(){
    Selector<Judge<(((x*y)>>2)&0x3), x3>::val, Printer<x,y>,Nothing>::val::calc();
  }
};
int main(int argc, char *argv[])
{
  cout << hex;
  Perms< 0, 0, 0, 0, 1, 2, 3>::calc();
}

順列を生成して出力するプログラムをかんがえる．んで，コンパイル時に順列を全生成して，その結果のみを出力するプログラムが最速である．なので，Template で順列を全生成して出力するプログラムを作ってみた．

とりあえず，ソースジェネレータと作られたソースをおいてみる…　コンパイルが激遅い…　ちなみに，生成された 3 の permutation のコードはこんなもん．

#include <iostream>
using namespace std;
template<int n, int x0, int x1, int x2>
struct Perms{   inline static void calc(){}
};
 
template<int x0, int x1, int x2>
struct Perms<0, x0, x1, x2>{
    inline static void calc(){
        Perms<1, x0, x1, x2>::calc();
        Perms<1, x1, x0, x2>::calc();
        Perms<1, x2, x1, x0>::calc();
    }
};
 
template<int x0, int x1, int x2>
struct Perms<1, x0, x1, x2>{
    inline static void calc(){
        Perms<2, x0, x1, x2>::calc();
        Perms<2, x0, x2, x1>::calc();
    }
};
 
template<int x0, int x1, int x2>
struct Perms<2, x0, x1, x2>{
    inline static void calc(){
        Perms<3, x0, x1, x2>::calc();
    }
};
 
template<int x0, int x1, int x2>
struct Perms<3, x0, x1, x2>{
    inline static void calc(){
        cout  << x0 << x1 << x2<<endl;
    }
};
 
int main(int argc, char *argv[])
{
    cout << hex;
    Perms< 0, 0, 1, 2>::calc();
}