C++ Template Metaprogramming——一个小型lambda库的实作

Boost里面的lambda库实在是很复杂，因此我对其进行了精简，缩减到300多行代码，只支持+-*/四则运算，虽没有boost中lambda库那么强大，亦可窥其奥妙。下面是lambda库的源码：

 

/*
 * lambda.h
 *
 *  Created on: 2010-12-28
 *      Author: 
 */

#ifndef LAMBDA_H_
#define LAMBDA_H_

#include "boost/tuple/tuple.hpp"
#include "boost/any.hpp"

using namespace boost;

#define CALL_TEMPLATE_ARGS class A, class B, class C, class Env
#define CALL_FORMAL_ARGS A& a, B& b, C& c, Env& env
#define CALL_ACTUAL_ARGS a, b, c, env
#define CALL_ACTUAL_ARGS_NO_ENV a, b, c
#define CALL_REFERENCE_TYPES A, B, C, Env&
#define CALL_PLAIN_TYPES A, B, C, Env

#define LAMBDA_DISABLE_IF_ARRAY1(A1, R1) typename R1::type
#define LAMBDA_DISABLE_IF_ARRAY2(A1, A2, R1, R2) typename R1, R2::type
#define LAMBDA_DISABLE_IF_ARRAY3(A1, A2, A3, R1, R2, R3) typename R1, R2, R3::type

template<class A1, class A2, class A3, class A4>
void do_nothing(A1&, A2&, A3&, A4&) {
}

#define CALL_USE_ARGS \
do_nothing(a, b, c, env)

template<class Base>
class lambda_functor;

template<class Act, class Args>
class lambda_functor_base;

struct null_type {
};

static const null_type constant_null_type = null_type();
#define cnull_type() constant_null_type

enum {
	NONE = 0x00, // Notice we are using bits as flags here.
	FIRST = 0x01,
	SECOND = 0x02,
	THIRD = 0x04,
	EXCEPTION = 0x08,
	RETHROW = 0x10
};

template<bool If, class Then, class Else> struct IF {
	typedef Then RET;
};

template<class Then, class Else> struct IF<false, Then, Else> {
	typedef Else RET;
};

template<class T1, class T2>
struct parameter_traits_ {
	typedef T2 type;
};

template<class T>
struct const_copy_argument {
typedef	typename
	parameter_traits_<
		T,
		typename IF<boost::is_function<T>::value, T&, const T>::RET
	>::type type;
};

// returns a reference to the element of tuple T
template<int N, class T> struct tuple_element_as_reference {
typedef	typename
	boost::tuples::access_traits<
		typename boost::tuples::element<N, T>::type
	>::non_const_type type;
};

template<int N, class Tuple> struct get_element_or_null_type {
typedef	typename
	tuple_element_as_reference<N, Tuple>::type type;
};
template<int N> struct get_element_or_null_type<N, null_type> {
	typedef null_type type;
};

template<int I> struct placeholder;

template<> struct placeholder<FIRST> {

	template<class SigArgs> struct sig {
		typedef	typename get_element_or_null_type<0, SigArgs>::type type;
	};

	template<class RET, CALL_TEMPLATE_ARGS>
	RET call(CALL_FORMAL_ARGS) const {
		BOOST_STATIC_ASSERT(boost::is_reference<RET>::value);
		CALL_USE_ARGS; // does nothing, prevents warnings for unused args
		return a;
	}
};

template<> struct placeholder<SECOND> {

	template<class SigArgs> struct sig {
		typedef	typename get_element_or_null_type<1, SigArgs>::type type;
	};

	template<class RET, CALL_TEMPLATE_ARGS>
	RET call(CALL_FORMAL_ARGS) const {CALL_USE_ARGS; return b;}
};

template<> struct placeholder<THIRD> {

	template<class SigArgs> struct sig {
		typedef	typename get_element_or_null_type<2, SigArgs>::type type;
	};

	template<class RET, CALL_TEMPLATE_ARGS>
	RET call(CALL_FORMAL_ARGS) const {CALL_USE_ARGS; return c;}
};

