|
|
Proto : |
Subject: Re: [proto] So I heard proto make AST ...
From: Gordon Woodhull (gordon_at_[hidden])
Date: 2010-08-09 23:24:22
Hi Joel, Christophe, Eric,
>>> I think you should talk to Gordon Woodhull. He's building a
>>> metagraph
>>> >> (among others) library, which I am going to use in msm for
>>> >> compile-time calculations and fsm analysis. This means there
>>> will be
>>> >> temporarily a metagraph library inside msm as proof of concept
>>> until
>>> >> there can be a review.
>>> >> Maybe he can adapt this library for proto analysis?
>>> >>
>> >Oh yeah, will save me some time indeed.
>> >Mayeb we shoudl invite him over here ?
> I just sent him a mail. BTW the metagraph library is in the sandbox,
> and a potential usage with msm was sent by Gordon on the devel list
> just at the end of the BoostCon.
Sorry for the slow response - been on vacation offline.
For sure, trees are on my roadmap, as metagraph is a library that
attempts to generalize all things graphlike. But I can't claim to
have the best solution yet.
The tree can be thought of as a special case of the graph where each
vertex has exactly one in-edge (or zero, if it's a root).
The nice thing about traversing trees is that you don't have to worry
about cycles, so you don't need a color map if you know your tree is
connected - way more efficient.
I wonder if Dan Marsden's Traversal library would solve this out of
the box? http://boost-spirit.com/dl_docs/traversal/html/traversal/introduction.html
The way I would solve it is to create an adapter that makes a Proto
tree look like a graph... Like Boost.Graph, Metagraph is designed to
allow adapting any metadata that is already graphlike to have a graph
API. (This wasn't the right approach for MSM because there's nothing
in those tables that immediately answers "what are the edges for this
vertex?")
If there is interest, I could probably pull this together pretty
quickly, as Proto already has such an expressive API. Then we'd
immediately have inefficient implementations of DFS & BFS and I could
see if there's a good way to factor out the color map stuff to make it
speedy.
The main API debate when it comes to traversals is "visitors or
iterators?" Currently metagraph takes the visitor approach from
Boost.Graph, which are more general and expressive, but iterators are
often more convenient. Any opinions here? AFAIK we don't have
coroutines or continuations in C++ metaprogramming to make the
inversion of control easier. ;-)
Thoughts?
Gordon
Proto list run by eric at boostpro.com