18.2 Encoding Expressions in Template Arguments

Ru-Brd

The key to resolving our problem is not to attempt to evaluate part of an expression until the whole expression has been seen (in our example, until the assignment operator is invoked). Thus, before the evaluation we must record which operations are being applied to which objects. The operations are determined at compile time and can therefore be encoded in template arguments.

For our example expression

 1.2*x + x*y; 

this means that the result of 1.2*x is not a new array but an object that represents each value of x multiplied by 1.2 . Similarly, x*y must yield each element of x multiplied by each corresponding element of y . Finally, when we need the values of the resulting array, we do the computation that we stored for later evaluation.

Let's look at a concrete implementation. With this implementation we transform the written expression

 1.2*x + x*y; 

into an object with the following type:

 A_Add< A_Mult<A_Scalar<double>,Array<double> >,         A_Mult<Array<double>,Array<double> > > 

We combine a new fundamental Array class template with class templates A_Scalar , A_Add , and A_Mult . You may recognize a prefix representation for the syntax tree corresponding to this expression (see Figure 18.1). This nested template-id represents the operations involved and the types of the objects to which the operations should be applied. A_Scalar is presented later but is essentially just a placeholder for a scalar in an array expression.

Figure 18.1. Tree representation of expression 1.2*x+x*y

graphics/18fig01.gif

18.2.1 Operands of the Expression Templates

To complete the representation of the expression, we must store references to the arguments in each of the A_Add and A_Mult objects and record the value of the scalar in the A_Scalar object (or a reference thereto). Here are possible definitions for the corresponding operands:

  // exprtmpl/exprops1.hpp  #include <stddef.h>  #include <cassert>  // include helper class traits template to select wether to refer to an   // ''expression template node'' either ''by value'' or ''by reference.''  #include "exprops1a.hpp"  // class for objects that represent the addition of two operands  template <typename T, typename OP1, typename OP2>  class A_Add {    private:      typename A_Traits<OP1>::ExprRef op1;  // first operand  typename A_Traits<OP2>::ExprRef op2;  // second operand  public:  // constructor initializes references to operands  A_Add (OP1 const& a, OP2 const& b)       : op1(a), op2(b) {      }  // compute sum when value requested  T operator[] (size_t idx) const {          return op1[idx] + op2[idx];      }  // size is maximum size  size_t size() const {          assert (op1.size()==0  op2.size()==0                   op1.size()==op2.size());          return op1.size()!=0 ? op1.size() : op2.size();      }  };  // class for objects that represent the multiplication of two operands  template <typename T, typename OP1, typename OP2>  class A_Mult {    private:      typename A_Traits<OP1>::ExprRef op1;  // first operand  typename A_Traits<OP2>::ExprRef op2;  // second operand  public:  // constructor initializes references to operands  A_Mult (OP1 const& a, OP2 const& b)       : op1(a), op2(b) {      }  // compute product when value requested  T operator[] (size_t idx) const {          return op1[idx] * op2[idx];      }  // size is maximum size  size_t size() const {          assert (op1.size()==0  op2.size()==0                   op1.size()==op2.size());          return op1.size()!=0 ? op1.size() : op2.size();      }  }; 

As you can see, we added subscripting and size-querying operations that allow us to compute the size and the values of the elements for the array resulting from the operations represented by the subtree of "nodes" rooted at the given object.

For operations involving arrays only, the size of the result is the size of either operand. However, for operations involving both an array and a scalar, the size of the result is the size of the array operand. To distinguish array operands from scalar operands, we define a size of zero for scalars. The A_Scalar template is therefore defined as follows :

  // exprtmpl/exprscalar.hpp   // class for objects that represent scalars  template <typename T>  class A_Scalar {    private:      T const& s;  // value of the scalar  public:  // constructor initializes value  A_Scalar (T const& v)       : s(v) {      }  // for index operations the scalar is the value of each element  T operator[] (size_t) const {          return s;      }  // scalars have zero as size  size_t size() const {          return 0;      };  }; 

Note that scalars also provide an index operator. Inside the expression, they represent an array with the same scalar value for each index.

You probably saw that the operator classes used a helper class A_Traits to define the members for the operands:

 typename A_Traits<OP1>::ExprRef op1;  // first operand  typename A_Traits<OP2>::ExprRef op2;  // second operand  

This is necessary because of the following: In general, we can declare them to be references because most temporary nodes are bound in the top-level expression and therefore live until the end of the evaluation of that complete expression. The one exception are the A_Scalar nodes. They are bound within the operator functions and might not live until the end of the evaluation of the complete expression. Thus, to avoid that the members refer to scalars that don't exist anymore, for scalars the operands have to get copied "by value." In other words, we need members that are

  • constant references in general:

     OP1 const& op1;  // refer to first operand by reference  OP2 const& op2;  // refer to second operand by reference  
  • but ordinary values for scalars:

     OP1 op1;  // refer to first operand by value  OP2 op2;  // refer to second operand by value  

This is a perfect application of traits classes. The traits class defines a type to be a constant reference in general, but an ordinary value for scalars:

  // exprtmpl/exprops1a.hpp  /  * helper traits class to select how to refer to an ''expression template node''   * - in general: by reference   * - for scalars: by value   *  /  template <typename T> class A_Scalar;  // primary template  template <typename T>  class A_Traits {    public:      typedef T const& ExprRef;  // type to refer to is constant reference  };  // partial specialization for scalars  template <typename T>  class A_Traits<A_Scalar<T> > {    public:      typedef A_Scalar<T> ExprRef;  // type to refer to is ordinary value  }; 

Note that since A_Scalar objects refer to scalars in the top-level expression, those scalars can use reference types.

18.2.2 The Array Type

With our ability to encode expressions using lightweight expression templates, we must now create an Array type that controls actual storage and that knows about the expression templates. However, it is also useful for engineering purposes to keep as similar as possible the interface for a real array with storage and one for a representation of an expression that results in an array. To this end, we declare the Array template as follows:

 template <typename T, typename Rep = SArray<T> >  class Array; 

The type Rep can be SArray if Array is a real array of storage, [1] or it can be the nested template-id such as A_Add or A_Mult that encodes an expression. Either way we are handling Array instantiations , which considerably simplify our later dealings. In fact, even the definition of the Array template needs no specializations to distinguish the two cases, although some of the members cannot be instantiated for types like A_Mult substituted for Rep .

[1] It is convenient to reuse the previously developed SArray here, but in an industrial-strength library, a special-purpose implementation may be preferable because we won't use all the features of SArray .

Here is the definition. The functionality is limited roughly to what was provided by our SArray template, although once the code is understood , it is not hard to add to that functionality:

  // exprtmpl/exprarray.hpp  #include <stddef.h>  #include <cassert>  #include "sarray1.hpp"  template <typename T, typename Rep = SArray<T> >  class Array {    private:      Rep expr_rep;  // (access to) the data of the array  public:  // create array with initial size  explicit Array (size_t s)       : expr_rep(s) {      }  // create array from possible representation  Array (Rep const& rb)       : expr_rep(rb) {      }  // assignment operator for same type  Array& operator= (Array const& b) {          assert(size()==b.size());          for (size_t idx = 0; idx<b.size(); ++idx) {              expr_rep[idx] = b[idx];          }          return *this;      }  // assignment operator for arrays of different type  template<typename T2, typename Rep2>      Array& operator= (Array<T2, Rep2> const& b) {          assert(size()==b.size());          for (size_t idx = 0; idx<b.size(); ++idx) {              expr_rep[idx] = b[idx];          }          return *this;      }  // size is size of represented data  size_t size() const {          return expr_rep.size();      }  // index operator for constants and variables  T operator[] (size_t idx) const {          assert(idx<size());          return expr_rep[idx];      }      T& operator[] (size_t idx) {          assert(idx<size());          return expr_rep[idx];      }  // return what the array currently represents  Rep const& rep() const {          return expr_rep;      }      Rep& rep() {          return expr_rep;      }  }; 

As you can see, many operations are simply forwarded to the underlying Rep object. However, when copying another array, we must take into account the possibility that the other array is really built on an expression template. Thus, we parameterize these copy operations in terms of the underlying Rep representation.

18.2.3 The Operators

We have most of the machinery in place to have efficient numeric operators for our numeric Array template, except the operators themselves . As implied earlier, these operators only assemble the expression template objects ”they don't actually evaluate the resulting arrays.

For each ordinary binary operator we must implement three versions: array-array, array-scalar, and scalar-array. To be able to compute our initial value we need, for example, the following operators:

  // exprtmpl/exprops2.hpp   // addition of two  Array  s  template <typename T, typename R1, typename R2>  Array<T,A_Add<T,R1,R2> >  operator+ (Array<T,R1> const& a, Array<T,R2> const& b) {      return Array<T,A_Add<T,R1,R2> >             (A_Add<T,R1,R2>(a.rep(),b.rep()));  }  // multiplication of two  Array  s  template <typename T, typename R1, typename R2>  Array<T, A_Mult<T,R1,R2> >  operator* (Array<T,R1> const& a, Array<T,R2> const& b) {      return Array<T,A_Mult<T,R1,R2> >             (A_Mult<T,R1,R2>(a.rep(), b.rep()));  }  // multiplication of scalar and  Array  template <typename T, typename R2>  Array<T, A_Mult<T,A_Scalar<T>,R2> >  operator* (T const& s, Array<T,R2> const& b) {      return Array<T,A_Mult<T,A_Scalar<T>,R2> >             (A_Mult<T,A_Scalar<T>,R2>(A_Scalar<T>(s), b.rep()));  }  // multiplication of  Array  and scalar   // addition of scalar and  Array  // addition of  Array  and scalar    

The declaration of these operators is somewhat cumbersome (as can be seen from these examples), but the functions really don't do much. For example, the plus operator for two arrays first creates an A_Add<> object that represents the operator and the operands

 A_Add<T,R1,R2>(a.rep(),b.rep()) 

and wraps this object in an Array object so that we can use the result as any other object that represents data of an array:

 return Array<T,A_Add<T,R1,R2> > (   ); 

For scalar multiplication, we use the A_Scalar template to create the A_Mult object

 A_Mult<T,A_Scalar<T>,R2>(A_Scalar<T>(s), b.rep()) 

and wrap again:

 return Array<T,A_Mult<T,A_Scalar<T>,R2> > (   ); 

Other nonmember binary operators are so similar that macros can be used to cover most operators with relatively little source code. Another (smaller) macro could be used for nonmember unary operators.

18.2.4 Review

On first discovery of the expression template idea, the interaction of the various declarations and definitions can be daunting. Hence, a top-down review of what happens with our example code may help crystallize understanding. The code we will analyze is the following (you can find it as part of meta/exprmain.cpp ):

 int main()  {      Array<double> x(1000), y(1000);   x = 1.2*x + x*y;  } 

Because the Rep argument is omitted in the definition of x and y , it is set to the default, which is SArray<double> . So, x and y are arrays with "real" storage and not just recordings of operations.

When parsing the expression

 1.2*x + x*y 

the compiler first applies the leftmost * operation, which is a scalar-array operator. Overload resolution thus selects the scalar-array form of operator* :

 template <typename T, typename R2>  Array<T, A_Mult<T,A_Scalar<T>,R2> >  operator* (T const& s, Array<T,R2> const& b) {      return Array<T,A_Mult<T,A_Scalar<T>,R2> >             (A_Mult<T,A_Scalar<T>,R2>(A_Scalar<T>(s), b.rep()));  } 

The operand types are double and Array<double, SArray<double> > . Thus, the type of the result is

 Array<double, A_Mult<double, A_Scalar<double>, SArray<double> > > 

The result value is constructed to reference an A_Scalar<double> object constructed from the double value 1.2 and the SArray<double> representation of the object x .

Next, the second multiplication is evaluated: It is an array-array operation x*y . This time we use the appropriate operator* :

 template <typename T, typename R1, typename R2>  Array<T, A_Mult<T,R1,R2> >  operator* (Array<T,R1> const& a, Array<T,R2> const& b) {      return Array<T,A_Mult<T,R1,R2> >             (A_Mult<T,R1,R2>(a.rep(), b.rep()));  } 

