PETE Tutorial 3
Synthesizing Types

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:

While these rules are trivial, the techniques shown below can be used to make compilers optimize much more complex expressions on more complicated domains.

The source files for this example are included in the examples/RGB directory of the PETE distribution. These files are:

On the Surface

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() function, which simply prints out the word "blue".

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

RGBDefs.in


001  classes
002  -----
003    ARG   = "class T[n]"
004    CLASS = "Operand<T[n]>"

RGB.cpp


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]
Copyright © Los Alamos National Laboratory 1999