Alternative solution to intermediate results problem of expression templates.
Hi I'm not sure if this has already been explored or even in current use but I think I may have come up with an alternative solution to the type deduction of intermediate results from expression templates. Instead of using automatic type erasing technique, take the compile-time parse tree of an intermediate expression and create an exact runtime replica of the expression tree using recursive variant types (using Boost.Variant in C++). The creation of the expression tree can be completely automated. I have tried this myself with promising results. The only (minor) downside is in order to avoid redundant copies of operands the types of the operands must be given but not the structure of the compile-time expression tree itself. Leaf nodes of the recursive variant hold constant references to there elements. I've done quick profile of this against the traditional eager evaluation of overloaded operators and it still is more efficient but tree creation does cost in time slightly. If people are interested I can post code the code for this.
On 10/21/2005 03:05 PM, Korcan Hussein wrote:
I think I may have come up with an alternative solution to the type deduction of intermediate results from expression templates.
I'm afraid I don't know what: type deduction of intermediate results from expression templates means. Could you explain more with examples?
Instead of using automatic type erasing technique, take the compile-time
What is this "type erasing technique"?
parse tree of an intermediate expression and create an exact runtime replica of the expression tree using recursive variant types (using Boost.Variant in C++). The creation of the expression tree can be completely automated.
Why would you want a runtime replica? I suppose to solve the "type deduction of intermediate results" problem mentioned above, but, as I've said, I don't know what this is :( [snip]
If people are interested I can post code the code for this.
Please do. Possibly here: http://boost-consulting.com/vault/ and maybe in the Template Metaprogramming subdirectory.
"Larry Evans" <cppljevans@cox-internet.com> wrote in message news:djbj4j$g62$1@sea.gmane.org...
On 10/21/2005 03:05 PM, Korcan Hussein wrote:
I think I may have come up with an alternative solution to the type deduction of intermediate results from expression templates.
I'm afraid I don't know what:
type deduction of intermediate results from expression templates
means. Could you explain more with examples?
I'll make a quote from the boost MPL book :-) [quote] One drawback of expression templates is that they tend to encourage writing large, complicated expressions, because evaluation is only delayed until the assignment operator is invoked. If a programmer wants to reuse some intermediate result without evaluating it early, she may be forced to declare a complicated type like: Expression< Expression<Array,plus,Array> , plus , Expression<Array,minus,Array>
intermediate = a + b + (c - d);
(or worse). Notice how this type not only exactly and redundantly reflects the structure of the computationand so would need to be maintained as the formula changesbut also overwhelms it? This is a long-standing problem for C++ DSELs. The usual workaround is to capture the expression using type erasure, but in that case one pays for dynamic dispatching. There has been much discussion recently, spearheaded by Bjarne Stroustrup himself, about reusing the vestigial auto keyword to get type deduction in variable declarations, so that the above could be rewritten as: auto intermediate = a + b + (c - d); This feature would be a huge advantage to C++ DSEL authors and users alike. [/qoute] Since the change of auto keyword isn't with us yet probably not at least till C++0x and compiler vendors start implementing it i think i may have a better alternative to type erasor (unless it's already in use or have been discussed about). I think it would be very useful to libraries such as uBlas and Spirit.
Instead of using automatic type erasing technique, take the compile-time
What is this "type erasing technique"?
Boost.Any is one example where type erasing is used, basically you keep richful type info to the very last possible moment and then lose most of it in a polymophic type and use dynamic dispatching etc. So it's like your erasing the type, would you like a code example? ;)
parse tree of an intermediate expression and create an exact runtime replica of the expression tree using recursive variant types (using Boost.Variant in C++). The creation of the expression tree can be completely automated.
Why would you want a runtime replica? I suppose to solve the "type deduction of intermediate results" problem mentioned above, but, as I've said, I don't know what this is :(
I think that should make a little more sense now, if not i can explain some more if need be ;)
On 10/21/2005 03:05 PM, Korcan Hussein wrote:
I think I may have come up with an alternative solution to the type deduction of intermediate results from expression templates.
[Snipped...]
Boost.Any is one example where type erasing is used, basically you keep richful type info to the very last possible moment and then lose most of it in a polymophic type and use dynamic dispatching etc. So it's like your erasing the type, would you like a code example? ;)
I am interested in seeing this. Chris
On 10/21/2005 04:37 PM, Korcan Hussein wrote:
"Larry Evans" <cppljevans@cox-internet.com> wrote in message [snip]
I'm afraid I don't know what:
type deduction of intermediate results from expression templates
means. Could you explain more with examples?
I'll make a quote from the boost MPL book :-)
[snip] That helps a lot (BTW, it's on p. 236). [snip]
better alternative to type erasor (unless it's already in use or have been discussed about). I think it would be very useful to libraries such as uBlas and Spirit.
[snip]
Boost.Any is one example where type erasing is used, basically you keep richful type info to the very last possible moment and then lose most of it in a polymophic type and use dynamic dispatching etc. So it's like your erasing the type, would you like a code example? ;) No. "type erasure" is in index of the MPL book; so, I'll just consult that.
parse tree of an intermediate expression and create an exact runtime replica of the expression tree using recursive variant types (using Boost.Variant in C++). The creation of the expression tree can be completely automated.
Why would you want a runtime replica? I suppose to solve the "type deduction of intermediate results" problem mentioned above, but, as I've said, I don't know what this is :(
I think that should make a little more sense now, if not i can explain some more if need be ;)
Please do. I'm guessing that the replica is encoded in the variant's which member function. IOW, just like the expression type in: http://www.boost.org/doc/html/variant/tutorial.html#variant.tutorial.recursi... encodes the type of expression as: variant.which() expression type ---------------------------------- 1 int 2 binary_op<add> 3 binary_op<sub> your proposal would do the same for each possible value of expression type. IOW, instead of dynamic dispatching as done by type erasure, the dispatching would be done on variant.which()?
"Larry Evans" <cppljevans@cox-internet.com> wrote in message news:djd9hd$8pf$1@sea.gmane.org...
On 10/21/2005 04:37 PM, Korcan Hussein wrote:
"Larry Evans" <cppljevans@cox-internet.com> wrote in message
Please do. I'm guessing that the replica is encoded in the variant's which member function. IOW, just like the expression type in:
http://www.boost.org/doc/html/variant/tutorial.html#variant.tutorial.recursi...
encodes the type of expression as:
variant.which() expression type ---------------------------------- 1 int 2 binary_op<add> 3 binary_op<sub>
your proposal would do the same for each possible value of expression type. IOW, instead of dynamic dispatching as done by type erasure, the dispatching would be done on variant.which()?
Something along the lines of that but not necessarily boost::variant::which, use a static visitor (check boost::static_visitor) no dynamic dispatching and no casting. Also you are not defining the structure of the tree since it could come in any shape/form (which is the point of this), in certain occasions only the types of leaf node operands are the most necessary info to be given by a user just once the rest is automated. Also (as I forget to mention earlier) boost::variant can not be used directly on it's own since directly assigning/construction from a compile-time expression tree will not work. You need to wrap it up, have a template constructor that takes an expression tree and automates tree construction, most of which is partially evaluated at compile-time, I have code that does this already and is trivial. I also forgot to mention that the most of the code used for the expression templates can be reused for this. Another advantage of this over erasing type is that more nodes can easily be added in other expressions, you could have a mix of compile-time & run-time expression trees etc. I did want to know if this has already been considered or already in use before posting code but I think I'll go to tidy up what I have at the moment to clarify things. Where should I post/put the example?
On 10/22/2005 03:04 PM, Korcan Hussein wrote:
"Larry Evans" <cppljevans@cox-internet.com> wrote in message
[snip]
I did want to know if this has already been considered or already in use before posting code but I think I'll go to tidy up what I have at the moment to clarify things. Where should I post/put the example?
I suggest http://boost-consulting.com/vault under 'Template Metapogramming'. Looking forward to it.
On 10/22/2005 06:58 AM, Larry Evans wrote:
On 10/21/2005 04:37 PM, Korcan Hussein wrote: [snip]
I'll make a quote from the boost MPL book :-)
[snip] That helps a lot (BTW, it's on p. 236). [snip] Also relevant is:
http://www.boost.org/libs/spirit/doc/subrules.html
better alternative to type erasor (unless it's already in use or have been discussed about). I think it would be very useful to libraries such as uBlas and Spirit.
Are you suggesting this as an alternative to Spirit subrules?
"Larry Evans" <cppljevans@cox-internet.com> wrote in message news:435B9E00.3030607@cox-internet.com...
On 10/22/2005 06:58 AM, Larry Evans wrote: Are you suggesting this as an alternative to Spirit subrules?
Doesn't need to replace subrules but could be an alternative implementation for them, if you read the part: [qoute] ... It might not be apparent but behind the scenes, plain rules are actually implemented using a pointer to a runtime polymorphic abstract class that holds the dynamic type of the parser assigned to it. When a Spirit expression is assigned to a rule, its type is encapsulated in a concrete subclass of the abstract class. A virtual parse function delegates the parsing to the encapsulated object. Rules have drawbacks though: It is coupled to a specific scanner type. The rule is tied to a specific scanner [see The Scanner Business]. The rule's parse member function has a virtual function call overhead that cannot be inlined. [/quote] That is what automatic type erasing is, i think there is an alternative to this that might be worth investigating if not done so already. I'm just on the verge of finishing make my (simple, primitive) example tidy, should be up in a thew hours. begin 666 bullet.gif M1TE&.#EA# `,`/,``/___\[.SL;O_YREC&OOUFN]_V.$M5*4:U*$]U)C6E)* M:S%*,2E:M2$Y8Q 8& ```"'Y! $`````+ `````,``P`0 1%$,A)9U@8N_>& M/$@A%"1!'-.@(&S334M8((QSG%0P''Q0`8%#0G'P612D&>/0,"9D,X,)!3BL 1&*['(K%();[<A>)'!D0``#L` ` end
"Korcan Hussein" <korcan_h@hotmail.com> wrote in message news:djg7t5$li$1@sea.gmane.org...
"Larry Evans" <cppljevans@cox-internet.com> wrote in message news:435B9E00.3030607@cox-internet.com...
On 10/22/2005 06:58 AM, Larry Evans wrote: Are you suggesting this as an alternative to Spirit subrules?
Doesn't need to replace subrules but could be an alternative implementation for them, if you read the part:
[qoute] ... It might not be apparent but behind the scenes, plain rules are actually implemented using a pointer to a runtime polymorphic abstract class that holds the dynamic type of the parser assigned to it. When a Spirit expression is assigned to a rule, its type is encapsulated in a concrete subclass of the abstract class. A virtual parse function delegates the parsing to the encapsulated object. Rules have drawbacks though:
It is coupled to a specific scanner type. The rule is tied to a specific scanner [see The Scanner Business]. The rule's parse member function has a virtual function call overhead that cannot be inlined.
[/quote]
That is what automatic type erasing is, i think there is an alternative to this that might be worth investigating if not done so already. I'm just on the verge of finishing make my (simple, primitive) example tidy, should be up in a thew hours.
I made a mistake there, that was about rules :/ well i'm not sure how subrules i implementated but this could be an alternative implementation for rules i suppose.
Korcan Hussein wrote:
"Larry Evans" <cppljevans@cox-internet.com> wrote in message news:435B9E00.3030607@cox-internet.com...
On 10/22/2005 06:58 AM, Larry Evans wrote: Are you suggesting this as an alternative to Spirit subrules?
Doesn't need to replace subrules but could be an alternative implementation for them, if you read the part:
[qoute] ... It might not be apparent but behind the scenes, plain rules are actually implemented using a pointer to a runtime polymorphic abstract class that holds the dynamic type of the parser assigned to it. When a Spirit expression is assigned to a rule, its type is encapsulated in a concrete subclass of the abstract class. A virtual parse function delegates the parsing to the encapsulated object. Rules have drawbacks though:
It is coupled to a specific scanner type. The rule is tied to a specific scanner [see The Scanner Business]. The rule's parse member function has a virtual function call overhead that cannot be inlined.
[/quote]
That quote pertains to (type-erased rules) not subrules. Subrules in Spirit are completely static. No type erasure. Please read the http://www.boost.org/libs/spirit/doc/subrules.html carefully. Read below the lines that you have quoted. Those lines you quoted were there just to explain the problems of type-erased rules. I'm quite interested if you have a better alternative. For example, how do you write the Spirit calculator using your scheme: rule<> group, factor, term, expression; group = '(' >> expression >> ')'; factor = integer | group; term = factor >> *(('*' >> factor) | ('/' >> factor)); expression = term >> *(('+' >> term) | ('-' >> term)); ? Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
"Joel de Guzman" <joel@boost-consulting.com> wrote in message news:djg9et$55i$1@sea.gmane.org...
That quote pertains to (type-erased rules) not subrules. Subrules in Spirit are completely static.
Yes sorry about that i already sent a message explain i made a mistake.
I'm quite interested if you have a better alternative. For example, how do you write the Spirit calculator using your scheme:
rule<> group, factor, term, expression;
group = '(' >> expression >> ')'; factor = integer | group; term = factor >> *(('*' >> factor) | ('/' >> factor)); expression = term >> *(('+' >> term) | ('-' >> term));
?
I'll get back to you on that one, for the time being i have uploaded the example i have been writing about, it is in the vault here: http://www.boost-consulting.com/vault/index.php?action=downloadfile&filename... In the example program you should see something similar, take note however this isn't a library in any form it is just a (very) rough example of the technique, it has (as of yet) not been fully generalized but it should not be to diffcult. It should be enough to give people an idea to discuss about and consider a possibility.
On 10/23/2005 12:12 PM, Korcan Hussein wrote: [snip]
I'm quite interested if you have a better alternative. For example, how do you write the Spirit calculator using your scheme:
rule<> group, factor, term, expression;
group = '(' >> expression >> ')'; factor = integer | group; term = factor >> *(('*' >> factor) | ('/' >> factor)); expression = term >> *(('+' >> term) | ('-' >> term)); [snip] I'll get back to you on that one, for the time being i have uploaded the example i have been writing about, it is in the vault here: http://www.boost-consulting.com/vault/index.php?action=downloadfile&filename...
In the example program you should see something similar, take note however this isn't a library in any form it is just a (very) rough example of the technique, it has (as of yet) not been fully generalized but it should not be to diffcult. It should be enough to give people an idea to discuss about and consider a possibility.
Hopefully, the file: proto_static_disp.cpp will also generate some ideas. AFAICT, the arith_expr_gram typedef in that file contains all the grammar (which is recursive) and *maybe* could be further developed to eliminate dynamic dispatching. Of course, I've only compiled it and not yet tried to parse anything with it. It's also not readable, but I'm thinking that maybe the proposed typeof and << and | and spirit operators could be used to replace the 2nd part of the mpl::pair's in the mpl::map.
On 10/23/2005 01:08 PM, Larry Evans wrote: [snip]
Hopefully, the file:
proto_static_disp.cpp
will also generate some ideas. AFAICT, the arith_expr_gram typedef in that file contains all the grammar (which is recursive) and *maybe* could be further developed to eliminate dynamic dispatching. Of course, I've only compiled it and not yet tried to parse anything with it. It's also not readable, but I'm thinking that maybe the proposed typeof and << and | and spirit operators could be used to replace the 2nd part of the mpl::pair's in the mpl::map.
There's now a proto_static_disp.zip containing code and it's output for two inputs: ident ident * ident The code avoids any dynamic dispatching by using the "Curiously Recurring Template Pattern" (See Abrahams and Gurtovoy's _C++ Template Metaprogramming_, section 9.8) in Grammar template.
On 10/30/2005 09:27 PM, Larry Evans wrote:
On 10/23/2005 01:08 PM, Larry Evans wrote: [snip]
There's now a proto_static_disp.zip containing code and it's output for
I should have said where. It's in http://boost-consulting.com/vault in "Template Metaprogramming" directory. I also should have said it uses a modifcation of the range/iterator_range.hpp that's here: http://cvs.sourceforge.net/viewcvs.py/boost-sandbox/boost-sandbox/boost/
two inputs:
ident ident * ident
The code avoids any dynamic dispatching by using the "Curiously Recurring Template Pattern" (See Abrahams and Gurtovoy's _C++ Template i.e. CRTP Metaprogramming_, section 9.8) in Grammar template.
It uses the mpl::map where keys are non-terminals and values are rhs for those non-terminals. It then uses mpl::fold to create a grammar class with a parser_production superclass for each non-terminal. The only place the CRTP is actually useful is where the a non-terminal is encountered on the rhs of the production. This is in: struct parser_rhs < vocabulary<nonterminal>::variable<WordId> , Grammar
{...}; Any comments or suggestions welcome. Since spirit also uses CRTP, I'm guessing it uses it for another purpose, i.e. a purpose other than eliminating the need for virtual functions. Anyone got a simple answer? Since this topic seems more relevant to spirit, I'm posting there also. TIA.
On 10/23/2005 12:12 PM, Korcan Hussein wrote: [snip]
I'll get back to you on that one, for the time being i have uploaded the example i have been writing about, it is in the vault here: http://www.boost-consulting.com/vault/index.php?action=downloadfile&filename...
In the example program you should see something similar, take note however
I ran it and tried to understand it. AFAICT, the key part of the code is: template < typename Tp > struct var { ... struct basic_eval : boost::static_visitor<float> { size_type curr_indx; basic_eval(size_type i = 0): curr_indx(i) {} float operator()(const Tp& val) const { return val[curr_indx]; } template < typename Expression > float operator()(const Expression& exp) const { using boost::apply_visitor; typedef typename Expression::operation_type Oper; float lhs_val=apply_visitor(*this, exp.get_lhs()); float rhs_val=apply_visitor(*this, exp.get_rhs()); float my_val=Oper::apply(lhs_val,rhs_val); return my_val; } }; ... }; I could see the Expression::operation_type is one of: addf_tag minusf_tag The apply_visitor is from: boost/variant/detail/apply_visitor_unary.hpp and the body of this apply_visitor is: apply_visitor(const Visitor& visitor, Visitable& visitable) { return visitable.apply_visitor(visitor); } Since there's no apply_visitor in the Expression<...> , I added a few variables (*_val) to store intermediate results to enable using gdb to see what was going on. After tracing several levels of calls in gdb in an effort to find how: apply_visitor(*this, exp.get_lhs()) get's back to var<Tp>::basic_eval::operator(...), I finally just decided it does, somehow, and since all variants of the var<Tp>::expr have a corresponding exact match amoung the basic_eval::operator(...)'s, not dynamic dispatching is done. HTH any other reviewers of expr_test.cpp.
Larry Evans wrote:
On 10/23/2005 12:12 PM, Korcan Hussein wrote: [snip]
I'll get back to you on that one, for the time being i have uploaded the example i have been writing about, it is in the vault here: http://www.boost-consulting.com/vault/index.php?action=downloadfile&filename...
In the example program you should see something similar, take note however
I ran it and tried to understand it. AFAICT, the key part of the code is:
HTH any other reviewers of expr_test.cpp.
I didn't run it but I think I understand what's going on. It simply encodes the recursive expression-type in the recursive variant. There's a significant flaw with this approach: all nodes must be known in advance. There is no possibility of user defined leaves; nor is there a possibility for having nodes that are from a different library; e.g. phoenix. Hence, AFAICT, semantic actions cannot be made to work. And, the system will be closed to extension --for example, in Spirit, we cannot write our own user defined primitives or composites, *after* the library has been written. Cheers, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
"Joel de Guzman" <joel@boost-consulting.com> wrote in message news:djhds4$vvv$1@sea.gmane.org...
I didn't run it but I think I understand what's going on. It simply encodes the recursive expression-type in the recursive variant. There's a significant flaw with this approach: all nodes must be known in advance. There is no possibility of user defined leaves; nor is there a possibility for having nodes that are from a different library;
I relized this when i was reading Spirit's documentation. I did mention from the begining all terminal leaf node types must be given, like in an MPL sequence (and probably for nonterminal node types if you can add more to the set). I did also mention this was in no way been generalized or a library of any form it was just an idea i had the other day. It's not true that there is "no possibility user-defined leaves" it is just not as simple as erasing type. I had some ideas to get around this, my initial thought was have a fallback on to type erasing you have a catch all type of the set of types in a variant that uses type erasing i don't like the idea but in this case there would probably be no choice. So yeah this does not gel so well with Spirit, maybe if boost::variant was like OCaml's polymorphic variants it would be a more feasible. Still though this could have it uses in other places where client wouldn't normally add new internal (nonterminal) nodes.
On 10/24/2005 04:08 AM, Korcan Hussein wrote: [snip]
So yeah this does not gel so well with Spirit, maybe if boost::variant was like OCaml's polymorphic variants it would be a more feasible. Still though
I'm unfamiliar with polymorphic variants. Could you please give a brief explanation or reference? Is it any way related to the topic discussed here: http://groups.google.com/group/comp.std.c++/msg/8a90765a6e61ce82
this could have it uses in other places where client wouldn't normally add new internal (nonterminal) nodes.
Maybe. I guess with a grammar, the user would know all the nonterminal nodes; hence, this would work, AFAICT. This might be a huge (where huge refers to number of nonterminals in grammar) variant. Maybe it could be calculated from the grammar? But then, since it's used in the grammar ..., maybe that's not possible.
On 10/24/2005 04:08 AM, Korcan Hussein wrote: [snip]
I relized this when i was reading Spirit's documentation. I did mention from the begining all terminal leaf node types must be given, like in an MPL
What's a "terminal leaf node type"?
sequence (and probably for nonterminal node types if you can add more to the set). I did also mention this was in no way been generalized or a library of any form it was just an idea i had the other day. It's not true that there is "no possibility user-defined leaves" it is just not as simple as erasing type.
The variant, var, in: http://tinyurl.com/72hx7 works by having: var<Tp>::basic_eval : boost::static_visitor<float> { Tp::value_type operator()(const Tp& val) const { return val[curr_indx]; } template < typename Expression > Tp::value_type operator()(const Expression& exp) const { } }; where Expression is some nonterminal in the grammar. Is Tp what you refer to as a "terminal leaf node type"?
"Larry Evans" <cppljevans@cox-internet.com> wrote in message news:djiene$hps$1@sea.gmane.org...
I'm unfamiliar with polymorphic variants. Could you please give a brief explanation or reference? Is it any way related to the topic discussed here:
http://groups.google.com/group/comp.std.c++/msg/8a90765a6e61ce82
OCaml supports normal varaint types and some called polymorphic types, i'm not sure if i understood them correctly myself but from what i think understand of them is that the set of (possible) types are not closed, allows of for code-reuse etc but i might be wrong. OCaml's definition can be found here: http://caml.inria.fr/pub/docs/manual-ocaml/manual012.html (in the variant types section). "Larry Evans" <cppljevans@cox-internet.com> wrote in message news:djihj1$qnv$1@sea.gmane.org...
On 10/24/2005 04:08 AM, Korcan Hussein wrote: [snip]
I relized this when i was reading Spirit's documentation. I did mention from the begining all terminal leaf node types must be given, like in an MPL
What's a "terminal leaf node type"?
Sorry i couldn't think of a better term/word to use, but basically the types of operands of an overloaded operator (excluding composite type). In the case of Boost.Spirit these would be all the primitive parsers. As Joel de Guzman was saying the problem is Boost.Spirit allows you to add not only new primitive parsers but composite parsers too, it is open to extension.
where Expression is some nonterminal in the grammar. Is Tp what you refer to as a "terminal leaf node type"?
Essentially yes, if this was generalized one way this could work is the user gives a boost.mpl sequence of types of operands (possibly give a sequence types for composite types depending on the context). Unfortunately this doesn't scale to well for Boost.Spirit since new types of either kind could be added later on which requires adding a new type to either type sequence and then recompilation.
participants (4)
-
Chris Weed -
Joel de Guzman -
Korcan Hussein -
Larry Evans