[RESOLVED] Problems with writing a metaprogram

**ar115** · April 18th, 2010, 01:49 PM

Hi, I have an enum in my program named Stype like below

Code:

enum Stype { T1, T2, T3 };

There is a template function compute which take two Stype as
template parameter

Code:

template< Stype st1, Stype st2 >
void compute(){
COMPILE_TIME_ASSERT(st1<=st2);
// do something
}

compute is symmetric so that compute<T1,T2>() == compute<T2,T1>()
but I want to restrict user to be able to call compute onnly when st1<=st2 as
forced by a compile-time assert in code.

Now, there is a function compute_at_runtime which is passed two Stype t1, t2 and calls the
correct compute function based on types of t1&t2. currently I have implemented it by hand like below

Code:

void compute_at_runtime( Stype t1, Stype t2 )
{
	if( t1==T1 ){
		if( t2==T1 ){
			compute<T1,T1>();
		} else
		if( t2==T2 ){
			compute<T1,T2>();
		} else
		if( t2==T3 ){
			compute<T1,T3>();
		}
	} else
	if ( t1==T2 ){
		if ( t2==T2 ){
			compute<T2,T2>();
		} else
		if ( t2==T3 ){
			compute<T2,T3>();
		}
	} else
	if ( t1==T3 ){
		if ( t2==T3 ){
			compute<T3,T3>();
		}
	}
}

but I want to make it a metaprogram which generates the code automatically by
recursive template instanciating (like Factorial<N> example) because the user
must be able to extend Stype with new types ( e.g. T4,T5,... ) and it becomes
vary cumbersome to take care of this function

I have written some simple metaprograms, but this one is very hard for me.
I would be very appreciated if anyone could help me with this
Many Thanks

**Lindley** · April 18th, 2010, 02:52 PM

You're trying to make a runtime decision using compile-time syntax. That's going to be tricky at best.

One option might be to use a std::map from the pair of enum values to the appropriate function pointer. It might be possible to use metaprogramming to specify the map contents at compile time, in combination with Boost.Assignment.

**ar115** · April 18th, 2010, 03:10 PM

Thanks I did not know about Boost.Assignment
1- since the number of types T1,T2,... is limited (i'm sure it would be less than 10)
the map search algorithm becomes a little inefficient compared to a simple search

2- and also compute_runtime will be called in a loop it is important for me to make
it as fast as possible, so I want to avoid using function pointers

so what if I want to avoid std::map and function pointers and have the if/else statement
to be generated by a metaprogram

Thanks

**Lindley** · April 18th, 2010, 04:12 PM

Originally Posted by ar115

1- since the number of types T1,T2,... is limited (i'm sure it would be less than 10)
the map search algorithm becomes a little inefficient compared to a simple search

I doubt very much that map's O(lg n) search would be less efficient than an exhaustive series of if/else statements. However, it's possible it might not provide good cache behavior; in that case, arranging to use a sorted vector of function pointers with std::lower_bound() will alleviate the problem.

2- and also compute_runtime will be called in a loop it is important for me to make
it as fast as possible, so I want to avoid using function pointers

Now, that is interesting. Is it likely to be called with the same parameters every time, or will they change?

I'm not good with metaprogramming so I can't offer much specific advice.

**ar115** · April 18th, 2010, 11:07 PM

Originally Posted by Lindley

I doubt very much that map's O(lg n) search would be less efficient than an exhaustive series of if/else statements. However, it's possible it might not provide good cache behavior; in that case, arranging to use a sorted vector of function pointers with std::lower_bound() will alleviate the problem.

I think you are correct, map binary search is good, and I think it would be fastest if the series of
left/right comparisons become unrolled at compile time ( again metaprogram! )

Originally Posted by Lindley

Now, that is interesting. Is it likely to be called with the same parameters every time, or will they change?
I'm not good with metaprogramming so I can't offer much specific advice.

in code it would be called like this

Code:

std::vector<Stype>  stype1;
std::vector<Stype> stype2;
for (int i=0; i<N; ++i){
      compute_at_runtime( stype1[i], stype2[i] );
}

So each time it would be called with different parameters
Thanks

**superbonzo** · April 19th, 2010, 03:17 AM

premising that I don't fully understand why are you doing so... you can use boost mpl for_each;

first of all, you'll need to make your enum "iteratable" by writing "struct Stype{ enum type { T1, T2, T3, size }; };" ( or use an mpl sequence from the beginning ), then you'll need to build the set of "allowed" pairs, finally iterate over them. The produced code should be roughly equivalent to your hand written if's:

Code:

#include <boost/mpl/range_c.hpp>
#include <boost/mpl/arithmetic.hpp>
#include <boost/mpl/transform_view.hpp>
#include <boost/mpl/filter_view.hpp>
#include <boost/mpl/for_each.hpp>

struct Stype{ enum type { T1, T2, T3, size }; };

template< Stype::type st1, Stype::type st2 >
void compute(){/*...*/}

struct call_compute
{
	call_compute( Stype::type v1, Stype::type v2 )
		: v1(v1), v2(v2) {}

	template< typename T > void operator()( T )
	{
		using namespace boost::mpl;

		static const Stype::type first_value = static_cast<Stype::type>( first<T>::type::value );
		static const Stype::type second_value = static_cast<Stype::type>( second<T>::type::value );

		if( v1 == first_value && v2 == second_value ) compute< first_value, second_value >();
	}

private:
	Stype::type v1, v2;
};

void compute_at_runtime( Stype::type t1, Stype::type t2 )
{
	using namespace boost::mpl;

	typedef range_c< int, 0, int(Stype::size)*int(Stype::size) - 1 >	basic_set;
	typedef transform_view< basic_set, pair<
			divides< _1, int_< Stype::size > >, modulus<_1, int_< Stype::size > >
		> >::type 							pairs;
	typedef filter_view< pairs, less_equal< first<_1>, second<_1> > >	ordered_pairs;

	for_each< ordered_pairs >( call_compute(t1,t2) );
}

**ar115** · April 19th, 2010, 10:17 AM

excellent! I did not know we can do such thing with a few boost::mpl code!

I added the int main() below to the code and wanted to compile it but i get errors

Code:

int main(){
Stype::type ts1 = Stype::T1;
Stype::type ts2 = Stype::T3;
compute_at_runtime( ts1, ts2 );
}

the error is:

Code:

mpl.cpp: In function ‘void compute_at_runtime(Stype::type, Stype::type)’:
mpl.cpp:39: error: ‘less_equal’ was not declared in this scope
mpl.cpp:39: error: wrong number of template arguments (3, should be 2)
/usr/local/include/boost/mpl/filter_view.hpp:28: error: provided for ‘template<class Sequence, class Predicate> struct boost::mpl::filter_view’
mpl.cpp:39: error: expected unqualified-id before ‘>’ token
mpl.cpp:41: error: ‘ordered_pairs’ was not declared in this scope
mpl.cpp:41: error: no matching function for call to ‘for_each(call_compute)’