[Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

classic Classic list List threaded Threaded
59 messages Options
123
Reply | Threaded
Open this post in threaded view
|

[Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

Mostafa-6
On Thu, 31 Jul 2014 10:54:59 -0700, Robert Ramey <[hidden email]> wrote:

> Eric Niebler-4 wrote
>> On 07/29/2014 05:14 PM, Niall Douglas wrote:
>>> I'm all for Concepts as in compiler enforced ones, and I'll add them
>>> to AFIO when and only when C++ gets them. But for documentation they
>>> don't help.
>>
>> Wow, I couldn't disagree more. I can't imagine how the standard
>> algorithms would be specified without the use of concepts like
>> "RandomAccessIterator", for instance. Clustering requirements into
>> meaningful abstractions and assigning them names makes it possible to
>> document library interfaces without an explosion of verbosity and
>> repetition.
>
> +10
>
> Usage of concepts is greatly:
>
> a) misunderstood
> b) misunderestimated as to their value in design AND documentation
> d) The word "concepts" is a big contributor to the problem - substitute
> "type requirements" or "type constraints" for concepts.

-1 to the above term substitutions for concepts. Type requirements/type
constrains are not concepts. The reason concepts are misunderstood is
because they have not been well defined. FWIW, here's my take on how they
should be defined:

Concepts are sets of types whose membership are compile-time determinable.
Precisely, a concept is any set expressible in the following form:

         { T | T is a type and p(T ...) }

where p is a (n+1)-ary compile time computable boolean function (a function
in the mathematical sense, not an actual C++ function). p is said
to be (or to express) the type requirements or type constrains for its
associated concept. (Note: just as a set membership predicate is not its
set,
a type requirement is not its concept. For example,
the predicate "there exists a,b and a,b are integers and b != 0 and c =
a/b" does not denote the set of rational numbers, the symbol Q does.)

A type T is said to model a concept C if T is a member of C. In such a
case we also say that "T is a C".
A concept B is said to be a refinement of a concept A if B is a subset of
A.

Why use concepts? Because they are helpful in documenting generic code,
especially template type parameter requirements.

Examples:

1) DefaultConstructible :=
          { T | T has the method "T()" defined and accessible. }

       // Requirements:
       //   T is DefaultConstructible.
       template <typename T>
       struct FooBar { ... };

       std::tuple<int> is DefaultConstructible, therefore
       FooBar< std::tuple<int> > is well formed.

Mostafa


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

Roland Bock-2
On 2014-08-04 13:32, Mostafa wrote:

> On Thu, 31 Jul 2014 10:54:59 -0700, Robert Ramey <[hidden email]> wrote:
>
>> Eric Niebler-4 wrote
>>> On 07/29/2014 05:14 PM, Niall Douglas wrote:
>>>> I'm all for Concepts as in compiler enforced ones, and I'll add them
>>>> to AFIO when and only when C++ gets them. But for documentation they
>>>> don't help.
>>>
>>> Wow, I couldn't disagree more. I can't imagine how the standard
>>> algorithms would be specified without the use of concepts like
>>> "RandomAccessIterator", for instance. Clustering requirements into
>>> meaningful abstractions and assigning them names makes it possible to
>>> document library interfaces without an explosion of verbosity and
>>> repetition.
>>
>> +10
>>
>> Usage of concepts is greatly:
>>
>> a) misunderstood
>> b) misunderestimated as to their value in design AND documentation
>> d) The word "concepts" is a big contributor to the problem - substitute
>> "type requirements" or "type constraints" for concepts.
>
> -1 to the above term substitutions for concepts. Type requirements/type
> constrains are not concepts. The reason concepts are misunderstood is
> because they have not been well defined. FWIW, here's my take on how they
> should be defined:
>
> Concepts are sets of types whose membership are compile-time
> determinable.
I think you are mistaken. A concept is a set of requirements, not a set
of types that fullfill these requirements.

This also reflects the normal meaning of the word concept, see for instance

http://www.oxforddictionaries.com/definition/english/concept




_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

Mostafa-6
On Mon, 04 Aug 2014 08:39:36 -0700, Roland Bock <[hidden email]> wrote:

> On 2014-08-04 13:32, Mostafa wrote:
>> On Thu, 31 Jul 2014 10:54:59 -0700, Robert Ramey <[hidden email]> wrote:
>>
>>> Eric Niebler-4 wrote
>>>> On 07/29/2014 05:14 PM, Niall Douglas wrote:
>>>>> I'm all for Concepts as in compiler enforced ones, and I'll add them
>>>>> to AFIO when and only when C++ gets them. But for documentation they
>>>>> don't help.
>>>>
>>>> Wow, I couldn't disagree more. I can't imagine how the standard
>>>> algorithms would be specified without the use of concepts like
>>>> "RandomAccessIterator", for instance. Clustering requirements into
>>>> meaningful abstractions and assigning them names makes it possible to
>>>> document library interfaces without an explosion of verbosity and
>>>> repetition.
>>>
>>> +10
>>>
>>> Usage of concepts is greatly:
>>>
>>> a) misunderstood
>>> b) misunderestimated as to their value in design AND documentation
>>> d) The word "concepts" is a big contributor to the problem - substitute
>>> "type requirements" or "type constraints" for concepts.
>>
>> -1 to the above term substitutions for concepts. Type requirements/type
>> constrains are not concepts. The reason concepts are misunderstood is
>> because they have not been well defined. FWIW, here's my take on how  
>> they
>> should be defined:
>>
>> Concepts are sets of types whose membership are compile-time
>> determinable.
> I think you are mistaken. A concept is a set of requirements, not a set
> of types that fullfill these requirements.

I understand that some may have a problem with such a definition because  
it does not have an immediate programmatic counterpart. That is we can  
only implement concept checks, hence Boost.ConceptChecks, and not concepts  
themselves in C++. But I view concepts not as a programmatic tool but as a  
communication tool for conveying programmer intent.

The main reason I hold this view is because it's easier to think in terms  
of sets of types than in terms of sets of type requirements. For example,

ShapeConcept := { T | T has the method "void display() const" defined }
TriangleConcept :=
   { T | T models Shape and T has the following methods defined:
         "Edge edgeOne()", "Edge edgeTwo()", "Edge edgeThree()" }

// T models ShapeConcept
template <typename T>
void Display(T & t);

It's obvious that if U models a TriangleConcept then Display(u) for an  
object u of type U is well-formed. (That's because TriangleConcept is a  
subset of ShapeConcept and U is a member of the latter.) Note that this is  
similar to the relationship between types and objects. Conceptually types  
are sets of objects and a subtype contains a subset of the objects of its  
supertype.

Now, let's try reworking the above example in terms of sets of type  
requirements instead. The TriangleConcept then is a refinement of  
ShapeConcept if the TriangleConcept is a superset of the ShapeConcept. But  
that's counter-intuitive because the number of types that satisfy the  
TriangleConcept is less than the number of types that satisfy ShapeConcept.

Additionally, if concepts were sets of type requirements than the phrase  
"T is DefaultConstructible" reads awkwardly, it almost sounds as if T were  
a type requirement itself, when we actually mean to say that T satisfies  
the requirements of default constructibility. And the language "x  
satisfies abc" usually connotates set membership.

> This also reflects the normal meaning of the word concept, see for  
> instance
>
> http://www.oxforddictionaries.com/definition/english/concept

??? From the above link:
"1.4 Philosophy An idea or mental image which corresponds to some distinct  
entity or class of entities, or to its essential features, or determines  
the application of a term (especially a predicate), and thus plays a part  
in the use of reason or language."

Mostafa


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

Michael Shepanski-2
In reply to this post by Roland Bock-2
On 5/08/2014 1:39 AM, Roland Bock wrote:
> On 2014-08-04 13:32, Mostafa wrote:
>> Concepts are sets of types
> I think you are mistaken. A concept is a set of requirements,

I am under a New Year's resolution not to start philosophical arguments,
but this one has already begun, so ...

It may be helpful to consider this principle about sets: set A and set B
are the same set whenever all the elements of A are elements of B and
all the elements of B are elements of A. Or in symbols:

     (A = B) iff (forall x)(x in A iff x in B)

(Standard example: The set of equilateral triangles and the set of
equiangular triangles are the same set, because all equilateral
triangles are equiangular and vice versa.)

So Mostafa's statement (above) commits him to this:
     Concept A and concept B are the same concept whenever all the types
in A are in B, and all the types in B are in A.

And Roland's statement commits him to this:
     Concept A and concept B are the same concept whenever all the
requirements in A are in B, and all the requirements in B are in A.

I think this means that Roland will be able to discriminate concepts
more finely than Mostafa can. Now, whether that is an advantage or a
disadvantage, I leave for you gentlemen to discuss.  :)

--- Michael


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

Roland Bock-2
In reply to this post by Mostafa-6
On 2014-08-05 02:08, Mostafa wrote:

> On Mon, 04 Aug 2014 08:39:36 -0700, Roland Bock <[hidden email]> wrote:
>
>> On 2014-08-04 13:32, Mostafa wrote:
>>> On Thu, 31 Jul 2014 10:54:59 -0700, Robert Ramey <[hidden email]>
>>> wrote:
>>>
>>>> Eric Niebler-4 wrote
>>>>> On 07/29/2014 05:14 PM, Niall Douglas wrote:
>>>>>> I'm all for Concepts as in compiler enforced ones, and I'll add them
>>>>>> to AFIO when and only when C++ gets them. But for documentation they
>>>>>> don't help.
>>>>>
>>>>> Wow, I couldn't disagree more. I can't imagine how the standard
>>>>> algorithms would be specified without the use of concepts like
>>>>> "RandomAccessIterator", for instance. Clustering requirements into
>>>>> meaningful abstractions and assigning them names makes it possible to
>>>>> document library interfaces without an explosion of verbosity and
>>>>> repetition.
>>>>
>>>> +10
>>>>
>>>> Usage of concepts is greatly:
>>>>
>>>> a) misunderstood
>>>> b) misunderestimated as to their value in design AND documentation
>>>> d) The word "concepts" is a big contributor to the problem -
>>>> substitute
>>>> "type requirements" or "type constraints" for concepts.
>>>
>>> -1 to the above term substitutions for concepts. Type requirements/type
>>> constrains are not concepts. The reason concepts are misunderstood is
>>> because they have not been well defined. FWIW, here's my take on how
>>> they
>>> should be defined:
>>>
>>> Concepts are sets of types whose membership are compile-time
>>> determinable.
>> I think you are mistaken. A concept is a set of requirements, not a set
>> of types that fullfill these requirements.
>
> I understand that some may have a problem with such a definition
> because it does not have an immediate programmatic counterpart. That
> is we can only implement concept checks, hence Boost.ConceptChecks,
> and not concepts themselves in C++. But I view concepts not as a
> programmatic tool but as a communication tool for conveying programmer
> intent.
>
> The main reason I hold this view is because it's easier to think in
> terms of sets of types than in terms of sets of type requirements.
That's not an argument IMHO. Even if a concept C is a set of
requirements, you can think of the set of types that meet these
requirements, lets call them T(C).

Then for two concepts A and B, we call A a refinement of B if T(A) is a
subset of T(B).

So you can still express everything you want to express and the concept
is what we write in code: A set of requirements.

<snip>
> Now, let's try reworking the above example in terms of sets of type
> requirements instead. The TriangleConcept then is a refinement of
> ShapeConcept if the TriangleConcept is a superset of the ShapeConcept.
> But that's counter-intuitive because the number of types that satisfy
> the TriangleConcept is less than the number of types that satisfy
> ShapeConcept.

See above.

And sure, if concept A is a superset of concept B, then T(A) is a subset
of T(B). There is nothing counter-intuitive about that afaict.

>
> Additionally, if concepts were sets of type requirements than the
> phrase "T is DefaultConstructible" reads awkwardly, it almost sounds
> as if T were a type requirement itself, when we actually mean to say
> that T satisfies the requirements of default constructibility. And the
> language "x satisfies abc" usually connotates set membership.
Sure, that type is a member of T(DefaultConstructible).

I don't get your argument at all. If you say "this car is green", you
say both "this car is a member of the set of green things" and "this car
meets the requirements of being green". It does neither imply that
"green is the set of green things" (endless recursion) nor does it say
that "green is a set of being-green-requirements" (also endless
recursion). Still, everyone knows what is meant without feeling awkward
about it.

So why not use the term concept in a way that matches what we actually
do in code?


>> This also reflects the normal meaning of the word concept, see for
>> instance
>>
>> http://www.oxforddictionaries.com/definition/english/concept
>
> ??? From the above link:
> "1.4 Philosophy An idea or mental image which corresponds to some
> distinct entity or class of entities, or to its essential features, or
> determines the application of a term (especially a predicate), and
> thus plays a part in the use of reason or language."
In short (and probably not precise enough since I am not a philosopher),
a concept is not a thing (aka type in template programming) or set of
things, it is an idea about it or its essential features, for instance a
predicate.


Regards,

Roland





_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

Krzysztof Czainski
In reply to this post by Michael Shepanski-2
2014-08-05 6:33 GMT+02:00 Michael Shepanski <[hidden email]>:

> On 5/08/2014 1:39 AM, Roland Bock wrote:
>
>> On 2014-08-04 13:32, Mostafa wrote:
>>
>>> Concepts are sets of types
>>>
>> I think you are mistaken. A concept is a set of requirements,
>>
>
> I am under a New Year's resolution not to start philosophical arguments,
> but this one has already begun, so ...
>

Please don't forget, that not all requirements can be checked at compile
time. For example: TotallyOrdered. Just by checking, that an expression
(a<b) is valid and yields something boolable, you can't distinguish between
TotallyOrdered, PartiallyOrdered, or maybe neiter.

So, while I think it doesn't matter, whether we view concepts as sets of
types or requirements, I'd like to support this sentence of Mostafa:
"I view concepts not as a programmatic tool but as a communication tool for
conveying programmer intent."

Cheers,
Kris

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

Roland Bock-2
On 2014-08-05 10:30, Krzysztof Czainski wrote:

> 2014-08-05 6:33 GMT+02:00 Michael Shepanski <[hidden email]>:
>
>> On 5/08/2014 1:39 AM, Roland Bock wrote:
>>
>>> On 2014-08-04 13:32, Mostafa wrote:
>>>
>>>> Concepts are sets of types
>>>>
>>> I think you are mistaken. A concept is a set of requirements,
>>>
>> I am under a New Year's resolution not to start philosophical arguments,
>> but this one has already begun, so ...
>>
> Please don't forget, that not all requirements can be checked at compile
> time. For example: TotallyOrdered. Just by checking, that an expression
> (a<b) is valid and yields something boolable, you can't distinguish between
> TotallyOrdered, PartiallyOrdered, or maybe neiter.
>
> So, while I think it doesn't matter, whether we view concepts as sets of
> types or requirements
Well, if you consider TotallyOrdered a concept, then by this reasoning,
it cannot be a set of types. But it could be a set of requirements :-)

I admit that in this context I haven't thought of concepts that cannot
be verified at compile time. Thanks for the hint!

> , I'd like to support this sentence of Mostafa:
> "I view concepts not as a programmatic tool but as a communication tool for
> conveying programmer intent."
>

I think it is both, a programmatic tool and a communication tool.


Cheers,

Roland


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

Mostafa-6
In reply to this post by Roland Bock-2
On Tue, 05 Aug 2014 00:07:42 -0700, Roland Bock <[hidden email]> wrote:

> On 2014-08-05 02:08, Mostafa wrote:
>> On Mon, 04 Aug 2014 08:39:36 -0700, Roland Bock <[hidden email]>  
>> wrote:

[snip]

>> Additionally, if concepts were sets of type requirements than the
>> phrase "T is DefaultConstructible" reads awkwardly, it almost sounds
>> as if T were a type requirement itself, when we actually mean to say
>> that T satisfies the requirements of default constructibility. And the
>> language "x satisfies abc" usually connotates set membership.
> Sure, that type is a member of T(DefaultConstructible).
>
> I don't get your argument at all. If you say "this car is green", you
> say both "this car is a member of the set of green things" and "this car
> meets the requirements of being green". It does neither imply that
> "green is the set of green things" (endless recursion) nor does it say
> that "green is a set of being-green-requirements" (also endless
> recursion). Still, everyone knows what is meant without feeling awkward
> about it.

Unfortunately English can be ambiguous, so let's be more precise. When one  
says "this car is green" one actually means "this car is a green thing"  
(green is being used as a noun, not as an adjective like "green balloon").  
That means "this car is a member of GreenThings". If GreenThings were a  
set of requirements then that means "this car" is also a requirement,  
which obviously it's not. Therefore GreenThings, the concept in this  
discussion, is a set of objects that satisfy the requirement of being  
green.

> So why not use the term concept in a way that matches what we actually
> do in code?

Because that's a narrow and implementation-dependent point of view. When  
we introduce people to classes, hopefully we don't first define them to be  
some set of rules for determining the layout of a region of memory, rather  
we define them to be nouns; that is it's a communication tool for  
expressing programmer intent. By thinking about classes abstractly, we are  
able to more easily reason with them, like how UML robustness diagrams can  
be used to discover classes and the relationships between them.

FWIW, it might interest you to read this blog on concepts by Bartosz  
Milewski: http://bartoszmilewski.com/2010/06/24/c-concepts-a-postmortem/ 
(Disclaimer: he holds my position and terms your definition "constrained  
templates", but his posting is informative in comparing our approaches.)

Mostafa


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

Mostafa-6
In reply to this post by Roland Bock-2
On Tue, 05 Aug 2014 01:59:34 -0700, Roland Bock <[hidden email]> wrote:

> On 2014-08-05 10:30, Krzysztof Czainski wrote:
>> 2014-08-05 6:33 GMT+02:00 Michael Shepanski <[hidden email]>:
>>
>>> On 5/08/2014 1:39 AM, Roland Bock wrote:
>>>
>>>> On 2014-08-04 13:32, Mostafa wrote:
>>>>
>>>>> Concepts are sets of types
>>>>>
>>>> I think you are mistaken. A concept is a set of requirements,
>>>>
>>> I am under a New Year's resolution not to start philosophical  
>>> arguments,
>>> but this one has already begun, so ...
>>>
>> Please don't forget, that not all requirements can be checked at compile
>> time. For example: TotallyOrdered. Just by checking, that an expression
>> (a<b) is valid and yields something boolable, you can't distinguish  
>> between
>> TotallyOrdered, PartiallyOrdered, or maybe neiter.
>>
>> So, while I think it doesn't matter, whether we view concepts as sets of
>> types or requirements
> Well, if you consider TotallyOrdered a concept, then by this reasoning,
> it cannot be a set of types. But it could be a set of requirements :-)

Yes it can. TotallyOrdered := { T | if a,b,c are objects of T then ... }


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

Roland Bock-2
On 2014-08-05 12:14, Mostafa wrote:

> On Tue, 05 Aug 2014 01:59:34 -0700, Roland Bock <[hidden email]> wrote:
>
>> On 2014-08-05 10:30, Krzysztof Czainski wrote:
>>> 2014-08-05 6:33 GMT+02:00 Michael Shepanski <[hidden email]>:
>>>
>>>> On 5/08/2014 1:39 AM, Roland Bock wrote:
>>>>
>>>>> On 2014-08-04 13:32, Mostafa wrote:
>>>>>
>>>>>> Concepts are sets of types
>>>>>>
>>>>> I think you are mistaken. A concept is a set of requirements,
>>>>>
>>>> I am under a New Year's resolution not to start philosophical
>>>> arguments,
>>>> but this one has already begun, so ...
>>>>
>>> Please don't forget, that not all requirements can be checked at
>>> compile
>>> time. For example: TotallyOrdered. Just by checking, that an expression
>>> (a<b) is valid and yields something boolable, you can't distinguish
>>> between
>>> TotallyOrdered, PartiallyOrdered, or maybe neiter.
>>>
>>> So, while I think it doesn't matter, whether we view concepts as
>>> sets of
>>> types or requirements
>> Well, if you consider TotallyOrdered a concept, then by this reasoning,
>> it cannot be a set of types. But it could be a set of requirements :-)
>
> Yes it can. TotallyOrdered := { T | if a,b,c are objects of T then ... }

As Kris pointed out: Whether an object is TotallyOrdered or not cannot
be checked at compile time because it does not depend on the type alone,
it also depends on runtime information. Hence, not a set of types.

Best,

Roland


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

Mostafa-6
On Tue, 05 Aug 2014 04:27:31 -0700, Roland Bock <[hidden email]> wrote:

> On 2014-08-05 12:14, Mostafa wrote:
>> On Tue, 05 Aug 2014 01:59:34 -0700, Roland Bock <[hidden email]>  
>> wrote:
>>
>>> On 2014-08-05 10:30, Krzysztof Czainski wrote:
>>>> 2014-08-05 6:33 GMT+02:00 Michael Shepanski <[hidden email]>:
>>>>
>>>>> On 5/08/2014 1:39 AM, Roland Bock wrote:
>>>>>
>>>>>> On 2014-08-04 13:32, Mostafa wrote:
>>>>>>
>>>>>>> Concepts are sets of types
>>>>>>>
>>>>>> I think you are mistaken. A concept is a set of requirements,
>>>>>>
>>>>> I am under a New Year's resolution not to start philosophical
>>>>> arguments,
>>>>> but this one has already begun, so ...
>>>>>
>>>> Please don't forget, that not all requirements can be checked at
>>>> compile
>>>> time. For example: TotallyOrdered. Just by checking, that an  
>>>> expression
>>>> (a<b) is valid and yields something boolable, you can't distinguish
>>>> between
>>>> TotallyOrdered, PartiallyOrdered, or maybe neiter.
>>>>
>>>> So, while I think it doesn't matter, whether we view concepts as
>>>> sets of
>>>> types or requirements
>>> Well, if you consider TotallyOrdered a concept, then by this reasoning,
>>> it cannot be a set of types. But it could be a set of requirements :-)
>>
>> Yes it can. TotallyOrdered := { T | if a,b,c are objects of T then ... }
>
> As Kris pointed out: Whether an object is TotallyOrdered or not cannot
> be checked at compile time because it does not depend on the type alone,
> it also depends on runtime information. Hence, not a set of types.

That's irrelevant. My original definition of concepts can easily be  
expanded to remove the compile time determinability restriction. Then,  
TotallyOrdered as a set of types does conceptually exist, and can be  
effectively used as a documentation tool. The concept TotallyOrdered may  
not depend on the *static* information of the type, but it sure does  
depend on objects of the type, and, ergo, it depends on the type.


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

Roland Bock-2
In reply to this post by Mostafa-6
On 2014-08-05 12:13, Mostafa wrote:

> On Tue, 05 Aug 2014 00:07:42 -0700, Roland Bock <[hidden email]> wrote:
>
>> On 2014-08-05 02:08, Mostafa wrote:
>>> On Mon, 04 Aug 2014 08:39:36 -0700, Roland Bock <[hidden email]>
>>> wrote:
>
> [snip]
>
>>> Additionally, if concepts were sets of type requirements than the
>>> phrase "T is DefaultConstructible" reads awkwardly, it almost sounds
>>> as if T were a type requirement itself, when we actually mean to say
>>> that T satisfies the requirements of default constructibility. And the
>>> language "x satisfies abc" usually connotates set membership.
>> Sure, that type is a member of T(DefaultConstructible).
>>
>> I don't get your argument at all. If you say "this car is green", you
>> say both "this car is a member of the set of green things" and "this car
>> meets the requirements of being green". It does neither imply that
>> "green is the set of green things" (endless recursion) nor does it say
>> that "green is a set of being-green-requirements" (also endless
>> recursion). Still, everyone knows what is meant without feeling awkward
>> about it.
>
> Unfortunately English can be ambiguous, so let's be more precise. When
> one says "this car is green" one actually means "this car is a green
> thing" (green is being used as a noun, not as an adjective like "green
> balloon"). That means "this car is a member of GreenThings". If
> GreenThings were a set of requirements then that means "this car" is
> also a requirement, which obviously it's not.

You're only ever seeing your view :-)
Another option is: When one says "this car is green", one actually means
"this car emits light with a wavelength around 510nm". So the concept
"green" is not a set of green things, it is a set of requirements (in
this case with one element, namely "emits light with a wavelength around
510nm").

Since both views are equally possible, I'd stick with the one closer to
practice.

> Therefore GreenThings, the concept in this discussion, is a set of
> objects that satisfy the requirement of being green.
>
>> So why not use the term concept in a way that matches what we actually
>> do in code?
>
> Because that's a narrow and implementation-dependent point of view.

I did not write "concepts are pieces of code"...

> When we introduce people to classes, hopefully we don't first define
> them to be some set of rules for determining the layout of a region of
> memory, rather we define them to be nouns; that is it's a
> communication tool for expressing programmer intent. By thinking about
> classes abstractly, we are able to more easily reason with them, like
> how UML robustness diagrams can be used to discover classes and the
> relationships between them.
>
> FWIW, it might interest you to read this blog on concepts by Bartosz
> Milewski:
> http://bartoszmilewski.com/2010/06/24/c-concepts-a-postmortem/
> (Disclaimer: he holds my position and terms your definition
> "constrained templates", but his posting is informative in comparing
> our approaches.)
I read that one before, but thanks for the reminder :-)

Afaict, your view is in line with what he calls concept maps.


Anyway, this has gone far too long already, I am out of here.


Best,

Roland

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

Roland Bock-2
In reply to this post by Mostafa-6
On 2014-08-05 13:48, Mostafa wrote:

> On Tue, 05 Aug 2014 04:27:31 -0700, Roland Bock <[hidden email]> wrote:
>
>> On 2014-08-05 12:14, Mostafa wrote:
>>> On Tue, 05 Aug 2014 01:59:34 -0700, Roland Bock <[hidden email]>
>>> wrote:
>>>
>>>> On 2014-08-05 10:30, Krzysztof Czainski wrote:
>>>>> 2014-08-05 6:33 GMT+02:00 Michael Shepanski <[hidden email]>:
>>>>>
>>>>>> On 5/08/2014 1:39 AM, Roland Bock wrote:
>>>>>>
>>>>>>> On 2014-08-04 13:32, Mostafa wrote:
>>>>>>>
>>>>>>>> Concepts are sets of types
>>>>>>>>
>>>>>>> I think you are mistaken. A concept is a set of requirements,
>>>>>>>
>>>>>> I am under a New Year's resolution not to start philosophical
>>>>>> arguments,
>>>>>> but this one has already begun, so ...
>>>>>>
>>>>> Please don't forget, that not all requirements can be checked at
>>>>> compile
>>>>> time. For example: TotallyOrdered. Just by checking, that an
>>>>> expression
>>>>> (a<b) is valid and yields something boolable, you can't distinguish
>>>>> between
>>>>> TotallyOrdered, PartiallyOrdered, or maybe neiter.
>>>>>
>>>>> So, while I think it doesn't matter, whether we view concepts as
>>>>> sets of
>>>>> types or requirements
>>>> Well, if you consider TotallyOrdered a concept, then by this
>>>> reasoning,
>>>> it cannot be a set of types. But it could be a set of requirements :-)
>>>
>>> Yes it can. TotallyOrdered := { T | if a,b,c are objects of T then
>>> ... }
>>
>> As Kris pointed out: Whether an object is TotallyOrdered or not cannot
>> be checked at compile time because it does not depend on the type alone,
>> it also depends on runtime information. Hence, not a set of types.
>
> That's irrelevant. My original definition of concepts can easily be
> expanded to remove the compile time determinability restriction. Then,
> TotallyOrdered as a set of types does conceptually exist, and can be
> effectively used as a documentation tool. The concept TotallyOrdered
> may not depend on the *static* information of the type, but it sure
> does depend on objects of the type, and, ergo, it depends on the type.

It depends on properties of the type/object. That's what requirements
are for.

Anyway, sorry, I can't continue here. See you in another thread :-)





_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

Mostafa-6
In reply to this post by Roland Bock-2
On Tue, 05 Aug 2014 04:58:35 -0700, Roland Bock <[hidden email]> wrote:

> On 2014-08-05 12:13, Mostafa wrote:
>> On Tue, 05 Aug 2014 00:07:42 -0700, Roland Bock <[hidden email]>  
>> wrote:
>>
>>> On 2014-08-05 02:08, Mostafa wrote:
>>>> On Mon, 04 Aug 2014 08:39:36 -0700, Roland Bock <[hidden email]>
>>>> wrote:
>>
>> [snip]
>>
>>>> Additionally, if concepts were sets of type requirements than the
>>>> phrase "T is DefaultConstructible" reads awkwardly, it almost sounds
>>>> as if T were a type requirement itself, when we actually mean to say
>>>> that T satisfies the requirements of default constructibility. And the
>>>> language "x satisfies abc" usually connotates set membership.
>>> Sure, that type is a member of T(DefaultConstructible).
>>>
>>> I don't get your argument at all. If you say "this car is green", you
>>> say both "this car is a member of the set of green things" and "this  
>>> car
>>> meets the requirements of being green". It does neither imply that
>>> "green is the set of green things" (endless recursion) nor does it say
>>> that "green is a set of being-green-requirements" (also endless
>>> recursion). Still, everyone knows what is meant without feeling awkward
>>> about it.
>>
>> Unfortunately English can be ambiguous, so let's be more precise. When
>> one says "this car is green" one actually means "this car is a green
>> thing" (green is being used as a noun, not as an adjective like "green
>> balloon"). That means "this car is a member of GreenThings". If
>> GreenThings were a set of requirements then that means "this car" is
>> also a requirement, which obviously it's not.
>
> You're only ever seeing your view :-)
> Another option is: When one says "this car is green", one actually means
> "this car emits light with a wavelength around 510nm". So the concept
> "green" is not a set of green things, it is a set of requirements (in
> this case with one element, namely "emits light with a wavelength around
> 510nm").

No, I see your pov, I just claim you're view is logically flawed. I find  
this topic interesting, so if I may, I shall try to prove the flaw.

1) I claim that when one says "this car is green" one means "this car is a  
green thing", that's because by the rules of English syntax "green" in the  
original sentence has to be a noun, and because "green" is neither a  
person nor a place, it must be a thing.
2) So the question becomes what is a "green thing"? I claim that a "green  
thing" is any thing that satisfies being "green".
3) Let's assume for the sake of argument that "green" is a set of  
requirements. What is a requirement? It's a logical predicate, which is  
itself a boolean-valued function. So the "green" concept can be defined as  
follows:
     green := { p = { (x, p(x)) | p(x) = "does x emit light at ...} }

4) How does a thing satisfy being "green"? Since "green" is a set, the  
thing in question satisfies being "green" by being a member of that set.  
Since "green" as defined above has only one member, the thing in question  
satisfies being "green" by being the predicate p.
5) Hence, a green thing can only be the predicate p and, ergo, the car is  
the predicate p.
6) Reductio ad absurdum. Our intent was not to say that the car is the  
predicate p, rather that the car was a truth value for p, that is it  
satisfied the predicate/requirement p.

Hence my original assertion that the English construct "T is  
DefaultConstructible" reads awkwardly if DefaultConstructible is defined  
as a set of requirements.

(Note, I'll tried to do was symbolize in the language of logic and set  
theory the sentence "this car is green", or "T is DefaultConstructible".)

Mostafa


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

Robert Ramey
In reply to this post by Mostafa-6
I believe that "C++ Concept" was originally defined by the following web page or writing contemporary to it.
https://www.sgi.com/tech/stl/stl_introduction.html . A relevent quote is

"One very important question to ask about any template function, not just about STL algorithms, is what the set of types is that may correctly be substituted for the formal template parameters. Clearly, for example, int* or double* may be substituted for find's formal template parameter InputIterator. "

I don't think we want to alter this definition.  It's not formal (in the mathematical sense), but it's not ambiguous in our context.

My complaint isn't the definition - it's the phrase/word that was chosen to embody the idea.  The word chosen was "Concepts" which, in my view has led to all sorts of confusion to the casual reader - as most of are when we read documentation.  So my view is that we would be better served by using the term "type requirements" and/or "type constraints" rather than the word "Concepts".  That's all.  Of course people can and will continue to use the word "Concept" in the way they have been.  But that doesn't prohibit me from using the phrase "type constraint" from referring to the original idea.

It's somewhat off topic, but I'm going to take the opportunity to point out
https://www.sgi.com/tech/stl/doc_introduction.html .  I've come to believe that C++ libraries - in particular parameterized types, are best described by the documentation approach embodied in this link.  It is sufficiently formal where it has to be - but not so formal that one gets too bogged down.  I've made a big point of this inhttp://rrsd.com/blincubator.com/requirements_documentation/ .   My criticism of the HANA documentation is really that it fails to follow this format and content.  One of the objections raised to my criticism is that this form of documentation is in some sense not modern, specific to STL, or in some way not a good model for all C++ libraries.  It is this idea which I reject - totally.  Library authors would be best served by producing this form of documentation (concurrently with code) and not spend any time re-inventing their own documentation form.  Use this one and spend your time on coding!

Another interesting quote is:

"Concepts are not a part of the C++ language; there is no way to declare a concept in a program, or to declare that a particular type is a model of a concept. "

But today we have the boost concept library which while it doesn't make concepts part of the language itself provides a library which permits type requirements to be specified as part of the code and checked at compile time.

But with C++11 it's much more interesting.  I just came upon:

http://en.cppreference.com/w/cpp/concept

which echoes my views on the whole subject.  I don't have the C++11 spec - but I'm assuming/hoping that these type requirements are part of it.  This section only defines the named type requirements.

But wait!!!! there's more !!!

For A good number of the concepts - example DefaultConstructable http://en.cppreference.com/w/cpp/concept/DefaultConstructible
 -there exists a constexpr function such as
http://en.cppreference.com/w/cpp/types/is_default_constructible .  So in this case we DO have concepts built into the language (libraries).  Making a concept checking class would be as simple is:

template<class T>
struct DefaultConstructible {
    static_assert(std::is_default_constructible<T>::value, "Class is not default constructible");
};

Making a new concept class is pretty simple - leave as an excursive for the reader

But wait - there's even more!!!!

if there were a type trait defined for each concept - we would have type dispatching based on named type requirements - example

std::enable_if<std::is_default_constructible<T>>
void f(const T &t);

So f would be declared for a type T if and only if T were DefaultConstructible.

Basically, this implements most of the functionality in Boost Concept Checking and also Concepts Lite
today - and in a way which dovetails with what is (in my view) the preferred documentation approach.
It makes for a coherent and complete system from coding to documentation. Since most of this is "form filling" it's easy, mechanical and almost guaranteed to be correct.

This is the direction we (Boost and all of C++) need to go.  That is, we've known what to do for some time
we just have to start doing more.

Robert Ramey

Reply | Threaded
Open this post in threaded view
|

Re: [Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

Robert Ramey
In reply to this post by Krzysztof Czainski
<quote author="Krzysztof Czainski">

Please don't forget, that not all requirements can be checked at compile
time. For example: TotallyOrdered. Just by checking, that an expression
(a<b) is valid and yields something boolable, you can't distinguish between
TotallyOrdered, PartiallyOrdered, or maybe neuter.

</quote>

This is not true.

requirements are on types - not on instantiations of types.  If it can't be
checked at compile time - it's not a type requirement - it's something else
(perhaps a pre-condition).

TotallyOrdered doesn't refer to some container that may or may not be sorted.
It refers to the existent of a comparison function for the type which fulfills
a number of requirements.  To see this look at
https://www.sgi.com/tech/stl/StrictWeakOrdering.html

Here we can specify type requirements on functions which provide
for a strict weak ordering.  These can all be verified at compile time
based on the properties of the types.   Note that not all can be
verified by the compiler as some depend upon the semantic definition
of the function.  But one doesn't have to know that runtime data to
verify that the function meets the conditions for a strict weak ordering.
To summarize - all type requirements can be verified when the code
is written - but not all type requirements can be verified automatically
by the compiler.

So verification of by the compiler isn't perfectly exhaustive - but it's
a heck of a lot better than what we usually do - which is nothing.

Robert Ramey

Reply | Threaded
Open this post in threaded view
|

Re: [Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

Roland Bock-2
In reply to this post by Robert Ramey
Hi Robert,

Focussing on the term "concept" below. I'll comment on some of the other
parts later.

On 2014-08-05 17:29, Robert Ramey wrote:
> I believe that "C++ Concept" was originally defined by the following web page
> or writing contemporary to it.
> https://www.sgi.com/tech/stl/stl_introduction.html . A relevent quote is
>
> "One very important question to ask about any template function, not just
> about STL algorithms, is what the set of types is that may correctly be
> substituted for the formal template parameters. Clearly, for example, int*
> or double* may be substituted for find's formal template parameter
> InputIterator. "
Thanks for providing this link!

Citing from it: "we call such a set of type requirements a /concept.
[...] //We say that a type /conforms to a concept/, or that it /is a
model of a concept/, if it satisfies all of those requirements"/.


>
> I don't think we want to alter this definition.  It's not formal (in the
> mathematical sense), but it's not ambiguous in our context.
>
> My complaint isn't the definition - it's the phrase/word that was chosen to
> embody the idea.  The word chosen was "Concepts" which, in my view has led
> to all sorts of confusion to the casual reader - as most of are when we read
> documentation.  So my view is that we would be better served by using the
> term "type requirements" and/or "type constraints" rather than the word
> "Concepts".  That's all.  Of course people can and will continue to use the
> word "Concept" in the way they have been.  But that doesn't prohibit me from
> using the phrase "type constraint" from referring to the original idea.
Calling it "type requirements" would be fully backed by the SGI document.

[...]
> But with C++11 it's much more interesting.  I just came upon:
>
> http://en.cppreference.com/w/cpp/concept
First sentence: "A concept is a term that describes a *named set of
requirements* for a type"

>
> which echoes my views on the whole subject.  I don't have the C++11 spec -
> but I'm assuming/hoping that these type requirements are part of it.  This
> section only defines the named type requirements.
>
>

Cheers,

Roland

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

Krzysztof Czainski
In reply to this post by Robert Ramey
2014-08-05 17:42 GMT+02:00 Robert Ramey <[hidden email]>:

>
>
> Please don't forget, that not all requirements can be checked at compile
> time. For example: TotallyOrdered. Just by checking, that an expression
> (a<b) is valid and yields something boolable, you can't distinguish between
> TotallyOrdered, PartiallyOrdered, or maybe neuter.
>
> &lt;/quote>
>
> This is not true.
>
> requirements are on types - not on instantiations of types.  If it can't be
> checked at compile time - it's not a type requirement - it's something else
> (perhaps a pre-condition).
>
> TotallyOrdered doesn't refer to some container that may or may not be
> sorted.
> It refers to the existent of a comparison function for the type which
> fulfills
> a number of requirements.  To see this look at
> https://www.sgi.com/tech/stl/StrictWeakOrdering.html
>
> Here we can specify type requirements on functions which provide
> for a strict weak ordering.  These can all be verified at compile time
> based on the properties of the types.   Note that not all can be
> verified by the compiler as some depend upon the semantic definition
> of the function.  But one doesn't have to know that runtime data to
> verify that the function meets the conditions for a strict weak ordering.
> To summarize - all type requirements can be verified when the code
> is written - but not all type requirements can be verified automatically
> by the compiler.
>
> So verification of by the compiler isn't perfectly exhaustive - but it's
> a heck of a lot better than what we usually do - which is nothing.
>
> Robert Ramey
>

What about this example:

struct Circ
{
  unsigned x;
  explicit Circ(unsigned i=0) : x(i%256) {}
};
bool operator<(Circ a, Circ b) { return (b.x-a.x)%256 < (a.x-b.x)%256; }

Is std::set<Circ> valid?

I think generally not, but... suppose that we know, that we're only going
to use values 0-127. In this case std::set<Circ> is valid.

Regards,
Kris

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

Roland Bock-2
In reply to this post by Mostafa-6
On 2014-08-05 15:17, Mostafa wrote:

> On Tue, 05 Aug 2014 04:58:35 -0700, Roland Bock <[hidden email]> wrote:
>
>> On 2014-08-05 12:13, Mostafa wrote:
>>> On Tue, 05 Aug 2014 00:07:42 -0700, Roland Bock <[hidden email]>
>>> wrote:
>>>
>>>> On 2014-08-05 02:08, Mostafa wrote:
>>>>> On Mon, 04 Aug 2014 08:39:36 -0700, Roland Bock <[hidden email]>
>>>>> wrote:
>>>
>>> [snip]
>>>
>>>>> Additionally, if concepts were sets of type requirements than the
>>>>> phrase "T is DefaultConstructible" reads awkwardly, it almost sounds
>>>>> as if T were a type requirement itself, when we actually mean to say
>>>>> that T satisfies the requirements of default constructibility. And
>>>>> the
>>>>> language "x satisfies abc" usually connotates set membership.
>>>> Sure, that type is a member of T(DefaultConstructible).
>>>>
>>>> I don't get your argument at all. If you say "this car is green", you
>>>> say both "this car is a member of the set of green things" and
>>>> "this car
>>>> meets the requirements of being green". It does neither imply that
>>>> "green is the set of green things" (endless recursion) nor does it say
>>>> that "green is a set of being-green-requirements" (also endless
>>>> recursion). Still, everyone knows what is meant without feeling
>>>> awkward
>>>> about it.
>>>
>>> Unfortunately English can be ambiguous, so let's be more precise. When
>>> one says "this car is green" one actually means "this car is a green
>>> thing" (green is being used as a noun, not as an adjective like "green
>>> balloon"). That means "this car is a member of GreenThings". If
>>> GreenThings were a set of requirements then that means "this car" is
>>> also a requirement, which obviously it's not.
>>
>> You're only ever seeing your view :-)
>> Another option is: When one says "this car is green", one actually means
>> "this car emits light with a wavelength around 510nm". So the concept
>> "green" is not a set of green things, it is a set of requirements (in
>> this case with one element, namely "emits light with a wavelength around
>> 510nm").
>
> No, I see your pov, I just claim you're view is logically flawed. I
> find this topic interesting, so if I may, I shall try to prove the flaw.
I find it interesting, too, so OK, here goes again.
>
> 1) I claim that when one says "this car is green" one means "this car
> is a green thing", that's because by the rules of English syntax
> "green" in the original sentence has to be a noun

I am not a native english speaker, but I am pretty sure that "green" is
an adjective, which is not a noun. It is something that describes a noun.

> , and because "green" is neither a person nor a place, it must be a
> thing.
> 2) So the question becomes what is a "green thing"? I claim that a
> "green thing" is any thing that satisfies being "green".
> 3) Let's assume for the sake of argument that "green" is a set of
> requirements. What is a requirement? It's a logical predicate, which
> is itself a boolean-valued function. So the "green" concept can be
> defined as follows:
>     green := { p = { (x, p(x)) | p(x) = "does x emit light at ...} }
>
> 4) How does a thing satisfy being "green"? Since "green" is a set, the
> thing in question satisfies being "green" by being a member of that set.

Well, I say there's your flaw. You claim that "a is b" automatically
means "a is a member of b" if b is a set. I am pretty sure that's not
backed by anything, not even math.


I'll try to illustrate with a more common example.

"x is rational" means two things

a) "x is a member of the set of rational numbers, called R"
b) "x meets the requirement that there are natural numbers a and b!=0
such that x = a/b"

Note that rational != R. rational is a predicate expressing a) and b).


Translating it to "this car is green": green is neither the set of green
things nor the set of requirements. It is a predicate that can express
set membership and/or met requirements.


Now, when we say "T is DefaultConstructible" and DefaultConstructible is
a concept, neither your nor my view of concept fits directly since
neither one is a predicate. I therefore think that it is question of
convention whether this means

a) T is one of the types of DefaultConstructible
b) T meets the requirements of DefaultConstructible

And if it is just a question of convention, you know my preference. And
see Robert's post and my reply to it, too.

Regards,

Roland

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Concepts] Definition. Was [GSoC] [Boost.Hana] Formal review request

Robert Ramey
In reply to this post by Krzysztof Czainski
Krzysztof Czainski wrote
What about this example:

struct Circ
{
  unsigned x;
  explicit Circ(unsigned i=0) : x(i%256) {}
};
bool operator<(Circ a, Circ b) { return (b.x-a.x)%256 < (a.x-b.x)%256; }

Is std::set<Circ> valid?

I think generally not, but... suppose that we know, that we're only going
to use values 0-127. In this case std::set<Circ> is valid.
it won't trap at compile time.  Of course depending upon the value of x it might not be valid at runtime - but "type requirements" don't pretend to address that.   Type requirements specify what types are permitted at for template parameters - no more no less.  It can't guarantee that any particular instance is "valid" (whatever that might mean).

Runtime checking is a job of "pre-conditions" and assert.

But if you want - you "could" go a little overboard and use

template<int X>
struct Circ
{
   static unsigned x = X;
};
bool operator<(Circ a, Circ b) { return (b.x-a.x)%256 < (a.x-b.x)%256; }

Of course this is outside the scope of "type requirements" but it's still interesting.

Robert Ramey






123