Re: [boost] [guidelines] why template errors suck

Subject: Re: [boost] [guidelines] why template errors suck
From: Smith, Jacob N (jacob.n.smith_at_[hidden])
Date: 2010-09-27 19:55:58

> -----Original Message-----
> From: boost-bounces_at_[hidden] [mailto:boost-
> bounces_at_[hidden]] On Behalf Of Eric Niebler
> Sent: Monday, September 27, 2010 11:06 AM
> To: boost_at_[hidden]
> Subject: Re: [boost] [guidelines] why template errors suck
> 
> On 9/27/2010 1:16 PM, Smith, Jacob N wrote:
> >
> > Disclaimer: it has been a couple of years since I worked with
> concepts.
> >
> >
> > concept SpiritPlusesShortProtoTree<typename Node>
> > {
> > 	// Checks that the "ShortProtoTree" is the expression: (+X) +
> (+Y)
> > 	requires SpiritNode<Node>,
> > 		ShortProtoTree<Node>,
> > 		IsBinaryPlusOperator<Node>,
> > 		IsUnaryPlusOperator<get_child<_0,
> ProtoNode<Node>::children>::type>,
> > 		IsUnaryPlusOperator<get_child<_1,
> ProtoNode<Node>::children>::type>;
> > }
> >
> > I am waving my hands at the "get_child" functor; it is
> straightforward to describe using concepts.
> >
> > Concepts are fairly tightly related to algebra declarations. Any
> algebra can be thought of as a tree, therefore, any tree should be
> checkable via concepts. Disjoint ("or") concept requirements are not
> needed in this situation since the concept mechanism will choose the
> most specialized concept that the model satisfies, not the least
> specialized. [This is not to say that disjoint concepts aren't
> necessary in some cases.]
> 
> You have shown that you can concept-check the expression (+X) + (+Y).
> You did it by traversing the tree in the SpiritPlusesShortProtoTree
> concept and verifying each node explicitly. I don't see (yet) how you
> can generalize this.

Do you want a concept checking the set of legal constructions of Spirit parsers or a concept checking a particular instance of the Spirit parsing framework? The first instance seems easier:

concept SpiritNode<typename Node>
{
        Iterator iterator = Node::iterator;
        typename children = Node::children; // opaque

        iterator parse(iterator, iterator, Node&);
}

concept SpiritTerminal<typename Node> : SpiritNode<Node> { }
 
concept SpiritUnaryNode<typename Node>
{
        requires SpiritNode<Node>;
        requires SpiritNode<get_child<_0, SpiritNode<Node>::children>::type>;
}

concept SpiritBinaryNode<typename Node>
{
        requires SpiritNode<Node>;
        requires SpiritNode<get_child<_0, SpiritNode<Node>::children>::type>,
                SpiritNode<get_child<_1, SpiritNode<Node>::children>::type>;
}

// etc. Althought I think this covers all the legal overloadable operators.

I'm not sure how "interesting" this is, other than to force a mapping to known arities for spirit nodes. In the second case, checking a particular instance of a grammar, let me take a short stab at it [this will assuredly have mistakes, but I don't think the fundamental solution is flawed modulo the "no concepts in C++" issue]:

S  ::= E0
E0 ::= E1 + E0 | E1
E1 ::= <symbol>

concept MyGrammarS<typename Node>
{
        requires SpiritNode<Node>;
        // Semantic qualification:
        //   It is not legal to define a direct modeling relationship
        //   to MyGrammarS. All such relationships must occur
        //   indirectly, i.e., through MyGrammarE0, MyGrammarE1, or MyGrammarE1pE0.
}

concept MyGrammarE0<typename Node>
{
        requires MyGrammarS<Node>;
}

concept MyGrammarE1<typename Node>
{
        requires SpiritNode<Node>;
}

concept MyGrammarE1pE0<typename Node>
{
        requires SpiritBinaryNode<Node>;
        requires MyGrammarE1<get_child<_0, SpiritNode<Node>::children>::type>,
                MyGrammarE0<get_child<_1, SpiritNode<Node>::children>::type>;
}

template <MyGrammarE0 Node>
concept_map MyGrammarS<Node> { }

template <MyGrammarE1 Node>
concept_map MyGrammarE0<Node> { }

// The following modeling relationship uses a made up syntax. I'm not sure
// anyone implemented a modeling relationship syntax from multisorted concepts
// without an underlying carrier.
template <MyGrammarS L, MyGrammarS R>
concept_map MyGrammarE0<MyGrammarE1pE0<L,R>> { }

Now when we define the modeling relationship from types to concepts, we do not allow an definition to the concept "MyGrammarS". For instance:

template <typename L, typename R> struct plus_node { };

template <MyGrammarS L, MyGrammarS R>
concept_map MyGrammarE1pE0<plus_node<L, R>> { }

template <int K> struct symbol_node { };

template <int K>
concept_map MyGrammarE1<symbol_node<K>> { }

The following type is legal:

typedef plus_node<plus_node<symbol_node<0>, symbol_node<1>>, plus_node<symbol_node<1>, symbol_node<2>>> my_gram0; // legal

But this type is illegal:

typedef plus_node<int, double> my_gram1; // illegal

Even if we have types that otherwise satisfy Spirit nodes:

struct foo { }; concept_map SpiritNode<foo> { /* impl */ }

They can't be used within my grammar:

typedef plus_node<foo, foo> my_gram2; // illegal

This of course relies on the fact that I don't try to "hide" MyGrammar* nodes by having them model MyGrammarS and not the fully specialized variant of the concept hierarchy for my node's type.

> You appear to be writing a new concept for each valid tree type. But
> there are an infinite number of trees that are valid Spirit trees (and
> an infinite number that are not). I still don't see how concepts can
> tell the difference between the two sets.
> 
> --
> Eric Niebler
> BoostPro Computing
> http://www.boostpro.com
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost