proto 高级篇(续)

我们这里讨论三个例子,这部分内容对应于这个系列 blog 第 4-8 篇内容。

函数的复合

这个例子基本上来自其中 function composition 那篇文章,

#include <boost/utility/result_of.hpp>

struct _ ;

template <class F>
struct func_comp {} ;

template <class F1, class F>
struct func_comp<F1 (F)> {
  typedef func_comp<F> F2 ;

  F1 f1 ;
  F2 f2 ;

  func_comp (F1 e1 = F1(), F2 e2 = F2())
    : f1 (e1), f2 (e2) {}

  template <class Signature>
  struct result ;

  template <class This, class T>
  struct result<This (T)> {
    typedef typename boost::result_of<F2 (T)>::type U ;
    typedef typename boost::result_of<F1 (U)>::type type ;
  } ;

  template <class T> inline typename result<func_comp (T)>::type
  operator() (const T& t) {
    return f1 (f2 (t)) ;
  }
} ;

template <class F>
struct func_comp<F (_)> : F {} ;

template <class F>
struct func_comp<F*> : func_comp<F> {} ;

最后两个特化非常重要,缺一不可,前者是对 template 递归的终止情形的实现(直接继承 F,非常简洁),后者是对编译器在处理 xxx (yyy (zzz (_))) 时将 object 转换成为对应指针的“修正”。我发现其实看原文理解不深刻,倒是通过自己写一遍发现很多错误才知道原来是这样的啊… 下面是一段调用它的代码

struct inc {
  template <class Signature>
  struct result ;

  template <class This, class T>
  struct result<This (T)> {
    typedef T type ;
  } ;

  template <class T> inline T
  operator() (const T& t) {
    return t + 1 ;
  }
} ;

struct sqr {
  template <class Signature>
  struct result ;

  template <class This, class T>
  struct result<This (T)> {
    typedef T type ;
  } ;

  template <class T> inline T
  operator() (const T& t) {
    return t * t ;
  }
} ;

int
main (int, char**) {
  func_comp<inc (sqr (inc (_)))> func ;
  int i = 2 ;
  std::cout << i << ": " << func (i) << std::endl ;
  return 0 ;
}

一个 lambda 的实现

这里我们提供一个类似 boost.lambda 实现,参考以上 blog 的第 4、5、7 篇。实现一个 lambda 其实不难,因为我们其实依赖的具体语义是 default_context 就具有的,这样,我们只需要通过某种手段构造出 expression template,生成一个合适的 functor 在需要的地方使用即可。

#include <boost/proto/proto.hpp>
#include <boost/mpl/int.hpp>
#include <boost/utility/result_of.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/preprocessor.hpp>

namespace util {

  namespace bp = boost::proto ;
  #ifndef UTIL_LAMBDA_ARGS
  #define UTIL_LAMBDA_ARGS 4
  #endif

  template <class Index>
  struct arg_tag {
    typedef Index index ;
  } ;

  template <class Index>
  struct arg_term : bp::terminal<arg_tag<Index> > {} ;

  template <class Expr> struct lambda_expr ;
  struct lambda_domain
    : bp::domain<bp::pod_generator<lambda_expr> > {} ;

  struct lambda ;
  template <class Expr>
  struct lambda_expr {
    template <class Signature>
    struct result ;

#define UTIL_LAMBDA_EXPR_RESULT_SPEC(z, n, unused)              \
    template <class This, class A                               \
              BOOST_PP_ENUM_TRAILING_PARAMS(n, class A)         \
              >                                                 \
    struct result<This (A BOOST_PP_ENUM_TRAILING_PARAMS(n, A))> \
      : boost::result_of<lambda (const This&,                   \
          const boost::tuple<A                                  \
            BOOST_PP_ENUM_TRAILING_PARAMS(n, A)>&)> {} ;

    BOOST_PP_REPEAT(UTIL_LAMBDA_ARGS, UTIL_LAMBDA_EXPR_RESULT_SPEC, ~)

    BOOST_PROTO_BASIC_EXTENDS(Expr, lambda_expr, lambda_domain)
    BOOST_PROTO_EXTENDS_ASSIGN()
    BOOST_PROTO_EXTENDS_SUBSCRIPT()

#define UTIL_LAMBDA_EXPR_NARY_FUNCTION_SPEC(z, n, unused)              \
    template <class A BOOST_PP_ENUM_TRAILING_PARAMS(n, class A)>       \
    typename result<lambda_expr (const A&                              \
      BOOST_PP_ENUM_TRAILING_BINARY_PARAMS(n, const A, & BOOST_PP_INTERCEPT))>::type                                            \
    operator() (const A& a                                             \
      BOOST_PP_ENUM_TRAILING_BINARY_PARAMS(n, const A, & a)) const {   \
      const boost::tuple<const A&                                      \
        BOOST_PP_ENUM_TRAILING_BINARY_PARAMS(n, const A, & BOOST_PP_INTERCEPT)>                                                   \
        state (a BOOST_PP_ENUM_TRAILING_PARAMS(n, a)) ;                \
      return lambda() (*this, state) ;                                 \
    }

    BOOST_PP_REPEAT(UTIL_LAMBDA_ARGS, UTIL_LAMBDA_EXPR_NARY_FUNCTION_SPEC, ~)
  } ;

  struct tuple_get : bp::callable {
    template <class Signature>
    struct result ;

    template <class This, class ArgTag, class Tuple>
    struct result <This (const ArgTag&, const Tuple&)> {
      typedef typename ArgTag::index N ;
      typedef typename boost::tuples::element<N::value, Tuple>::type type ;
    } ;

