www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - RFC: std.*.concept convention

reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
------------
Preface
------------

I'd like to start by saying that this is a relatively low-impact 
enhancement in the short term, but should pay off in the long 
term. It also requires very little effort, so it is low-hanging 
fruit, although it requires some foresight to see the benefit.

------------
Primer of type concepts for the uninitiated (skip if you know 
this stuff)
------------

In D we have the idea of a type concept. Current notable concepts 
are the range concept and the container concept. The idea is that 
any type that satisfies the operations of a certain usage pattern 
can be said to satisfy a certain type concept, and thus be usable 
in algorithms that use a permutation of said usage pattern. The 
operations making up a type concept are called the primitives of 
the concept.

For example, for a type to satisfy the input range concept, the 
following usage pattern must compile:
---
R r;              // can define a range object
if (r.empty) {}   // can test for empty
r.popFront();     // can invoke popFront()
auto h = r.front; // can get the front of the range of non-void 
type
---
The three required operations for the input range concept are the 
front, empty and popFront primitives. In addition there may be 
certain restrictions on runtime behaviour; for example, `front` 
should never be called on an empty range.

For convenient verification of a type satisfying a concept, we 
have concept checker templates such as isInputRange[1].

------------
Suggestion
------------

Lately there is a trend of splitting up modules into packages in 
Phobos. Notably, std.range and std.container have been split up 
into packages.

Currently all the range concept checkers are defined in a module 
std.range.primitives, bundled with the UFCS implementations of 
the range primitives for in-built slice types.

Containers do not (yet) have concept checkers, but I consider it 
likely we'll see them in the future, as we see more generic 
container algorithms as well as higher-order containers.

Additionally, Andrei has suggested a new type RefCountedSlice!T 
that presents the same dynamic array interface of T[], but with a 
reference-counted backend in lieu of the GC backend of T[]. It is 
conceivable that generic array algorithms may want to accept 
either type, and thus the "dynamic slice" concept is born.

Putting the complexity of the container concept aside; I think we 
should factor out the concept checkers from std.range.primitives 
and put them in std.range.concept and establish a convention of 
using modules named std.*.concept for concept checkers in the 
future. The consistency gained by such a convention makes type 
concepts easier to understand and commonly used module names 
easier to remember. If we do it now, there is no breakage, as the 
splitting of std.range has not yet been released: hence the 
otherwise clumsy timing of this suggestion.

It is very little work, but anticipating complaints of 
bike-shedding if I didn't explain myself, I decided to post here 
first. I'd like to get some feedback before I file a PR.

[1] http://dlang.org/phobos/std_range#isInputRange
Feb 11 2015
next sibling parent reply Rikki Cattermole <alphaglosined gmail.com> writes:
On 11/02/2015 9:00 p.m., Jakob Ovrum wrote:

 ------------
 Preface
 ------------

 I'd like to start by saying that this is a relatively low-impact
 enhancement in the short term, but should pay off in the long term. It
 also requires very little effort, so it is low-hanging fruit, although
 it requires some foresight to see the benefit.

 ------------
 Primer of type concepts for the uninitiated (skip if you know this stuff)
 ------------

 In D we have the idea of a type concept. Current notable concepts are
 the range concept and the container concept. The idea is that any type
 that satisfies the operations of a certain usage pattern can be said to
 satisfy a certain type concept, and thus be usable in algorithms that
 use a permutation of said usage pattern. The operations making up a type
 concept are called the primitives of the concept.

 For example, for a type to satisfy the input range concept, the
 following usage pattern must compile:
 ---
 R r;              // can define a range object
 if (r.empty) {}   // can test for empty
 r.popFront();     // can invoke popFront()
 auto h = r.front; // can get the front of the range of non-void type
 ---
 The three required operations for the input range concept are the front,
 empty and popFront primitives. In addition there may be certain
 restrictions on runtime behaviour; for example, `front` should never be
 called on an empty range.

 For convenient verification of a type satisfying a concept, we have
 concept checker templates such as isInputRange[1].

 ------------
 Suggestion
 ------------

 Lately there is a trend of splitting up modules into packages in Phobos.
 Notably, std.range and std.container have been split up into packages.

 Currently all the range concept checkers are defined in a module
 std.range.primitives, bundled with the UFCS implementations of the range
 primitives for in-built slice types.

 Containers do not (yet) have concept checkers, but I consider it likely
 we'll see them in the future, as we see more generic container
 algorithms as well as higher-order containers.

 Additionally, Andrei has suggested a new type RefCountedSlice!T that
 presents the same dynamic array interface of T[], but with a
 reference-counted backend in lieu of the GC backend of T[]. It is
 conceivable that generic array algorithms may want to accept either
 type, and thus the "dynamic slice" concept is born.

 Putting the complexity of the container concept aside; I think we should
 factor out the concept checkers from std.range.primitives and put them
 in std.range.concept and establish a convention of using modules named
 std.*.concept for concept checkers in the future. The consistency gained
 by such a convention makes type concepts easier to understand and
 commonly used module names easier to remember. If we do it now, there is
 no breakage, as the splitting of std.range has not yet been released:
 hence the otherwise clumsy timing of this suggestion.

 It is very little work, but anticipating complaints of bike-shedding if
 I didn't explain myself, I decided to post here first. I'd like to get
 some feedback before I file a PR.

 [1] http://dlang.org/phobos/std_range#isInputRange


