On 10/13/2010 11:08 PM, Thomas Heller wrote:
> Let me try again ...
> I tried to solve the problem that when writing a proto grammar+transform you
> might want to dispatch your transform based on tags.
You mean expression tags, right? First time I read this, I accepted this
statement as fact. Now I wonder.
*Why* do you want to dispatch your transforms based on tags? You're
thinking of proto::switch_, which dispatches grammars based on
expression tags, right? But it doesn't follow that transforms are best
dispatched on expression tags, too. We are close to the bare
requirements, but we're not there yet. In my understanding, the
requirements are as I stated before (and which you agreed with):
A) Have an openly extensible grammar.
B) Have an equally extensible set of transforms.
C) Be able to substitute out a whole other (extensible) set of transforms.
I have an alternate solution that meets these requirements and doesn't
dispatch to transforms based on expression tags. It dispatches to
transforms using grammar rules. This has a number of nice properties.
Keep reading...
> Additionally you would
> like to replace that particular transform which evaluates your expression by
> another one.
> proto::switch_ allows you to dispatch grammar + transform based on a specific
> tag already, I think we agree that .
> The major usecase i had in mind for this was phoenix.
> First use case is, when defining some generic grammar like this:
>
> struct phoenix_cases
> {
> template <typename Tag>
> struct case_
> : proto::otherwise<evaluate<Tag>(proto::_, proto::_state)>
> /*call the phoenix evaluator, how? My proposed solution is through tag
> dispatching! */
> {};
> };
>
> struct phoenix_grammar
> : switch_<phoenix_cases>
> {};
>
> So far so good. I hope we agree that this might be a good way to define the
> phoenix grammar.
My solution works differently. Which one is better is still an open
question.
> The need to further define how a valid phoenix grammar can
> look like is through specialising phoenix_cases::case_ (*).
> Ok, I think this is a good solution already.
>
> But now, think about, that people might want to evaluate a phoenix
> expression differently!
> One example to this is that i want to generate a valid C++ string out of my
> phoenix expression, save it for later and compile it again with my native
> C++ compiler. I might even want to be able to evaluate a phoenix expression
> to openCL/cuda/glsl/hlsl whatever. Another thing i might want to add to the
> evaluation process is autoparallelization. I hope you agree that these might
> be valid usecases!
>
> With the definition of the phoenix grammar above, this is not easily
> possible! I would have to repeat the phoenix grammar all over again (maybe
> this is the point where i am totally of the line).
I'm with you here.
> The next, logical (IMHO) step is to parameterize our phoenix_grammar to
> allow an arbitrary transform to be dispatched on the tag basis (Again, there
> might be a different solution, I can't see any though).
Dispatch to transforms on grammar rules.
> Note: This is the step where the name "Visitor" came in, because it is what
> it does: it visits an expression and transforms it, somehow.
>
> So, the design will change to this:
>
> template <template <typename> Visitor>
> struct phoenix_cases
> {
> template <typename Tag>
> struct case_
> : proto::otherwise<Visitor<Tag>(proto::_, proto::_state)>
> /*call the phoenix evaluator, how? My proposed solution is through tag
> dispatching! */
> {};
> };
>
> template <template <typename> Visitor>
> struct phoenix_grammar
> : switch_<phoenix_cases<Visitor>
> {};
>
> // bring our default evaluator back into the game:
> typedef phoenix_grammar<evaluate> evaluator;
>
> I hope this still makes sense.
I have followed your logic this far, although our solutions have diverged.
> The next step involved the "problem" of defining what valid phoenix
> expressions look like (We discussed this in (*)). So for the sake of
> simplicity, why not parameterize our phoenix_grammar on a Grammar as well,
> so narrowing down the validity of phoenix expressions becomes the act of
> specializing one simple struct, instead of this phoenix_case beast.
Here's where you lose me. I didn't know there was a problem with
defining what a valid phoenix expression looks like. Proto::switch_
seems to be good enough. To allow the phoenix grammar to be openly
extensible.
> So, the whole thing becomes:
>
> template <template <typename> Visitor, template <typename> Grammar>
> struct phoenix_cases
> {
> template <typename Tag>
> struct case_
> : proto::when<Grammar<Tag>, Visitor<Tag>(proto::_,
> proto::_state)>
> /*call the phoenix evaluator, how? My proposed solution is through tag
> dispatching! */
> {};
> };
>
> template <template <typename> Visitor, template <typename> Grammar>
> struct phoenix_grammar
> : switch_<phoenix_cases<Visitor, Grammar>
> {};
>
> // bring our default evaluator back into the game:
> typedef phoenix_grammar<evaluate, grammar> evaluator;
So, you're allowing both the grammar and the semantic actions to float,
and they both depend on expression tags. I get it. I see problems with
this design (see below), but the largest is that the phoenix_grammar is
now so flexible as to be meaningless. Anybody can change anything. The
very simple question of "what is a valid phoenix expression?" now
becomes *very* difficult to wrap your head around. But there's a more
practical consideration that I'll discuss later.
> So, Visitor is now some transform that gets called with the expression and
> state. However, what if someone wants to have data as well or doesn't care
> about the current expression. No problem, let Visitor<Tag> be just like any
> other regular transform!
> So the final design evolved to this:
>
> template <template <typename> Visitor, template <typename> Grammar>
> struct phoenix_cases
> {
> template <typename Tag>
> struct case_
> : proto::when<Grammar<Tag>, Visitor<Tag> >
> /*call the phoenix evaluator, how? My proposed solution is through tag
> dispatching! */
> {};
> };
>
> template <template <typename> Visitor, template <typename> Grammar>
> struct phoenix_grammar
> : switch_<phoenix_cases<Visitor, Grammar>
> {};
>
> template <typename Tag>
> struct evaluate : proto::_default {};
>
> template <typename Tag>
> struct grammar : proto::_ {};
>
> // bring our default evaluator back into the game:
> typedef phoenix_grammar<evaluate, grammar> evaluator;
>
> This is where Joel Falcou came in and said: "Hey this is a nice abstraction
> of the stuff i already had done!" (paraphrasing here)
>
> Thus I generalized what is now phoenix_grammar and called it proto::visitor.
> And proposed it to this very list.
I understand now. Thanks. "Visitor" is really a generalization of
proto::switch_. Switch_ accepts one argument and treats it as a
collection of grammars that are indexed on expression tag. Visitor
accepts two arguments---a collection of grammars and another collection
of transforms---both of which are indexed on expression tags. Really,
visitor could just be a further generalization of switch_.
But I don't think that's a good idea. More below.
> I hope this makes more sense now. Please point out where I am missing
> something, or where you can not follow the line of thought.
>
> If this still doesn't help I am sorry to have wasted your time. I couldn't
> think of another solution. I would be very happy to see an alternative
> approach to solve this very problem (I like what you did with the split
> example).
First, let me say that everything you've done is perfectly reasonable,
and I (finally!) understand what you've done and why you've done it. Whew!
Here's the fundamental problem with dispatching to transforms based on
expression tags: the tags are insufficient to pick the right transform.
Consider:
// Define an openly extensible grammar using switch_
struct MyGrammar
: proto::switch_< struct MyCases >
{};
struct MyCases
{
template<typename Tag>
struct case_
: proto::not< proto::_ >
{};
};
// OK, handle the terminals we allow:
template<>
struct MyCases::case_< proto::tag::terminal >
: proto::or_<
proto::when< proto::terminal<int>, DoIntAction >
, proto::when< proto::terminal<char>, DoCharAction >
>
{};
// ... define other case_ specializations ...
The important thing to note is that tag::terminal is not enough to
determine whether a particular terminal is valid for MyGrammar, so we
have to use proto::or_ to further specialize.
Also note that the int and char terminals have different semantic
actions. In this case, dispatching to a transform based on expression
tag is fundamentally too weak to pick the right one. AFAICT, there would
be no way to use your visitor to handle this situation.
What's the alternative? Rather than dispatching to transforms based on
expression tags, dispatch on grammar rules. Then document which rules in
your grammar are customization points.
The above example becomes this:
// A collection of actions indexable by rules.
struct MyActions
{
template<typename Rule>
struct action;
};
// A helper that finds the appropriate action by looking it
// up by rule
template<typename Rule, typename Actions>
struct MyWhen
: proto::when< Rule, typename Actions::template action<Rule> >
{};
// An easier way to dispatch to a tag-specific sub-grammar
template<typename Tag, typename Actions>
struct MyCases
: proto::not< proto::_ >
{};
template<typename Actions>
struct MyCasesImpl
{
template<typename Tag>
struct case_
: MyCases<Tag, Actions>
{};
};
// Define an openly extensible grammar using switch_
template<typename Actions = MyActions>
struct MyGrammar
: proto::switch_< MyCasesImpl<Actions> >
{};
// Define a grammar rule for int terminals
struct IntTerminalRule
: proto::terminal<int>
{};
// Define a grammar rule for char terminals
struct CharTerminalRule
: proto::terminal<char>
{};
// OK, handle the terminals we allow:
template<typename Actions>
struct MyCases< proto::tag::terminal, Actions >
: proto::or_<
MyWhen< IntTerminalRule, Actions >
, MyWhen< CharTerminalRule, Actions >
>
{};
// Now, populate the MyActions metafunction class
// with the default actions:
template<>
struct MyActions::action< IntTerminalRule >
: DoIntAction
{};
template<>
struct MyActions::action< CharTerminalRule >
: DoCharAction
{};
Some things to note about this solution:
- MyGrammar can be parameterized by a set of actions.
- The actions are accessed by indexing via a well-defined
and openly extensible set of grammar rules.
- Although the grammar is extensible, it is not mutable.
That is, new constructs can be added, but existing ones
cannot be changed. That makes it easier to understand
what it means for an expression to match the grammar.
(If a different grammar is desired, a new one needs to be
defined. It can reuse parts of MyGrammar, but MyGrammar
itself remains unchanged. This, I think, is desirable.)
- The Actions parameter has *no* effect on what expressions
match the MyGrammar. MyGrammar<MyActions> and MyGrammar<
YourActions> both match exactly the same set of expressions.
- A new set of actions can be created easily by delegating
to MyActions::action by default, and specializing only those
rules that need custom handling.
I'm attaching the beginnings of a Phoenix implementation that is built
using this technique. It is obviously just a shell. No nice actor
wrappers or anything. This is just to demonstrate that the technique
works. It builds an extensible core, handles placeholders, terminals
(including reference_wrapped terminals), and if_/then_/else_ built as an
extension to the core.
Comments?
--
Eric Niebler
BoostPro Computing
http://www.boostpro.com
#include "stdafx.h"
#include <iostream>
namespace mpl = boost::mpl;
namespace proto = boost::proto;
namespace fusion = boost::fusion;
using proto::_;
#ifdef _MSC_VER
#pragma warning(disable: 4355)
#endif
// A collection of semantic actions, indexed by phoenix grammar rules
struct PhoenixActions
{
template<typename Rule>
struct action;
};
// Simple utility for binding a semantic action to a rule
template<typename Rule, typename Actions>
struct rule_with_action
: proto::when<Rule, typename Actions::template action<Rule> >
{};
// The phoenix grammar and evaluator algorithm, parameterized
// by a collection of semantic actions.
template<typename Actions = PhoenixActions>
struct PhoenixGrammar;
// The Phoenix "default" rule, which handles most operands by
// delegating to proto::_default.
struct PhoenixRuleDefault
: proto::_default<PhoenixGrammar<> >
{};
// Add to the collection of semantic actions the thing to
// do in the "default" case.
template<>
struct PhoenixActions::action<PhoenixRuleDefault>
: proto::_default<PhoenixGrammar<> >
{};
// An openly extensible collection of phoenix rules and actions.
// "Tag" here is an expression tag.
template<typename Tag, typename Actions>
struct PhoenixAlgorithmCases
: rule_with_action< PhoenixRuleDefault, Actions >
{};
// Simple wrapper for PhoenixAlgorithmCases to make it
// suitable for use with proto::switch_
template<typename Actions>
struct PhoenixAlgorithmCasesImpl
{
template<typename Tag>
struct case_
: PhoenixAlgorithmCases<Tag, Actions>
{};
};
// The phoenix grammar and evaluator is just a
// collection of phoenix rules, parameterized by
// the actions to take for each rule.
template<typename Actions>
struct PhoenixGrammar
: proto::switch_<PhoenixAlgorithmCasesImpl<Actions> >
{};
// Define placeholders
template<typename I>
struct placeholder
{
typedef I type;
typedef typename I::value_type value_type;
static value_type const value = I::value;
};
// Here is the arg1 placeholder
proto::terminal<placeholder<mpl::int_<0> > >::type const arg1 = {};
// Simple TR1-style function object for indexing a Fusion sequence
struct at : proto::callable
{
template <typename Sig>
struct result;
template <typename This, typename N, typename Env>
struct result<This(N, Env)>
: fusion::result_of::at_c<
typename boost::remove_reference<Env>::type
, boost::remove_reference<N>::type::value
>
{};
template<typename N, typename Env>
typename fusion::result_of::at_c<Env, N::value>::type
operator()(N, Env &env) const
{
return fusion::at_c<N::value>(env);
}
};
// The phoenix rule for matching placeholder
// (Can later be generalized with boost::is_placeholer)
struct PhoenixRulePlaceholder
: proto::terminal<placeholder<_> >
{};
// The action to take for placeholders
template<>
struct PhoenixActions::action<PhoenixRulePlaceholder>
: proto::call<at(proto::_value, proto::_state)>
{};
// Customization point for special terminal handling
template<typename T>
struct is_custom_terminal
: mpl::false_
{};
// Customization point for special terminal handling
template<typename T>
struct get_custom_terminal;
// Phoenix rule for matching custom terminals
struct PhoenixRuleCustomTerminal
: proto::if_<is_custom_terminal<proto::_value>()>
{};
// Phoenix action to take for custom terminals
template<>
struct PhoenixActions::action<PhoenixRuleCustomTerminal>
: proto::lazy<get_custom_terminal<proto::_value>(proto::_value)>
{};
// Bind actions to rules for terminals
template<typename Actions>
struct PhoenixAlgorithmCases<proto::tag::terminal, Actions>
: proto::or_<
rule_with_action< PhoenixRulePlaceholder, Actions >
, rule_with_action< PhoenixRuleCustomTerminal, Actions >
, rule_with_action< PhoenixRuleDefault, Actions >
>
{};
// Create a phoenix terminal, stored by value
template<typename T>
typename proto::terminal<T>::type val(T t)
{
return proto::terminal<T>::type::make(t);
}
// Create a phoenix terminal, stored by reference
template<typename T>
typename proto::terminal<boost::reference_wrapper<T> >::type ref(T &t)
{
return proto::terminal<boost::reference_wrapper<T>
>::type::make(boost::ref(t));
}
// Create a phoenix terminal, stored by const reference
template<typename T>
typename proto::terminal<boost::reference_wrapper<T const> >::type cref(T const
&t)
{
return proto::terminal<boost::reference_wrapper<T const>
>::type::make(boost::cref(t));
}
// Call out boost::reference_wrapper for special handling
template<typename T>
struct is_custom_terminal<boost::reference_wrapper<T> >
: mpl::true_
{};
// Special handling for boost::reference_wrapper
template<typename T>
struct get_custom_terminal<boost::reference_wrapper<T> >
{
typedef T &result_type;
T &operator()(boost::reference_wrapper<T> r) const
{
return r;
}
};
//-----
// Begin if_/then_/else_ implementation
//-----
// Define some tags for additional statements
namespace tag
{
struct if_then {};
struct if_then_else {};
}
template<typename Cond, typename Then, typename Else>
struct if_then_else
: proto::nary_expr<tag::if_then_else, Cond, Then, Else>
{};
template<typename Cond, typename Then>
struct else_gen
{
else_gen(Cond const& cond, Then const& then)
: cond(cond)
, then(then)
{}
template <typename Else>
typename if_then_else<Cond, Then, Else>::type const
operator[](Else const &else_) const
{
return if_then_else<Cond, Then, Else>::type::make(cond, then, else_);
}
Cond const &cond;
Then const &then;
};
template<typename Expr>
struct if_expr
: Expr
{
if_expr(Expr const& expr)
: Expr(expr)
, else_(proto::child_c<0>(*this), proto::child_c<1>(*this))
{}
typedef typename proto::result_of::child_c<Expr, 0>::type cond_type;
typedef typename proto::result_of::child_c<Expr, 1>::type then_type;
else_gen<cond_type, then_type> else_;
};
template<typename Cond, typename Then>
struct if_then
: proto::binary_expr<tag::if_then, Cond, Then>
{};
template<typename Cond>
struct if_gen
{
explicit if_gen(Cond const& cond)
: cond(cond)
{}
template<typename Then>
if_expr<typename if_then<Cond const &, Then const &>::type> const
operator[](Then const &then) const
{
return if_then<Cond const &, Then const &>::type::make(cond, then);
}
Cond const &cond;
};
template <typename Cond>
if_gen<Cond> const if_(Cond const &cond)
{
return if_gen<Cond>(cond);
}
// Callable for evaluating if_/then_ statements
template<typename Actions>
struct if_then_eval : proto::callable
{
typedef void result_type;
template <typename Cond, typename Then, typename Env>
result_type operator()(Cond const& cond, Then const& then, Env& env) const
{
if(PhoenixGrammar<Actions>()(cond, env))
{
PhoenixGrammar<Actions>()(then, env);
}
}
};
// Phoenix rule for matching if_/then_ statements
struct PhoenixRuleIfThen
: if_then<PhoenixGrammar<>, PhoenixGrammar<> >
{};
// Phoenix action to take for if_/then_ statements
template<>
struct PhoenixActions::action<PhoenixRuleIfThen>
: proto::call<if_then_eval<PhoenixActions>(proto::_child0, proto::_child1,
proto::_state)>
{};
// Bind actions to rules for if_/then_ statements
template<typename Actions>
struct PhoenixAlgorithmCases<tag::if_then, Actions>
: rule_with_action< PhoenixRuleIfThen, Actions >
{};
// Callable for evaluating if_/then_/else_ statements
template<typename Actions>
struct if_then_else_eval : proto::callable
{
typedef void result_type;
template <typename Cond, typename Then, typename Else, typename Env>
result_type operator()(Cond const& cond, Then const& then, Else const&
else_, Env& env) const
{
if(PhoenixGrammar<Actions>()(cond, env))
{
PhoenixGrammar<Actions>()(then, env);
}
else
{
PhoenixGrammar<Actions>()(else_, env);
}
}
};
// Phoenix rule for matching custom terminals
struct PhoenixRuleIfThenElse
: if_then_else<PhoenixGrammar<>, PhoenixGrammar<>, PhoenixGrammar<> >
{};
// Phoenix action to take for custom terminals
template<>
struct PhoenixActions::action<PhoenixRuleIfThenElse>
: proto::call<if_then_else_eval<PhoenixActions>(proto::_child0,
proto::_child1, proto::_child2, proto::_state)>
{};
// Bind actions to rules for terminals
template<typename Actions>
struct PhoenixAlgorithmCases<tag::if_then_else, Actions>
: rule_with_action< PhoenixRuleIfThenElse, Actions >
{};
//-----
// End if_/then_/else_ implementation
//-----
int main()
{
PhoenixGrammar<> phoenix_eval;
fusion::vector1<int> env(42);
proto::literal<int> i(1), j(2);
int k = phoenix_eval(i + j);
std::cout << k << std::endl;
k = phoenix_eval(i + arg1, env);
std::cout << k << std::endl;
k = phoenix_eval(cref(42), env);
std::cout << k << std::endl;
phoenix_eval( if_(i == 1)[ ++i ], env );
std::cout << i.get() << std::endl;
phoenix_eval( if_(i == 1)[ ++i ].else_[ --i ], env );
std::cout << i.get() << std::endl;
}
_______________________________________________
proto mailing list
proto@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/proto
