Lecture Notes for Advanced Programming II

6 May 2004 - Expression Templates

Outline

• Function arguments and the no-lambda problem.

• Template metaprogramming.

• The interpreter pattern.

• From run time to compile time.

• Abstracting interpreter classes.

• Helper template functions and overloadeding.

• Type mapping and traits.

• Expression template arguments.

• Callable expression templates.

Function Arguments

• Given a list of patient temperatures, how many are abnormal?

  template <class Temps>
  unsigned abnormal_count(const Temps & temps)
    return 
      std::count_if(
        temps.begin(), temps.end(), 
        abnormal_temperature)
  
  
  static bool
  abnormal_temperature(double temp)
    return (temp < 97.6) or (99.6 < temp)
  

• How many are normal?

  template <class Temps>
  unsigned normal_count(const Temps & temps)
  
    return 
      std::count_if(
        temps.begin(), temps.end(), 
        std::not1(
          std::ptr_fun(
            abnormal_temperature)))
  

The No-Lambda Problem

• This is a pain. Isn't there an easier way?

• Yes, in languages with lambda expressions.

  template <class Temps>
  unsigned abnormal_count(const Temps & temps)
    return std::count_if(
      temps.begin(), temps.end(), 
      abnormal_temperature
      t < 97.6 || 99.6 > t)
  

• A lambda expression is an anonymous function; a function without a name.

  • "Lambda" is the name of the constructor.

• Some languages support some form of lambda expression.

  • Lisp, Smalltalk, and Python.

• But C++ suffers from the no-lambda problem: it doesn't have lambda expressions.

  • Or does it...

Template Metaprogramming

• C++ templates form a separate sub-language within C++.

  • It has its own syntax, semantics, and evaluation phase separate from C++.

• Templates are a Turing-complete, compile-time programming language.

  • "Turing complete" means templates are as powerful as any other programming langauge.

  • "Compile time" means evaluation is performed at host-language compile time.

• Template metaprogramming exploits this by writing programs in the template sub-language.

Run-Time Expression Evaluation

• How would you implement a calculator?

  ? 1 + 3
  4
  
  ? (10 + 13 + 8)/3
  10.33
  
  ?
  

• The calculator

  1. reads in the expression,

  2. figures out what it says (parses it),

  3. computes the expression's value (executes it),

  4. prints the result,

  5. and goes to step 1.

• Expression parsing and evaluation is occurring at run-time.

The Interpreter Pattern

• The interpreter pattern is a useful technique for run-time parsing and evaluation.

• A hierarchy of classes for representation.
  

• The parse tree for (t < 97.6) || (99.6 < t).
  

The Interpreter Abstract Classes

• The abstract parent class.

  typedef double result_type
  
  class expression
    public:
      virtual result_type evaluate() const = 0
  

• The parent class for zero-argument expressions.

  class nilary_expression : public expression
  

• The parent class for one-argument expressions.

  class unary_expression : public expression
    protected:
      expression * operand
  

• The parent class for two-argument expressions.

  class binary_expression : public expression
    protected:
      expression * left, * right
  

The Interpreter Leaf Classes

• A nilary expression.

  struct literal : public nilary_expression
  
    literal(result_type v) : value(v) { }
  
    result_type evaluate() const
      return value
  
    private:
      result_type value
  

• A binary expression.

  struct less : public binary_expression
  
    less(expression * l, expression * r)
      left = l
      right = r
  
    result_type evaluate() const
      return
        left->evaluate() < right->evaluate()
  

Using The Interpreter Classes

• Expressions are built up by calling constructors.

  
  $ cat ex-test.cc
  #include <iostream>
  #include "expression.h"
  
  int main()
    double t = 102.3
    // t < 97.6 || 99.6 < t 
    expression * ep = 
      new or_else(
       new less (
         new variable(t), new literal(97.6)),
       new less (
         new new literal(99.6), variable(t)))
  
    std::cout 
      << t << " is " 
      << (ep->evaluate() ? "ab" : "") 
      << "normal.\n"
  
  $ g++ -o ex-test ex-test.cc
  
  $ ./ex-test
  102.3 is abnormal
  
  $ 
  

  See the complete code.

From Run Time to Compile Time

• Well, that's nice, but so what? It's all at run-time.

