I encountered the following problem today which I've reduced down to a simple example. Basically what I want to do is recurse through a typelist (mpl::vector) popping an element each time and end recursion by using apply_if with mpl::empty<List> as the condition. I've made a simple Reverse class template to illustrate the problem. (The Reverse class is of course intended to reverse the contents of a typelist....) --------------------- begin code --------------------- #include <boost/mpl/front.hpp> #include <boost/mpl/push_back.hpp> #include <boost/mpl/pop_front.hpp> #include <boost/mpl/apply_if.hpp> #include <boost/mpl/empty.hpp> #include <boost/mpl/size.hpp> #include <boost/mpl/vector.hpp> using namespace boost::mpl; template <typename List> struct Reverse { typedef typename front<List>::type FrontElem; typedef typename pop_front<List>::type Rest; typedef typename apply_if< empty<Rest>, vector<FrontElem>, typename push_back<typename Reverse<Rest>::Type, FrontElem>::type >::type Type; }; typedef vector<int,int,long> List; typedef Reverse<List>::Type RevList; --------------------- end code ----------------------- When attempting to create the RevList type however, gcc spits the following at me: reverse.cpp: In instantiation of `boost::mpl::pop_front<boost::mpl::vector0<boost::mpl::void_> >': reverse.cpp:15: instantiated from `Reverse<boost::mpl::vector0<boost::mpl::void_> >' reverse.cpp:21: instantiated from `Reverse<boost::mpl::vector1<long int> >' reverse.cpp:21: instantiated from `Reverse<boost::mpl::vector2<int, long int> >' reverse.cpp:21: instantiated from `Reverse<List>' reverse.cpp:25: instantiated from here reverse.cpp:15: base class ` boost::mpl::pop_front_traits<boost::mpl::aux::vector_tag<0>
::algorithm<boost::mpl::vector0<boost::mpl::void_> >' has incomplete type reverse.cpp: In instantiation of `Reverse<boost::mpl::vector0<boost::mpl::void_> >': reverse.cpp:21: instantiated from `Reverse<boost::mpl::vector1<long int> >' reverse.cpp:21: instantiated from `Reverse<boost::mpl::vector2<int, long int> >' reverse.cpp:21: instantiated from `Reverse<List>' reverse.cpp:25: instantiated from here reverse.cpp:15: no type named `type' in `struct boost::mpl::pop_front<boost::mpl::vector0<boost::mpl::void_> >' reverse.cpp:21: no type named `type' in `struct boost::mpl::pop_front<boost::mpl::vector0<boost::mpl::void_> >' reverse.cpp: In instantiation of `Reverse<boost::mpl::vector1<long int> ': reverse.cpp:21: instantiated from `Reverse<boost::mpl::vector2<int, long int> >' reverse.cpp:21: instantiated from `Reverse<List>' reverse.cpp:25: instantiated from here reverse.cpp:21: no type named `Type' in `struct Reverse<boost::mpl::vector0<boost::mpl::void_> >' reverse.cpp: In instantiation of `Reverse<boost::mpl::vector2<int, long int> >': reverse.cpp:21: instantiated from `Reverse<List>' reverse.cpp:25: instantiated from here reverse.cpp:21: no type named `Type' in `struct Reverse<boost::mpl::vector1<long int> >' reverse.cpp: In instantiation of `Reverse<List>': reverse.cpp:25: instantiated from here reverse.cpp:21: no type named `Type' in `struct Reverse<boost::mpl::vector2<int, long int> >' reverse.cpp:25: syntax error before `;' token
I cannot see why it reaches the point where it tries to instantiate Reverse with an empty typelist - the apply_if should stop that (at least that's my intention. Am I being a complete ass somewhere in this code snippet? I've become blinded by now, so if anyone can point out what's wrong I would greatly appreciate it. Sincerely, -- Tarjei
Tarjei Knapstad <tarjeik@chemcon.no> writes:
I encountered the following problem today which I've reduced down to a simple example. Basically what I want to do is recurse through a typelist (mpl::vector) popping an element each time and end recursion by using apply_if with mpl::empty<List> as the condition. I've made a simple Reverse class template to illustrate the problem. (The Reverse class is of course intended to reverse the contents of a typelist....)
--------------------- begin code ---------------------
#include <boost/mpl/front.hpp> #include <boost/mpl/push_back.hpp> #include <boost/mpl/pop_front.hpp> #include <boost/mpl/apply_if.hpp> #include <boost/mpl/empty.hpp> #include <boost/mpl/size.hpp> #include <boost/mpl/vector.hpp>
using namespace boost::mpl;
template <typename List> struct Reverse { typedef typename front<List>::type FrontElem; typedef typename pop_front<List>::type Rest; typedef typename apply_if< empty<Rest>, vector<FrontElem>, typename push_back<typename Reverse<Rest>::Type, FrontElem>::type >::type Type; };
typedef vector<int,int,long> List; typedef Reverse<List>::Type RevList;
--------------------- end code -----------------------
When attempting to create the RevList type however, gcc spits the following at me:
reverse.cpp: In instantiation of `boost::mpl::pop_front<boost::mpl::vector0<boost::mpl::void_> >': reverse.cpp:15: instantiated from `Reverse<boost::mpl::vector0<boost::mpl::void_> >' reverse.cpp:21: instantiated from `Reverse<boost::mpl::vector1<long int> >' reverse.cpp:21: instantiated from `Reverse<boost::mpl::vector2<int, long int> >' reverse.cpp:21: instantiated from `Reverse<List>' reverse.cpp:25: instantiated from here
reverse.cpp:15: base class ` boost::mpl::pop_front_traits<boost::mpl::aux::vector_tag<0>
::algorithm<boost::mpl::vector0<boost::mpl::void_> >' has incomplete type
That line above means that you tried to pop the front element off an empty vector, and it's easy to see that pop_front<List>::type is evaluated whether List is empty or not. Some things to note: 1. If your algorithm is doing repeated pop_fronts, you probably want a list: since each successive list is a sublist of the previous one, the new list doesn't cost any instantiations 2. Barring that, use an iterator_range to avoid instantiating a new vector at each iteration 3. The easy way to do this is mpl::fold< List , mpl::push_front<> , typename mpl::clear<List>::type>::type > I believe. HTH, -- Dave Abrahams Boost Consulting www.boost-consulting.com
On Mon, 2003-05-19 at 21:34, David Abrahams wrote:
Tarjei Knapstad <tarjeik@chemcon.no> writes:
I encountered the following problem today which I've reduced down to a simple example. Basically what I want to do is recurse through a typelist (mpl::vector) popping an element each time and end recursion by using apply_if with mpl::empty<List> as the condition. I've made a simple Reverse class template to illustrate the problem. (The Reverse class is of course intended to reverse the contents of a typelist....)
--------------------- begin code ---------------------
#include <boost/mpl/front.hpp> #include <boost/mpl/push_back.hpp> #include <boost/mpl/pop_front.hpp> #include <boost/mpl/apply_if.hpp> #include <boost/mpl/empty.hpp> #include <boost/mpl/size.hpp> #include <boost/mpl/vector.hpp>
using namespace boost::mpl;
template <typename List> struct Reverse { typedef typename front<List>::type FrontElem; typedef typename pop_front<List>::type Rest; typedef typename apply_if< empty<Rest>, vector<FrontElem>, typename push_back<typename Reverse<Rest>::Type, FrontElem>::type >::type Type; };
typedef vector<int,int,long> List; typedef Reverse<List>::Type RevList;
--------------------- end code -----------------------
When attempting to create the RevList type however, gcc spits the following at me:
reverse.cpp: In instantiation of `boost::mpl::pop_front<boost::mpl::vector0<boost::mpl::void_> >': reverse.cpp:15: instantiated from `Reverse<boost::mpl::vector0<boost::mpl::void_> >' reverse.cpp:21: instantiated from `Reverse<boost::mpl::vector1<long int> >' reverse.cpp:21: instantiated from `Reverse<boost::mpl::vector2<int, long int> >' reverse.cpp:21: instantiated from `Reverse<List>' reverse.cpp:25: instantiated from here
reverse.cpp:15: base class ` boost::mpl::pop_front_traits<boost::mpl::aux::vector_tag<0>
::algorithm<boost::mpl::vector0<boost::mpl::void_> >' has incomplete type
That line above means that you tried to pop the front element off an empty vector, Yes, I noticed that but...
and it's easy to see that pop_front<List>::type is evaluated whether List is empty or not.
...is it? I thought apply_if<> only instantiated either the 'true' or 'false' statement depending on the condition. When the recursion gets down to where the Rest type is a list with only one element, this is what I thought should happen: 1. 'FrontElem' becomes the one reamining type in the list. 2. 'Rest' becomes an empty list after pop_front<> has been applied to List which has one element. 3. The condition empty<Rest> in the apply_if evaluates to true, thus Type is now vector<FrontElem> instead of instantiating another Reverse class with the empty list which would of course wreak havoc. Types are then recursively pushed onto this vector. At least that was the thought behind all this, i.e. because of the apply_if, Reverse should never be instantiated with an empty list.
Some things to note:
1. If your algorithm is doing repeated pop_fronts, you probably want a list: since each successive list is a sublist of the previous one, the new list doesn't cost any instantiations
2. Barring that, use an iterator_range to avoid instantiating a new vector at each iteration
Thanks, will keep in mind. In fact it looks like I can more or less adopt my STL mindset to the MPL which I guess is half the point :) (barring the pop_back stuff ;) )
3. The easy way to do this is
mpl::fold< List , mpl::push_front<> , typename mpl::clear<List>::type>::type >
I believe.
Thanks a lot, this works great! (except that the push_front and clear arguments need to be switched around) Thanks once again for your help Dave, -- Tarjei
Tarjei Knapstad <tarjeik@chemcon.no> writes:
On Mon, 2003-05-19 at 21:34, David Abrahams wrote:
Tarjei Knapstad <tarjeik@chemcon.no> writes:
I encountered the following problem today which I've reduced down to a simple example. Basically what I want to do is recurse through a typelist (mpl::vector) popping an element each time and end recursion by using apply_if with mpl::empty<List> as the condition. I've made a simple Reverse class template to illustrate the problem. (The Reverse class is of course intended to reverse the contents of a typelist....)
--------------------- begin code ---------------------
#include <boost/mpl/front.hpp> #include <boost/mpl/push_back.hpp> #include <boost/mpl/pop_front.hpp> #include <boost/mpl/apply_if.hpp> #include <boost/mpl/empty.hpp> #include <boost/mpl/size.hpp> #include <boost/mpl/vector.hpp>
using namespace boost::mpl;
template <typename List> struct Reverse { typedef typename front<List>::type FrontElem; typedef typename pop_front<List>::type Rest; typedef typename apply_if< empty<Rest>, vector<FrontElem>, typename push_back<typename Reverse<Rest>::Type, FrontElem>::type >::type Type; };
typedef vector<int,int,long> List; typedef Reverse<List>::Type RevList;
<snip>
and it's easy to see that pop_front<List>::type is evaluated whether List is empty or not.
...is it?
Sure! What happens when you try to Reverse an empty sequence?
I thought apply_if<> only instantiated either the 'true' or 'false' statement depending on the condition.
Yes, but it doesn't inhibit evaluation *lexically*. Whenever you write ::type, you get a non-lazy evaluation. In fact, your apply_if is not delaying anything, since you greedily evaluate the 2nd argument, and the first argument is already the right type. You'd get the first argument correctly because vector<T1, T2, ... TN>::type == vector<T1, T2, ... TN> And for the same reasons, the 2nd argument to apply_if has the right type but is evaluated early. Even if you stripped the outer typename...::type and wrote: typedef typename apply_if< empty<Rest> , vector<FrontElem> , push_back< typename Reverse<Rest>::Type , FrontElem > >::type Type; you'd still be in trouble because Reverse is being evaluated greedily. The code above translates to something like (runtime): return ( // select a function object Rest.empty() ? boost::bind(identity, seq<type>(1, FrontElem)) : boost::bind(push_back, reverse(Rest), FrontElem) ) (); // now invoke it If you really want to do it that way, break the thing you want to delay out into a separate metafunction: template <class Seq, class E> struct append_reversed : push_back<typename Reverse<Seq>::type, E> { }; ... typedef typename apply_if< empty<Rest> , vector<FrontElem> , append_reversed<Rest,FrontElem> >::type Type; or, apply a lambda expression explicitly: typedef typename apply_if< empty<Rest> , vector<FrontElem> , apply< lambda<push_back<Reverse<_1>, FrontElem> > , Rest > >::type Type;
Some things to note:
1. If your algorithm is doing repeated pop_fronts, you probably want a list: since each successive list is a sublist of the previous one, the new list doesn't cost any instantiations
2. Barring that, use an iterator_range to avoid instantiating a new vector at each iteration
Thanks, will keep in mind. In fact it looks like I can more or less adopt my STL mindset to the MPL which I guess is half the point :) (barring the pop_back stuff ;) )
Oh, and please, do yourself a favor and follow the MPL metafunction protocol! That means your result is called "::type", not "::Type".
3. The easy way to do this is
mpl::fold< List , mpl::push_front<> , typename mpl::clear<List>::type>::type >
I believe.
Thanks a lot, this works great! (except that the push_front and clear arguments need to be switched around)
Thanks once again for your help Dave,
Sure thing. -- Dave Abrahams Boost Consulting www.boost-consulting.com
On Tue, 2003-05-20 at 17:56, David Abrahams wrote:
Tarjei Knapstad <tarjeik@chemcon.no> writes:
On Mon, 2003-05-19 at 21:34, David Abrahams wrote:
Tarjei Knapstad <tarjeik@chemcon.no> writes:
<snip>
and it's easy to see that pop_front<List>::type is evaluated whether List is empty or not.
...is it?
Sure! What happens when you try to Reverse an empty sequence?
Ah yes certainly, but in my real case (i.e. not this Reverse thingy), giving an empty sequence means you're trying to generate illegal code, so it's actually a positive side effect there (sorry, forgot to mention this...)
I thought apply_if<> only instantiated either the 'true' or 'false' statement depending on the condition.
Yes, but it doesn't inhibit evaluation *lexically*. Whenever you write ::type, you get a non-lazy evaluation. In fact, your apply_if is not delaying anything, since you greedily evaluate the 2nd argument, and the first argument is already the right type. You'd get the first argument correctly because
<snip, long explanation> Ahh, it was the ::type requests which I didn't have a sufficient understanding for. I've solved it for now by specializing my class template for an empty sequence (I had a look at the Lambda stuff, but it involved quite a bit more than the specialization so I've postponed it)
Oh, and please, do yourself a favor and follow the MPL metafunction protocol! That means your result is called "::type", not "::Type".
Yes, but this goes againts our own coding standards unfortunately (all types are captialized). I'm considering a modification to our standards though, in that stuff that models STL concepts (like iterators etc.) should be named like they are in the STL. I'm still undecided on what will end up being less confusing... On a sidenote, I seem to remember from the ACCU conf. in Oxford this year that you were preparing a book on the MPL? Is it in it's early stages, or do you have any rough date for it's completion? (It certainly looks like I could need a copy ;) ) Thanks, -- Tarjei
Tarjei Knapstad <tarjeik@chemcon.no> writes:
Ahh, it was the ::type requests which I didn't have a sufficient understanding for. I've solved it for now by specializing my class template for an empty sequence (I had a look at the Lambda stuff, but it involved quite a bit more than the specialization so I've postponed it)
If that's the only change you made, I guess I'd say... ick. Why not use the nice fold invocation I gave you instead? But, to each his own.
Oh, and please, do yourself a favor and follow the MPL metafunction protocol! That means your result is called "::type", not "::Type".
Yes, but this goes againts our own coding standards unfortunately (all types are captialized). I'm considering a modification to our standards though, in that stuff that models STL concepts (like iterators etc.) should be named like they are in the STL. I'm still undecided on what will end up being less confusing...
It's less about confusability than about interoperability. If your template is an MPL metafunction you can use it in lambda expressions, with apply_if, etc. Otherwise, you can't.
On a sidenote, I seem to remember from the ACCU conf. in Oxford this year that you were preparing a book on the MPL? Is it in it's early stages, or do you have any rough date for it's completion? (It certainly looks like I could need a copy ;) )
It's in its early-middle stages. -- Dave Abrahams Boost Consulting www.boost-consulting.com
participants (2)
-
David Abrahams -
Tarjei Knapstad