template<> struct placeholder<EXCEPTION> {

	template<class SigArgs> struct sig {
		typedef	typename get_element_or_null_type<3, SigArgs>::type type;
	};

	template<class RET, CALL_TEMPLATE_ARGS>
	RET call(CALL_FORMAL_ARGS) const {CALL_USE_ARGS; return env;}
};

// select functions -------------------------------
template<class Any, CALL_TEMPLATE_ARGS>
inline Any& select(Any& any, CALL_FORMAL_ARGS) {CALL_USE_ARGS; return any;}

template<class Arg, CALL_TEMPLATE_ARGS>
inline typename Arg::template sig<tuple<CALL_REFERENCE_TYPES> >::type
select ( const lambda_functor<Arg>& op, CALL_FORMAL_ARGS ) {
	return op.template call<
	typename Arg::template sig<tuple<CALL_REFERENCE_TYPES> >::type
>	(CALL_ACTUAL_ARGS);
}
template<class Arg, CALL_TEMPLATE_ARGS>
inline typename Arg::template sig<tuple<CALL_REFERENCE_TYPES> >::type
select ( lambda_functor<Arg>& op, CALL_FORMAL_ARGS) {
	return op.template call<
	typename Arg::template sig<tuple<CALL_REFERENCE_TYPES> >::type
>	(CALL_ACTUAL_ARGS);
}

class plus_action {};
class minus_action {};
class multiply_action {};
class divide_action {};

#define LAMBDA_BINARY_ACTION(SYMBOL, ACTION_CLASS)  					 \
template<class Args>                                                      \
class lambda_functor_base<ACTION_CLASS, Args> {                           \
public:                                                                   \
  Args args;                                                              \
public:                                                                   \
  explicit lambda_functor_base(const Args& a) : args(a) {}                \
                                                                          \
  template<class RET, CALL_TEMPLATE_ARGS>                                 \
  RET call(CALL_FORMAL_ARGS) const {                                      \
    return select(boost::tuples::get<0>(args), CALL_ACTUAL_ARGS)  \
           SYMBOL                                                         \
           select(boost::tuples::get<1>(args), CALL_ACTUAL_ARGS); \
  }                                                                       \
  template<class SigArgs> struct sig {                                    \
    typedef typename                                                      \
		boost::tuples::element<0,SigArgs>::type type;         			  \
  };                                                                      \
};

LAMBDA_BINARY_ACTION(+,plus_action)
LAMBDA_BINARY_ACTION(-,minus_action)
LAMBDA_BINARY_ACTION(*,multiply_action)
LAMBDA_BINARY_ACTION(/,divide_action)


template<class T>
class lambda_functor: public T {
public:
	typedef T inherited;

	lambda_functor() {}

	lambda_functor(const lambda_functor& l) : inherited(l) {}

	lambda_functor(const T& t) :
		inherited(t) {
	}


	  template<class A>
	  typename inherited::template sig<tuple<A> >::type
	  operator()(A& a) const {
	    return inherited::template call<
	      typename inherited::template sig<tuple<A> >::type
	    >(a, cnull_type(), cnull_type(), cnull_type());
	  }

	  template<class A>
	  LAMBDA_DISABLE_IF_ARRAY1(A, inherited::template sig<tuple<A> >)
	  operator()(A const& a) const {
	    return inherited::template call<
	      typename inherited::template sig<tuple<A> >::type
	    >(a, cnull_type(), cnull_type(), cnull_type());
	  }

	template<class A, class B>
	typename inherited::template sig<tuple<A, B> >::type
	operator()(A& a, B& b) const {
		return inherited::template call<
			typename inherited::template sig<tuple<A, B> >::type
		>(a, b, cnull_type(), cnull_type());
	}

	template<class A, class B>
	LAMBDA_DISABLE_IF_ARRAY2(A, B, inherited::template sig<tuple<A, B> >)
	operator()(A const& a, B& b) const {
		return inherited::template call<
			typename inherited::template sig<tuple<A, B> >::type
		>(a, b, cnull_type(), cnull_type());
	}

