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
18.2.1 Operands of the Expression TemplatesTo 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
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 TypeWith 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 .
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 OperatorsWe 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 ReviewOn 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 AssignmentsIt 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 |