2005年10月

自由変数のないラムダ式を S, K, I のコンビネータで記述するためのプログラムを書いてみた．演習の課題で S,K,I 以外のコンビネータを S,K,I で書けという問題があるそうだけどそんなのはプログラムでやるものだし（Bなんか手でやる気がしない）．んで，毎度のごとく Haskell でコンパクトに．

data LExp = Lambda (Int, LExp)
          | Apply  (LExp, LExp)
          | Var    Int
          | S
          | K
          | I
ctc (Lambda (x, exp)) = let exp' = ctc exp in (ctc' exp' x)
  where
  ctc' (Apply (exp1, exp2)) x = Apply (Apply (S, ctc' exp1 x), ctc' exp2 x)
  ctc' (Var y) x = if y == x then I else Apply (K, Var y)
  ctc' l x = Apply (K, l)
ctc (Apply (exp1, exp2)) = Apply (ctc exp1, ctc exp2)
ctc x = x

ラムダ式 LExp はλ抽象，適用，変数と，コンビネータ S, K, I で．コンパイル自体はλ抽象を内側からコンビネータに変換していくだけ．変換はアプリケーションに関しては S にして，変数に関しては束縛されるなら I, そうでないなら K.

折角なのでコンビネータからラムダ式への変換（alpha変換, beta簡約）も書いて知ってるコンビネータも全部書いてみた CompileToCombinators.hs .

C++ のテンプレートでテンプレート引数に関数ポインタが指定されたときだけ挙動を変えたい．でもやり方が良くわからない...　ポインタかどうかの判定法は知ってるが，関数ポインタか否かはどうすれば？

動作に全く違いのない二つのプログラムに結構な速度差が出てるから原因はなんだろうとしばし悩む．プログラムの動作はまったく同じなのに...　んでよく見てみたら vector の型がちと違っていた．vector<int> で使ってるほうが速く，vector<bool> が遅かった．キャッシュに乗り切ってしまうサイズだったし int でのアクセスのほうが機械にやさしかったと．こんなんで倍速くなるとは少々驚きの結果だった．

でいくのはいいとして，再帰のベースケースだけを rank に応じて分けて計算し，最後に結果をマージして全プロセッサに結果を丸ごと持たせると...　結局スピードアップしかしないのね．メモリ消費量は下げられないし．これで通信量が大丈夫なのかと気にもなるけど実際外側が再帰してしまうとこれ以外の解決法が無いような．あとはコピー量を減らすか...

MPI使ってるときにルートプロセスだけ cout で情報を出力するように cout をのっとってみた．副作用として iomanip がどうやって処理されているかを身をもって知る羽目になった（一番下のテンプレート定義だけだとうまくコンパイルできなかった...）

class myOstream : public std::ostream {
 public:
  // for iomanip
  myOstream&
  operator<<(__ostream_type& (*manip)(__ostream_type&
    if(rank==0) std::cout << manip;
    return *this;
  }
  myOstream&
  operator<<(__ios_type& (*manip)(__ios_type&)){
    if(rank==0) std::cout << manip;
    return *this;
  }
  myOstream&
    operator<<(ios_base& (*manip) (ios_base&)){
    if(rank==0) std::cout << manip;
    return *this;
  }
  // for other types
  template <typename C>
  myOstream& operator<<(const C&v){
    if(rank==0) std::cout << v;
    return *this;
  }
};
muOstream cout;

型を決定できないのかねぇ．ちゃんと書いといてやらんと．