	template<class A, class B>
	LAMBDA_DISABLE_IF_ARRAY2(A, B, inherited::template sig<tuple<A, B> >)
	operator()(A& a, B const& b) const {
		return inherited::template call<
			typename inherited::template sig<tuple<A, B> >::type
		>(a, b, cnull_type(), cnull_type());
	}

	template<class A, class B>
	LAMBDA_DISABLE_IF_ARRAY2(A, B, inherited::template sig<tuple<A, B> >)
	operator()(A const& a, B const& b) const {
		return inherited::template call<
			typename inherited::template sig<tuple<A, B> >::type
		>(a, b, cnull_type(), cnull_type());
	}

	template<class A, class B, class C>
	typename inherited::template sig<tuple<A, B, C> >::type
	operator()(A& a, B& b, C& c) const
	{
		return inherited::template call<
			typename inherited::template sig<tuple<A, B, C> >::type
		>(a, b, c, cnull_type());
	}

	template<class A, class B, class C>
	LAMBDA_DISABLE_IF_ARRAY3(A, B, C, inherited::template sig<tuple<A , B , C> >)
	operator()(A const& a, B const& b, C const& c) const
	{
		return inherited::template call<
			typename inherited::template sig<tuple<A , B , C> >::type
		>(a, b, c, cnull_type());
	}
};

#define LAMBDA_BE1(OPER_NAME, ACTION, CONSTA, CONSTB, CONVERSION)      \
template<class Arg, class B>                                                 \
inline const                                                                 \
lambda_functor<                                                              \
  lambda_functor_base<                                                       \
    ACTION,                                                                  \
    tuple<lambda_functor<Arg>, typename const_copy_argument <CONSTB>::type>  \
  >                                                                          \
>                                                                            \
OPER_NAME (const lambda_functor<Arg>& a, CONSTB& b) {                      \
  return                                                                     \
    lambda_functor_base<                                                     \
      ACTION,                                                                \
      tuple<lambda_functor<Arg>, typename const_copy_argument <CONSTB>::type>\
    >                                                                        \
   (tuple<lambda_functor<Arg>, typename const_copy_argument <CONSTB>::type>(a, b)); \
}

#define LAMBDA_BE2(OPER_NAME, ACTION, CONSTA, CONSTB, CONVERSION)      \
template<class A, class Arg>                                                 \
inline const                                                                 \
lambda_functor<                                                              \
  lambda_functor_base<                                                       \
    ACTION,                                                                  \
    tuple<typename CONVERSION <CONSTA>::type, lambda_functor<Arg> >        \
  >                                                                          \
>                                                                            \
OPER_NAME (CONSTA& a, const lambda_functor<Arg>& b) {                      \
  return                                                                     \
    lambda_functor_base<                                                     \
      ACTION,                                                                \
      tuple<typename CONVERSION <CONSTA>::type, lambda_functor<Arg> >      \
    >                                                                        \
  (tuple<typename CONVERSION <CONSTA>::type, lambda_functor<Arg> >(a, b)); \
}

#define LAMBDA_BE3(OPER_NAME, ACTION, CONSTA, CONSTB, CONVERSION)    \
template<class ArgA, class ArgB>                                           \
inline const                                                               \
lambda_functor<                                                            \
  lambda_functor_base<                                                     \
    ACTION,                                                                \
    tuple<lambda_functor<ArgA>, lambda_functor<ArgB> >                     \
  >                                                                        \
>                                                                          \
OPER_NAME (const lambda_functor<ArgA>& a, const lambda_functor<ArgB>& b) { \
  return                                                                   \
    lambda_functor_base<                                                   \
      ACTION,                                                              \
      tuple<lambda_functor<ArgA>, lambda_functor<ArgB> >                   \
    >                                                                      \
  (tuple<lambda_functor<ArgA>, lambda_functor<ArgB> >(a, b));              \
}

#define LAMBDA_BE(OPER_NAME, ACTION, CONSTA, CONSTB, CONST_CONVERSION) 	   \
LAMBDA_BE1(OPER_NAME, ACTION, CONSTA, CONSTB, CONST_CONVERSION)      \
LAMBDA_BE2(OPER_NAME, ACTION, CONSTA, CONSTB, CONST_CONVERSION)      \
LAMBDA_BE3(OPER_NAME, ACTION, CONSTA, CONSTB, CONST_CONVERSION)

