Статьи » Метапрограммирование. Шаблоны выражений (expression templates). Часть 2

Шаблоны выражений (expression templates). Часть 2

Другой шаблон выражений – арифметические выражения

Давайте продвинемся еще один на один шаг дальше и рассмотрим реальную составную структуру: арифметические выражения, состоящие из унарных и бинарных арифметических операторов, переменных и констант. Именно для этого случая в книге GOF имеется паттерн Interpreter.

Паттерн Interpreter предусматривает представление языка в виде абстрактного синтаксического дерева и интерпретатор, который использует это синтаксическое дерево для интерпретации языковых конструкций. Это частный случай паттерна Composite. Отношение “часть-целое” паттерна Composite соответствует отношению выражения и подвыражения в паттерне Interpreter (интерпретатор).

• Leaf является терминальным выражением.
• Composite является нетерминальным выражением.
• Вычисление компонентов является интерпретацией синтаксического дерева и его выражений.

Синтаксическое дерево представляется такими арифметическими выражениями как (a+1)*c или log(abs(х-N)). Есть два типа терминалов: числовые литералы и числовые переменные. Литералы имеют константное значение, в то время как значения переменных могут меняться между интерпретациями выражения. Нетерминалами являются унарные или бинарные выражения, состоящие из одного или двух подвыражений. Выражения имеют различную семантику, такую как +, -, *, / , ++, --, exp, log, sqrt.

Давайте возьмем конкретный пример выражения, скажем (x+2)*3. Составная структура, то есть синтаксическое дерево для этого выражения будет выглядеть следующим образом:

Рис. 7. Пример синтаксического дерева для арифметического выражения

Классический объектно-ориентированный подход для реализации паттерна Interpreter, как предложено в книге GOF, будет включать в себя следующие классы:

Рис. 8. Uml-диаграмма классов объектно-ориентированной реализации интерпретатора арифметических выражений

Соответствующий исходный код реализации показан в листинге 9. Базовый класс для UnaryExpr реализуется по аналогии с классом BinaryExpr и все конкретные унарные и бинарные выражения следуют примеру класса Sum.

Листинг 9: Объектно-ориентированная реализация интерпретатора для арифметических выражений

class AbstractExpr { 
public: 
   virtual double eval() const = 0; 
}; 
class TerminalExpr : public AbstractExpr { 
}; 
class NonTerminalExpr : public AbstractExpr { 
}; 
class Literal : public TerminalExpr { 
public: 
   Literal(double v) : _val(v) {} 
   double eval() const { return _val; } 
private: 
   const double _val; 
}; 
class Variable : public TerminalExpr  { 
public: 
   Variable(double& v) : _val(v) {} 
   double eval() const { return _val; } 
private: 
   double& _val; 
}; 
class BinaryExpr : public NonTerminalExpr { 
protected: 
   BinaryExpr(const AbstractExpr* e1, const AbstractExpr* e2)  
     : _expr1(e1),_expr2(e2) {} 
   virtual ~BinaryExpr ()  
   { delete const_cast<AbstractExpr*>(_expr1);  
     delete const_cast<AbstractExpr*>(_expr2);  
   } 
   const AbstractExpr* _expr1; 
   const AbstractExpr* _expr2; 
};  
class Sum : public BinaryExpr { 
public: 
   Sum(const AbstractExpr* e1, const AbstractExpr* e2)  
     : BinExpr(e1,e2) {} 
   double eval() const  
   { return _expr1->eval() + _expr2->eval(); } 
}; 
... 

Листинг 10 показывает, как будет использоваться интерпретатор для вычисления выражения (x+2)*3.

Листинг 10: Использование интерпретатора для арифметических выражений

void someFunction(double x) 
{ 
  Product expr(new Sum(new Variable(x),new Literal(2)), new Literal(3)); 
  cout << expr.eval() << endl; 
} 

Сначала создается объект выражения expr, который представляет выражение (x+2)*3 и затем вычисляется объект выражения. Конечно, это крайне неэффективный способ вычисления результата такого примитивного выражения, как (x+2)*3. Подождите; теперь мы превратим объектно-ориентированный подход в решение на основе шаблона.

Как и прежде, в случае скалярного произведения мы устраним все абстрактные базовые классы, так как шаблонные решения основаны на общности имен, а не наследовании. По этой причине, мы не нуждаемся в базовых классах. Вместо представления всех терминальных и нетерминальных выражений с помощью автономных классов, мы будем использовать функцию оценки с именем eval().

