Boost logo

Boost :

Subject: Re: [boost] [contract] concepts: pseudo-signatures vs. usage patterns
From: Dave Abrahams (dave_at_[hidden])
Date: 2012-10-13 20:53:28


on Sat Oct 13 2012, Larisse Voufo <lvoufo-AT-indiana.edu> wrote:

> Thanks for the feedback. Hopefully I'm addressing your comments well below.
>
> On Sat, Oct 13, 2012 at 5:10 PM, Dave Abrahams <dave_at_[hidden]> wrote:
>
>>
>> on Sat Oct 13 2012, Larisse Voufo <lvoufo-AT-indiana.edu> wrote:
>>
>> > On Sat, Oct 13, 2012 at 9:53 AM, Larisse Voufo <lvoufo_at_[hidden]>
>> wrote:
>> >
>> >>
>> >>
>> >> On Fri, Oct 12, 2012 at 3:05 PM, Doug Gregor <doug.gregor_at_[hidden]
>> >wrote:
>> >>
>> >>> From the standardization perspective, we'll make zero progress until
>> >>> someone gets working on a real implementation. Just having a concept
>> >>> parser + archetype generator (which then instantiates template
>> >>> definitions based on those archetypes) would be a huge win.
>> >>
>> >>
>> >> This is intriguing. Based on my current experience with ConceptClang
>> >> (and I could be missing something), I would actually argue that
>> ^^^^^^^^
>>
>> This word seems to imply that you think you are contradicting Doug, but
>> to me it sounds like what you say here reinforces his statement.
>
> I don't think I'm contradicting Doug in terms of archetypes and template
> definitions being important.
> I am just not sure that his proposed implementation is sufficient, hence
> the "something".
>
>> The
>> only way I can make sense of this is to assume you mean something
>> different by "concept model archetypes" than Doug and I mean when we say
>> "archetypes."
>
> I think that when you guys say "archetypes", you mean both "type
> archetypes" and
> "concept model archetypes",

I don't know what either of those things are, so saying that doesn't
mean much to me.

> and I find the term sometimes ambiguous to me. I also think you think
> of them in terms of how they are implemented in ConceptGCC

No; I've never looked at the implementation. And, by the way, baseless
assumptions that perspective has been distorted by too much familiarity
with a particular implementation are a sore point for some of us. I
guess you picked them up from part of the culture around this project,
so I don't blame you, but I suggest that they are unhelpful when trying
to understand my point of view.

> and N2914, that is, as embedded with the checking of template
> definitions.

I don't know what you mean by that.

When I say "archetypes" I mean
what's described in
http://www.boost.org/doc/libs/1_51_0/libs/concept_check/concept_covering.htm.

In the context of a language feature, I expect them to be generated
automatically by the compiler based on concept declarations and
constraints.

I do expect them to be used in checking template definitions.

> In other words, there seems to be an implicit assumption that declarations
> in concept model archetypes
     ^^^^^^^^^^^^^^^^^^^^^^^^
Here's that undefined term again.

> corresponding to the template's constraints ought to be injected into the
> associated template parameter scope.

Until you define your terms, I'm not going to be able to respond
usefully to the above. An example would be very helpful here also.

> Therefore, the notion of concept model archetype is implicit and doesn't
> have an explicit representation in the compiler.

Just based on the grammar of what you said, without fully grasping the
meaning, I don't see how that sentence could be a logical conclusion of
what comes before.

> Further, constraints satisfaction and the
           ^^^^^^^^^^^^^^^^^^^^^^^^
> binding of entity references, at instantiation time, with respect to
  ^^^^^^^ ^^^^^^^^^^^^^^^^^
> model implementations comes for free with the treatment of
> concept models as class template specializations.
>
> In the WGP ConceptClang paper,

By which you mean
http://www.generic-programming.org/software/ConceptClang/papers/wgp06v-voufo.pdf
?

I note that most of these terms you're throwing around don't appear in
that paper.

> we made the distinction that:
>
> 1. We didn't need type archetypes in ConceptClang since Clang
                       ^^^^^^^^^^^^^^^
> already does a good enough job treating template type parameters as
> types.

> 2. We gave concept model archetypes explicit representations as simply
                ^^^^^^^^^^^^^^^^^^^^^^^^
> concept models satisfied by substituting declarations over from their
> mapped concepts. This way it is clear to see the two main roles that
> constraints are supposed to serve: Acting as predicates and providing scope
> for name resolution.
> 3. In the body of template definitions, names no longer bind to
> declarations inside class template specializations. Rather, to declarations
> in the concept model archetypes, which are basically placeholders for when
            ^^^^^^^^^^^^^^^^^^^^^^^^
> we have concrete maps at the point of template use.
>
> 4. At the point of template use, constraints satisfaction
> explicitly performs concept model lookup and needs to rebuild
                         ^^^^^^^^^^^^^^^^^^^^
> entity references that were bound to declarations in archetypes so
     ^^^^^^^^^^^^^^^^^ ^^^^^^^^^^
> that they now bind to declarations in the concrete concept models.
>
> I think the paper goes further on key distinctions, but the basic idea
> is that we have decoupled the notion of concept model archetypes with
                                          ^^^^^^^^^^^^^^^^^^^^^^^^
> their implementation, which provides more genericity and allows us to
> really understand how the design decisions we make affect the
> different components of concepts: concept definitions, concept models
> (templates, archetypes, or concrete), constrained template definitions
> -- w/ constraints specification, and constrained templates uses --
> with constraints satisfaction, followed by a rebuilding of the
> references at instantiation time.
>
> Given this distinction, I hope it is now clear how the implementation
> that Doug suggests is simply a special case of a larger
> infrastructure.

Unfortunately, nothing is now clear, because you haven't clearified your
terms and distinctions.

> Whether it is the right approach or not, I think some parameters still
> need to be investigated further. If I am not mistaking, I read a paper
> at some point that addressed how c++ concepts where not completely
> expressible in terms class templates and their specializations. But I
> have to double-check on that.

They are indeed not. Early on, they were nearly so IIUC, but
rvalue-erasing and the creation of unnecessary copies put an end to
that. Of course there are always also new lookup rules involved in a
concepts implementation, but I don't think you are referring to that
dimension of things.

>> Unfortunately, although you're wielding it as though it
>> were a term of art, you haven't defined it, so it's hard to be sure...
>>
>
> I'm sorry for not clarifying myself well earlier. It is definitely in the
> ConceptClang paper though.

Umm, which one?
There are three listed at
http://www.generic-programming.org/software/ConceptClang/.
As I mentioned, the first one doesn't define many of the terms you use.

> Thanks for pointing out my differing terminology. I am updating it as I get
> more accustomed with C++ terminology.
>>
>> >> concept model archetypes (CMA) are the most essential component of
>> >> any implementation of concepts -- N2914 or N3351 or else -- in that
>> >> they are the essential glue to all components:
>> >>
>> >> 1. They link the requirements specified in concept definitions with
>> >> their uses in the definitions of generic components.
>> >> 2. They tell constraints satisfaction which concept model to look for
>> >> or generate. Note that:
>> >> 1. concept model checking reuses constraints satisfaction, and
>> >> 2. entity reference rebuilding, at instantiation time, is not
>> >> always necessary---since the need varies based on the design and
>> >> implementation model.
>> >> 3. When entity reference rebuilding is supported -- as in
>> >> ConceptClang's current implementation of N2914 and some flavors of
>> the
>> >> N3351 implementation, then concrete concept models become
>> particularly
>> >> essential as well.
>>
>> Other terms of art used without definition here: "constraints
>> satisfaction" (one can guess, but you seem to be referring to something
>> very specific, so one could be wrong) and "entity reference rebuilding"
>
> I don't believe "constraints satisfaction" is a term of my making. I
> borrowed it from previous litterature on concepts.
> I did make up "rebuilding", but not "entity reference" (I don't think).
> Either way, I am not sure what the right C++-compatible terminology would
> be. Any idea?
> I tried to explain the concept above as the rebinding of names from concept
> model archetypes to concrete concept models.
> Please let me know if I can be any clearer.

You can be clearer. I don't yet know what you mean by "concept model
archetypes," so it's hard to make head or tail of any of this. From the
context, I am beginning to suspect that my "archetype" == your "concept
model archetype," but I am not yet sure.

>> >> In some sense -- and I'm still working on this idea, an
>> >> implementation of CMAs can indicate the extend to which explicit
>> >> concept models are needed to bind to customized implementations.
>>
>> "explicit concept models?" -- i.e. explicit modeling mechanism for
>> concepts, as in "explicit concepts".

This is unclear. I don't think this term can mean a mechanism at all.
By "explicit concept model" I think you mean "one or more types that
have been explicitly declared by the user to model a concept." However,
you're using it in the sentence as though you mean the declaration
itself.

>> "bind to?" -- e.g. a function call binds arguments to a function
>> declaration.

"bind to" will probably make plenty of sense once you clarify the other
terms.

>> "customized implementations?" -- i.e. implementations in concrete concept
>> models.

Sounds like you just mean

   the extent to which explicit model declarations are needed

and you don't need

   "to bind to customized implementations"

which probably really means "to bind concepts to concrete models"
because, after all, an explicit model declaration binds a given concrete
concept model to the concept; I mean, that's *all* it does!

>> >> That being said, independently of the concepts design, any parsing
>> >> and checking of concept definitions should make the implementation
>> >> of CMAs as easy as possible.
>> >>
>> >> There are other issues that I am currently finding with the
>> >> semantics of checking entity references in restricted scope, in
>> >> N2914, but that is something that I should perhaps leave for
>> >> another discussion. In fact, I would like to run this by people
>> >> who would be interest at the next committee meeting (next week).
>> >> The bottom line is that, if I am right, then implementing the
>> >> checking properly is a complex task -- either due to the
>> >> implementation structure of Clang or just the nature of C++
>> >> grammar. (I'm not sure which one yet.)
>> >>
>> >> That complexity is, unfortunately, one of the main reasons for the
>> >> hold up on deploying an updated version of ConceptClang.
>> >>
>> >>
>> > Just to clarify my point above, I find the idea of automatically
>> > generating archetype classes intriguing in the sense that they
>> > offer an alternative implementation for CMAs, in contrast to what
>> > ConceptClang is currently doing.
>>
>> I don't know what ConceptClang is currently doing, but if (as you seem
>> to imply) you're not doing checking by generating concrete archetypes
>> and instantiating constrained templates with them, then
>>
>> a. You are setting yourself up for a great deal more work than
>> necessary, because you have to implement a complex algorithm that
>> closely parallels what C++ already does.
>
> Actually, I'd like to argue that the algorithm actually helps find
> some incompleteness with previous work. That's the point of
> ConceptClang to begin with.

Seriously, to find problems with previous work?

>> b. The semantics of your checking are much more likely to "not make
>> sense" to C++ users today, because the rules will be subtly
>> different.
>
> The semantics are just the same, but more implemented more abstractly,
> i.e. I think of components of concepts separately from previously
> proposed implementations.

As noted above, please drop that line of assumption about others'
thinking.

>> > However, I still wonder if the class template / class template
>> > specialization approach to representing concept definitions /
>> > concept maps is as powerful as the approach of treating concepts as
>> > first class entities of the language.
>>
>> They're not mutually exclusive. The "first class entities in the
>> language" might intentionally be defined (as they were in N2914) to have
>> the same semantics as existing language features, and thus be
>> implementable in terms of the same code.
>
> That's what I'm not too sure about, just yet... And like I said
> earlier, I could be missing something.

Could be.

>> > On the other hand, the class template approach removes the need for to
>> > rebuild entity references at instantiation time.
>>
>> There's that term of art again.
>>
>
> Sorry. :)
>
>>
>> > An alternative that I see that still uses archetypes is for archetype
>> > classes to be generated as in the Caramel system.
>> > I particularly find this useful in checking constrained template
>> > definitions because they allow to do that non-intrusively (or at least
>> less
>> > intrusively than the current implementation). That is, instead of
>> checking
>> > every dependent entity reference in the body of a template (and all the
>> > complexity that comes with it as I'm finding), appropriate archetype
>> > classes can simply be instantiated and used on the template upon parsing
>> > the template.
>>
>> I'm truly surprised to hear (if I'm understanding correctly) that you
>> didn't go down that road in the first place. I think it was
>> well-understood to be the obvious approach.
>
> This is a different alternative which is not like Doug's suggestion
> above, but rather like BCCL's archetypes.

I seriously doubt Doug means something different from BCCL's archetypes
in any important respect. Of course, I could be wrong, but when Doug
and I talk and one of us says "archetype," there's never any confusion
about what's meant.

>> > However, I am not exactly sure how this approach couples up with the
>> > checking of the remaining components (concept defns, models, template
>> > uses, etc...). I suspect that either it will only be useful if concept
>> > maps are not supported; and constraints are only intended to serve as
>> > predicates and not provide a scope for name resolution
>> > (hence, no need to rebuild entity references). Otherwise, it will be
>> > unnecessary with any effort to complement its use.
>>
>> You mostly lost me with the last paragraph.
>
> Let's take the example of constrained function templates. Simply
> instantiating archetypes, constructing a new call expression with
> them, and checking that call only checks for concept coverage. (I'm
> borrowing the terminology from the BCCL paper).

Yes. What else do you want to check?

> When are the calls in the template definitions bound to the concept
> model archetypes?

Example please. I can guess at what you mean about "binding a call to a
concept model archetype", but it would be better if you'd spell it out.

-- 
Dave Abrahams
BoostPro Computing                  Software Development        Training
http://www.boostpro.com             Clang/LLVM/EDG Compilers  C++  Boost

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk