On Jan 15, 2011, at 5:01 PM, Gordon Woodhull wrote:

I'm pleased to announce that the proposed MPL.Graph will be included in release 1.46 as a sublibrary of MSM! msm::mpl_graph

Forgot to mention that mpl_graph is being used by MSM to find regions / connected components in state machines, and to find unreachable states. I think that work may lead me to implement a forest for efficient disjoint set tracking. I also want to abstract out the connected components algo - Christophe is using DFS directly for now. Cheers, Gordon

On Jan 15, 2011, at 11:23 PM, caustik wrote:

This sounds relevant to my interests -- Can these meta-graphs be recursive? In other words, can a meta-graph contain a subgraph of itself as a node?

Those sorts of higher-order graph problems are why I started thinking about metagraphs many years ago. When I found out about MPL I realized that all kinds of - graphs at levels of detail, subgraphs, bipartite graphs, graphs within graphs, graphs of graphs - could be implemented by using graph metadata graphs to describe the structure of the runtime graphs. The higher-order runtime graph data structure ("metagraph") is no longer simply vertices and edges, it is many types, but the way those types are connected is a compile-time graph "pattern". (Or even several overlaid patterns. For instance, a node in one pattern is also a subgraph in another pattern.) Expect progress on this in 2011.

Also curious if, and to what extent, the project might support MPI?

Not sure which way you mean this. * MPL.Graph is purely compile-time (wish we could parallelize that!). * I haven't thought about parallelizing metagraphs yet because I haven't written them yet - I'll be sure to get some ideas from Parallel BGL. * Joel Falcou has this intriguing Quaff project to build up compile-time skeletons of data flow for parallelized algorithms and IIRC we talked at BoostCon about how it would be neat to generalize skeletons to compile-time graphs. Anywhere you know the whole contents of the graph at compile time - in that case, the contents of some expressions - you might want to consider MPL.Graph for paying the abstraction penalty upfront instead of passing it on to your users. Thanks for the interest! Gordon

On 16/01/11 05:07, Gordon Woodhull wrote:

On Jan 15, 2011, at 5:01 PM, Gordon Woodhull wrote:

...

I'm pleased to announce that the proposed MPL.Graph will be included in release 1.46 as a sublibrary of MSM! msm::mpl_graph

Forgot to mention that mpl_graph is being used by MSM to find regions / connected components in state machines, and to find unreachable states.

I think that work may lead me to implement a forest for efficient disjoint set tracking. I also want to abstract out the connected components algo - Christophe is using DFS directly for now.

Jumping again here. What are th eimpact of said algorithm on compile time ? Is there a way we can handle DAG in a meaningful way ? My experiences with rpoto lead me to think that we need some CT-DAG to get more out of our proverbial proto AST.

On 24/01/11 09:30, Eric Niebler wrote:

On 1/24/2011 2:17 PM, Joel Falcou wrote:

...

Jumping again here. What are th eimpact of said algorithm on compile time ? Is there a way we can handle DAG in a meaningful way ? My experiences with rpoto lead me to think that we need some CT-DAG to get more out of our proverbial proto AST.

Can you share details? What are you trying to do, Joel?

Some advanced compilation techniques require a directed acyclic graph instead of an AST. DAG usually helps to find basic blocks and other fundamental code fragment. We want to get down to this level for some fine grain parallelization task in real-time constraints code generation where we may need to split series of statement in non-trivial way. In this case, the DAG allow us to "see" where the code can be splitted without error. As i never found how to make some CT structure looking like an AST but with a way to get the parent node, DAG is next best thiung we have in store

Hi Joel -

Some advanced compilation techniques require a directed acyclic graph instead of an AST. DAG usually helps to find basic blocks and other fundamental code fragment. We want to get down to this level for some fine grain parallelization task in real-time constraints code generation where we may need to split series of statement in non-trivial way. In this case, the DAG allow us to "see" where the code can be splitted without error.

As i never found how to make some CT structure looking like an AST but with a way to get the parent node, DAG is next best thiung we have in store

So is it a DAG or a tree with parent accessors you're looking for? Right now with using MPL.Graph you would pay for copying the whole structure into an mpl map-of-maps. There's an argument to be made that the library should support a mode where some concepts are implemented by adapting existing constructs (as I demonstrated before) and the metadata to support other concepts is constructed as needed. If you'll recall, last time we talked about this, we discovered that adapting Proto would require sort of a Fusion.Graph... Stay tuned!

On Jan 16, 2011, at 1:15 AM, Hal Finkel wrote:

You might be interested in looking at Martin Erwig's Functional Graph Library (available for Haskell or ML). I don't know Haskell or ML, but I've found the algorithm implementations reasonably easy to understand (there is also a paper), and I've found that using functional programs as a "template" for template metaprograms is often easier than trying to port imperative versions.

http://web.engr.oregonstate.edu/~erwig/fgl/

Thanks Hal, this is very interesting - I'm not sure if I grasp it yet but I'll be studying it thoroughly in months to come. We have O(1) maps in MPL so life is perhaps a little easier for us than for pure Haskell authors (at least as far as time complexity goes).