On Friday 22 October 2010 11:29:07 Joel de Guzman wrote:
> On 10/22/10 4:17 PM, Thomas Heller wrote:
> > On Friday 22 October 2010 09:58:25 Eric Niebler wrote:
> >> On 10/22/2010 12:33 AM, Thomas Heller wrote:
> >>> On Friday 22 October 2010 09:15:47 Eric Niebler wrote:
> >>>> On 10/21/2010 7:09 PM, Joel de Guzman wrote:
> >>>>> Check out the doc I sent (Annex A). It's really, to my mind,
> >>>>> generic languages -- abstraction of rules and templated grammars
> >>>>> through metanotions and hyper-rules.
> >>>>
> >>>> Parameterized rules. Yes, I can understand that much. My
> >>>> understanding stops when I try to imagine how to build a parser
> >>>> that recognizes a grammar with parameterized rules.
> >>>
> >>> And I can't understand how expression templates relate to parsing.
> >>
> >> It doesn't in any practical sense, really. No parsing ever happens in
> >> Proto. The C++ compiler parses expressions for us and builds the tree.
> >> Proto grammars are patterns that match trees. (It is in this sense
> >> they're closer to schemata, not grammars that drive parsers.)
> >>
> >> They're called "grammars" in Proto not because they drive the parsing
> >> but because they describe the valid syntax for your embedded language.
> >
> > Ok, this formulation makes it much clearer :)
>
> It's just the metaphor! And what I saying is that you will get into
> confusion land if you mix metaphors from different domains. Proto uses
> the parsing domain and it makes sense (*). It may (and I say may) be
> possible to extend that metaphor and in the end it may be possible
> to incorporate that into proto instead of phoenix (if it is indeed
> conceptually understandable and reusable) --an opportunity that may
> be missed if you shut the door and dismiss the idea prematurely.
>
> It is OK to switch metaphors and have a clean cut. But again,
> my point is: use only one metaphor. Don't mix and match ad-hoc.
>
> (* regardless if it doesn't do any parsing at all!)
>
> >>>>> I have this strong feeling that that's the intent of Thomas and
> >>>>> your recent designs. Essentially, making the phoenix language a
> >>>>> metanotion in itself that can be extended post-hoc through
> >>>>> generic means.
> >>>>
> >>>> I don't think that's what Thomas and I are doing. vW-grammars
> >>>> change the descriptive power of grammars. But we don't need more
> >>>> descriptive grammars. Thomas and I aren't changing the grammar of
> >>>> Phoenix at all. We're just plugging in different actions. The
> >>>> grammar is unchanged.
> >>>
> >>> Exactly.
> >>> Though, I think this is the hard part to wrap the head around. We
> >>> have a grammar, and this very same grammar is used to describe
> >>> "visitation".
> >>
> >> It's for the same reason that grammars are useful for validating
> >> expressions that they are also useful for driving tree traversals:
> >> pattern matching. There's no law that the /same/ grammar be used for
> >> validation and evaluation. In fact, that's often not the case.
> >
> > True.
> > However it seems convenient to me reusing the grammar you wrote for
> > validating your language for the traversal of an expression matching
> > that grammar.
> > This is what we tried with this rule based dispatching to Semantic
> > Actions. I am currently thinking in another direction, that is
> > separating traversal and grammar again, very much like proto contexts,
> > but with this rule dispatching and describing it with proto transforms
> > ... the idea is slowly materializing in my head ...
>
> Again I should warn against mixing metaphors. IMO, that is the basic
> problem why it is so deceptively unclear. There's no clear model
> that conceptualizes all this, and thus no way to reason out on
> an abstract level. Not good.
Alright, I think mixing metaphors is indeed a very bad idea.
IMHO, it is best to stay in the grammar with semantic actions domain as it
always(?) has been.
I broke my head today, and developed a solution which stays in these very
same proto semantics, and reuses "keywords" (more on that) already in proto.
Attached, you will find the implementation of this very idea.
So, semantic actions in are kind of simple right now. the work by having
proto::when<some_grammar_rule, some_transform>
They ultimatevily bind this specific transform to that specific grammar.
The solution attached follows the same principles. However, grammars and
transform can now be decoupled. Transforms are looked up by rules that define
the grammar. In order to transform an Expression by this new form of
semantic actions, a special type of transform has to be used which i call
"traverse". This transform is parametrized by the grammar, which holds the
rules, and the Actions which holds the actions.
The action lookup is done by the following rules (the code might differ from
the description, this is considered a bug in the code):
1) Peel of grammar constructs like or_, and_ and switch.
2) Look into this inner most layer of the grammar and see if the supplied
actions implement a action for that rule. If this rule also matches the
current expression, that action is returned.
3) If no action was found, just return the expression itself.
The handling of these rules is completely implemented in the
_traverse<Grammar, Actions> transform. This leaves the grammar what it is, a
grammar. Making it possible to reuse it with a set of transforms.
This set of transforms is called Actions.
An Actions class has a nested struct when<Rule, Actions>. This resembles the
behavior of the already existing proto::when.
Example (from above):
struct some_actions
: actions<some_actions>
{
template <typename Actions>
struct when<some_grammar_rule, Actions> : some_transform {};
};
traverse<some_grammar, some_actions>(expr);
With expression being an AST conforming to some_grammar.
I think this is the simplification of client proto code we searched for. It
probably needs some minor polishment though.
Thoughts?
Cheers,
Thomas
#include <iostream>
#include <boost/proto/proto.hpp>
namespace proto = boost::proto;
namespace mpl = boost::mpl;
namespace detail
{
struct action_not_found_ {};
template <typename Actions, typename Rule>
struct has_action
{
typedef char yes;
typedef struct { char c[2]; } no;
template <typename A, typename R>
static yes check(typename A::template when<R, A>::transform_type*);
template <typename A, typename R>
static no check(...);
static const bool value = (sizeof(check<Actions, Rule>(0)) == sizeof(yes));
typedef mpl::bool_<value> type;
};
template <typename Actions, typename Grammar, typename Action, typename Expr>
struct select_action_;
template <
typename Actions
, typename Grammar
, template <typename, typename> class Action
, typename Rule
, typename Expr>
struct select_action_<Actions, Grammar, Action<Rule, Actions>, Expr>
{
typedef
typename mpl::eval_if<
mpl::and_<
has_action<Actions, Rule>
, proto::matches<Expr, Rule>
>
, mpl::identity<Action<Rule, Actions> >
, mpl::identity<action_not_found_>
>::type
type;
};
template <typename Actions>
struct fold_actions
: mpl::fold<
Actions
, action_not_found_
, mpl::if_<
boost::is_same<
mpl::_2
, action_not_found_
>
, mpl::_1
, mpl::_2
>
>
{};
#define M0(Z, N, DATA) \
typename select_action_< \
Actions \
, typename BOOST_PP_CAT(G, N)::proto_grammar \
, typename Actions::template when< \
BOOST_PP_CAT(G, N), Actions \
>, Expr \
>::type \
/**/
#define M1(Z, N, DATA) \
template < \
typename Actions \
BOOST_PP_ENUM_TRAILING_PARAMS(N, typename G) \
, template <typename, typename> class Action \
, typename Rule \
, typename Expr> \
struct select_action_< \
Actions \
, proto::DATA<BOOST_PP_ENUM_PARAMS(N, G)> \
, Action<Rule, Actions> \
, Expr> \
{ \
struct hide \
: proto::DATA<BOOST_PP_ENUM_PARAMS(N, G)> \
{}; \
typedef \
BOOST_PP_CAT(mpl::vector, BOOST_PP_INC(N))< \
typename select_action_< \
Actions \
, hide \
, Action<Rule, Actions> \
, Expr \
>::type \
BOOST_PP_ENUM_TRAILING(N, M0, _) \
> \
actions; \
typedef typename fold_actions<actions>::type type; \
}; \
/**/
BOOST_PP_REPEAT(BOOST_PROTO_MAX_LOGICAL_ARITY, M1, or_)
BOOST_PP_REPEAT(BOOST_PROTO_MAX_LOGICAL_ARITY, M1, and_)
#undef M0
#undef M1
template <
typename Actions
, typename Cases
, template <typename, typename> class Action
, typename Rule
, typename Expr>
struct select_action_<
Actions
, proto::switch_<Cases>
, Action<Rule, Actions>
, Expr>
{
struct hide
: proto::switch_<Cases>
{};
typedef
typename Cases::template case_<
typename proto::tag_of<Expr>::type
>
case_;
typedef
mpl::vector3<
typename select_action_<
Actions
, hide
, Action<Rule, Actions>
, Expr
>::type
, typename select_action_<
Actions
, typename case_::proto_grammar
, typename Actions::template when<case_, Actions>
, Expr
>::type
, typename select_action_<
Actions
, typename case_::proto_grammar
, typename Actions::template when<
typename case_::proto_grammar
, Actions
>
, Expr
>::type
>
actions;
typedef typename fold_actions<actions>::type type;
};
}
template <typename Grammar, typename Actions, typename Expr>
struct select_action
: detail::select_action_<
Actions
, typename Grammar::proto_grammar
, typename Actions::template when<Grammar, Actions>, Expr
>
{};
template <typename Grammar, typename Actions>
struct _traverse
: proto::transform<_traverse<Grammar, Actions> >
{
template <typename Expr, typename State, typename Data>
struct impl
: proto::transform_impl<Expr, State, Data>
{
typedef
typename select_action<Grammar, Actions, Expr>::type
action;
template <typename Action>
struct result_helper
{
typedef
typename Action::template impl<
Expr, State, Data
>::result_type
type;
};
typedef
typename mpl::eval_if<
boost::is_same<
action
, detail::action_not_found_
>
, mpl::identity<Expr>
, result_helper<action>
>::type
result_type;
result_type operator()(
typename impl::expr_param e
, typename impl::state_param s
, typename impl::data_param d
) const
{
return invoke(e,s,d, action());
}
private:
template <typename Action>
result_type invoke(
typename impl::expr_param e
, typename impl::state_param s
, typename impl::data_param d
, Action
) const
{
return typename Action::template impl<Expr, State, Data>()(e, s, d);
}
result_type invoke(
typename impl::expr_param e
, typename impl::state_param s
, typename impl::data_param d
, detail::action_not_found_
) const
{
return e;
}
};
};
namespace boost { namespace proto
{
template <typename Grammar, typename Actions>
struct is_callable<_traverse<Grammar, Actions> > : mpl::true_ {};
}}
template <typename Grammar, typename Actions, typename Expr>
typename
_traverse<
Grammar
, Actions>::template impl<
Expr const &
, int
, int
>::result_type
traverse(Expr const& expr)
{
return
typename _traverse<
Grammar
, Actions>::template impl<
Expr const &
, int
, int
>()(expr, 0, 0);
}
template <typename DefaultActions>
struct action
{
template <typename Rule, typename Actions = DefaultActions>
struct when;
};
struct int_terminal
: proto::terminal<int>
{};
struct char_terminal
: proto::terminal<char>
{};
struct my_grammar
: proto::or_<
int_terminal
, char_terminal
, proto::plus<int_terminal, int_terminal>
>
{};
struct my_actions;
struct print : proto::callable
{
typedef std::string result_type;
result_type operator()(int) const
{
return "int";
}
result_type operator()(char) const
{
return "char";
}
template <typename T1, typename T2>
result_type operator()(T1 const& t1, T2 const& t2) const
{
std::string res("");
res += traverse<my_grammar, my_actions>(t1);
res += " + ";
res += traverse<my_grammar, my_actions>(t2);
return res;
}
};
struct my_actions
: action<my_actions>
{
template <typename Actions>
struct when<int_terminal, Actions>
: proto::call<print(proto::_value)>
{};
template <typename Actions>
struct when<char_terminal, Actions>
: proto::call<print(proto::_value)>
{};
template <typename Actions>
struct when<proto::plus<int_terminal, int_terminal>, Actions>
: proto::call<
print(
proto::_left
, proto::_right
)
>
{};
};
int main()
{
proto::literal<int> i(8), j(9);
proto::literal<char> a('a'), b('b');
std::cout << traverse<char_terminal, my_actions>(a) << "\n"; // printing char
std::cout << traverse<int_terminal, my_actions>(a) << "\n"; // printing nothing, cause no char terminal in the int_terminal grammar
std::cout << traverse<char_terminal, my_actions>(i) << "\n"; // printing nothing, cause no int terminal in char_terminal grammar
std::cout << traverse<int_terminal, my_actions>(j) << "\n"; // printing int
std::cout << traverse<my_grammar, my_actions>(j) << "\n"; // printing int
std::cout << traverse<my_grammar, my_actions>(a) << "\n"; // printing char
std::cout << traverse<my_grammar, my_actions>(i + i) << "\n"; // printing int + int
}
_______________________________________________
proto mailing list
proto@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/proto
