Contents:
Introduction
On the Surface
Under the Hood
Summary
Source Files
RGB.h
RGBDefs.in
RGB.cpp
Introduction
This tutorial shows how to use PETE to perform non-arithmetic operations on a program as it is being compiled, and in particular how to synthesize new types and values by extending PETE's specialized templates and operator overloadings. The problem domain is the three primary colors---red, green, and blue---which are combined according to three simple rules:
The source files for this example are included in the examples/RGB directory of the PETE distribution. These files are:
PETE was created to make it easy for programmers to extend expression templates. In particular, PETE lets programmers specify a wide range of computations that are to be carried out as the program is being compiled. To do this, the programmer must provide three things: the type(s) of object(s) to be operated on, the functor(s) to be used to extract values from those objects, and the combiner(s) to be used to process those values.
In our example, the values being manipulated are the three primary colors red, green, and blue. Each color is represented by an empty tag class, whose only purpose is to act as a strongly-typed placeholder as the compiler is instantiating templates. The three classes are defined at the top of RGB.h:
017 struct Red { }; 018 struct Green { }; 019 struct Blue { };
Our example defines a single functor, called GetColor. Like Red, Green, and Blue, GetColor is an empty class, no instances of which are ever actually created by a running program.
In addition, RGB.h defines one more empty tag class, called ColorCombine. This tag is used to signal to the compiler that we are combining colors, rather than (for example) adding vectors. The two definitions are:
020 struct GetColor { }; 021 struct ColorCombine { };
We have one more empty class to define in order to begin building our computational framework. The class Operand<> serves as a wrapper around color expressions; its purpose is to identify those expressions by giving them a well-known overall type. Operand<> is therefore similar to the generic PETE expression class Expression<>, which is used to distinguish PETE expressions from other types of expressions. In our case, the Operand<> class is used only to wrap up a color expression:
109 template<class ColorTag> 110 struct Operand 111 { // body is empty 112 };
We must now tell PETE how to store an Operand<> value in the leaf of an expression tree. The required definition is:
119 template<class ColorTag> 120 struct CreateLeaf<Operand<ColorTag> > 121 { 122 typedef Operand<ColorTag> Leaf_t; 123 inline static 124 const Leaf_t &make(const Operand<ColorTag> &a) { return a; } 125 };
Note how the formal class name used in the template header, ColorTag, appears as an argument to Operand<> in the formal parameter list of the CreateLeaf<> specialization. This ensures that our definition only applies to properly-formed Operand<>s.
Note also the typedef inside this specialization of CreateLeaf<>. PETE's template specialization rules require every specialization of CreateLeaf<> to have a typedef called Leaf_t, which specifies the type of the leaf node. This is also the declared return type of the static method make(), which constructs a leaf node given an actual object (in this case, a color class instance).
CreateLeaf<> tells PETE how to store values in leaf nodes; specializations of LeafFunctor<> tell PETE how to apply a user-defined functor to those nodes to obtain a value. As before, we template our specialization of LeafFunctor<> on a formal parameter that will be filled in with a color class, but then nest that formal parameter inside Operand<> in order to ensure that the compiler only tries to use this specialization of LeafFunctor<> on the right kinds of expressions.
LeafFunctor<> takes a second template parameter, which is the functor that is being applied to the leaf node. In our case, we have defined only one functor on colors, namely GetColor. Our specialization is therefore:
132 template<class Color> 133 struct LeafFunctor<Operand<Color>, GetColor> 134 { 135 typedef Color Type_t; 136 };
Unlike the LeafFunctor<> specializations in previous tutorials, notice that this version does not have an apply() method. The reason is that we're using this functor only for compile-time type calculations. We're never going to call apply() so we therefore don't need to go to the trouble of defining it.
Our last task is to define some specializations of Combine2<>, the combiner that PETE uses to operate on values in binary expressions. Six specializations are defined, for each possible ordered combination of different color values. The combiner for Red and Green is:
063 template<class Op> 064 struct Combine2<Red, Green, Op, ColorCombine> 065 { 066 typedef Blue Type_t; // not required inline static // not required Type_t combine(Red, Green, Op, ColorCombine) // not required { // not required return Blue(); // not required } 067 };
The generic form of Combine2<> takes four template parameters: the classes of its operands, a tag identifying the C++ operator from which the expression was created (such as OpAdd or OpMultiply), and a user-defined tag, which can be used to force the compiler to calculate a different expression than the one apparently specified. In the case of this example, the first two parameters specify the colors being combined, while the last parameter signals that these values are being combined according to our own rules. This is the only use for ColorCombine. The formal template parameter Op is not referenced anywhere in this class, so that any binary operation on colors, including addition, multiplication, bitwise OR, or left shift, will use the user-defined rules.
Combiners typically have two elements: a type Type_t that gives the type of object formed by combining the operands and a combine methods that takes the operands and does whatever is necessary to produce a Type_t object. Like the LeafFunctor<> specialization above, we don't need the combine method here since we're synthesizing types. However, we've shown what this function would look like if it were necessary to define it.
We can now test that our definitions do the right thing by defining three functions to print out the color of an expression involving colors. The function for Red takes a constant reference to a Red object, and prints a simple string:
027 inline void calc(const Red &) 028 { 029 cout << "This expression is red." << endl; 030 }
The other two overloadings of this function, which are defined on lines 32-40 for the tag classes Green and Blue, print out "green" and "blue" instead of "red".
Finally, the templated function printColor<>() takes an expression, evaluates it during compilation by forcing the compiler to expand the expression using our GetColor and ColorCombine tags, and then uses the deduced color of the expression to select a version of calc(), which prints out that color's name. The whole definition is:
048 template <class Expr> 049 void printColor(const Expression<Expr> &expr) 050 { 051 typedef typename ForEach<Expression<Expr>, GetColor, ColorCombine>::Type_t 052 DeducedColor_t; 053 054 calc(DeducedColor_t()); 055 }
It is worth looking at this function definition closely. The
expansion of CreateLeaf<>::Leaf_t extracts and formats
the type of the expression according to our color-based evaluation
rules. The expansion of the PETE-defined template
ForEach<> does most of the work. During its expansion,
the functor and combiner tags are passed down the parse tree. They are
used to extract types from the leaves of the parse tree. These types
are combined at non-leaf nodes to produce new types, which are passed
up the parse tree. The result is a type---Red, Green,
or Blue---that is labelled by DeducedColor_t. This
type, in turn, triggers instantiation of an appropriate version of
calc().
Under the Hood
Let's take a closer look at exactly what happens when printColor() is instantiated with a color expression, as it is at the start of the test program in RGB.cpp:
005 printColor(Operand<Red>() + Operand<Green>());
Let's start with the automatically-generated operator overloadings in RGBOperators.h, which are created using the MakerOperators tool described in the first tutorial. The overloading for operator+ is:
618 template<class T1,class T2> 619 inline typename MakeReturn<BinaryNode<OpAdd, 620 typename CreateLeaf<Operand<T1> >::Leaf_t, 621 typename CreateLeaf<Operand<T2> >::Leaf_t, 622 StoreByRefTag> >::Expression_t 623 operator+(const Operand<T1> & l,const Operand<T2> & r) 624 { 625 typedef BinaryNode<OpAdd, 626 typename CreateLeaf<Operand<T1> >::Leaf_t, 627 typename CreateLeaf<Operand<T2> >::Leaf_t, 628 StoreByRefTag> Tree_t; 629 return MakeReturn<Tree_t>::make(Tree_t( 630 CreateLeaf<Operand<T1> >::make(l), 631 CreateLeaf<Operand<T2> >::make(r))); 632 }
Once again, there is less going on here than first meets the eye. We are trying to perform computations using C++ template notation, a job for which that notation was not designed. The first things to look at are the uses of CreateLeaf<>::Leaf_t. As we saw above, in the case of an Operand<> with a color type argument, Leaf_t is just the color type argument wrapped in an Operand<> type; the CreateLeaf<> indirection is provided to give programmers a hook for doing other things if they so desire. This means that we can simplify the code above as:
618 template<class T1,class T2> 619 inline typename MakeReturn<BinaryNode<OpAdd, 620 Operand<T1>, 621 Operand<T2>, 622 StoreByRefTag> >::Expression_t 623 operator+(const Operand<T1> & l,const Operand<T2> & r) 624 { 625 typedef BinaryNode<OpAdd, 626 Operand<T1>, 627 Operand<T2>, 628 StoreByRefTag> Tree_t; 629 return MakeReturn<Tree_t>::make(Tree_t( 630 CreateLeaf<Operand<T1> >::make(l), 631 CreateLeaf<Operand<T2> >::make(r))); 632 }
By referring back to the arguments of printColor(), we can replace T1 with Red, and T2 with Green:
619 inline typename MakeReturn<BinaryNode<OpAdd, 620 Operand<Red>, 621 Operand<Green>, 622 StoreByRefTag> >::Expression_t 623 operator+(const Operand<Red> & l,const Operand<Green> & r) 624 { 625 typedef BinaryNode<OpAdd, 626 Operand<Red>, 627 Operand<Green>, 628 StoreByRefTag> Tree_t; 629 return MakeReturn<Tree_t>::make(Tree_t( 630 CreateLeaf<Operand<Red> >::make(l), 631 CreateLeaf<Operand<Green> >::make(r))); 632 }
Looking back at CreateLeaf<> once more, we see that its make() method simply returns its argument. (In the case of STL containers, make() could return an iterator over its argument.) Our operator thus becomes simpler still:
619 inline typename MakeReturn<BinaryNode<OpAdd, 620 Operand<Red>, 621 Operand<Green>, 622 StoreByRefTag> >::Expression_t 623 operator+(const Operand<Red> & l,const Operand<Green> & r) 624 { 625 typedef BinaryNode<OpAdd, 626 Operand<Red>, 627 Operand<Green>, 628 StoreByRefTag> Tree_t; 629 return MakeReturn<Tree_t>::make(Tree_t(l, r)); 632 }
To simplify this further, we must turn to the definition of MakeReturn<> in PETE's CreateLeaf.h:
136 template<class T> 137 struct MakeReturn 138 { 139 typedef Expression<T> Expression_t; 140 inline static 141 Expression_t make(const T &a) { return Expression_t(a); } 142 };
The default expansion of MakeReturn<T>::Expression_t is simply Expression<T>, and MakeReturn<>'s make() method just returns its argument, appropriately typed. This may seem unnecessary, but as the PETE header files themselves explain:
MakeReturn<> is used to wrap expression objects (UnaryNode<>, BinaryNode<> etc.) inside an Expression<> object. Usually this indirection is unnecessary, but the indirection allows users to specify their own approach to storing trees. By specializing MakeReturn<UnaryNode<>>, MakeReturn<BinaryNode<>>, etc. you could cause the expression trees to be stored in another format. For example, POOMA stores expressions inside Arrays, so the result of Array+Array is another Array.
We can now expand our operator one more level:
623 operator+(const Operand<Red> & l,const Operand<Green> & r) 624 { 625 typedef BinaryNode<OpAdd, 626 Operand<Red>, 627 Operand<Green>, 628 StoreByRefTag> Tree_t; 629 return Expression<Tree_t>(Tree_t(l, r)); 632 }
Note that we are no longer bothering to show the return type of the function, since it is the same as the type of the return statement inside the function body.
With this in hand, let's return to printColor():
048 template <class Expr> 049 void printColor(const Expression<Expr> &expr) 050 { 051 typedef typename ForEach<Expression<Expr>, GetColor, ColorCombine>::Type_t 052 DeducedColor_t; 053 054 calc(DeducedColor_t()); 055 }
The formal parameter expr is an instance of Expression<BinaryNode<OpAdd,Operand<Red>,Operand<Green>,StoreByRefTag> >, with an Operand<Red> and a Operand<Green> as its left and right members. This type is passed to PETE's ForEach class. We this class rather than the forEach function because we are synthesizing types. Referring to the PETE header file ForEach.h, we see that the most specific matching definition is:
146 template<class T, class FTag, class CTag> 147 struct ForEach<Expression<T>, FTag, CTag> 148 { 149 typedef typename ForEach<T, FTag, CTag>::Type_t Type_t; 150 inline static 151 Type_t apply(const Expression<T> &expr, const FTag &f, 152 const CTag &c) 153 { 154 return ForEach<T, FTag, CTag>::apply(expr.expression(), f, c); 155 } 156 };
As we've mentioned, we are synthesizing types in this example so the apply function (lines 150-155) will never actually be called. Therefore, in subsequent definitions, we'll omit this for brevity. The important thing to note is that the typedef of Type_t is generated by extracting the type wrapped by the Expression<> object and using that in another ForEach. Recall that this wrapped type in our example is BinaryNode<OpAdd,Operand<Red>,Operand<Green>,StoreByRefTag>. This means that the relevant ForEach definition is
107 template<class Op, class A, class B, class ST, class FTag, class CTag> 108 struct ForEach<BinaryNode<Op, A, B, ST>, FTag, CTag > 109 { 110 typedef typename ForEach<A, FTag, CTag>::Type_t TypeA_t; 111 typedef typename ForEach<B, FTag, CTag>::Type_t TypeB_t; 112 typedef typename Combine2<TypeA_t, TypeB_t, Op, CTag>::Type_t Type_t; 122 };
Now is a good time to perform some type substitutions. The result is
107 template<> 108 struct ForEach<BinaryNode<OpAdd,Operand<Red>,Operand<Green>,StoreByRefTag>, OpAdd, GetColor, ColorCombine> 109 { 110 typedef ForEach<Operand<Red>, GetColor, ColorCombine>::Type_t TypeA_t; 111 typedef ForEach<Operand<Green>, GetColor, ColorCombine>::Type_t TypeB_t; 112 typedef Combine2<TypeA_t, TypeB_t, OpAdd, ColorCombine>::Type_t Type_t; 122 };
To proceed, we need to resolve the ForEach types in lines 110 and 111. Looking through ForEach.h, we see that the only partial specialization that matches is the most general version of ForEach:
074 template<class Expr, class FTag, class CTag> 075 struct ForEach 076 { 077 typedef typename LeafFunctor<Expr, FTag>::Type_t Type_t; 083 };
This version of ForEach is meant to be used for leaves. It simply passes the task to the LeafFunctor class. Substituting this above gives:
107 template<> 108 struct ForEach<BinaryNode<OpAdd,Operand<Red>,Operand<Green>,StoreByRefTag>, OpAdd, GetColor, ColorCombine> 109 { 110 typedef LeafFunctor<Operand<Red>, GetColor>::Type_t TypeA_t; 111 typedef LeafFunctor<Operand<Green>, GetColor>::Type_t TypeB_t; 112 typedef Combine2<TypeA_t, TypeB_t, OpAdd, ColorCombine>::Type_t Type_t; 122 };
This is starting to look promising: we now have some invocations of Combine2<>, the combiner that was overridden in RGB.h, and some uses of LeafFunctor<>, which was also overridden. In fact, as we saw earlier, when LeafFunctor<> has an Operand<> as its first type argument, and the GetColor functor tag as its second argument, its Type_t definition is just its color argument. We can therefore simplify the definition of ForEach<> on binary nodes to be:
107 template<> 108 struct ForEach<BinaryNode<OpAdd,Operand<Red>,Operand<Green>,StoreByRefTag>, OpAdd, GetColor, ColorCombine> 109 { 112 typedef Combine2<Red, Green, OpAdd, ColorCombine>::Type_t Type_t; 122 };
The compiler can now match the specialized definition of
Combine2<> shown earlier
against this code. Thus, the return type of the expansion of ForEach<>
inside of printColor is Blue. This, in turn, is used to select
the calc
This may seem like a lot of work simply to print out a different word. However, it illustrates an extremely powerful capability of PETE: selecting custom algorithms at compile time based on the a synthesized type. All of the type computations outlined above are performed at compile-time. Also, the various calc functions are inlined. This means that the compiler will generate a custom printColor function for our expression that is equivalent to
048 template <> 049 void printColor(const Expression<BinaryNode<OpAdd,Operand<Red>,Operand<Green>,StoreByRefTag> > &expr) 050 { 054 cout << "This expression is blue." << endl; 055 }
This is an example of compile-time polymorphism. We've used the C++ compiler
to generate special code based on the types we pass into a function rather than making
a run-time choice of a function to call. This can lead to the generation of extremely
efficient code.
Summary
This tutorial has shown how to extend PETE to synthesize type
information during compilation by performing symbolic manipulations on
parse trees. The user-level definitions required are more complex
than those needed to use PETE simply to optimize expression
evaluation, but tracing through their operation shows how PETE
exploit's the C++ compiler's pattern matching and type expansion
facilities to do what it does.
Source Files
RGB.h
001 #ifndef PETE_EXAMPLES_RGB_RGB_H 002 #define PETE_EXAMPLES_RGB_RGB_H 003 004 //----------------------------------------------------------------------------- 005 // Include files 006 //----------------------------------------------------------------------------- 007 008 #include <iostream.h> 009 010 #include "PETE/PETE.h" 011 012 //----------------------------------------------------------------------------- 013 // Tag classes representing colors. Also, a functor for getting a color from 014 // a leaf and a combiner for combining colors. 015 //----------------------------------------------------------------------------- 016 017 struct Red { }; 018 struct Green { }; 019 struct Blue { }; 020 struct GetColor { }; 021 struct ColorCombine { }; 022 023 //----------------------------------------------------------------------------- 024 // A few overloaded functions that print out color names given a type. 025 //----------------------------------------------------------------------------- 026 027 inline void calc(const Red &) 028 { 029 cout << "This expression is red." << endl; 030 } 031 032 inline void calc(const Blue &) 033 { 034 cout << "This expression is blue." << endl; 035 } 036 037 inline void calc(const Green &) 038 { 039 cout << "This expression is green." << endl; 040 } 041 042 //----------------------------------------------------------------------------- 043 // A function that deduces a color at compile time and calls a special 044 // function based on the value. 045 // 046 //----------------------------------------------------------------------------- 047 048 template <class Expr> 049 void printColor(const Expression<Expr> &expr) 050 { 051 typedef typename ForEach<Expression<Expr>, GetColor, ColorCombine>::Type_t 052 DeducedColor_t; 053 054 calc(DeducedColor_t()); 055 } 056 057 //----------------------------------------------------------------------------- 058 // A set of combiners that produce new colors according to some arbitrary 059 // rules: red & green give blue, red & blue give green, blue and green give 060 // red. 061 //----------------------------------------------------------------------------- 062 063 template<class Op> 064 struct Combine2<Red, Green, Op, ColorCombine> 065 { 066 typedef Blue Type_t; 067 }; 068 069 template<class Op> 070 struct Combine2<Red, Blue, Op, ColorCombine> 071 { 072 typedef Green Type_t; 073 }; 074 075 template<class Op> 076 struct Combine2<Green, Blue, Op, ColorCombine> 077 { 078 typedef Red Type_t; 079 }; 080 081 template<class Op> 082 struct Combine2<Green, Red, Op, ColorCombine> 083 { 084 typedef Blue Type_t; 085 }; 086 087 template<class Op> 088 struct Combine2<Blue, Green, Op, ColorCombine> 089 { 090 typedef Red Type_t; 091 }; 092 093 template<class Op> 094 struct Combine2<Blue, Red, Op, ColorCombine> 095 { 096 typedef Green Type_t; 097 }; 098 099 template<class C1, class C2, class Op> 100 struct Combine2<C1, C2, Op, ColorCombine> 101 { 102 typedef C1 Type_t; 103 }; 104 105 //----------------------------------------------------------------------------- 106 // A class that has a single template parameter that specifies a color. 107 //----------------------------------------------------------------------------- 108 109 template<class ColorTag> 110 struct Operand 111 { 112 }; 113 114 //----------------------------------------------------------------------------- 115 // We need to specialize CreateLeaf<T> for Operand, so that operators 116 // know what to stick in the leaves of the expression tree. 117 //----------------------------------------------------------------------------- 118 119 template<class ColorTag> 120 struct CreateLeaf<Operand<ColorTag> > 121 { 122 typedef Operand<ColorTag> Leaf_t; 123 inline static 124 const Leaf_t &make(const Operand<ColorTag> &a) { return a; } 125 }; 126 127 //----------------------------------------------------------------------------- 128 // Specialization of LeafFunctor class for applying the getting the "color" 129 // of an operand. 130 //----------------------------------------------------------------------------- 131 132 template<class Color> 133 struct LeafFunctor<Operand<Color>, GetColor> 134 { 135 typedef Color Type_t; 136 }; 137 138 #include "RGBOperators.h" 139 140 #endif // PETE_EXAMPLES_RGB_RGB_H
001 classes 002 ----- 003 ARG = "class T[n]" 004 CLASS = "Operand<T[n]>"
001 #include "RGB.h" 002 003 int main() 004 { 005 printColor(Operand<Red>() + Operand<Green>()); 006 printColor(Operand<Red>() + Operand<Green>() + Operand<Blue>()); 007 printColor(Operand<Red>() + (Operand<Green>() + Operand<Blue>())); 008 }
[Prev] | [Home] | [Next] |