Metaprogramming observations

From: Peter Dimov (pdimov_at_[hidden])
Date: 2001-12-15 11:53:03

The recent "meta-activity" on the list prompted me to try and actually
metaprogram something. I recalled that Dave Abrahams mentioned sorting a
list at compile time; this looked like a good "assignment."

The result is at the end of this message; I'd be interested to compare it
with Dave's original compile-time sort, or another MPL-based or influenced
sort.

What I learned from writing the sort<> metafunction (I deliberately did not
look at MPL first) and then comparing with MPL:

* the MPL concept of "metafunction" (class with a nested template apply<>)
is pretty much necessary given the current state of C++.

* the MPL 'port' of <functional> is very useful and independent of the
iterative-vs-recursive debate. Perhaps because <functional> itself is a
port. ;-)

* many of the MPL algorithms are very useful and necessary; there is a bit
of a naming conflict between the STL and the established 'functional' names
but it's not a showstopper.

* MPL is dominated by an iterative idiom, AFAICS. Nearly everything is done
with a for-style loop. This might have its benefits (more gentle learning
curve for C++/STL programmers) but I think that the recursive style of
programming sometimes produces more elegant and readable functions.

* MPL tries to emulate the STL to the extent of using iterators into
abstract sequences, and providing different 'containers' with their
associated 'traits.' It even has a 'clear' function that returns a new empty
'container' of the same type.

In contrast, Lisp builds everything out of pairs; its only data structure is
the binary tree. A Lisp tree is nearly always a slist; nevertheless,
sometimes a binary tree is a better fit for the concept being modeled.

Both approaches have pros and cons. I prefer the traditional Lisp way.
Without a motivating example to the contrary, I'm inclined to think that in
this area MPL is over-generic.

--
Peter Dimov
Multi Media Ltd.
#include <iostream>
#include <typeinfo>
template<class, class> struct pair;
class nil;
template<int I> struct value_wrapper
{
 enum { value = I };
};
template<class, class> struct less_helper;
template<int A, int B> struct less_helper<value_wrapper<A>, value_wrapper<B>
>
{
 enum { value = (A < B) };
 typedef value_wrapper<value> type;
};
struct less
{
 template<class A, class B> struct apply
 {
  typedef typename less_helper<A, B>::type type;
 };
};
template<class MF> struct not2
{
 template<class A, class B> struct apply
 {
  typedef typename MF::template apply<A, B>::type temp;
  enum { value = !temp::value };
  typedef value_wrapper<value> type;
 };
};
template<class, class> struct append;
template<class A, class B, class C> struct append<pair<A, B>, C>
{
 typedef pair<A, typename append<B, C>::type> type;
};
template<class B> struct append<nil, B>
{
 typedef B type;
};
template<class P, class V> struct bind1st
{
 template<class A> struct apply
 {
  typedef typename P::template apply<V, A>::type type;
 };
};
template<class P, class V> struct bind2nd
{
 template<class A> struct apply
 {
  typedef typename P::template apply<A, V>::type type;
 };
};
template<int A, class B, class C> struct ct_if
{
 typedef B type;
};
template<class B, class C> struct ct_if<0, B, C>
{
 typedef C type;
};
template<class L, class P> struct select_if;
template<class P> struct select_if<nil, P>
{
 typedef nil type;
};
template<class A, class B, class P> struct select_if<pair<A, B>, P>
{
 typedef typename select_if<B, P>::type rest;
 typedef typename P::template apply<A>::type cond;
 enum { cv = cond::value };
 typedef typename ct_if<cv, pair<A, rest>, rest>::type type;
};
template<class L> struct sort;
template<> struct sort<nil>
{
 typedef nil type;
};
template<class A, class B> struct sort<pair<A, B> >
{
 typedef typename select_if<B, bind2nd<less, A> >::type before;
 typedef typename select_if<B, bind2nd<not2<less>, A> >::type after;
 typedef typename append<typename sort<before>::type, pair<A, typename
sort<after>::type> >::type type;
};
int main()
{
 typedef pair<value_wrapper<11>, pair<value_wrapper<5>,
pair<value_wrapper<-1>, pair<value_wrapper<3>, nil> > > > list;
 typedef sort<list>::type list4;
 std::cout << typeid(list4).name() << '\n';
}