The operand types are both Array<double, SArray<double> > , so the result type is

 Array<double, A_Mult<double, SArray<double>, SArray<double> > > 

This time the wrapped A_Mult object refers to two SArray<double> representations: the one of x and the one of y .

Finally, the + operation is evaluated. It is again an array-array operation, and the operand types are the result types that we just deduced . So, we invoke the array-array operator + :

 template <typename T, typename R1, typename R2>  Array<T,A_Add<T,R1,R2> >  operator+ (Array<T,R1> const& a, Array<T,R2> const& b) {      return Array<T,A_Add<T,R1,R2> >             (A_Add<T,R1,R2>(a.rep(),b.rep()));  } 

T is substituted with double whereas R1 is substituted with

 A_Mult<double, A_Scalar<double>, SArray<double> > 

and R2 is substituted with

 A_Mult<double, SArray<double>, SArray<double> > 

Hence, the type of the expression to the right of the assignment token is

 Array<double,        A_Add<double,              A_Mult<double, A_Scalar<double>, SArray<double> >,              A_Mult<double, SArray<double>, SArray<double>>>> 

This type is matched to the assignment operator template of the Array template:

 template <typename T, typename Rep = SArray<T> >  class Array {    public:    // assignment operator for arrays of different type  template<typename T2, typename Rep2>      Array& operator= (Array<T2, Rep2> const& b) {          assert(size()==b.size());          for (size_t idx = 0; idx<b.size(); ++idx) {              expr_rep[idx] = b[idx];          }          return *this;      }   }; 

The assignment operator computes each element of the destination x by applying the subscript operator to the representation of the right side, the type of which is

 A_Add<double,        A_Mult<double, A_Scalar<double>, SArray<double> >,        A_Mult<double, SArray<double>, SArray<double> > > > 

Carefully tracing this subscript operator shows that for a given subscript idx , it computes

 (1.2*x[idx]) + (x[idx]*y[idx]) 

which is exactly what we want.

18.2.5 Expression Templates Assignments

It is not possible to instantiate write operations for an array with a Rep argument that is built on our example A_Mult and A_Add expression templates. (Indeed, it makes no sense to write a+b = c .) However, it is entirely reasonable to write other expression templates for which assignment to the result is possible. For example, indexing with an array of integral values would intuitively correspond to subset selection. In other words, the expression

 x[y] = 2*x[y]; 

should mean the same as

 for (size_t idx = 0; idx<y.size(); ++idx) {      x[y[idx]] = 2*x[y[idx]];  } 

Enabling this implies that an array built on an expression template behaves like an lvalue (that is, is "writable"). The expression template component for this is not fundamentally different from, say, A_Mult , except that both const and non- const versions of the subscript operators are provided and they return lvalues (references):

  // exprtmpl/exprops3.hpp  template<typename T, typename A1, typename A2>  class A_Subscript {    public:  // constructor initializes references to operands  A_Subscript (A1 const & a, A2 const & b)       : a1(a), a2(b) {      }  // process subscription when value requested  T operator[] (size_t idx) const {          return a1[a2[idx]];      }      T& operator[] (size_t idx) {          return a1[a2[idx]];      }  // size is size of inner array  size_t size() const {          return a2.size();      }    private:      A1 const & a1;  // reference to first operand  A2 const & a2;  // reference to second operand  }; 

The extended subscript operator with subset semantics that was suggested earlier would require that additional subscript operators be added to the Array template. One of these operators could be defined as follows (a corresponding const version would presumably also be needed):

  // exprtmpl/exprops4.hpp  template<typename T, typename R1, typename R2>  Array<T,A_Subscript<T,R1,R2> >  Array<T,R1>::operator[] (Array<T,R2> const & b) {      return Array<T,A_Subscript<T,R1,R2> >             (A_Subscript<T,R1,R2>(a.rep(),b.rep()));  } 
Ru-Brd


C++ Templates
C++ Templates: The Complete Guide
ISBN: 0201734842
EAN: 2147483647
Year: 2002
Pages: 185

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net