    template <class ArgTag, class Tuple>
    typename result<tuple_get (const ArgTag&, const Tuple&)>::type
    operator() (const ArgTag&, const Tuple& t) const {
      typedef typename ArgTag::index N ;
      return boost::get<N::value> (t) ;
    }
  } ;

  struct lambda : bp::or_<
    bp::when<
      arg_term<bp::_>,
      tuple_get (bp::_value(bp::_), bp::_state)
    >,
    bp::otherwise<
      bp::_default <lambda> (bp::_, bp::_state)
    >
  > {} ;

#define UTIL_LAMBDA_DUMBASS_SPEC(z, n, unused)              \
  const lambda_expr<arg_term<boost::mpl::int_<n> >::type > _##n = {} ;

  BOOST_PP_REPEAT(UTIL_LAMBDA_ARGS, UTIL_LAMBDA_DUMBASS_SPEC, ~)
}

这段 code 不建议直接看,因为为了灵活,使用了 boost.preprocessor 进行加强,我们现在设定的有 5 个占位符,已经多于 boost.lambda 默认的三个了。这里我们从 high level 讲一下程序的大致思路:

  • 比较讲究的是 tag,这次并没有使用一个一个定义的,也没有直接使用 template<int> 而是继承了 boost::mpl::int_,这是因为我们不仅需要区分这些 tag,更重要的是需要利用“值”来获得 context 里面的对应参数;
  • 这个 context 也没有使用 calculator 例子里面的 std::vector,这是因为我们的参数是异质的(类型可能互相不同),我们无法使用一个 std::vector 来封装(使用 boost.any 带来了运行时开销);
  • 定义了 tag 之后,使用 arg_term 直接继承 boost::proto::terminal 作为我们的 terminal;
  • 之后为了定义 domain(即 lambda_domain),我们前向声明了 expression(即 lambda_expr);
  • 在 lambda_expr 中,我们使用了 lambda 语法,因此我们首先前向声明了语法;
  • lambda_expr 包括 overload 的 operator,这里我们使用 boost.proto 提供的宏;留下的 operator() 被用来构造 functor;记得在 calculator 里面我们特别定义了一个 context,但是这里我们直接使用 boost.tuple 而不在额外定义(定义一个也可以,这样 get_tuple 的任务就会挪到 context 里面去实现);为了使我们的 lambda_expr 成为一个 TR1 标准的 functor,我们也为其提供了 result 模板结构。
  • 事实上,eval 的过程就是在使用 lambda 语法产生的对象作用在当前的 expression 和 context 之上;
  • tuple_get 这个 functor 是为了在 lambda 语法中使用而定义的 transform,它将 terminal 对应的 tag 转换成 tuple 里面的元素,这其实是对 boost::get 的一个 wrapper;
  • 最后定义了 lambda 语法,这个语法非常简单,对 terminal 来说从 tuple 里面取值,而对其他的 expression 就使用默认语义进行变换即可。

不得不承认看了作者原先的代码到写出来,花了不少时间,不得不佩服作者用 code 如金的风格,几乎是字不能增也不得减,拜服!

对 vector 加法的优化

这里我们就简单的解决两个 vector 相加取下标 (a + b)[1] 这类操作的优化,其他的优化我们以后讨论。这个看起来很不可思议的事情其实就是教会编译器知道“下标对加法的分配律”这个语法!

这个说法看起来很不可思议,但是实际上就是这样,问题是如何通过 boost.proto 的 grammar 机制表达这个概念

namespace misc {
  namespace bp = boost::proto ;

  template <class T>
  struct is_std_vector : boost::mpl::false_ {} ;

  template <class T>
  struct is_std_vector<std::vector<T> > : boost::mpl::true_ {} ;

  struct some_domain : bp::domain<> {} ;

  BOOST_PROTO_DEFINE_OPERATORS(is_std_vector, some_domain)

  struct take_index : bp::or_<
    bp::when<
      bp::terminal<bp::_>,
      bp::_make_subscript(bp::_, bp::_state)
    >,
    bp::plus<take_index, take_index>
  > {} ;

  struct distr_index : bp::or_<
    bp::terminal<bp::_>,
    bp::plus<distr_index, distr_index>,
    bp::when<
      bp::subscript<take_index, bp::_>,
      take_index (bp::_left (bp::_), bp::_right (bp::_))
    >
  > {} ;
}

前面都是一些 routine work,我们主要说明现在的语法是如何工作的:distr_index 对 terminal 或者加法都是无所谓的,但是碰到了取下标的时候就看看是否能匹配上前一个参数符合 take_index 语法的 expression,后一个随意,匹配上的时候我们调用 transform,这个 transform 还是 take_index 语法,它将此时的第一个参数作为 expression,第二个参数作为 context 传递;take_index 语法也很简单,如果是 terminal 就取下标,下标存放在 _state 里面,其他支持对加法的匹配。这样通过 take_index 就能将取下标 distribute 到每个加数上了。

int data [] =  {2, 0, 1, 2} ;
std::vector<int> a (data, data + 4), b (a) ;
using namespace misc ;
bp::display_expr ((a + b)[1]) ;
bp::display_expr (distr_index() ((a + b)[1])) ;

这段代码输出的两棵树如下

subscript(
    plus(
        terminal(St6vectorIiSaIiEE)
      , terminal(St6vectorIiSaIiEE)
    )
  , terminal(1)
)
plus(
    subscript(
        terminal(St6vectorIiSaIiEE)
      , terminal(1)
    )
  , subscript(
        terminal(St6vectorIiSaIiEE)
      , terminal(1)
    )
)

——————-
And he said, Hagar, Sarai’s maid, from where came you? and where will you go? And she said, I flee from the face of my mistress Sarai.

Advertisements
proto 高级篇(续)

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s