As long as the std.concept package get's good documentation, I think its 
a damn good idea!
Feb 11 2015
parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Wednesday, 11 February 2015 at 08:21:40 UTC, Rikki Cattermole 
wrote:

 As long as the std.concept package get's good documentation, I 
 think its a damn good idea!


In the spirit of type concepts as a federation of types, not a 
hierarchy of types, I think std.*.concept, such as 
std.range.concept, is more appropriate than an std.concept 
package.

It would be the intuitive go-to module for documenting the 
concept, including abstract information, which we've had a hard 
time working into the reference documentation so far. To wit, the 
documentation for std.range defers to Andrei's informit.com 
article on ranges.
Feb 11 2015
parent Rikki Cattermole <alphaglosined gmail.com> writes:
On 11/02/2015 9:47 p.m., Jakob Ovrum wrote:

 On Wednesday, 11 February 2015 at 08:21:40 UTC, Rikki Cattermole wrote:

 As long as the std.concept package get's good documentation, I think
 its a damn good idea!


 In the spirit of type concepts as a federation of types, not a hierarchy
 of types, I think std.*.concept, such as std.range.concept, is more
 appropriate than an std.concept package.


I'm not too concerned. Gets the same job done.
Feb 11 2015
prev sibling next sibling parent ketmar <ketmar ketmar.no-ip.org> writes:
i like the idea. "concept programming" rocks, and having concept checkers=20
in well-defined places too.=
Feb 11 2015
prev sibling next sibling parent reply Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Wednesday, February 11, 2015 08:00:53 Jakob Ovrum via Digitalmars-d wrote:

 Putting the complexity of the container concept aside; I think we
 should factor out the concept checkers from std.range.primitives
 and put them in std.range.concept and establish a convention of
 using modules named std.*.concept for concept checkers in the
 future. The consistency gained by such a convention makes type
 concepts easier to understand and commonly used module names
 easier to remember. If we do it now, there is no breakage, as the
 splitting of std.range has not yet been released: hence the
 otherwise clumsy timing of this suggestion.


I think that the idea is a good one, and this isn't the first time that it's
been suggested, but I think that it would be more consistent if we used the
term traits rather than the term concepts. We really haven't been using the
term concepts for anything in D, and instead have been heavily using the
term traits for what you're talking about - e.g. isInputRange is considered
to be a trait. In addition, we probably don't want to confuse them with
C++'s concepts. Much as they're similar, they're quite not the same thing.
So, if we go this route, I think that it should be std.*.traits and not
std.*.concept.

But I think that the idea is a solid one, particularly because it allows us
to import the traits for use in template constraints without having to
import any of the functions related to them, and then those functions can be
imported as appropriate with local imports.

- Jonathan M Davis
Feb 11 2015
parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Wednesday, 11 February 2015 at 08:54:41 UTC, Jonathan M Davis 
wrote:

 We really haven't been using the
 term concepts for anything in D, and instead have been heavily 
 using the
 term traits for what you're talking about - e.g. isInputRange 
 is considered
 to be a trait.


My opinion is the opposite. I've never seen anyone use the term 
"traits", but I have seen the term "concept".


 In addition, we probably don't want to confuse them with
 C++'s concepts. Much as they're similar, they're quite not the 
 same thing.


The implementation differs in the details but the idea is exactly 
the same. Using the same term is helpful for people who are 
familiar with C++ concepts.
Feb 11 2015
parent reply Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Wednesday, February 11, 2015 08:59:30 Jakob Ovrum via Digitalmars-d wrote:

 On Wednesday, 11 February 2015 at 08:54:41 UTC, Jonathan M Davis
 wrote:

 We really haven't been using the
 term concepts for anything in D, and instead have been heavily
 using the
 term traits for what you're talking about - e.g. isInputRange
 is considered
 to be a trait.


 My opinion is the opposite. I've never seen anyone use the term
 "traits", but I have seen the term "concept".


We have a whole module full of them - std.traits - so we're already using
that term in Phobos, whereas you won't find the term concepts in there
anywhere. And you seem to be looking for exactly the same thing except in
specific areas - ranges, containers, etc. - rather than having all them
sitting in std.traits.

- Jonathan M Davis
Feb 11 2015
parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Wednesday, 11 February 2015 at 09:11:18 UTC, Jonathan M Davis 
wrote:

 We have a whole module full of them - std.traits - so we're 
 already using
 that term in Phobos, whereas you won't find the term concepts 
 in there
 anywhere. And you seem to be looking for exactly the same thing 
 except in
 specific areas - ranges, containers, etc. - rather than having 
 all them
 sitting in std.traits.


There is a difference between a concept and a trait. A concept 
can be composed of multiple traits. In the context of a concept, 
these traits could be called primitives.

Saying that `isInputRange` is a trait is just clumsy. It's a 
checker template. You could rephrase it and say that it's a 
checker template for the input range trait; but it doesn't check 
for a single distinguishing quality[1], it checks if all of a 
number of traits are present. Querying whether or not a type has 
"the input range trait" is just plain linguistically awkward.

Using the term concept puts us in line with C++, the biggest - 
perhaps the only - competitor D has in the field of template 
metaprogramming, which surely aids learning. Indeed, even the 
Wikipedia article on C++ concepts[2] seems like a good resource 
for understanding the same idea we have in D.

[1] http://www.merriam-webster.com/dictionary/trait
[2] https://en.wikipedia.org/wiki/Concepts_%28C%2B%2B%29
Feb 11 2015
parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Wednesday, February 11, 2015 09:30:12 Jakob Ovrum via Digitalmars-d wrote:

 There is a difference between a concept and a trait. A concept
 can be composed of multiple traits. In the context of a concept,
 these traits could be called primitives.

 Saying that `isInputRange` is a trait is just clumsy. It's a
 checker template. You could rephrase it and say that it's a
 checker template for the input range trait; but it doesn't check
 for a single distinguishing quality[1], it checks if all of a
 number of traits are present.


_Every_ trait is just a "checker template" - be it isInputRange,
isDynamicArray, isInteger, isSomeString, hasLength, etc. In all cases,
they're checking something about a type. I don't see anything different
about isInputRange from hasLength or isPointer except for what they're
checking for, and that's different for every trait. And some of the traits
in std.traits are quite complicated, so it's not like the ones in there are
simple, and the ones elsewhere in Phobos are complex.


 Querying whether or not a type has
 "the input range trait" is just plain linguistically awkward.


I don't see why you'd even need to talk that way. It's not a question of
whether something has the input range trait or whether something has the
input range concept. It's a question of whether something _is_ an input
range, and the trait isInputRange checks that.

- Jonathan M Davis
Feb 11 2015
prev sibling next sibling parent "Baz" <bb.temp gmx.com> writes:
Hello, I remember the first post about this, a few monthes ago, 
and the concept of concept is interesting. Do you think it'll be 
possible to extract a collection of delegate from an agregate 
which verifies a concept ?

- get the concept from an interface
- check if this concept is in a struct
- extract the concept methods from the struct

=> almost polymorphic struct !

Don't know if it's clear.
Feb 11 2015
prev sibling next sibling parent reply "Brad Anderson" <eco gnuk.net> writes:
On Wednesday, 11 February 2015 at 08:00:54 UTC, Jakob Ovrum wrote:

 [snip]

 Putting the complexity of the container concept aside; I think 
 we should factor out the concept checkers from 
 std.range.primitives and put them in std.range.concept and 
 establish a convention of using modules named std.*.concept for 
 concept checkers in the future. The consistency gained by such 
 a convention makes type concepts easier to understand and 
 commonly used module names easier to remember. If we do it now, 
 there is no breakage, as the splitting of std.range has not yet 
 been released: hence the otherwise clumsy timing of this 
 suggestion.

 [snip]


+1. Makes a lot of sense to do it this way.

I prefer "concept" over "trait". I think of traits as more 
primitive building blocks. With a trait you are querying 
information about a type. With a concept you are fitting a type 
to its requirements.
Feb 11 2015
parent David Gileadi <gileadis NSPMgmail.com> writes:
On 2/11/15 12:47 PM, Brad Anderson wrote:

 On Wednesday, 11 February 2015 at 08:00:54 UTC, Jakob Ovrum wrote:

 [snip]

 Putting the complexity of the container concept aside; I think we
 should factor out the concept checkers from std.range.primitives and
 put them in std.range.concept and establish a convention of using
 modules named std.*.concept for concept checkers in the future. The
 consistency gained by such a convention makes type concepts easier to
 understand and commonly used module names easier to remember. If we do
 it now, there is no breakage, as the splitting of std.range has not
 yet been released: hence the otherwise clumsy timing of this suggestion.

 [snip]


 +1. Makes a lot of sense to do it this way.

 I prefer "concept" over "trait". I think of traits as more primitive
 building blocks. With a trait you are querying information about a type.
 With a concept you are fitting a type to its requirements.


My uneducated feeling is that if there's a clear dividing line as to 
what is a trait and what is a concept—for instance if they have 
different syntax—then it makes sense to have two names. Otherwise I 
think it makes more sense to have just one. Fuzzy categorization tends 
to hurt.
Feb 11 2015
prev sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
Just make sure that what is implemented is what is needed.

I have gone over std.traits to see what is used in phobos and the 
following constraints appears not to be used at all:

hasNested
isAbstractClass
isBasicType
isBuiltinType
isFinalClass
isNested
isTypeTuple
isUnsafe

And these only once:

isCovariantWith
isExpressionTuple
isFinalFunction
isInstanceOf
isScalarType

...
Feb 12 2015