LAMBDA_BE(operator+, plus_action,const A,const B,const_copy_argument)
LAMBDA_BE(operator-, minus_action,const A,const B,const_copy_argument)
LAMBDA_BE(operator*, multiply_action,const A,const B,const_copy_argument)
LAMBDA_BE(operator/, divide_action,const A,const B,const_copy_argument)

typedef const lambda_functor<placeholder<FIRST> > placeholder1_type;
typedef const lambda_functor<placeholder<SECOND> > placeholder2_type;
typedef const lambda_functor<placeholder<THIRD> > placeholder3_type;

placeholder1_type free1 = placeholder1_type();
placeholder2_type free2 = placeholder2_type();
placeholder3_type free3 = placeholder3_type();

placeholder1_type& _1 = free1;
placeholder2_type& _2 = free2;
placeholder3_type& _3 = free3;

#endif /* LAMBDA_H_ */

 

 

在深入理解代码之前，我们先来看一下lambda的使用：

 

//============================================================================
// Name        : lambdatest.cpp
// Author      : 
// Version     :
// Copyright   : 
// Description : Test my lambda, Ansi-style
//============================================================================

#include "lambda.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

template <class T>
inline void PRINT_ELEMENTS (const T& coll, const char* optcstr="")
{
  typename T::const_iterator pos;
  std::cout << optcstr;
  for (pos=coll.begin(); pos!=coll.end(); ++pos) {
	  std::cout << *pos << ' ';
  }
  std::cout << std::endl;
}


int main() {
	vector<int> intArr;
	intArr.push_back(1);
	intArr.push_back(2);
	intArr.push_back(3);
	intArr.push_back(4);
	intArr.push_back(5);
	//lambda作用于标准库算法
	transform(intArr.begin(),intArr.end(),intArr.begin(),_1*2);
	PRINT_ELEMENTS(intArr);
	//lambda作用于普通运算
	cout<<(_1+_2)(1,2)<<endl;
	return 0;
}

在STL的算法中，我们一般需要自行定义一些仿函数来使用一些算法，而使用lambda库，我们只要使用类似“_1*2”的形式即可使用STL的算法。不妨想象一下，如果我们的lambda库定义了多种多样的运算符，那么我们完全可以省去写仿函数的时间，而直接使用lambda表达式。

好，既然我们都同意lambda库是很有用的，那么现在就来来看看这个小型lambda的实作细则吧o(∩_∩)o ！

直观上看，我们的lambda表达式（如上面的_1*2，_1+_2等）是由占位符和表达式组成的，因此我们可以大胆的推测占位符是一些模版类，而占位符支持+，*之类的运算符是因为这些模版类已经重载了这些运算符。

没错，事实就是这样的。

到源码里去（到祖国的大西部去，口号都是一样的）！

我们看到_1，_2，_3是lambda_functor模板类的三个实例。 而lambda_functor则通过宏定义重载了+-*/四个运算符：

 

LAMBDA_BE(operator+, plus_action,const A,const B,const_copy_argument)
LAMBDA_BE(operator-, minus_action,const A,const B,const_copy_argument)
LAMBDA_BE(operator*, multiply_action,const A,const B,const_copy_argument)
LAMBDA_BE(operator/, divide_action,const A,const B,const_copy_argument)

 

  这么easy啊（看到这里，也许你会觉得不过而而），没你想象的那么简单的，这只是一根语法主线而已，事情还要繁杂的多。

 

型别计算与推演：（这才是重点，important！！！）

一切还是从头来，拿_1+_2举例，我们对于lambda_functor的+运算宏展开之后的定义如下：

 

 

template<class ArgA, class ArgB>                                          
inline const                                                              
lambda_functor<                                                           
  lambda_functor_base<                                                     
    plus_action,                                                               
    tuple<lambda_functor<ArgA>, lambda_functor<ArgB> >                     
  >                                                                        
