Hi Gordon (and whoever else is involved), What's the current status of metagraph / mpl_graph? I've been using msm::mpl_graph for error-checking/scheduling in a compile-time filter graph framework (similar to state machines, but focus is on data flow), and I'd certainly like to see more. As is, I've already implemented a topological sort based on the BFS which doesn't yield errors on cyclic graphs (which I'd be happy to contribute if you don't already have one), and I have some thoughts on improvement. I saw the BoostCon slides and the current state of the sandbox, and I was wondering if there's more code lurking out there somewhere, unchecked-in. Anyway, the single biggest flaw I see with the current BFS and DFS (and the BGL models they're based on) is that there is no way for the user to specify a termination condition in the base algorithm. It seems silly that an algorithm called "Search" can't end without traversing the whole connected component! Indeed, if there were simply an optional predicate determining whether a candidate vertex should be added to the stack/queue, I wouldn't have needed to write a separate algorithm for topo sort. The other thing is that not all of the listed visitor operations are called in the current implementations. Adding things like "initialize_vertex" and "non_tree_edge" to BFS is an easy fix. Thanks, Nick Kitten Software Engineer Center for Video Understanding Excellence ObjectVideo, Inc. http://www.objectvideo.com
Hi Nick, Glad to hear you're using MPL.Graph! On Jan 27, 2012, at 11:07 AM, Kitten, Nicholas wrote:
What's the current status of metagraph / mpl_graph? I've been using msm::mpl_graph for error-checking/scheduling in a compile-time filter graph framework (similar to state machines, but focus is on data flow), and I'd certainly like to see more. As is, I've already implemented a topological sort based on the BFS which doesn't yield errors on cyclic graphs (which I'd be happy to contribute if you don't already have one), and I have some thoughts on improvement. I saw the BoostCon slides and the current state of the sandbox, and I was wondering if there's more code lurking out there somewhere, unchecked-in.
I made a lot of progress over the summer, but unfortunately I've been distracted with real-world concerns since then. As you can see, the sandbox version now has an iterator-based design rather than using recursion. I also implemented a parser for angly expressions like graph<node<A, edge<t, B>, edge<u, C> >, ...> but I admit that probably seems pretty esoteric to most people. (See metagraph.info)
Anyway, the single biggest flaw I see with the current BFS and DFS (and the BGL models they're based on) is that there is no way for the user to specify a termination condition in the base algorithm. It seems silly that an algorithm called "Search" can't end without traversing the whole connected component! Indeed, if there were simply an optional predicate determining whether a candidate vertex should be added to the stack/queue, I wouldn't have needed to write a separate algorithm for topo sort.
Yes, that certainly makes sense. After all we can't throw an exception as we can in BGL, at least not without Abel's creative monad-based MPL extension. [1] If you see how to write a patch for that, I'd be glad to have a co-author. (The iterator design is based on Franz Alt's feedback and his alternative MGL. [2]) Topo sort is also one of the algorithms needed before this goes to review. Josh mentioned an interesting fusion dataflow application on the Spirit mailing list. [3]
The other thing is that not all of the listed visitor operations are called in the current implementations. Adding things like "initialize_vertex" and "non_tree_edge" to BFS is an easy fix.
Yes, that certainly should be fixed too. Cheers, Gordon [1] http://abel.web.elte.hu/mpllibs/metamonad/index.html [2] https://svn.boost.org/svn/boost/sandbox/mgl [3] http://boost.2283326.n4.nabble.com/caching-fusion-map-idea-query-td3797738.h...
On Fri, Jan 27, 2012 at 11:39 AM, Gordon Woodhull <gordon@woodhull.com> wrote:
As you can see, the sandbox version now has an iterator-based design rather than using recursion. I also implemented a parser for angly expressions like graph<node<A, edge<t, B>, edge<u, C> >, ...> but I admit that probably seems pretty esoteric to most people. (See metagraph.info)
Wait, now I'm confused; the sandbox/metagraph/ <https://svn.boost.org/svn/boost/sandbox/metagraph/> (from what I can tell, anyway) uses the original recursion-based design (but includes the angly parser), while sandbox/mgl/ (which I hadn't seen before) has iterator-based design, but no angly parser. What am I missing here? Does metagraph now consist of both folders? As a side note, I can't tell whether "angly expression" refers to the profusion of angle brackets, or to some theoretician named "Angly" who works with DFAs :)
Anyway, the single biggest flaw I see with the current BFS and DFS (and the BGL models they're based on) is that there is no way for the user to specify a termination condition in the base algorithm. It seems silly that an algorithm called "Search" can't end without traversing the whole connected component! Indeed, if there were simply an optional predicate determining whether a candidate vertex should be added to the stack/queue, I wouldn't have needed to write a separate algorithm for topo sort.
Yes, that certainly makes sense. After all we can't throw an exception as we can in BGL, at least not without Abel's creative monad-based MPL extension. [1]
Compile-time exception propagation is certainly an interesting concept, especially considering how poorly compilers do reporting errors for metaprogramming. I actually stumbled across the metatest suite from the same group of libraries not long ago, and it's good stuff. However, I think if we did incorporate it, we'd need a way to make it optional, since there will likely always be people who don't want to pay the extra cost for using exceptions. To enable errors, I don't see how we could get around requiring the do / let notation for propagating monads, but perhaps a little preprocessor magic could disable them? I'll have to think on that. For topological sort in particular, what I have simply returns partial results for everything that _can_ be sorted, leaving cycles and components lower in the ordering behind. That makes it so you can try to sort without doing any checks, and if all nodes are returned, you're done. If not, you break cycles on the remaining subgraph, then continue sorting (this is exactly what I do in my own use case).
If you see how to write a patch for that, I'd be glad to have a co-author. (The iterator design is based on Franz Alt's feedback and his alternative MGL. [2])
I will write a patch, once I'm sure where the definitive home for this library is at the moment. My impression was that iterators and recursion each had their pros and cons, so I'd be interested to hear the rationale for switching.
Topo sort is also one of the algorithms needed before this goes to review. Josh mentioned an interesting fusion dataflow application on the Spirit mailing list. [3]
Here, I see mgl already has a simple dfs-based solution, which is probably fine as long as find_cycles is also provided - which again begs the question, where is the merging happening? Best, -Nick Kitten Software Engineer Center for Video Understanding Excellence ObjectVideo, Inc. http://www.objectvideo.com
Hi Nick/Gordon,
Compile-time exception propagation is certainly an interesting concept, especially considering how poorly compilers do reporting errors for metaprogramming. I actually stumbled across the metatest suite from the same group of libraries not long ago, and it's good stuff. However, I think if we did incorporate it, we'd need a way to make it optional, since there will likely always be people who don't want to pay the extra cost for using exceptions. To enable errors, I don't see how we could get around requiring the do / let notation for propagating monads, but perhaps a little preprocessor magic could disable them? I'll have to think on that.
The do and let notations are general tools for monads - if you need exception propagation only, there is another utility for that in metamonad: the try_ template (http://abel.web.elte.hu/mpllibs/metamonad/try_.html). Instead of writing template <class T1, ..., class Tn> struct my_metafunction : body {}; you write template <class T1, ..., class Tn> struct my_metafunction : try_<body> {}; and it instruments body to propagate errors. As an example demonstrating its usage you can take a look at https://github.com/sabel83/mpllibs/blob/master/libs/metamonad/example/min/mi.... To support the use case when people don't want to pay for exception propagation, I can extend metamonad the following way: when a macro (eg. DISABLE_TMP_EXCEPTIONS) is defined, try_ becomes the identity metafunction. In that case it will have a minimal cost (1 extra instantiation). What do you think? Regards, Abel
Hi Abel, On Feb 2, 2012, at 4:09 PM, Abel Sinkovics wrote:
The do and let notations are general tools for monads - if you need exception propagation only, there is another utility for that in metamonad: the try_ template (http://abel.web.elte.hu/mpllibs/metamonad/try_.html). Instead of writing
template <class T1, ..., class Tn> struct my_metafunction : body {};
you write
template <class T1, ..., class Tn> struct my_metafunction : try_<body> {}; and it instruments body to propagate errors.
If body calls another metafunction then does that one have to be instrumented too?
To support the use case when people don't want to pay for exception propagation, I can extend metamonad the following way: when a macro (eg. DISABLE_TMP_EXCEPTIONS) is defined, try_ becomes the identity metafunction. In that case it will have a minimal cost (1 extra instantiation). What do you think?
That sounds like a good idea but I haven't experimented with the library yet. Your library came up because a recursive depth-first-search isn't interruptible without exceptions, but I'm still not sure whether that means getting rid of recursion or introducing exceptions. Cheers, Gordon
Hi Gordon,
The do and let notations are general tools for monads - if you need exception propagation only, there is another utility for that in metamonad: the try_ template (http://abel.web.elte.hu/mpllibs/metamonad/try_.html). Instead of writing
template<class T1, ..., class Tn> struct my_metafunction : body {};
you write
template<class T1, ..., class Tn> struct my_metafunction : try_<body> {}; and it instruments body to propagate errors. If body calls another metafunction then does that one have to be instrumented too?
Yes. If body calls another metafunction, that has to be instrumented too (or be prepared for handling exceptions). When a metafunction "throws" an exception, every metafunction in the "call-chain" needs to be instrumented until the point the exception is handled. When an exception is propagated to a metafunction that is not instrumented, it causes a compilation error. Instrumentation guarantees that no metafunctions in the instrumented expression are called with exceptions as their arguments. Regards, Abel
Hi Nick, On Feb 2, 2012, at 1:20 PM, Kitten, Nicholas wrote:
As you can see, the sandbox version now has an iterator-based design rather than using recursion. Wait, now I'm confused; the sandbox/metagraph/ <https://svn.boost.org/svn/boost/sandbox/metagraph/> (from what I can tell, anyway) uses the original recursion-based design (but includes
On Fri, Jan 27, 2012 at 11:39 AM, Gordon Woodhull <gordon@woodhull.com> wrote: the angly parser),
Sorry; I thought I had checked in the iterator versions. They are there now.
while sandbox/mgl/ (which I hadn't seen before) has iterator-based design, but no angly parser. What am I missing here? Does metagraph now consist of both folders?
No, MGL is a competing library by Franz Alt that I've learned a lot from. The story is that Christophe Henry badly needed a graph metaprogramming library for verifying MSMs, so he encouraged Franz to write that one. I had already written MPL.Graph but hadn't publicized it much. I think my design is better (more closely parallels BGL; tighter metafunctions) but Franz's is somewhat faster and more memory-efficient. Part of that was the iterators, which I've now adopted.
As a side note, I can't tell whether "angly expression" refers to the profusion of angle brackets, or to some theoretician named "Angly" who works with DFAs :)
Yep, just my made-up name for these sorts of EDSLs. :)
Compile-time exception propagation is certainly an interesting concept, especially considering how poorly compilers do reporting errors for metaprogramming. I actually stumbled across the metatest suite from the same group of libraries not long ago, and it's good stuff. However, I think if we did incorporate it, we'd need a way to make it optional, since there will likely always be people who don't want to pay the extra cost for using exceptions. To enable errors, I don't see how we could get around requiring the do / let notation for propagating monads, but perhaps a little preprocessor magic could disable them? I'll have to think on that.
Yes, I think it may be too expensive for everyday use until compilers catch up, though I haven't tried it yet. Note you don't need exceptions to interrupt search with an iterator-based design.
For topological sort in particular, what I have simply returns partial results for everything that _can_ be sorted, leaving cycles and components lower in the ordering behind. That makes it so you can try to sort without doing any checks, and if all nodes are returned, you're done.
This design makes more sense to me than just dying if there are cycles.
If not, you break cycles on the remaining subgraph, then continue sorting (this is exactly what I do in my own use case).
I presume you mean you build a new graph with the cycles broken, since MPL.Graph doesn't (yet?) support mutable graphs.
If you see how to write a patch for that, I'd be glad to have a co-author. (The iterator design is based on Franz Alt's feedback and his alternative MGL. [2])
I will write a patch, once I'm sure where the definitive home for this library is at the moment. My impression was that iterators and recursion each had their pros and cons, so I'd be interested to hear the rationale for switching.
Do you know any resources comparing iterators and recursion in TMP? The reason I switched is that MPL.Graph was *dramatically* slower on my old machine, because template recursion seems to use a lot more memory and so it ran out of physical memory. I know the Abrahams/Gurtovoy book strongly advises against deep recursion - but compilers may have changed. The new design, with an explicit stack, is more complex but I think more powerful. It's probably worthwhile to measure the performance difference. On a new machine with more RAM, I didn't really see much difference between MGL and either version of MPL.Graph, so I kind of stopped worrying about it.
Here, I see mgl already has a simple dfs-based solution, which is probably fine as long as find_cycles is also provided - which again begs the question, where is the merging happening?
So far there has only been conceptual merging - his coding style is way different. I think once MPL.Graph has topo sort, strong components and/or biconnected components, and maybe something fancy like Dijkstra's shortest paths (requires a heap metadata structure), it'll be ready for review. Any help would be appreciated! Cheers, Gordon
participants (3)
-
Abel Sinkovics -
Gordon Woodhull -
Kitten, Nicholas