Затем мы выразим все нетерминальные выражения, такие как сумма или произведение, через классы, порожденные от шаблонов классов UnaryExpr и BinaryExpr, каждый из которых параметризируется структурной информацией. Эти шаблоны классов будут принимать типы их подвыражений как ”типовые” шаблонные аргументы. Кроме того, мы параметризируем шаблоны классов выражений типом операции, которые они представляют, то есть, фактическая операция (+,-,*,/,++,--,abs,exp,log) будет предоставлена как объект функции и ее тип будет одним из шаблонных аргументов в шаблоне класса выражения.

Терминальные выражения будут реализованы как обычные (нешаблонные) классы как при объектно-ориентированном подходе.

Вместо рекурсии на этапе выполнения мы снова будем использовать рекурсию на этапе компиляции: мы заменим рекурсивный вызов виртуальной вычислительной функции на рекурсивное создание экземпляров шаблонов классов выражений.

На рисунке 9 ниже показаны классы на основе шаблонного решения:

Рис. 9. UML-диаграмма классов шаблонной реализации интерпретатора арифметических выражений

Исходный код реализации приведен в листинге 11.

Листинг 11: Шаблонная реализация интерпретатора арифметических выражений

class Literal { 
public: 
   Literal(const double v) : _val(v) {} 
   double eval() const { return _val; } 
private: 
   const double _val; 
}; 
class Variable { 
public: 
   Variable(double& v) : _val(v) {} 
   double eval() const { return _val; } 
private: 
   double& _val; 
}; 
  
template <class ExprT1,class ExprT2, class BinOp> 
class BinaryExpr { 
public: 
   BinaryExpr(ExprT1 e1, ExprT2 e2,BinOp op=BinOp()) 
      : _expr1(e1),_expr2(e2),_op(op) {} 
   double eval() const  
   { return _op(_expr1.eval(),_expr2.eval()); } 
private: 
   ExprT1 _expr1; 
   ExprT2 _expr2; 
   BinOp  _op; 
}; 
... 

Шаблон класса для UnaryExpr реализуется по аналогии с классом BinaryExpr. В качестве операций мы можем использовать предопределенные в STL типы объектов функций плюс, минус, умножение и деление, и т.д., а также можем определить наши собственные типы объектов функций в случае необходимости. Например, бинарное выражение, представляющее сумму, будет иметь тип BinaryExpr< ExprT1, ExprT2, plus<double> >. Поскольку это имя типа довольно громоздкое, для более удобного использования нашего решения мы добавим создающие функции.

template <class T1, class T2>  
class pair { 
public:  pair(T1 t1,T2 t2); 
}; 
template <class T1, class T2>  
pair<T1,T2> make_pair(t1 t1, T2 t2) 
{ return pair<T1,T2>(t1,t2); } 

pair< pair<string,complex<double>>, pair<string,complex<double> > >
( pair<string,complex<double> >("origin", complex<double>(0,0)),
  pair<string,complex<double> >("saddle", aCalculation())
) 

make_pair(make_pair("origin", complex<double>(0,0)),  
          make_pair("saddle", aCalculation()) 
         )

Мы будем использовать методику создающих функций для облегчения создания наших объектов выражений. В листинге 12 ниже показано два примера этих создающих функций:

Листинг 12: Создающие функции для объектов выражений

template  <class ExprT1,class ExprT2> 
BinaryExpr<ExprT1,ExprT2,plus<double> > 
makeSum(ExprT1 e1, ExprT2 e2)  
{ return BinaryExpr<ExprT1,ExprT2,plus<double> >(e1,e2); }  
template  <class ExprT1,class ExprT2> 
BinaryExpr <ExprT1,ExprT2,multiplies<double> > 
makeProd(ExprT1 e1, ExprT2 e2)  
{ return    BinaryExpr<ExprT1,ExprT2,multiplies<double> >(e1,e2);  } 

Листинг 13 показывает использование шаблонной реализации интерпретатора для расчета выражения (x+2)*3.

Листинг 13: Использование шаблонного интерпретатора для арифметических выражений

void someFunction (double x)  
{ 
  BinaryExpr< BinaryExpr < Variable,Literal,plus<double> >, 
              Literal, 
              multiplies<double> >  
  expr = makeProd (makeSum (Variable(x), Literal(2)), Literal(3)); 
  cout << expr.eval() << endl; 
} 

Во-первых, создается объект выражения, который представляет выражение (х+2)*3, а затем рассчитывается само выражение. Заметим, что в этом решении тип объекта выражения уже отражает структуру синтаксического дерева.

Часто довольно длинное имя типа объекта выражения даже не нужно указывать. В приведенном выше примере нам не нужна переменная expr мы можем напрямую использовать результаты создающей функции makeProd() для расчета выражения, как показано ниже:

cout 
  << makeProd(makeSum(Variable(x),Literal(2)),Literal(3)).eval() 
  << endl;

Оценка

Что мы получили с помощью реализации интерпретатора на основе шаблонов, а не наследования? Если компилятор встраивает все создающие функции, конструкторы и функции Eval() (скорее всего так и будет, так как они тривиальные) выражение

cout 
  << makeProd(makeSum(Variable(x),Literal(2)),Literal(3)).eval() 
  << endl;

сводится к (x+2)*3.

Сравните это с

Product expr(new Sum(new Variable(x),new Literal(2)), new Literal(3)).eval()

(см. листинг 10). Оно приводит к ряду распределений памяти из кучи и последующих конструирований, а также нескольким вызовам виртуальной функции eval(). Скорее всего, ни один из вызовов eval() не будет встроенным, так как компиляторы обычно не встраивают функции, которые вызываются через указатели.

Решение на основе шаблонов выполняется гораздо быстрее, чем объектно-ориентированная реализация.

Дальнейшее совершенствование решения на основе шаблонов выражений

Давайте настроим шаблоны выражений и превратим их в нечто действительно полезное. Сначала улучшим их читаемость. Мы хотим сделать выражение, такое как

makeProd(makeSum(Variable(x),Literal(2)),Literal(3)).eval() 

более удобным для чтения в том смысле, чтобы оно выглядело более или менее похоже на выражение, которое оно представляет, а именно: (х+2)*3. Это может быть достигнуто путем перегрузки операторов. Путем незначительных модификаций выражению можно придать следующий вид eval((v+2)*3.0).

Первое изменение заключается в переименовании создающих функций так, чтобы они были перегруженными операторами; то есть мы переименуем makeSum() в operator+(), makeProd() в operator*(), и так далее. Тогда

makeProd(makeSum(Variable(x),Literal(2)),Literal(3)) 

превращается в

((Variable(x) + Literal(2)) * Literal(3))

Это конечно хорошо, но недостаточно хорошо. Мы хотели бы написать ((х+2)*3). Таким образом, наша цель состоит в устранении создания переменных и литералов, которые по-прежнему загромождают выражение.

Для того чтобы выяснить, как мы можем улучшить наше решение, рассмотрим, что означает выражение х+2, которое мы переименовали из создающей функции makeSum() в operator+(). Реализация operator+() показана в листинге 14 ниже.

Листинг 14: Создающая функция для выражения суммы через перегруженный operator+

template  <class ExprT1,class ExprT2> 
BinaryExpr<ExprT1,ExprT2,plus<double> > 
operator+(ExprT1 e1, ExprT2 e2)  
{ return BinaryExpr<ExprT1,ExprT2,plus<double> >(e1,e2); }  

Мы бы хотели, чтобы x+2 соответствовал operator+(x,2), который ранее был makeSum(х, 2). По этой причине x+2 является результатом создания объекта бинарного выражения, представляющего собой сумму и которому в качестве аргументов были переданы переменная х типа double и литерал 2 типа int. Более точно, это безымянный объект, созданный как BinaryExpr<double,int,plus<double>>(x,2). Обратите внимание, что тип объекта, это не совсем то, что мы хотим. Нам нужно создать объект типа BinaryExpr<Variable,Literal,plus<double>>, но при автоматическом выводе шаблонных аргументов неизвестно, что х является переменной, а 2 литералом. Компилятор выводит тип double из аргумента х и тип int из аргумента 2, потому что он проверяет типы аргументов, передаваемых функции.

Получается, что мы должны немного помочь компилятору вывести то, что нам необходимо. Если бы мы передали объект типа Variable вместо оригинальной переменной х, то автоматический вывод аргументов дал бы результат типа BinaryExpr<Variable,int,plus<double>>, который чуть ближе к цели. (Мы рассмотрим оставшееся преобразование int в Literal через минуту). По этой причине, минимальная степень сотрудничества со стороны пользователей неизбежна: они должны обернуть свои переменных в объекты типа Variable, чтобы это сработало, как показано в листинге 15:

Листинг 15: Использование шаблонного интерпретатора для арифметических выражений

void someFunction (double x)  
{ 
  Variable v = x; 
  cout << ((v + 2) * 3).eval() << endl; 
}

При использовании объекта v типа Variable вместо простой числовой переменной, мы добились того, что такое выражение, как v+2 расчитывается как неименованный объект BinaryExpr<Variable,int,plus<double>>(v,2). Такой объект BinaryExpr имеет два члена данных типа Variable и int соответственно. Вычислительная функция BinaryExpr<Variable,int,plus<double>>::eval() будет возвращать сумму двух членов данных. Суть в том, что член данных int не знает, как себя вычислить, мы должны преобразовать литерал 2 в объект типа Literal, который уже знает, как себя вычислить. Как мы можем автоматически преобразовать константы любого числового типа в объектов типа Literal? Для того, чтобы решить эту проблему мы определим свойства выражений traits.

Мы будем применять технику traits для решения нашей проблемы путем преобразования числовых литералов в объекты типа Literal. Мы определим свойства выражений, которые для каждого типа выражения предусматривают информацию о том, как они должны храниться внутри объектов выражений, операндами которых являются. Все сущности числовых типов должны храниться  в виде объектов типа Literal; все объекты типа Variable должны храниться как Variables; и все нетерминальные объекты выражений должны также сохраняться. Листинг 16 показывает определение свойств выражений:

Листинг 16: Свойства выражений

template <class ExprT> struct exprTraits  
{ typedef ExprT expr_type; }; 
template <> struct exprTraits<double>  
{ typedef Literal expr_type; }; 
template <> struct exprTraits<int>  
{ typedef Literal expr_type; }; 
... 

Класс свойств выражений определяет вложенный тип expr_type, который представляет собой тип выражения для объекта выражения. Существует шаблон общих свойств, который определяет тип выражения для всех выражений, которые относятся к типам классов, таких как BinaryExpr, UnaryExpr или Variable. Кроме того, существуют специализации шаблона класса для всех встроенных числовых типов, таких как short, int, long, float, double и т. д. Для всех неклассовых выражений тип выражения определяется как тип Literal.

Внутри определения классов BinaryExpr и UnaryExpr мы будем использовать свойства выражений для определения типов членов данных, содержащих подвыражения.

Листинг 17: Использование свойств выражений

template <class ExprT1,class ExprT2, class BinOp> 
class BinaryExpr { 
public: 
   BinaryExpr(ExprT1 e1, ExprT2 e2,BinOp op=BinOp()) 
      : _expr1(e1),_expr2(e2),_op(op) {} 
   double eval() const  
   { return _op(_expr1.eval(),_expr2.eval()); } 
private: 
   exprTraits<ExprT1>::expr_type _expr1; 
   exprTraits<ExprT2>::expr_type _expr2; 
   BinOp  _op; 
};  

Благодаря использованию свойств выражений объект типа BinaryExpr<Variable,int,plus<double>> будет содержать два операнда в виде объектов типов Variable и Literal, как и хотелось.

Теперь мы добились того, что выражение, такое как ((v+2)*3).eval(), где v является Variable - оберткой double переменной х, будет вычисляться как (х+2)*3. Давайте сделаем некоторые незначительные изменения, чтобы сделать его еще более удобным для чтения. Большинство людей находят странным вызов функции-члена сущности, которая выглядит как выражение. Если мы определим вспомогательную функцию, мы можем преобразовать наше выражение ((v+2)*3).eval() во что то, похожее на eval((v+2)*3), которое выглядит более естественно для большинства людей, но остается эквивалентом в остальном. Листинг 18 показывает эту вспомогательную функцию:

Листинг 18: Вспомогательная функция eval()

template <class ExprT> 
double eval(ExprT e) { return e.eval(); } 

Рисунок 10 иллюстрирует, как выражение ((v+2)* 3).eval(), где v является Variable – оберткой double переменной x, постепенно разворачивается во время компиляции к выражению (x+2)*3.

Рис. 10. Вычисление объекта выражения (v+2)*3 на этапе компиляции

Повторное использование объектов выражений

Вам может все еще интересно, в чем заключается польза от объектов выражений. Каждый объект выражения представляет синтаксическую декомпозицию арифметического выражения; это синтаксическое дерево знает, как интерпретировать себя для вычисления числового значения. В принципе, мы создали механизм для вычисления выражений, такое, которое уже встроено в язык. Итак, в чем же смысл? Дальнейшие минимальные корректировки нашего решения приведут нас к сути.

До сих пор интерпретация синтаксического дерева была статичной. Каждое синтаксическое дерево создается и интерпретируется только один раз. Возможно и более динамичное использование, где данное синтаксическое дерево может строиться неоднократно при разных входных значениях. Помните, что в конечном итоге мы хотим вычислять интегралы, такие как

используя интегрирующую функцию, которая аппроксимирует интеграл путем вычисления выражения для указанного ряда равноудаленных точек в интервале:

template <class ExprT> 
double integrate (ExprT e,double from,double to,size_t n) 
{  double sum=0, step=(to-from)/n; 
   for (double i=from+step/2; i<to; i+=step) 
       sum+=e.eval(i); 
   return step*sum; 
} 

Эта функция могла бы использоваться для аппроксимации интеграла x/(1+x) из примера выше:

Identity<double> x; 
cout << integrate (x/(1.0+x),1.0,5.0,10) << endl;

Нам нужен объект выражения, который может быть неоднократно интерпретирован, что пока не позволяет наш шаблон выражения. Для превращения нашей статической интерпретации синтаксического дерева в повторную необходимы незначительные изменения. Мы просто должны изменить все вычислительные функции наших шаблонов так, чтобы они принимали входной аргумент, а именно значение, по которому они будут производить вычисления. Нетерминальные выражения будут передавать аргумент своим подвыражениям. Литерал будет принимать аргумент и игнорировать его; он будет продолжать возвращать константное значение, которое он представляет. Переменная Variable больше не будет возвращать значение переменной, на которую указывает, а будет возвращать значение аргумента. По этой причине мы переименуем ее в Identity. Листинг 19 ниже, показывает изменения в классах:

Листинг 19: Шаблон выражения с повторным использованием

class Literal { 
public:   Literal(double v) : _val(v) {} 
          double eval(double) const { return _val; } 
private:  const double _val; 
}; 
template<class T> 
class Identity { 
public:   T eval(T d) const { return d; } 
}; 
template <class ExprT1,class ExprT2, class BinOp> 
class BinExpr { 
public:   double eval(double d) const  
          { return _op(_expr1.eval(d),_expr2.eval(d)); } 
}; 
... 

Если мы добавим нетерминальные выражения для включения числовых функций, таких как sqrt(), sqr(), exp(), log() и т.д., мы можем даже вычислять распределение Гаусса:

Листинг 20: Вычисление распределения Гаусса

double sigma=2.0, mean=5.0; 
const double Pi = 3.141593; 
cout << integrate( 
 1.0/(sqrt(2*Pi)*sigma) * exp(sqr(x-mean)/(-2*sigma*sigma)), 
 2.0,10.0,100) << endl; 

Для выражений, представляющих числовые функции, мы можем использовать функции из стандартной библиотеки C. Все, что нам нужно сделать, это добавить создающие функции для унарных или бинарных выражений, операции которых являются одной из стандартных функций C. В листинг 21 показано несколько примеров:

Листинг 21: Числовые функции как шаблоны нетерминальных выражений

template  <class ExprT> 
UnaryExpr<ExprT,double(*)(double)> 
sqrt(const ExprT& e)  
{return UnaryExpr<ExprT,double(*)(double)>(e,::std::sqrt);} 
template  <class ExprT> 
UnaryExpr<ExprT,double(*)(double)> 
exp(const ExprT& e)  
{ return UnaryExpr<ExprT,double(*)(double)>(e,::std::exp); } 
... 

С этими дополнениями у нас появились мощные и высокопроизводительные решения для расчета арифметических выражений. Можно предположить, что применение методов, продемонстрированных в этой статье, позволяет настроить шаблоны для логических выражений. Путем переименования вычислительной функции eval() в operator()(), которая является оператором вызова функции, мы можем легко превратить объекты выражений в функциональные объекты, которые затем могут быть использованы в сочетании с алгоритмами STL. Ниже приведен пример логического выражения, которое используются в качестве предиката для подсчета элементов в списке:

list<int> l; 
Identity<int> x; 
count_if(l.begin(),l.end(), x >= 0 && x <= 100 ); 

Этот пример хорошо иллюстрирует читабельность шаблонов выражений при нулевой вычислительной стоимости на этапе выполнения. Шаблоны выражений могут быть удобны в использовании. Создание библиотеки шаблонов выражений совсем другая история, она включает в себя понимание большего числа других методик шаблонного программирования, помимо тех, которые мы рассмотрели в этой статье. Тем не менее, все библиотеки шаблонов строятся на принципах, описанных в этой статье.

Шаблоны выражений (expression templates). Часть 1

Источник: http://www.angelikalanger.com/Articles/Cuj/ExpressionTemplates/ExpressionTemplates.htm