|
|
Proto : |
Subject: Re: [proto] So I heard proto make AST ...
From: Eric Niebler (eric_at_[hidden])
Date: 2010-08-10 14:36:40
On 8/10/2010 4:48 AM, Gordon Woodhull wrote:
> Thanks Joel,
>
> This is food for thought!
Indeed, but I'm struggling to keep up because I don't really know what
you guys are after.
> On Aug 10, 2010, at 2:47 AM, joel falcou wrote:
>> On 10/08/10 05:24, Gordon Woodhull wrote:
>>>
>>> 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
>>
>> Oh nice link, I didn't knew that :o
>>
>>> 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,
There is! I think. What is the goal? To be able to apply graph
algorithms to Proto expressions? Why, exactly? Turning an expression
tree into a graph seems like a step backward to me. Trees are easier to
process than graphs, IIUC. Where have I gone astray?
>>> 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.
>>
>> We're looking at two challenge in Proto :
>> -> traversing the AST type at compile-time to apply meta-function onto
>> tree node
Above and beyond what you get by using Proto grammars+transforms?
> I just committed an example which does this part. See end of message.
Committed where?
>> -> traversing the AST value at run-time to apply function onto tree node
Again, this is what Proto grammars+transforms are for. If they're not
doing the job, let's talk about why.
> This requires a Fusion/BGL interface, which I haven't thought out yet.
> Probably just means moving a parameter from the <> to () as usual. :-D
IIUC, BGL has a homogeneous interface, like the STL. I don't think you
can get it to play well with Fusion, or Proto for that matter.
>> for example here is my current use-cases:
>>
>> - walkign through a proto AST to apply a visitor onto node/leaf : turn
>> the AST on array into the same AST with pointer element before evaluation
>
> Yes, I imagine that's the most common use case. How hard can that
> Fusion/BGL interface be?
I can do this easily with a Proto grammar w/ transform.
>> - turning the AST into a DAG
>
> Yay!
Use case?
> Stjepan Rajko and I talked about doing this in order to allow Proto
> expressions to define graph metadata.
>
> Maybe you'd kind of cut and paste the Proto tree into an mpl graph while
> looking for vertices with duplicate IDs. Should work just as well on
> graphs with cycles.
>
> This way you'd end up with sort of a graph metadata overlay over the
> Proto tree. Each vertex would contain metadata instructions for how to
> get to the corresponding Proto node in the expression, and each edge
> would be vertex+child#. No extra runtime data needed, if I'm not mistaken.
>
> You could also imagine doing this with a Fusion graph somehow, if you
> wanted to add runtime data... but I don't grok the Fusion/Proto
> allocation/reference magic yet, so I'm not quite sure what I'm saying.
I can speak to Proto's allocation/reference magic. There is no (dynamic)
allocation. By default, everything is held by reference, even
intermediate temporary expressions. The default can be changed and
things can be held by value. There's also a deep_copy function to turn
references into values.
Proto is not built on top of Fusion. There is an adaptor layer, but it
doesn't fit too well at the moment; heterogeneous trees are hard until
Fusion gets complete segmented iteration support, and I'm not 100%
convinced that's the way forward (see iterators vs. visitors).
>> - applying a visitor performing osme kind of reduction on the tree
>> startign form the leaf to evaluate the value of the AST in a given
>> point of evaluation
>
> Postorder traversal? I guess the trick is in what you produce:
> annotating the existing nodes, easy, vs building something new, maybe
> not so.
>
>> - for a given assign node (lhs = rhs) check if the lhs data address is
>> somewhere in the terminal of rhs. This is basically our trickiest
>> runtime algorithm in nt2 that helps us detetcing alias in expression
>> without having ppl using alias(x) function.
>
> Again, DFS with a Fusion/BGL interface.
>
>> - detecting pattern in the AST (like a+b*c) and repalce all of them,
>> recurisvely into another (here by madd(a,b,c)). It's currently done
>> with special grammar and it's maybe better to do it like this but we
>> never know.
>
> Haha, I haven't thought about graph pattern matching for a while, though
> that's where I started with graphs 15 years ago.
>
> Special-purpose Proto grammars/transforms are probably the best way to
> modify Proto expressions, but like you say, we never know. Maybe
> something cool could be done with graph transformations of fusionish
> graph data.
Just as trees are a special case of graphs, tree algorithms are probably
a better fit for expression manipulation than graph algorithms.
> Let me see if I am starting to understand the Proto/Fusion memory
> model. You end up with the original expression as one object, and then
> a bunch of new AST nodes holding references into the original
> expression, right?
That's one possibility, but object lifetime can be an issue.
>> I'm from the old guard w/r to tree, so I'm mostly thinking in visitor.
>> But if you care to show me how iterators can be used, I'm open to
>> suggestion.
>
> Cool. Visitors are way more powerful.
Even in STL-land, sequential iteration over tree-like things feels like
putting on shoes that are too small. The problem gets much worse once
you allow for heterogeneous trees. Even if all Fusion algorithms had
segmented variants, you'd *still* want additional algorithm that don't
force you to ignore the very tree structure that make trees interesting
and useful.
> If you go with iterators you end up creating different iterator types
> for every kind of traversal. But then they don't muck with your control
> flow. Here is a good message describing that approach, from one of the
> boost::tree discussions. (There have been a few valiant attempts.)
> http://lists.boost.org/Archives/boost/2005/03/83203.php
>
> So, here's how far I got tonight: there's
> sandbox/metagraph/libs/metagraph/example/proto_adaptor.cpp
> which does compile-time traversal of the Proto expression _1*12/_2,
> printing this nice error message showing that the preorder traversal
> worked (in reverse order):
A pre-order traversal, pushing each visited node into an mpl vector? How
about:
#include <iostream>
#include <typeinfo>
#include <boost/proto/proto.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/push_back.hpp>
#include <boost/mpl/for_each.hpp>
namespace proto = boost::proto;
namespace mpl = boost::mpl;
using proto::_;
template<typename T> struct wrap {};
struct PreOrder
: proto::or_<
proto::when<
proto::terminal<_>
, mpl::push_back<proto::_state, wrap<_>()>()
>
, proto::otherwise<
proto::fold<
_
, mpl::push_back<proto::_state, wrap<_>()>()
, PreOrder
>
>
>
{};
struct print_name
{
template<typename T>
void operator()(wrap<T> const &) const
{
std::cout << typeid(T).name() << "\n\n";
}
};
template<typename Vector>
void static_print(Vector)
{
mpl::for_each<Vector>(print_name());
}
template<int I> struct placeholder {};
proto::terminal< placeholder< 1 > >::type const _1 = {{}};
proto::terminal< placeholder< 2 > >::type const _2 = {{}};
int main()
{
static_print( PreOrder()(_1*12/_2, mpl::vector<>() ) );
}
This prints the following, which is the same as yours, except in the
correct order. ;-)
struct boost::proto::exprns_::expr<struct
boost::proto::tag::divides,struct boost::proto::argsns_::list2<struct
boost::proto::exprns_::expr<struct boost::proto::tag::multiplies,struct
boost::proto::argsns_::list2<struct boost::proto::exprns_::expr<struct
boost::proto::tag::terminal,struct boost::proto::argsns_::term<struct
placeholder<1> >,0> const &,struct boost::proto::exprns_::expr<struct
boost::proto::tag::terminal,struct boost::proto::argsns_::term<int const
&>,0> >,2> const &,struct boost::proto::exprns_::expr<struct
boost::proto::tag::terminal,struct boost::proto::argsns_::term<struct
placeholder<2> >,0> const &>,2>
struct boost::proto::exprns_::expr<struct
boost::proto::tag::multiplies,struct boost::proto::argsns_::list2<struct
boost::proto::exprns_::expr<struct boost::proto::tag::terminal,struct
boost::proto::argsns_::term<struct placeholder<1> >,0> const &,struct
boost::proto::exprns_::expr<struct boost::proto::tag::terminal,struct
boost::proto::argsns_::term<int const &>,0> >,2>
struct boost::proto::exprns_::expr<struct
boost::proto::tag::terminal,struct boost::proto::argsns_::term<struct
placeholder<1> >,0>
struct boost::proto::exprns_::expr<struct
boost::proto::tag::terminal,struct boost::proto::argsns_::term<int const
&>,0>
struct boost::proto::exprns_::expr<struct
boost::proto::tag::terminal,struct boost::proto::argsns_::term<struct
placeholder<2> >,0>
HTH,
-- Eric Niebler BoostPro Computing http://www.boostpro.com
Proto list run by eric at boostpro.com