RFC Generic data structure traversal / manipulation library
Hi All I'm posting an early version of a library for manipulating hierarchical data structures, for example the parse trees that are produced by Spirit2. The library enables traversals, and local modifications of complex data structures, without the need to implement large amounts of repetitive traversal code. The library is in a very early state, but has a pretty large introduction and quick start guide, which (hopefully) will help get people started with the library. Formal documentation is unfortunately non-existent at this point. The library is based on techniques from the Haskell community, links to relevant papers are provided in the documentation. The library is intended to play well with the rest of Boost, it already contains support for structures built with Boost.Optional and Boost.Variant, and Boost.Fusion, and will support other Boost libraries in future releases. The library makes heavy use of function objects, and is intended to work with Boost.Lambda, Phoenix, and other function object libraries in Boost. Online documentation can be found at: http://tinyurl.com/2eyjeh A gzip copy of the latest source is available for download at. http://tinyurl.com/2h2tb6 I've also detailed some of the directions that future implementations of the library make take. Any feedback gratefully accepted. Thanks Dan ___________________________________________________________ Yahoo! Answers - Got a question? Someone out there knows the answer. Try it now. http://uk.answers.yahoo.com/
dan marsden wrote:
Hi All
I'm posting an early version of a library for manipulating hierarchical data structures, for example the parse trees that are produced by Spirit2.
Or expression trees produced by proto. I just want to say that I think this is very important work -- I've been reading up on "scrap your boilerplate" in Haskell -- and I'm looking forward to leveraging Dan's work in proto, and other places besides. More comments later... -- Eric Niebler Boost Consulting www.boost-consulting.com
Eric Niebler wrote:
dan marsden wrote:
Hi All
I'm posting an early version of a library for manipulating hierarchical data structures, for example the parse trees that are produced by Spirit2.
Or expression trees produced by proto. I just want to say that I think this is very important work -- I've been reading up on "scrap your boilerplate" in Haskell -- and I'm looking forward to leveraging Dan's work in proto, and other places besides. More comments later...
Ditto. I've done some early reviews of Dan's work. I think it is a very powerful library. Dan is a bit too modest but the Haskell guys call this the mother-of-all-traversals. If you've done complex tree traversals before, if you've delved into complex object visitations before, this one is a must read. http://www.cs.vu.nl/boilerplate/ http://research.microsoft.com/~simonpj/papers/hmap/ and the c++ one. "'Scrap Your Boilerplate' (SYB) is a well studied and widely used design pattern for generic traversal in the Haskell language, but almost unknown to generic programmers in C++." : http://portal.acm.org/citation.cfm?doid=1159861.1159871 Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
dan marsden wrote:
The library is intended to play well with the rest of Boost, it already contains support for structures built with Boost.Optional and Boost.Variant, and Boost.Fusion, and will support other Boost libraries in future releases. The library makes heavy use of function objects, and is intended to work with Boost.Lambda, Phoenix, and other function object libraries in Boost.
Online documentation can be found at:
This must be a good idea ... because like all good ideas I can't believe that no one has done this before :-) I haven't played with the code, but the docs look very nice, and the design looks to be very useful and broadly applicable. So more power to your elbow says I :-) Regards, John.
John Maddock wrote:
dan marsden wrote:
The library is intended to play well with the rest of Boost, it already contains support for structures built with Boost.Optional and Boost.Variant, and Boost.Fusion, and will support other Boost libraries in future releases. The library makes heavy use of function objects, and is intended to work with Boost.Lambda, Phoenix, and other function object libraries in Boost.
Online documentation can be found at:
This must be a good idea ... because like all good ideas I can't believe that no one has done this before :-)
It's been done before in Haskell and even in C++ too: http://portal.acm.org/citation.cfm?doid=1159861.1159871 The document mentions Fusion, but, as a proof of concept does not take advantage of it, nor any Boost library, opting instead to use straight C++. Dan's work is a Boostified and Fusionified version of it. Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
I'm posting an early version of a library for manipulating hierarchical data structures, for example the parse trees that are produced by Spirit2. The library enables traversals, and local modifications of complex data structures, without the need to implement large amounts of repetitive traversal code. The library is in a very early state, but has a pretty large introduction and quick start guide, which (hopefully) will help get people started with the library. Formal documentation is unfortunately non-existent at this point.
The library is based on techniques from the Haskell community, links to relevant papers are provided in the documentation.
The library is intended to play well with the rest of Boost, it already contains support for structures built with Boost.Optional and Boost.Variant, and Boost.Fusion, and will support other Boost libraries in future releases. The library makes heavy use of function objects, and is intended to work with Boost.Lambda, Phoenix, and other function object libraries in Boost.
I second the expressed opinion that this library is a very important piece of work and I'm looking forward to having it available. IIUC, the traversal library is designed to help traversing arbitrary data structures and to apply local _value_ changes. My question is: Is the used concept extensible in a way allowing for _structural_ changes of the traversed data structure? This would make it usable for tree transformations, which would be especially interesting if used with Spirit.Qi (parsing) and Spirit.Karma (generation). Regards Hartmut
dan marsden wrote:
Hi All
I'm posting an early version of a library for manipulating hierarchical data structures, for example the parse trees that are produced by Spirit2. The library enables traversals, and local modifications of complex data structures, without the need to implement large amounts of repetitive traversal code. The library is in a very early state, but has a pretty large introduction and quick start guide, which (hopefully) will help get people started with the library. Formal documentation is unfortunately non-existent at this point.
[snip]
Online documentation can be found at:
Page: http://spirit.sourceforge.net/dl_docs/traversal/html/traversal/quick_start_g... contains: BOOST_FUSION_ADAPT_STRUCT(demo::dept, (std::string, name) (std::vector<demo::unit>, units)) I'm assuming demo is a namespace; yet, there's no declaration on that page. Also, although I could guess what
Larry Evans wrote:
dan marsden wrote:
Hi All
I'm posting an early version of a library for manipulating hierarchical data structures, for example the parse trees that are produced by Spirit2. The library enables traversals, and local modifications of complex data structures, without the need to implement large amounts of repetitive traversal code. The library is in a very early state, but has a pretty large introduction and quick start guide, which (hopefully) will help get people started with the library. Formal documentation is unfortunately non-existent at this point.
[snip]
Online documentation can be found at:
Page:
http://spirit.sourceforge.net/dl_docs/traversal/html/traversal/quick_start_g...
contains:
BOOST_FUSION_ADAPT_STRUCT(demo::dept, (std::string, name) (std::vector<demo::unit>, units))
I'm assuming demo is a namespace; yet, there's no declaration on that page. Also, although I could guess what
Sorry, hit wrong button. Continuing: Although I could guess what BOOST_FUSION_ADAPT_STRUCT does, it would help to provide the reference: http://spirit.sourceforge.net/dl_more/fusion_v2/libs/fusion/doc/html/fusion/... I couldn't find any doc on my local copy of fusion, and the boost.org docs: http://www.boost.org/libs/libraries.htm had nothing; so, I had to search the mailing list for some location before I found adapt_struct.html.
dan marsden wrote: [snip]
I'm posting an early version of a library for manipulating hierarchical data structures, for example the parse trees that are produced by Spirit2. The library enables traversals, and local modifications of complex data structures, without the need to implement large amounts of repetitive traversal code.
Is there any reason why this couldn't replace visit_each: http://www.boost.org/doc/html/boost/visit_each.html ?
On 01/14/2008 04:25 PM, dan marsden wrote: [snip]
Hi All
Online documentation can be found at:
Page: http://spirit.sourceforge.net/dl_docs/traversal/html/traversal/quick_start_g... contains a section titled: Type Unification however, it appears like what it describes is more like the stl's accumulate or mpl's fold. Could you explain the reason for the title and why a title using accumulate or fold wouldn't be more intuitive to readers?
participants (6)
-
dan marsden -
Eric Niebler -
Hartmut Kaiser -
Joel de Guzman -
John Maddock -
Larry Evans