I'm not sure whether what I'm trying is possible, but I'm asking anyhow, that's cheap. I have a context like the following, which overloads operator() for a bunch of terminals and a predefined mask(left,right) and mask(what, left, right): template<typename Expr, typename Target, typename Source> struct meta_context : proto::callable_context<const meta_context<Expr,Target,Source> > { typedef meta_context<Expr, Target, Source> self; typedef unsigned int result_type; meta_context (const Target& target, const Source& source) : m_target (target), m_source (source) {} #define RESULT_FOR(NAME, EXPR) result_type operator () (proto::tag::terminal, NAME##_tag NAME) const { return EXPR; } RESULT_FOR (source, proto::arg(m_source).m_data) RESULT_FOR (source_left, proto::arg(m_source).left ()) RESULT_FOR (source_right, proto::arg(m_source).right ()) RESULT_FOR (target, proto::arg(m_target).m_data) RESULT_FOR (target_left, proto::arg(m_target).left ()) RESULT_FOR (target_right, proto::arg(m_target).right ()) template<typename What, typename Left, typename Right> result_type operator () (mask_tag, const What& what, const Left& left, const Right& right) const { std::size_t what_value = proto::eval (what, *this); std::size_t left_value = proto::eval (left, *this); std::size_t right_value = proto::eval (right, *this); if (left_value == sizeof (unsigned long long)*8) return what_value & (~0ULL << right_value); else return what_value & (~(~1ull << (left_value-1) | ~(~0ull << right_value))); } template<typename Left, typename Right> result_type operator () (mask_tag, const Left& left, const Right& right) const { std::size_t left_value = proto::eval (left, *this); std::size_t right_value = proto::eval (right, *this); if (left_value == sizeof (unsigned long long)*8) return ~0ULL << right_value; else return ~(~1ull << (left_value-1) | ~(~0ull << right_value)); } #undef RESULT_FOR const Target& m_target; const Source& m_source; }; This is find and does its job, delegating most of the work to inherithed defaults. Now I'd like to shortcut the run-time evaluation when a value can be determined solely from the type. Let's assume I have a transform that returns either an mpl::int_<> giving the compile time value or the special type run_time when no compile time result can be computed. I know (haven't tried, so it's just a semi-educated guess) that I could just overload everything, check whether none of the arguments returns run_time, rebuild the original expression type (because I think once I'm in one of the operator() overloads the expression is decomposed in tag and arguments, with the complete one available nowhere), call the transform on the newly created expression and return the compile time value. If any of the arguments evaluate to run_time, do the run-time processing. But this overloading everything is not what I'd like. What I'd like is to leave the few overloads that do something special in the context and in addition overload eval like this: template<typename Expr1> struct eval { typedef typename self::result_type result_type; result_type operator()(Expr1 const &expr, self &ctx) { ... do compile time evaluation ... ... if known, return value, otherwise: return proto::default_eval<Expr1, self>()(expr, ctx); } }; Except that this doesn't quite do it, default_eval knows nothing about the semantics of my terminals and non-terminals. But I cannot simply call proto::eval either. Is there a way to do this in proto already, so that some additional behaviour can be spliced in before the normal (but not the default) behaviour? Thanks, Maurizio
Hullo fellow Boosters, I am writing especially to those of you in Aspen, but also to anyone out there who is interested in, or who has already implemented, any kind of "meta" graph (network). I would like to create or contribute to some Boost libraries for graphlike structures / "metagraphs" / higher order graphs / whatchamacallits. Below I describe some ideas simplistically/vaguely, both for lack of time and to try to grab the interest of people who have thought about these things but perhaps not in quite the same way. So far I have thought of three general types of graphs which are beyond the scope of graph libraries I know about: - Graphs in metadata, i.e. graphs of C++ types. This seems to be pretty easy to implement using MPL and I did this a couple of years ago, though poorly. I.e. it's easy to create a BGL-like interface with angle brackets instead of parentheses. :-) - Graphlike structures which are not graphs. Actually any objects which point to other objects form a graph of sorts; what we know as "graph" happens to be the special case where an edge points to two nodes and nodes point to a bunch of edges. What if there are more types than just Node and Edge, or they don't look quite like that? This is something like a Fusion for heterogeneous/polymorphic graphs. - (Here is my root problem.) Graphs that refer to other graphs, such as subgraphs, graphs at different layers of detail (where a node/edge at one level corresponds to a subgraph at another level), constraints on graphs... I have maybe mostly figured out a system for the last, which relies on the other two. Any of the three might be generally useful; I really need the last because it's prohibitively difficult and/or inefficient to maintain correspondences between graphs, and all of my dynamic graph drawing problems keep spawning more corresponding graphs! Disclaimer: because I'm interested in dynamic (changing) graphs, I'm looking at the problem as a bunch of node and edge objects pointing to each other, and using intrusive containers for efficiency/locality of reference. But I'd like to generalize wherever possible. Anyone who is here in Aspen who's interested in these ideas, please seek me out. Anyone else, please write me. I think I have some good ideas about how to proceed, and I will write up more specific descriptions, but first I would like to know what of this space has already been explored, additional requirements from similar applications, etc. My impression is that, with the reuse of MPL, Fusion, BGL, STL, and intrusive containers, none of this would require a lot of code, but there is a LOT to be designed and abstracted. I see it as at least three libraries, each depending on the last in the order above. My apologies if I have missed any prior discussion. I have been lurking around Boost for a while but just joined the list. Cheers! Gordon P.S. Extra apologies for the length of this letter. Been thinking about this for a few years...
Hi Gordon, On May 14, 2007, at 11:45 PM, Gordon Woodhull wrote:
I am writing especially to those of you in Aspen, but also to anyone out there who is interested in, or who has already implemented, any kind of "meta" graph (network). I would like to create or contribute to some Boost libraries for graphlike structures / "metagraphs" / higher order graphs / whatchamacallits.
Great!
So far I have thought of three general types of graphs which are beyond the scope of graph libraries I know about: - Graphs in metadata, i.e. graphs of C++ types. This seems to be pretty easy to implement using MPL and I did this a couple of years ago, though poorly. I.e. it's easy to create a BGL-like interface with angle brackets instead of parentheses. :-)
Yikes! I originally thought you wanted to take static information about C++ types and turn it into a dynamic graph for use in the BGL, but you're talking about doing this entirely statically... it would certainly be very, very interesting to try to implement some core graph algorithms in the template system.
- Graphlike structures which are not graphs. Actually any objects which point to other objects form a graph of sorts; what we know as "graph" happens to be the special case where an edge points to two nodes and nodes point to a bunch of edges. What if there are more types than just Node and Edge, or they don't look quite like that? This is something like a Fusion for heterogeneous/polymorphic graphs.
The notion of a "vertex" or "edge" in this case becomes a very, very abstract entity, which can have multiple different types. In the Graph library, this would probably mean that the vertex or edge is actually a variant, or an any, or some other kind of "container" type that points to an object of unknown type.
- (Here is my root problem.) Graphs that refer to other graphs, such as subgraphs, graphs at different layers of detail (where a node/edge at one level corresponds to a subgraph at another level), constraints on graphs...
I have maybe mostly figured out a system for the last, which relies on the other two. Any of the three might be generally useful; I really need the last because it's prohibitively difficult and/or inefficient to maintain correspondences between graphs, and all of my dynamic graph drawing problems keep spawning more corresponding graphs!
The BGL has a notion of subgraphs, encapsulated in the "subgraph" adaptor at http://www.boost.org/libs/graph/doc/subgraph.html . The BGL "subgraph" is an induced subgraph that allows one to build a tree of such subgraphs, and it maintains those subgraphs as one makes changes to the root graph. The BGL "subgraph" is not a multi-level graph data structure, however;. Vertices in the "subgraph" are just vertices; they aren't subgraphs. We've thought about graphs at different levels of detail, because they are extremely important in a lot of applications. Layout, visualization, and partitioning were our areas of interest at the time. Although we never came up with anything concrete, we're still very interested in this notion of multi-level graphs.
Anyone who is here in Aspen who's interested in these ideas, please seek me out. Anyone else, please write me. I think I have some good ideas about how to proceed, and I will write up more specific descriptions, but first I would like to know what of this space has already been explored, additional requirements from similar applications, etc.
I'm also here in Aspen, and I'm interested in chatting about your ideas. Let's see if we can find each other among the BoostCon horde :) I'm relatively easy to find... I'll be giving the concepts talk Wednesday and Thursday morning. - Doug
Waiting for Eric, the following works, although it is way more verbose than if a single eval overload could be spliced in, before other operator() overloads. The trick is to only specialize eval, rather than mixing eval and operator ()s. I also think this solution is much heavier on the compiler. The assembly code I get is very nice, and for now I don't seem to need compile-time simplifications: what I've seen in assembler is optimal. Still it gives a warm feeling to know that there're place where optimizations can be placed as needed. -------------------------------------------------------------------------------------------------------- template<typename Expr, typename Target, typename Source> struct meta_context : proto::callable_context<const meta_context<Expr,Target,Source> > { typedef meta_context<Expr, Target, Source> self; typedef unsigned int result_type; meta_context (const Target& target, const Source& source) : m_target (target), m_source (source) {} template<typename T> struct aux : mpl::if_<boost::is_same<T,run_time>, mpl::false_, T> {}; template<typename Expr_, typename Enable=void> struct eval : proto::default_eval<Expr_, self> { typedef unsigned int result_type; result_type operator () (const Expr_& expr, self ctx) { typedef typename meta_transform<Target, Source>::template apply<Expr_,mpl::void_, mpl::void_>::type result; if (boost::is_same<result, run_time>::value) return proto::default_eval<Expr_,self>::operator () (expr, ctx); else return aux<result>::type::value; } }; #define RESULT_FOR(NAME, EXPR) \ template<typename Expr_> \ struct eval<Expr_, typename boost::enable_if<proto::matches<Expr_, proto::terminal<NAME##_tag> > >::type> { \ typedef unsigned int result_type; \ result_type operator () (const Expr_& expr, self ctx) { \ return EXPR; \ } \ }; RESULT_FOR (source, proto::arg(ctx.m_source).m_data) RESULT_FOR (source_left, proto::arg(ctx.m_source).left ()) RESULT_FOR (source_right, proto::arg(ctx.m_source).right ()) RESULT_FOR (target, proto::arg(ctx.m_target).m_data) RESULT_FOR (target_left, proto::arg(ctx.m_target).left ()) RESULT_FOR (target_right, proto::arg(ctx.m_target).right ()) template<typename Expr_> struct eval<Expr_, typename boost::enable_if<proto::matches<Expr_, proto::binary_expr<mask_tag, proto::_, proto::_> > >::type> { typedef unsigned int result_type; result_type operator () (const Expr_& expr, self ctx) { typedef typename meta_transform<Target, Source>::template apply<Expr_,mpl::void_, mpl::void_>::type result; if (boost::is_same<result, run_time>::value) { std::size_t left_value = proto::eval(proto::arg_c<0>(expr), ctx); std::size_t right_value = proto::eval(proto::arg_c<1>(expr), ctx); return ... run-time value ... } else return aux<result>::type::value; } }; template<typename Expr_> struct eval<Expr_, typename boost::enable_if<proto::matches<Expr_, proto::nary_expr<mask_tag, proto::_, proto::_, proto::_> > >::type> { typedef unsigned int result_type; result_type operator () (const Expr_& expr, self ctx) { typedef typename meta_transform<Target, Source>::template apply<Expr_,mpl::void_, mpl::void_>::type result; if (boost::is_same<result, run_time>::value) { std::size_t what_value = proto::eval(proto::arg_c<0>(expr), ctx); std::size_t left_value = proto::eval(proto::arg_c<1>(expr), ctx); std::size_t right_value = proto::eval(proto::arg_c<2>(expr), ctx); return ... run-time value ... } else return aux<result>::type::value; } }; #undef RESULT_FOR const Target& m_target; const Source& m_source; };
Maurizio Vitale wrote:
Waiting for Eric, the following works, although it is way more verbose than if a single eval overload could be spliced in, before other operator() overloads. The trick is to only specialize eval, rather than mixing eval and operator ()s.
I'm a bit rushed, so forgive me if I've misunderstood your requirements, but it seems to me you could accomplish this with a layered context struct. See the following for an idea (totally untested): struct my_context_aux : proto::callable_context<my_context_aux const> { typedef unsigned int result_type; // handle int terminals. Everything else is handled by default. result_type operator()(proto::tag::terminal, int) const { return 0; } }; struct my_context { // Use this eval when we don't know the result at compile time. // It defers to the internal aux context. template<typename Expr, typename EnableIf = void> struct eval { typedef my_context_aux::result_type result_type; result_type operator()(Expr &expr, my_context const &ctx) const { // Defer to the aux context return proto::eval(expr, ctx.aux_ctx_); } }; // Use this eval when we know the result at compile time // based on the type of Expr template<typename Expr> struct eval<Expr, typename disable_if< is_same<run_time, ... determine return type ... > > { typedef ... result_type; result_type operator()(Expr &expr, my_context const &ctx) const { return result_type(); } }; my_context_aux aux_ctx_; }; HTH, -- Eric Niebler Boost Consulting www.boost-consulting.com
Wonderful, I didn't think of two contexts. Here's the result, with only two changes to your suggestion: - I nested the two contexts inside each other - I've added arguments to the inner_context so that is able to use the outer_context for evaluation This is beacause when you have a function with more than one arguments is is possible that some of them are compile-time constants, so it is worth a trip to save run-time evaluations. Haven't checked the generated assembly, so I don't know the effect of passing target and source through the constructor of the inner_context. Maybe this can also be turned into an example. Thanks again, Maurizio -------------------------------------------------------------------------------------------------------- template<typename Target, typename Source> struct meta_context : proto::callable_context<const meta_context<Target,Source> > { typedef meta_context<Target, Source> self; typedef unsigned int result_type; meta_context (const Target& target, const Source& source) : m_inner_context(*this, target, source) {} template<typename Expr_> struct compile_time_eval : meta_transform<Target, Source>::template apply<Expr_,mpl::void_, mpl::void_> {}; template<typename Expr_> struct compile_time_unknown : boost::is_same<typename compile_time_eval<Expr_>::type, run_time> { }; template<typename Expr_, typename Enable=void> struct eval { typedef unsigned int result_type; result_type operator () (const Expr_& expr, self ctx) const { return compile_time_eval<Expr_>::type::value; } }; template<typename Expr_> struct eval<Expr_, typename boost::enable_if<typename compile_time_unknown<Expr_>::type >::type > { typedef unsigned int result_type; result_type operator () (const Expr_& expr, self ctx) const { return proto::eval (expr, ctx.m_inner_context); } }; template<typename Outer_Context> struct inner_context : proto::callable_context<const inner_context<Outer_Context> > { typedef meta_context<Target, Source> self; typedef unsigned int result_type; inner_context (const Outer_Context& outer_context, const Target& target, const Source& source) : m_outer_context (outer_context), m_target (target), m_source (source) {} #define RESULT_FOR(NAME, EXPR) result_type operator () (proto::tag::terminal, NAME##_tag NAME) const { return EXPR; } RESULT_FOR (source, proto::arg(m_source).m_data) RESULT_FOR (source_left, proto::arg(m_source).left ()) RESULT_FOR (source_right, proto::arg(m_source).right ()) RESULT_FOR (target, proto::arg(m_target).m_data) RESULT_FOR (target_left, proto::arg(m_target).left ()) RESULT_FOR (target_right, proto::arg(m_target).right ()) template<typename What, typename Left, typename Right> result_type operator () (mask_tag, const What& what, const Left& left, const Right& right) const { std::size_t what_value = proto::eval (what, m_outer_context); std::size_t left_value = proto::eval (left, m_outer_context); std::size_t right_value = proto::eval (right, m_outer_context); if (left_value == sizeof (unsigned long long)*8) return what_value & (~0ULL << right_value); else return what_value & (~(~1ull << (left_value-1) | ~(~0ull << right_value))); } template<typename Left, typename Right> result_type operator () (mask_tag, const Left& left, const Right& right) const { std::size_t left_value = proto::eval (left, m_outer_context); std::size_t right_value = proto::eval (right, m_outer_context); if (left_value == sizeof (unsigned long long)*8) return ~0ULL << right_value; else return ~(~1ull << (left_value-1) | ~(~0ull << right_value)); } #undef RESULT_FOR const Outer_Context& m_outer_context; const Target& m_target; const Source& m_source; }; inner_context<self> m_inner_context; };
participants (4)
-
Douglas Gregor -
Eric Niebler -
Gordon Woodhull -
Maurizio Vitale