[proto] design of expr<>
Hi! I want to discuss the internal data structure expr<>: I like the way expr<> is built regarding to the first and second template argument: It is well thought and done to have the expression tag as first argument and some fusion-compatible typelist as its second argument containing the operands. OTOH the third template argument contains redundant information: The docs say: "Proto expression nodes are valid Fusion random-access sequences of their children nodes." So the information about the number of arguments is accessible via some size<T>::type metafunction e.g. depending on result_of::distance<result_of::begin<S>::type result_of::end<S>::type>::type? In my unfinished attempts to write a paper about ET library design (now obsolote, thanks to Eric) I have a statement that any expression representation taking more than 2 template arguments is wrong. Eric, since you always have a good reason for your design: Could you please elaborate on this? Also I ask myself whether there was a good reason not to follow mpl and use types to represent numbers. I'd prefer at least some parallism to mpl here: size_t<c>? Markus
Steven Watanabe <watanabesj <at> gmail.com> writes:
Sorry if I do not get that one.
And users don't need to care about it, since it has a default.
"User" is a very ambiguous word for proto. Actually most "users" of proto will be "library writers" seeking to boost (sic!) their productivity. So even the nitty-gritty details matter. I reject any "do-not-mind-it's-only-deep-inside" arguments here. Everybody writing a compile time algorithm acting on proto structures for whatever reason will be affected by this "detail" and the implications might only become clear later, when somebody is in need to do some compile-time-magic.
From Daixtrose I know that the number of template arguments can be reciprocal to readability, maintainability and extensibility.
Markus
AMDG Markus Werle wrote:
The definition of expr is something like: template<class Tag, class Args, int Arity = Args::arity> struct expr; template<class Tag, class Args> struct expr<Tag, Args, 0> { typename Args::arg0 arg0; }; template<class Tag, class Args> struct expr<Tag, Args, 1> { typename Args::arg0 arg0; }; template<class Tag, class Args> struct expr<Tag, Args, 2> { typename Args::arg0 arg0; typename Args::arg1 arg1; }; ...
You can (and should) write expr<terminal_tag, args0<int> > rather than expr<terminal_tag, args0<int>, 0>. Library writers are not somehow special in this respect. When I said "user" I meant anyone who is not the author or maintainer of proto.The only problems that I can see are that mpl::apply<expr<mpl::_, mpl::_>, terminal_tag, args0<int> > won't work and that mpl::quote2<expr> will fail. In Christ, Steven Watanabe
Steven Watanabe <watanabesj <at> gmail.com> writes:
AMDG
Markus Werle wrote:
OK, and what is the advantage of the 3rd template argument Arity then? AFAICS this is needed for the BOOST_PP_ITERATION magic, but strictly speaking it is not necessary for the data _representation_, right? Also I feel very uncomfortable about those typedefs above ... can't we get along accessing by index when in need for it? Markus
Markus Werle wrote:
You have to partially specialize on *something*. That's what the 3rd template parameter is for. This is not something I can remove. I can't get the design I need without it.
Also I feel very uncomfortable about those typedefs above ... can't we get along accessing by index when in need for it?
You mean, with a Fusion-like at<> template? It's there if you want to use it, and are ok with the cost of instantiating a template to access an element. Proto's internals access nested typedefs directly so they don't need to instantiate more templates than needed. -- Eric Niebler Boost Consulting www.boost-consulting.com
On 03/10/08 12:08, Eric Niebler wrote:
Couldn't you use a helper template, e.g. expr_arity, *with* the third parameter = size<Args>::value and then expr_arity is specialized on that last arg? OOPS, then you'd be the same place you are now with an the 2 arg expr and the 3 arg expr_arity specialized the same number of times as the existing 3 arg expr. Since there no gain is ability be extra templates, the better solution is the existing 3 arg expr with specialization on last arg. IOW, I kinda agree with Eric here.
On 03/10/08 13:16, Larry Evans wrote:
What about recording the arity *with* the tag instead of in the expression associated with the tag? IOW, instead of: expr<Tag,Args,Arity> have: expr<tag_arity<Tag,Arity>,Args> Why? Well, it directly associates the arity with the Tag instead of with the expression. After all, sin(X) is not expressed as sin(x,1). [or in lisp terms, (sin x) is not expressed as (sin x 1) ].
On 03/20/08 16:53, Eric Niebler wrote:
I don't think it solves any problem that can't already be solved, but it makes the solution clearer. It's clearer because the arity is associated with the tag *not* the expression. The arity of a tag does not depend on the expression; so, it should not be in the expression. Instead the arity of the tag determines the expression validity. OK, but you may say "the arity *still* is in the expression: expr<tag_arity<Tag,Arity>,Args> "; however, it's "more closely" associated with the tag than the expression, so it's really more a matter of style, I guess. OTOH, I would guess it would make specifying morphisms between algebra's easier since any morphism would map equal arity's to equal arities; and if the arity were directly associate with the tag, as in tag_arity<Tag,Arity>, then the mapping would be easier to understand and verify (with maybe a boost concepts class which assured the pairs in the mpl map had equal arities on both sides).
Larry Evans wrote:
Sorry, but that's backwards. Tags don't have arities, expressions do. The arity of tag::function could be anything. The arity represents the number of children of an expression node. So the arity is a very real part of an expression. -- Eric Niebler Boost Consulting www.boost-consulting.com
On 03/20/08 19:11, Eric Niebler wrote:
Fair enough. That's a lotta freedom. That also allows: expr<tag::shift_right, Args, 0> I guess. However, I'd imagine some people would want this restricted to just two elements, which could be done with something like: template<class Tag,int Arity> struct tag_arity { private: tag_arity(void) ; void operator=(tag_arity const&) ; }; struct shift_right; template<> struct tag_arity<shift_right,2> { public: tag_arity(void) {} void operator=(tag_arity const&) {} }; tag_arity<shift_right,2> tag_shift_right_2; tag_arity<shift_right,1> tag_shift_right_1;//fails compile And now, if size<Args>::value is restricted to the Arity in tag_arity<shift_right,Arity> then it would be restricted to 2. Now to handle the case of function, just do: struct function; template<int Arity> struct tag_arity<function,Arity> { public: tag_arity(void) {} void operator=(tag_arity const&) {} }; So anything with function will allow any int value for size<Args>::value.
Larry Evans wrote:
Users may very well want to restrict tag::plus to arity 2 *in their domain*, but they shouldn't be foisting that decision on other consumers of Proto. The best way to ensure that expressions have the arity you expect is to encode that in the grammar for your domain, and check it with proto::matches. -- Eric Niebler Boost Consulting www.boost-consulting.com
On Fri, Mar 21, 2008 at 9:17 AM, Eric Niebler <eric@boost-consulting.com> wrote:
I'm nowhere near being an expert, but how would a BOOST_STATIC_ASSERT fit in ensuring that Args has the correct arity provided in the construction of expr<>? Would there be a way to statically assert that 'Args' has arity 'Arity' from within Proto? Or would that be too much compile time trouble on top of all the compile time burdens Proto+Fusion+MPL already bring? -- Dean Michael C. Berris Software Engineer, Friendster, Inc. [http://blog.cplusplus-soup.com] [mikhailberis@gmail.com] [+63 928 7291459] [+1 408 4049523]
Dean Michael Berris wrote:
What do you mean by "correct" here?
construction of expr<>? Would there be a way to statically assert that 'Args' has arity 'Arity' from within Proto? Or would that be too much
Oh, Arity is the size of Args by default. expr<> is defined like: struct expr<Tag, Args, long Arity = Args::size> Nowhere does Proto enforce that Arity really *is* Args::size, though.
compile time trouble on top of all the compile time burdens Proto+Fusion+MPL already bring?
I don't think a static assert would be very expensive, but I also don't think it would add much safety. In fact, it would force me to remove an optimization in matches.hpp, where I fudge the Arity parameter to save a few template instantiations. -- Eric Niebler Boost Consulting www.boost-consulting.com
On Sat, Mar 22, 2008 at 12:05 AM, Eric Niebler <eric@boost-consulting.com> wrote:
I say "correct" and mean that Args really does have arity 'Arity'.
The question then should be, would it be beneficial (for correct usage's sake) if Proto did make sure that the Arity parameter of the construction of an 'expr<>' was really the correct arity of the Args parameter? This should make defining expr's that have different Arity's but the same Arguments incorrect usage: expr<my_tag, my_args, 2> should not compile if my_args really has an arity other than 2, and expr<my_tag, my_args, 2> shouldn't be different from expr<my_tag, my_args, 3> (which given that we assert my_args has arity 2, would be illegal). In this case 'expr<my_tag, my_args>' is really just what's necessary.
I think this begs the question then, what is the necessity for an Arity parameter as part of the definition of an expr<>? Should expr<my_tag, my_args, 3> and expr<my_tag, my_args, 2> be different? Should the arity even be part of the instantiation of the expr<>, or should it really be just a nested value inside expr<>? template <class Tag, class Args> struct expr { static typename arity_count<Args>::type arity = arity_count<Args>::value; ... }; Of course, the above requires the arity_count<> trait/metafunction to be defined for each Args possibility (in which case it can be an overloaded metafunction wrapper to existing Sequence arity counting metafunctions). Which eerily, can also be applied to the 'tag' instead of the Args parameter, coming close to what Larry has been proposing of having the arity associated somehow with the tag instead. Moreover, something like: arity_count< expr<my_tag, my_args> > May even make some sense, although it's hard for me to think about a use case for that from within or even outside of Proto. Just throwing some ideas around. I hope this helps. -- Dean Michael C. Berris Software Engineer, Friendster, Inc. [http://blog.cplusplus-soup.com] [mikhailberis@gmail.com] [+63 928 7291459] [+1 408 4049523]
On 03/22/08 06:12, Dean Michael Berris wrote: [snip]
I think this begs the question then, what is the necessity for an Arity parameter as part of the definition of an expr<>?
According to: http://archives.free.net.ph/message/20080310.170830.c4548dd4.en.html it's use for specialization. In my reply to that post I suggested maybe a helper template to eliminate the need for this 3ird parameter, but then, AFAICT, this just delays the need for a 3 parameter expr...but wait, if some how the 2 parameter expr were public and somehow the 3 parameter were made private, maybe that would be better. Like you, I'm just "throwing some ideas around". Apparently it's not used to enforce the arity of the 2nd expr arg. Eric suggested this be done by using a grammar and matches, but AFAICT that sorta delays the detection of arity violation.
On 03/22/08 09:13, Steven Watanabe wrote:
Hi Steven, Could you post a test case with the before (only 1 expr with 3 args) and after (i.e. 2 expr templates where proto::expr takes 2 args and proto::detail::expr takes 3 args, where the 3ird is the arity) and then maybe some example in proto which specializes on arity and show how the 2 expr template method wouldn't work? Of course I could try it and see if I could make it fail, but I was hoping you had a better idea of how to make it ( i.e. the 2 expr method) fail. -regards, Larry
AMDG Larry Evans wrote:
template<class Tag, class Args, int arity = Args::arity> struct expr3; template<class Tag, class Args> struct expr3<Tag, Args, 2> { typename Args::arg0 arg0; typename Args::arg1 arg1; }; template<class Tag, class Args> struct expr2 { expr3<Tag, Args> args; }; struct test { int i; }; struct my_args { enum { arity = 2 }; typedef test arg0; typedef test arg1; }; struct my_tag {}; int main() { expr3<my_tag, my_args> x3 = { {1}, {1} }; expr2<my_tag, my_args> x2 = { {1}, {1} }; // error C2078: too many initializers } In Christ, Steven Watanabe
AMDG Larry Evans wrote:
Exactly. If you recall I said that it changes the interface. Not that it doesn't work. In short, the existence of the "private" partially specialized version of expr would not entirely be an implementation detail. This may also add overhead because of the extra template. On the other hand, it may compile faster because the operator() overloads don't need to be duplicated. Oh. I just realized that this would also force expr::make to change. expr::make() takes a number of arguments equal to the arity so it needs to be in the private struct as well. I'm afraid that this would ripple across the library, and turn out to be a not so minor change, after all. In Christ, Steven Watanabe
Steven Watanabe wrote:
Yes, I've played with a similar design, and I've found it to cause initialization to be rather tricky. Consider the following initializations today: terminal<int>::type t = {1}; plus< terminal<int>::type , terminal<int>::type
::type u = {{1}, {1}};
That's fairly straightforward. With an extra set of braces with each expr, it becomes the rather unwieldy: terminal<int>::type t = {{1}}; plus< terminal<int>::type , terminal<int>::type
::type u = {{{{1}}, {{1}}}};
That hurts my eyes. -- Eric Niebler Boost Consulting www.boost-consulting.com
On 03/22/08 22:26, Eric Niebler wrote:
The file, expk_test.zip here: http://www.boost-consulting.com/vault/index.php?&directory=Strings%20-%20Text%20Processing Contains a prototype where tags contain the arity. This prototype enables initialization like: <===== cut here ======= using namespace boost::proto; typedef tags::tag_kind_arity<tags::tag2<tags::tag2_shift_right>,tags::tag_valu,2> tag_shift_right_2; expk<tag_shift_right_2,args2<int,int> > shift_right_int_int={1,2};
===== cut here =======
Now if, instead of args2<int,int>, there was args2<terminal<int>,terminal<int> >, I'm assuming it would behave like the current: u = {{1}, {1}} I tried to figure out if putting arity in tags would prevent some specialization on arity which proto currently uses to do it's work. I guessed that maybe this specialization was used in or_ or and_; however, when I looked in matches.hpp, all I found (that was relevant, AFAICT) was: // and_ and or_ implementation template<bool B, typename Expr, typename G0> struct or1 : mpl::bool_<B> { typedef G0 which; }; template<bool B> struct and1 : mpl::bool_<B> {}; and I couldn't figure out how it works. I would have guessed there would be some specialization on the bool B template parameter, but apparently not. Eric, could you mention the code where specialization on arity is used and how it works. I might could figure it out eventually, but I'm guessing others, in the future, might like to understand this also, and this information, documented somewhere in an implementation or design guide, would be *real* handy. Of course, I realize you're in the middle of analyzing all the proto reviews, but eventually, getting this information about how it works would be quite helpful. TIA -regards, Larry
Larry Evans wrote:
What's that?
expk<tag_shift_right_2,args2<int,int> > shift_right_int_int={1,2};
Why? What is there works very well and nobody is complaining about it.
Just about every part of Proto is specialized on expression arity. See the file iteration in deep_copy.hpp for an example.
I probably won't ever document Proto's internal implementation details, sorry. Use the source. Preprocess it first, if it makes it easier. -- Eric Niebler Boost Consulting www.boost-consulting.com
On 03/20/08 20:17, Eric Niebler wrote:
Good point. I agree. then just define: template<class Tag,int Arity,class Domain=default_domain> tag_arity{}; which has no restrictions on arity, but it allow the user to specify restrictions by specializaing on Domain.
Like in the attached?
Larry Evans wrote:
Proto provides this functionality, but in a different way. When defining your domain, you can specify the grammar to which all expressions within that domain must conform. If you do that, Proto will ensure that only expressions that conform to your grammar are created. It does this by disabling (via SFINAE) the operator overloads that would create non-conforming expressions.
You got it. -- Eric Niebler Boost Consulting www.boost-consulting.com
Steven Watanabe wrote:
The expr<> type doesn't show up in code, unless you're doing something a little weird. Can you say why you think an extra defaulted template parameter on a type which doesn't show up in user code affects readability, maintainability or extensibility?
You can (and should) write expr<terminal_tag, args0<int> > rather than expr<terminal_tag, args0<int>, 0>.
I agree it's worth considering these issues, but have a look at Proto's examples. The expr<> type is not mentioned once in any of them. The advanced features of Proto make stating expression types in code unnecessary.
That's a legitimate concern. How important do you consider these use cases? -- Eric Niebler Boost Consulting www.boost-consulting.com
AMDG Eric Niebler wrote:
I personally avoid mpl::lambda, so this won't affect me. I wouldn't worry about mpl::quote. In any event, it's easy to write a wrapper metafunction. It may cause surprises that lambda doesn't work (especially because it will be silent), but as you mentioned above direct use of expr should be uncommon. In Christ, Steven Watanabe
Steven Watanabe wrote:
The typelist used there is not Fusion-compatible, but expr<> as a whole is. For a while, I was using mpl::vector<> as the second template parameter to expr<>, but I changed to a very simple custom type because it improved compile times.
That's true.
Steven has it right. The expr<> struct has no primary implementation ... just specializations. And it is designed to be POD where possible so that it can be statically initialized. Considering that the implementation of a binary expr must differ from that of a unary expr, the only way I could do that would be to add a defaulted template parameter on which I could create specializations. There was another reason, too. Users might want to be able to overload on the arity of an expression. // handle unary expressions template<typename Tag, typename Args> void foo(expr<Tag, Args, 1> const &e); // handle binary expressions template<typename Tag, typename Args> void foo(expr<Tag, Args, 2> const &e); This sort of thing was common in the bad old days before Proto had grammars and transforms. It's not as important now, but still a nice-to-have, IMO.
Yes, I've considered this, and I'm willing to change it. The original reason for going with raw numbers was to make the overloading trick above easier. (Users don't have to worry, is it a size_t<> or an int_<> or a ...?) Since the overloading trick is not commonly needed I don't have strong feelings about it. The only bad thing about that change is that it would make the debug symbols for complicated expressions even longer, and give users longer compiler error messages to wade through. HTH, -- Eric Niebler Boost Consulting www.boost-consulting.com
On 03/10/08 11:29, Eric Niebler wrote:
Could you give some estimate as to how much it improved compile times? Do you have handy a benchmark test to show this? I would like to try this benchmark with the variadic template compiler to see how close they are. I know you've already tried the variadic compiler, but I'd like to try the benchmark myself and maybe show the results and code to Douglas Gregor so that maybe he can figure out why the variadic compiler is not improving compile times. As you noted in a private email to me, the basic reason is: Instantiating templates is expensive. By comparison, expanding a macro is cheap. However, maybe the benchmark would prompt Douglas to look for ways to improve the compiler's template instantiation speed.
Larry Evans wrote:
I switched away from mpl containers very early on. I don't have any of the old code for you to test. I recall compile times improved by about ~8-10%. The issue is accessing the members. Going thru mpl::at_c<> to get at each child forces an extra template instantiation. Ditto for getting the length via mpl::size<>. These template instantiations add up and cause a measurable perf hit.
I've already spoken with Doug about it. Variadics are great and do improve compile times for variadic functions, esp. when combined with rvalue refs. Variadic class templates are another matter. The only way to metaprogram with them is with recursive template instantiations. That means instantiating lots of templates. The preprocessor can improve the situation by doing loop unrolling, but in the limit, the number of template instantiations is going to be linear with the length of the parameter pack. If you want to play with the variadic Proto code, you can find it at branches/proto/v3. I recently resurrected this branch because some people on the std committee were interested in it. It's not production code, though. -- Eric Niebler Boost Consulting www.boost-consulting.com
On 03/10/08 14:41, Eric Niebler wrote: [snip]
The args.hpp code here: http://svn.boost.org/trac/boost/browser/branches/proto/v3/boost/xpressive/pr... around line 61 contains: #define BOOST_PP_ITERATION_PARAMS_1 (3, (1, BOOST_PROTO_MAX_ARITY, <boost/xpressive/proto/args.hpp>)) 58 #include BOOST_PP_ITERATE() 59 60 #ifdef BOOST_HAS_VARIADIC_TMPL 61 template<BOOST_PP_ENUM_PARAMS(BOOST_PROTO_MAX_ARITY, typename A), typename... Args> 62 struct args< BOOST_PP_ENUM_PARAMS(BOOST_PROTO_MAX_ARITY, A), Args... > 63 { 64 BOOST_STATIC_CONSTANT(long, size = BOOST_PROTO_MAX_ARITY + sizeof...(Args)); 65 I don't understand why BOOST_PP_ENUM_PARMS is used in the same statement as Args.... AFAICT, the BOOST_PP_ENUM_PARMS should be used when #undef BOOST_HAS_VARIADIC_TMPL and the Args... when #define BOOST_HAS_VARIADIC_TMPL. Am I missing something?
Larry Evans wrote:
<snip>
It uses the preprocessor to do loop unrolling. It was an effort to bring compile times under control by reducing the number of template instantiations. -- Eric Niebler Boost Consulting www.boost-consulting.com
participants (5)
-
Dean Michael Berris -
Eric Niebler -
Larry Evans -
Markus Werle -
Steven Watanabe