AMDG Markus Werle wrote:

Steven Watanabe <watanabesj <at> gmail.com> writes:

...

Markus Werle wrote: [...]

...

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?

[...] I believe that it is needed to allow partial specialization. expr<Tag, Args, 0>, expr<Tag, Args, 1>, ...

Sorry if I do not get that one.

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; }; ...

...

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.

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

Markus Werle wrote:

Steven Watanabe <watanabesj <at> gmail.com> writes:

...

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; };

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?

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 13:16, Larry Evans wrote:

On 03/10/08 12:08, Eric Niebler wrote:

...

Markus Werle wrote:

...

Steven Watanabe <watanabesj <at> gmail.com> writes:

...

The definition of expr is something like:

template<class Tag, class Args, int Arity = Args::arity> struct expr; [snip] 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? 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.

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.

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:

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) ].

What problem does that solve?

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).

On 03/20/08 18:10, Eric Niebler wrote:

Larry Evans 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.

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.

So: expr<tag::shift_right, Args, 20> is a valid expression?

On 03/20/08 19:11, Eric Niebler wrote:

Larry Evans wrote:

...

On 03/20/08 18:10, Eric Niebler wrote:

...

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.

So:

expr<tag::shift_right, Args, 20>

is a valid expression?

If Args has 20 elements in it, sure.

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.

On Fri, Mar 21, 2008 at 9:17 AM, Eric Niebler <eric@boost-consulting.com> wrote:

Larry Evans wrote:

...

However, I'd imagine some people would want this restricted to just two elements, which could be done with something like: <snip>

And now, if size<Args>::value is restricted to the Arity in tag_arity<shift_right,Arity> then it would be restricted to 2.

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.

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]

On Sat, Mar 22, 2008 at 12:05 AM, Eric Niebler <eric@boost-consulting.com> wrote:

Dean Michael Berris 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

What do you mean by "correct" here?

I say "correct" and mean that Args really does have arity 'Arity'.

...

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.

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.

...

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.

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]

AMDG Larry Evans wrote:

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.

Well, since expr is an aggregate, adding an extra layer of indirection would change the interface, so I don't think that would work. In Christ, Steven Watanabe

AMDG Larry Evans wrote:

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.

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:

To make x2 compile, add an extra {}, IOW

x2 = { { {1}, {1} } }

where the extran {} is for expr2::args.

So, the cost of this extra indirection is 1 more curly braces in every expr initializer list?

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

On 03/22/08 22:26, Eric Niebler wrote:

Steven Watanabe wrote:

...

AMDG

Larry Evans wrote:

...

To make x2 compile, add an extra {}, IOW

x2 = { { {1}, {1} } }

where the extran {} is for expr2::args.

So, the cost of this extra indirection is 1 more curly braces in every expr initializer list?

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.

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.

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

On 03/20/08 20:17, Eric Niebler wrote:

Larry Evans wrote:

...

However, I'd imagine some people would want this restricted to just two elements, which could be done with something like: <snip> And now, if size<Args>::value is restricted to the Arity in tag_arity<shift_right,Arity> then it would be restricted to 2.

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.

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.

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.

Like in the attached?

Steven Watanabe wrote:

Markus Werle wrote:

...

"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.

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.

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.

That's a legitimate concern. How important do you consider these use cases? -- Eric Niebler Boost Consulting www.boost-consulting.com

Steven Watanabe wrote:

AMDG

Markus Werle wrote:

...

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.

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.

...

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?

That's true.

...

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?

I believe that it is needed to allow partial specialization. expr<Tag, Args, 0>, expr<Tag, Args, 1>, ... And users don't need to care about it, since it has a default.

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.

...

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>?

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

Larry Evans wrote:

On 03/10/08 11:29, Eric Niebler wrote:

...

...

AMDG

Markus Werle wrote: [snip] 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

Steven Watanabe wrote: parameter to expr<>, but I changed to a very simple custom type because it improved compile times.

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 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 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.

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

Larry Evans wrote:

The args.hpp code here:

http://svn.boost.org/trac/boost/browser/branches/proto/v3/boost/xpressive/pr...

around line 61 contains:

<snip>

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?

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