ETの考え方とその簡単な実装

id:Cryolite:20040506#p2より続きます．
今日はETの基本的な考え方とその簡単な実装について書きます．
ETの鍵となる考え方は，式の中に現れる各演算の結果をそのつど計算するのではなく，各演算を表す小さなオブジェクトを順々に生成していくことにあります．例えば，今Vectorのオブジェクトuとvがあったときに，u + vという式が演算の結果を返すのではなく，uとvの加算である，ということを表すオブジェクトを返すことにするのです．このオブジェクトは例えば以下のように書くことが出来ます．

template
class VectorAdd{
  L const & l;
  R const & r;

public:
  VectorAdd(L const & lhs, R const & rhs)
    : l(lhs)
    , r(rhs)
  {
    assert(l.dim() == r.dim());
  }
  ... // その他の実装．すぐ後で完全なものを書きます．
};

何故，このクラスがテンプレートなのかは後ですぐに分かります．取り合えず，このクラスは+という演算子そのものを意味し，+の左側の式の型がLで右側の式の型がR，lとrはその式への参照を保持することで+という演算そのものを表現するのだという理解で良いです．
そして，u + vという演算が実際に計算を行うのではなく，単に上のクラスのオブジェクトを返すだけにしてしまいます．
そのために，まずVectorクラスのメンバ関数であるoperator+を削除し，代わりに非メンバ関数のoperator+を以下のように定義してしまいます．

// 注意：実際にはこのような関数テンプレートをグローバルに定義するのは
// 滅茶苦茶まずいのですが，ここでは話を簡単にするためにこうします．
// このことに関する議論は後回しにします．
template
inline
VectorAdd
operator+(L const & l, R const & r)
{
  return VectorAdd(l, r);
}

この関数を定義することによって，u + vという演算がVectorAdd(u, v)という小さなオブジェクトを返すだけになり，これがuとvの加算であるということを記録しています．
で次に，ベクトル同士の加算の結果はやはりベクトルですから，VectorAddは次元がいくらであるとか，第i番目の要素の値がいくらであるかなどに答えなければならないです．従って，VectorAddの他のメンバ関数を定義しなければなりません．VectorAddの他のメンバ関数は以下のように定義できます．

// VectorAddの完全な実装
template
class VectorAdd{
  L const & l;
  R const & r;

public:
  VectorAdd(L const & lhs, R const & rhs)
    : l(lhs)
    , r(rhs)
  {
    assert(l.dim() == r.dim());
  }

  double operator[](size_t i) const
  {
    return l[i] + r[i];
  }

  size_t dim() const
  {
    return l.dim();
  }
};

operator[]の実装は，u + vのi番目の要素がu[i] + v[i]であることをきちんと反映しています．つまり，(u + v)[i]と書けば，それはu[i] + v[i]を意味するようになっています．u + vの次元は，u（あるいはv）と等しく，uとvの次元が等しいことはVectorAddの生成時にassertしているので，単に左側のuの次元を返せば良いだけです．dim()の実装はそれを反映しています．
このVectorAddにはVectorクラスにあるような，代入演算子は必要ないです．それは，このVectorAddが常に右辺値（要するに読み取り専用）として使われることを意図しているからです．これは例えばu + v = w;という書き方に必要性が感じられない（し適切な実装を思いつかない）ことから分かります．
さて，次はu + vによって生成されたオブジェクトをVectorのオブジェクトに代入することを考えます．そのために，Vectorクラスにメンバ関数を追加します．

class Vector{
...
// これもまた非常によろしくない（というかやってはいけない）実装ですが
// 簡単にするためにこうしておきます．
  template
  Vector & operator=(E const & rhs)
  {
    for(size_t i = 0; i < n; ++i){
      val[i] = rhs[i];
    }
    return *this;
  }
...
};

これで，ベクトルの加算に対するETの実装は終わりです．では，実際にw = u + v;という式がどのように評価されていくかを見ていきます．
まず，u + vという式はVectorAdd(u, v)によって，VectorAddのオブジェクトを返します．

w = VectorAdd(u, v);

これはさっき定義したVectorクラスの代入演算子によって，以下のように評価されます．

for(size_t i = 0; i < n; ++i){
  w[i] = VectorAdd(u, v)[i];
}

さらに，VectorAddのoperator[]の定義によって，結局w = u + vは以下のように評価されます．

for(size_t i = 0; i < n; ++i){
  w[i] = u[i] + v[i];
}

求めていた，overheadの無いベクトルの加算の書き方になっていることが分かると思います．
さて，次にt = u + v + w;のような，2つ以上の加算が続いた場合を考えなければならないのですが，実はこれに対する実装はすでに上にあるものだけで足りてしまっています．
さきと同じく，t = u + v + w;がどのように評価されるか，順を追って見ていきます．
まず，最初にu + vが評価され，VectorAdd(u, v)によって，VectorAddのオブジェクトが生成されます．

t = VectorAdd(u, v) + w;

次に，VectorAdd(u, v) + wが評価されますが，ここでoperator+とVectorAddをテンプレートにした意味が生きてきます．
VectorAdd(u, v) + wは，L = VectorAdd, R = Vectorとして，再びoperator+によって評価され，VectorAdd, Vector>(VectorAdd(u, v), w)を返します．

t = VectorAdd, Vector>(VectorAdd(u, v), w);

このような，テンプレートが再帰した構造を伴うところがETの強烈なところです．この構造はu + v + wに対応する以下のような構文木

を，再帰的なテンプレートによって以下のようにエンコードしたものと考えることも出来ます．

（っていうか，ここって画像表示できるのね・・・）
最後に，Vectorクラスの代入演算子によってwにVectorAdd, Vector>のオブジェクトが代入されます．

// 面倒なのでテンプレート引数は省略して書きます
for(size_t i = 0; i < n; ++i){
  w[i] = VectorAdd(VectorAdd(u, v), w)[i];
}

これはVectorAddのoperator[]の定義により，まず以下のようになります．

for(size_t i = 0; i < n; ++i){
  w[i] = VectorAdd(u, v)[i] + w[i];
}

さらにもう一段，VectorAddのoperator[]が適用されて，結局，以下のように評価されます．

for(size_t i = 0; i < n; ++i){
  w[i] = u[i] + v[i] + w[i]
}

この場合も，求めていた形の実装に落ち着くことが分かります．
最後に，加算と同様，スカラー倍もETが使えるように，Vectorのメンバ関数だったoperator*とfriend宣言を削除して，以下のようなスカラー倍を表現するクラスと大域のoperator*を定義します．

template
class ScalarMult{
  L l; // scalar
  R const & r; // vector

public:
  ScalarMult(L lhs, R const & rhs)
    : l(lhs)
    , r(rhs)
  {
  }

  double operator[](size_t i) const
  {
    return l * r[i];
  }

  size_t dim() const
  {
    return r.dim();
  }
};

// スカラーが左からかかる場合
template
inline
ScalarMult
operator*(double k, R const & v)
{
  return ScalarMult(k, v);
}

// スカラーが右からかかる場合
// っていうか，かなり苦し紛れの実装・・・
template
inline
ScalarMult
operator*(L const & v, double k)
{
  return ScalarMult(k, v);
}

以上で，加算とスカラー倍をETによって提供したVectorクラスが出来ました．
具体的なコードはこれです．勝手に取っていってもらってかまいません．
それでは，次回はこの簡単なETの実装の効果を検証してみたいと思います．
id:Cryolite:20040510#p2へ続きます．