>                                                                          
operator+ (const lambda_functor<ArgA>& a, const lambda_functor<ArgB>& b) {
  return                                                                  
    lambda_functor_base<                                                  
      plus_action,                                                             
      tuple<lambda_functor<ArgA>, lambda_functor<ArgB> >                 
    >                                                                     
  (tuple<lambda_functor<ArgA>, lambda_functor<ArgB> >(a, b));             
}

 

 

两个参数_1、_2即使参数a和b，加法运算的结果仍然是返回一个lambda_functor对象，我们姑且把这个lambda_functor叫做_0。那么_0(1,2)就是要调用lambda_functor重载的()

运算符了。好，让我们继续前进，我们这里要调用的lambda_functor的方法如下：

 

	template<class A, class B>
	LAMBDA_DISABLE_IF_ARRAY2(A, B, inherited::template sig<tuple<A, B> >)
	operator()(A const& a, B const& b) const {
		return inherited::template call<
			typename inherited::template sig<tuple<A, B> >::type
		>(a, b, cnull_type(), cnull_type());
	}

 lambda_functor的()重载函数继续调用了，其inherited的call函数，这个inherited就我们前面看到的

 

 

lambda_functor_base<                                                     
    plus_action,                                                               
    tuple<lambda_functor<ArgA>, lambda_functor<ArgB> > 
>

 

 

让我们继续展开lambda_functor_base的定义，（是不是快晕了，别着急，马上胜利了^_^）

 

 

template<class Args>                                                      
class lambda_functor_base<plus_action, Args> {                           
public:                                                                   
  Args args;                                                              
public:                                                                  
  explicit lambda_functor_base(const Args& a) : args(a) {}                
                                                                          
  template<class RET, class A, class B, class C, class Env>                                
  RET call(A& a, B& b, C& c, Env& env) const {                                     
    return select(boost::tuples::get<0>(args), a, b, c, env)  
           +
           select(boost::tuples::get<1>(args), a, b, c, env); 
  }                                                                      
  template<class SigArgs> struct sig {                                   
    typedef typename                                                      
		boost::tuples::element<0,SigArgs>::type type;         			
  };                                                                     
};

 

 

看来还要着落在slect函数身上啊：

 

template<class Arg, CALL_TEMPLATE_ARGS>
inline typename Arg::template sig<tuple<CALL_REFERENCE_TYPES> >::type
select ( const lambda_functor<Arg>& op, CALL_FORMAL_ARGS ) {
	return op.template call<
	typename Arg::template sig<tuple<CALL_REFERENCE_TYPES> >::type
>	(CALL_ACTUAL_ARGS);
}

 

 

这里是的op参数是什么呢？ 就是我们上面的_1，这里继续调用了_1的call函数，而_1的的类型定义是这样的：

 

typedef const lambda_functor<placeholder<FIRST> > placeholder1_type;

 

 因此会调用placeholder<FIRST>的call方法：

 

template<> struct placeholder<FIRST> {

	template<class SigArgs> struct sig {
		typedef	typename get_element_or_null_type<0, SigArgs>::type type;
	};

	template<class RET, CALL_TEMPLATE_ARGS>
	RET call(CALL_FORMAL_ARGS) const {
		BOOST_STATIC_ASSERT(boost::is_reference<RET>::value);
		CALL_USE_ARGS; // does nothing, prevents warnings for unused args
		return a;
	}
};

 

 

ok，placeholder<FIRST>为我们选取了第一个参数a，也就是（1,2）中的1。

也就是说_0(1,2)最后将转化成1+2。好了，参数的推演我们已经很清楚了。

再来看先返回值的推演，我为了使得这个lambda库的规模尽可能小，对返回值的推演做了简化，返回值主要是通过sig这个内嵌结构推演出来的。我们看下sig的定义：

template<class SigArgs> struct sig {                                    
    typedef typename                                                      
		boost::tuples::element<0,SigArgs>::type type;         			  
  }; 

 

在这里我们只是简单的返回了第一个参数的类型。

 

ok，说完了。关于boost的lambda库，我将在后续的文章中陆续详细写明。