• Templates move us from run time to compile time.

• Moving to compile time changes the interpreter classes.

  • There's no program heap, so there's no new calls.

  • There's no run-time, so there's no run-time (dynamic) look-up.

• Using templates requires a change to the interpreter classes.

  • Replace new calls with template instantiation.

  • Replace dynamic look-up with template resolution.

Abstracting Interpreter Classes

• Consider binary expressions. How do they differ?

  result_type or_else::
  evaluate() const
    return 
      left->evaluate() || right->evaluate()
  
  result_type sum::
  evaluate() const
    return 
      left->evaluate() + right->evaluate()
  
  result_type xor::
  evaluate() const
    return 
      left->evaluate() ^ right->evaluate()
  

  • They differ in their operand types

    • left could be a binary expression or a literal.

  • They differ in their operator.

• Extract these common parts with template parameters.

Template Interpreter Expression Classes

• The template binary-expression class.

  template 
    <class LExpr, // Left operand's type.
     class RExpr, // Right operand's type.
     class BinOp> // Binary operator's type.
  
  struct binary_expression
  
    binary_expression(
      LExpr l, RExpr r, BinOp op = BinOp())
      : left(l), right(r), op(op) { }
  
    result_type evaluate() const
      return 
        op(left.evaluate(), right.evaluate())
  
    private:
      LExpr left
      RExpr right
      BinOp op
  

• The template unary-expression class is defined similarly .

Template Interpreter Nilary Classes

• The literal and variable classes don't change with respect to type.

  typedef double result_type
  
  struct literal
  
    literal(result_type v) : value(v) { }
  
    result_type evaluate() const
      return value
  
    private:
      result_type value
  
  
  struct variable
  
    variable(result_type & v) : var(v) { }
  
    result_type evaluate() const
      return var
  
    private:
      result_type var
  

  • Inheritance isn't needed any more.

Using Template Interpreter Classes

• Expressions are built up using nested template instantiation.

  $ cat et-test.cc
  #include <iostream>
  #include <functional>
  #include "expression.h"
  
  int
  main()
    result_type t = 102.5
    // (t < 97.6) || (99.6 < t)
    const bool abnormal =
      binary_expression<
        binary_expression
          <variable, literal, std::less<result_type> >,
        binary_expression
          <literal, variable, std::less<result_type> >,
        std::logical_or<result_type> >
        (binary_expression
           <variable, literal, std::less<result_type> >
           (variable(t), literal(97.6)), 
         binary_expression
           <literal, variable, std::less<result_type> >
           (literal(99.6), variable(t))).evaluate()
         
    std::cout 
      << t << " is " 
      << (abnormal ? "ab" : "") 
      << "normal.\n"
  

  See the complete code.

Unpacking the Beast

• Representing (t < 97.6) || (99.6 < t).

binary_expression

  <binary_expression
     <variable, literal, std::less<rtype> >,

   binary_expression
     <literal, variable, std::less<rtype> >,

   std::logical_or<result_type> 
  >

  (binary_expression
     <variable, 
      literal, 
      std::less<result_type> 
     >
     (variable(t), literal(97.6)), 

   binary_expression
     <literal,
      variable,
      std::less<result_type> 
     >
     (literal(99.6), variable(t)
  )  

Compile-Time Evaluation

• Surely you're kidding. Does that work?

  • Nope. Yep.

    $ g++ -o et-test et-test.cc
    
    $ ./et-test
    102.5 is abnormal.
    
    $ CC -o et-test et-test.cc
    
    $ ./et-test
    102.5 is abnormal.
    
    $
    

• What about the call to evaluate()?

  • The compiler has to

    1. inline member functions, and

    2. do compile-time expression simplification

    for this scheme to work well.

  • It will work without them, but not at compile time.

Helper Template Functions

• Helper functions simplify compile-time expressions.

  template <class LExpr, class RExpr>
  binary_expression 
    <LExpr, RExpr, std::less<rtype> >
  make_less(LExpr l, RExpr r)
    return 
      binary_expression
        <LExpr, RExpr, std::less<rtype> >
        (l, r)
  
  template 
  binary_expression
    <LExpr, RExpr, std::logical_or<rtype> >
  make_logical_or(LExpr l, RExpr r)
    return 
      binary_expression
        <LExpr, RExpr, std::logical_or<rtype> >
        (l, r)
  

• For example

  const bool abnormal =
    make_logical_or(
      make_less(variable(t), literal(97.6)),
      make_less(literal(99.6), variable(t))
      ).evaluate()
  

Helper Template Function Example

The expression

make_less(variable(t), literal(97.6))

resolves to the template function

template <class LExpr, class RExpr>

binary_expression 
  <LExpr, RExpr, std::less<rtype> >

make_less(LExpr l, RExpr r)
  return 
    binary_expression
      <LExpr, RExpr, std::less<rtype> >
      (l, r)

with LExpr binding to variable and RExpr binding to literal.

Overloaded Helper Template Functions

• Overloaded helper functions are even better.

  template <class LExpr, class RExpr>
  binary_expression 
    <LExpr, RExpr, std::less<rtype> >
  make_less(LExpr l, RExpr r)
  operator < (LExpr l, RExpr r)
    return 
      binary_expression
        <LExpr, RExpr, std::less<rtype> >
        (l, r)
  
  template 
  binary_expression
    <LExpr, RExpr, std::logical_or<rtype> >
  make_logical_or(LExpr l, RExpr r)
  operator || (LExpr l, RExpr r)
    return 
      binary_expression
        <LExpr, RExpr, std::logical_or<rtype> >
        (l, r)
  

• For example

  const bool abnormal =
    ((variable(t) < literal(97.6)) || 
     (literal(99.6) < variable(t))).evaluate()
  

Variables

• We can get rid of variable() calls by delaring them before hand.

  return_type temp = 100
  variable t = temp
  
  const bool abnormal =
    ((t < literal(97.6)) || 
     (literal(99.6) < t)).evaluate()
  

Literals

• Dealing with literals poses some problems.

  • Why not do like variables?

• Given

  return_type temp = 100
  variable t = temp
  const bool abnormal =
    ((t < 97.6) || (99.6 < t)).evaluate()
  

  what is the type of t < 97.6?

• It's

  binary_expression 
    <variable, double, std::less<result_type> >
  

• The problem is double is a plain-old data type.

  • It doesn't know how to evaluate().

Literal Conversions

• Might conversions help?

  • literal::literal(return_type v) is a cast conversion.

• Template resolution doesn't use conversions.

  • These are template classes, not functions, so we can't force a conversion.

  • The combinatorics would be deadly even if we could.

• Is there some other way we can indicate a conversion?

  • We need to map a value type to its representation type.

  • For example, double -> literal

• Use a struct to represent the mapping.

  struct double_representation
    typedef literal type
  

  • The representation type is given by

    double_representation::type
    

Type Mapping

• The expression-class types map into themselves.

  struct literal_representation
    typedef literal type
  
  struct variable_representation
    typedef variable type
  
  struct unary_expression_representation
    typedef unary_expression type
  
  struct binary_expression_representation
    typedef binary_expression type
  

• Expression-class types don't matter; abstract them.

  template < class ExprType >
  struct representation
    typedef ExprType type
  

• The representation type for an expression class T is

  representation<T>::type
  

  and is the same as T.

Mapping POD Types

• Use template specialization to deal with POD types.

  template < >
  struct representation<int>
    typedef literal type
  
  template < >
  struct representation<double>
    typedef literal type
  
  // and so on for bool, short, ...
  

• The representation type for a POD type T is

  representation<T>::type
  

  and is the same as literal literal.

Type Mapping Example

• Consider

  representation<double>::type
  

  resolves to

  template <class ValueType>
  struct representation
    typedef ValueType type
  

  with ValueType as double, and to

  template < >
  struct representation<double>
    typedef literal type
  

  but the latter is more specific.

  • One exact match vs. zero exact matches for the former.

Using Type Representations

• Modify the expression classes to use representation mappings.

  template 
    <class LExpr, // Left operand's type.
     class RExpr, // Right operand's type.
     class BinOp> // Binary operator's type.
  
  struct binary_expression
  
    binary_expression(
      LExpr l, RExpr r, BinOp op = BinOp())
      : left(l), right(r), op(op) { }
  
    result_type evaluate() const
      return 
        op(left.evaluate(), right.evaluate())
  
    private:
  
      LExpr left
      typename 
        representation<LExpr>::type left
      RExpr right
      typename 
        representation<RExpr>::type right
      BinOp op
  

Type Representation Mapping Example

• Consider the binary expression

  t < 101.5
  

  with t declared a variable.

• The binary expression has type

  binary_expression 
    <variable, double, std::less<result_type> >
  

• Instance variable right has type

  typename representation<RExpr>::type
  

• When RExpr is double, representation resolves to

  template < >
  representation<double>
    typedef literal type
  

• right has type literal.

• The initialization right(r) converts the double 101.5 to the literal right.

Traits

• A class defining type-based mappings is a traits class.

  • Trait classes allow for type-based customization.

  • The STL makes heavy use of them.

• Example template expressions with traits.

  $ cat et-traits.cc
  int
  main()
    result_type temp = 450.0
    variable t = temp
  
    const bool abnormal =
      ((t < 97.6) || (99.6 < t)).evaluate()
  
    std::cout 
      << temp << " is " 
      << (abnormal ? "ab" : "") 
      << "normal.\n"
  
  $ g++ -o et-traits et-traits.cc
  
  $ ./et-traits
  450 is abnormal.
  
  $ 
  

  See the complete code.

Expression Template Arguments

• We need a way to pass values into expression templates.

  • This is how generic algorithms will pass values to the expression.

• Pass the value into the expression via evaluate().

  • Literals ignore the argument value.

    result_value
    literal::evaluate(result_value)
      return v
    

  • Variables reflect the argument value.

    result_value
    variable::evaluate(result_value v)
      return var
      return v
    

  • Expressions pass the argument value along.

    result_value binary_expression::
    evaluate(result_value v)
      return 
        operator(
          left.evaluate(), right.evaluate()
          left.evaluate(v), right.evaluate(v))
    

Expression Template Argument Example

$ cat et-lambda.cc
template < class Expression >
static result_type
find_max(Expression expr, 
  double l, double r, double s)

  result_type mx = expr.evaluate(l)
  while l < r
    mx = std::max(expr.evaluate(l), mx)
    l += s
  return mx


int main()
  variable x
  std::cout 
    << find_max((x - 3)*(x - 5), 1, 10, 1)
    << "\n"
    << find_max((x - 3)/(x + 5), 1, 10, 1)
    << "\n"

$ g++ -o et-lambda et-lambda.cc

$ ./et-lambda
24
0.428571

$ 

See the complete code.

Callable Expression Templates

• Expression templates are called within generic algorithms.

• Turn evaluate() into a call operator.

  result_value
  literal::operator () (result_value)
    return v
  
  result_value
  variable::operator () (result_value v)
    return v
  
  result_value binary_expression::
  operator () (result_value v)
    return 
      op(left.evaluate(v), right.evaluate(v)) 
      op(left(v), right(v)) 
  

Callable Expression Templates Example

 
$ cat et-callable.cc 
template <class Temps> 
static unsigned
abnormal_count(const Temps & temps) 
  variable t 
  return 
    std::count_if(
      temps.begin(), temps.end(), 
      (t < 97.6) || (99.6 < t))


int main() 
  double temps[] = 
    { 95, 96, 97, 98, 99, 100, 101} 
  std::vector t(temps, temps + 7)

  std::cout << abnormal_count(t) 
            << " abnormal temperatures.\n"

$ g++ -o et-callable et-callable.cc

$ ./et-callable
5 abnormal temperatures.

$

See the complete code.

Points to Remember

• Never say "You can't do that in C++."

  • Particularly when Stroustrup's showing it to you.

• The interpreter pattern allows for run-time parsing and evaluation.

• The C++ template mechanism is another programming lanague.

  • And leads to the idea of template metaprogramming.

  • Nobody, however, says it's a nice programming language.

  • And it's an excellent way to break C++ compilers.

• Trait classes allow for type-determined behavior at compile-time.

• C++ suffers from the no-lambda problem.

  • But template metaprogramming can solve that problem.

Bibliography

C++ Expression Templates by Angelika Langer and Klaus Kreft, C/C++ Users Journal, March, 2003

These notes were derived from this article.

The Boost Lambda Library.

An industrial-strength implementation of the ideas discussed here.

This page last modified on 6 May 2004.