Hello everyone.

A big thank you for the very insightful and quite long responses. I will
try to respond to all of them, but this will take me some time.

Am 15.12.19 um 03:36 schrieb Arthur O'Dwyer:
> On Sat, Dec 14, 2019 at 7:44 PM Martin Beeger via SG20
> <sg20_at_[hidden] <mailto:sg20_at_[hidden]>> wrote:
>
> Concept will IMHO change how the think about template arguments and
> template function radically, and will give us the power to express
> semantic contracts much more clearly in definition.
>
>
> Well, IMHO the opposite. :) Ever since Stepanov in the mid-1990s, C++
> programmers have known the general outlines of "generic programming":
> that in C++ it's based on templates, that templates impose syntactic
> and semantic requirements on their type parameters, and that a bundle
> of type requirements can be called a "concept."
> C++11 allows us to write "concepts" fairly conveniently in the form of
> type-traits.
> Orthogonally, C++98 allows us to write function templates that SFINAE
> away for types that don't match their preferred concept (in the form
> of `enable_if`).

I had a really good time reading "From Mathematics to Generic
Programming" by Stepanov last year, which then motivated me to read most
of "Elements of Programming" and although I somewhat knew about generic
programming and Iterator concepts before, it really changed the way I
think about writing templates. Armed with that knowlegde I tried to
improve code quality by using enable_if as a concepts replacement. I
first focussed on some key places, where to most lifting errors to
compile time could be done. The results were, that it indeed catches
error, but compile time explodes. It basically left us with the
unfortunate choice of enable_if(ing) or code or compiling our code, but
not both. I expect to be better off when Modules arrive, but until then,
that in reality. And getting coworkers to think in terms of concepts
when they are not at all enforced and completely invisible is hard.


> C++2a adds new, shorter syntax to accomplish these tasks in fewer
> keystrokes, but it doesn't change how we should /*think*/ about
> generic programming. The mere existence of shorter syntax should not
> lead us to use templates more often, nor to use SFINAE more often.

Interestingly Stepanovs book lead me already before concepts arrived to
use templates less and localize them, by defining (or including from
abseil) semantic types and program against valid semantic non-template
types like duration instead of having templates and overload sets for
different duration types (double seconds, int64_t ticks etc.).

>
> But as one uses
> concepts to modernize template functions, one quickly realizes that
> nearly all template functions either have design flaws or have
> constraints on template parameters which can be expressed by concepts.
>
>
> Yes, there is no such thing as a "truly generic" template. A generic
> function does things to its arguments in terms of their capabilities
> (properties, affordances). A function that says "I compare my
> arguments" requires that its arguments be comparable (using the <
> syntax). A function that says "I swap my arguments" requires that its
> arguments be swappable (using some syntax). So, yes, all function
> templates impose (syntactic) requirements on their type parameters.
> Any syntactic requirement can be expressed via C++2a Concepts, or via
> plain old C++11.
> So, yes, every template imposes syntactic requirements on its type
> parameters which can be expressed by Concepts.
> Equivalently, every template imposes syntactic requirements on its
> type parameters which can be expressed /*without */Concepts.
>
> If you have templates in your codebase today that are not
> SFINAE-friendly — that are not std::enable_if'ed on some type-trait
> that describes their syntactic requirements — then you should ask
> yourself, "Why?" Why would a C++11 programmer occasionally write an
> "unconstrained" template, even as he knows that it must impose some
> kind of requirement and that the requirement must be expressible in C++?

As I said above: compile time. enable_if in about 20 core places doubles
my compile time. type_traits and enable if template metaprogramming
costs a lot.


>
> Off the top of my head:
> (1) The constraint is so complicated that it's not worth the effort to
> specify. For example, imagine the variadic version of this template:
> template<class F, class T1, class T2, class T3>
> bool all_permutations(F f, T1 t, T2 u, T3 v) {
> return f(t,u,v) && f(t,v,u) && f(u,t,v) && f(u,v,t) &&
> f(v,t,u) && f(v,u,t);
> }
> It's probably possible to work out the C++ equivalent of "F is
> callable with all permutations of Ts...", but the cost/benefit
> analysis is against it.

This smells to me. You are doing something complicated, but general. So
try to find an implementation elsewhere. Does the STL have it? Does
abseil have it? Does hana have it? If not, is your original problem
perhaps better seen in a different way? It may be the right thing to do,
but sth. being a smell means for me "a reviewer stumbling upon should
have some questions and some discussions" and "if that doesn't help,
there should a comment explaining that you thought about it", not "you
should never merge that".

Also I think the permutation stuff (at least very similar) is in
Stepanovs book and I think he hard concepts for it (permutations are the
basis of permuation-based sorting). So while I get your point, you might
choose an example where Stepanov hasn't got you covered IIRC.


> (2) The function does not need to mess with overload resolution, and
> it is so trivial that its type-requirement is no more or less than
> that its body compiles. For example:
> template<class T, class U> bool equals(T t, U u) { return t == u; }

This function is just a wrapper. You rename equality and inherit all the
requirements. C++ hat no way to inherit/lift concepts, so yeah wrapper
functions are a good answer to my questions. Your function requires
copyability on top, but that can be fixed. There is a class of
"semantically inactive" functions, like wrapper functions which
themselves to not have concept requirements. I did not see that, thank you.


> The error message "can't find a suitable operator== for t == u" is
> going to be just as useful to the client programmer as "can't find a
> suitable equals for equals(x, y)".
> (3) The function does not need to mess with overload resolution, and
> for usability's sake, it prefers to static_assert its
> type-requirements rather than SFINAE away. For example:
> template<class Socket> void read_from_socket(Socket s) {
> static_assert(is_socket_v<Socket>); ... }

As for such a function the definition and declaration would usually
seperate (as it is not a one-liner) and if I program against it reading
its declaration, I will use them wrong. Yes, the compiler shouts at me,
which is good, but annoying. In a review I would question the usuability
gain, looking a the actual usage of the function and other overloads.


> (4) The compile-time cost of SFINAE is so large that the codebase has
> guidelines suggesting "no unnecessary SFINAE." Notice that many
> templates are used as implementation details. For example:
> template<class Iter> void sort_helper(Iter a, Iter b,
> std::random_access_tag) { ... }
> template<class Iter> requires
> is_swappable_v<iterator_value_t<Iter>> void sort(Iter a, Iter b) {
> sort_helper(a, b, iterator_category_t<Iter>{}); }
> I think most template programmers would agree that it would be
> counterproductive to repeat the same constraints on `sort_helper` that
> were already applied on `sort`. For one thing, it violates the Don't
> Repeat Yourself principle; but more importantly, it costs compile time
> and brings no benefit in return.

This is again a case of not repeating conecpts in semantically inactive
wrapper functions, I get that. This specific wrapper function should no
longer be needed with C++20, am I right?


>
> This lead us to the conclusion, that one should have a coding
> guidelines
> that flags unconstrained template parameters as a code smell.
>
>
> I think this is viable for small codebases, but I suspect a
> significant fraction of large codebases would run into #4 above if
> they tried to add constraints on /all/ their templates.

A significantly large codebase (where "significantly" is up for debate)
can only afford a limited number of template function instantiations.
Otherwise its compile time will blow up anyway. I would rather afford a
few less template functions, with well defined named concepts instead of
a larger number of template function w/o them. Hopefully modules can
alleviate some of this tension.


>
> We really struggled to find one by looking though our codebase.
> The plus
>
> function came to mind, but this requires the arguments to form a
> magma
> at least, which is definitively a valid requires clause.
>
>
> The plus function obviously requires `t + t` to be well-formed, which
> is a valid requires-clause.
> FWIW, I dispute your claim that this has anything to do with
> mathematical magmas. A magma is a set (i.e. a type) with a binary
> operation (let's spell it `operator+`) which is closed; I interpret
> that in a C++ context to mean that decltype(t+t) ought to be T, or at
> least something explicitly convertible to T. But that's definitely not
> a requirement imposed by the `plus` function! Not if it's defined as
> template<class T> auto plus(T t, T u) { return t + u; }
> anyway. However, I suggest we don't pursue /*this*/ rabbit-hole. We
> can pursue the next one if you like. :)

Oh yeah, there is a deep rabbit hole about whether is is benefical to
have plus over a closed set separate from plus over an open set. And how
to express commutativity here... Lets not go there.


>
> The next
> candidate was the identity function, but for the identity function
> to be
> correct, its result must be identical to the input, which only has
> valid
> meaning if the input and the output is actually equality comparable,
> which is a valid requires clause.
>
>
> Here I absolutely disagree. The `identity` function
> template<class T> T identity(T t) { return t; }
> requires that T be move-constructible and destructible, but absolutely
> does not require that T be equality-comparable. For example,
> `identity` remains a useful operation even when T is
> `std::function<void()>`. `std::function<void()>` is not, and cannot
> ever be made, equality-comparable.
>
> The type-requirements of a generic algorithm are driven by what the
> algorithm /*actually does*/. It requires what it /*does*/ to be
> well-formed. My kneejerk impression is that no generic algorithm
> should ever "require" some capability of its type parameter if its
> implementation does not depend on that capability.
But for a non-comparable type template<class T> T identity(T t) { return
T {}; } is often a faster implementation. It may not be what the
programmer expected, but how to write test? Equality is a postcondition
of the type. As the postcondition is impossible to verify, semantics
meaning of the function gets lost and the function itself gets
misleading. If you wanted a "semantically inactive" no-op function,
state that an name it appropiuately. Identity has a mathematical meaning
that different from no-op. I think the identity function on
non-comparable types would not be "provable" in Lisa Lippincott's sense.
So I personally claim it should not be written that way.
> To take a really extreme and probably singular example, imagine what
> the STL would have been like if we'd said, "The std::copy algorithm
> requires the expression `std::addressof(*dest)` to have pointer type."
> That's "obvious," right, because the point of std::copy is to be a
> type-safe replacement for memcpy, and objects always have addresses?
> ...But then we never would have gotten ostream_iterator or
> back_insert_iterator!

The copy function is defined without mention of memcpy. A copy function
is a function which takes Range T and produces a new range T2 where the
following two postconditions hold: The range T is unchanged and the
range is T2 equal to the original range T. And if adressof(*dest) is not
a pointer, the function can still reach its postconditions. So this is
not really a requirement. memcpy-ability or relocatability (yes I have
seen your talk :)) how you call it, may be a requirement of candidate
within the overload set of std::copy to select the fastest algorithm but
never a condition on the copy overload set as a whole, because such a
set I would call copy_to_pointer_location.


>
> I suspect that a sufficiently motivated programmer could always find a
> /*semantic*/ requirement that you failed to capture in your naming
> scheme. ;) Even something as simple as "fclose(fp) expects fp to be a
> file that is open, not a file that has already been closed." But
> maybe it's domain-dependent; maybe "no hidden semantic requirements"
> actually works in your particular codebase.

I agree. This is a Sean-Parent-esk "goal". You will never reach it, but
dude, how much cool stuff you can get from trying and even getting part
of the way there.

If fp was an RAII object which invariant was: for the object to exist, a
open file must exist, the semantic requirement of fclose would be to get
a valid FP object of which its invariant is satifisfied, et voila, you
are done. You cannot correct missing invariant on the type definition of
a function parameter at the function declaration. Get your types right
and RAII for the win.

> [...]
>
> preferred over auto, contains a semantically meaningless auto! A rule
> along the lines of "just avoid auto" is much simpler than to teach
> than
> a rule along the lines of "just avoid auto, except when there is this
> confusing thing which spells auto but is not really a semantic
> auto, as
> it will not match what auto normally matches". So a a result, this
> shorthand notion tends to be avoided out of misinterpretation of the
> guidelines, which then makes concepts unnecessarily hard to use.
>
>
> I do think it's important to teach that (as of C++14) there are two
> different possible meanings for "auto" depending on where it appears
> in the program. When I write
>
> auto int f() { auto i = 0; for (auto&& elt : vec) ++elt; return i; }
> template<class T> void g() { auto x = T(); }
>
> all four of those "auto"s mean the same thing: "There is one single
> concrete type that I have in mind, and I am just too lazy to write it
> out. Compiler, please infer it for me." (In the last case, the
> concrete type differs in each specific template instantiation, but
> it's always the same as `T`.)
> In contrast, when I write
>
> std::sort(first, last, [&](auto&& a, auto&& b) { return a < b; });
> or in C++2a
> void h(auto x) { static int y = 0; std::cout << x << ++y; }
>
> there the "auto"s mean something vastly different: "This thing is a
> template. There is no one concrete type I have in mind; please
> generate a template that can be instantiated for many different things."
> Importantly, since `h` is a template, there are many different `y`s —
> one per instantiation — not just one `y`.

I will go into more detail in the response to Herb Sutters mail, which
also covers this.

>
> For this reason, I conservatively suggest avoiding the `void
> func(Iterator auto it)` syntax that you dislike, and preferring an
> old-fashioned
> template<Iterator It>
> void func(It it) { ... }
> or even
> template<class It> requires Iterator<It>
> void func(It it) { ... }
> which makes it clear that you /*want*/ a template and you /*want*/ it
> to SFINAE away when the parameter type wouldn't be an Iterator.
This is worth some experimentation. Thank you.
>
>
> I can understand that a syntax of "void func(ForwardIterator it)"
> raised
> some eyebrows, but what is the reasoning behind preferring a
> syntax of
> "void func(ForwardIterator auto it)" over alternatives like "void
> func(concept ForwardIterator it)" or similar? Or am I missing a
> way to
> consistently tell this story and not confuse people?
>
>
> I don't think `void func(concept ForwardIterator it)` was ever proposed.
> ("If you didn't want the product to be bad then why didn't you write a
> paper proposing that the product be good?" ;))
I value understanding the current situation before one tries to change
it. So I deemed a mail to a mailing list a better start than a paper.
And as I found the misunderstanding to be on my end, this was the right
choice.
> However, `concept Foo` is also more typing than `Foo auto`, so I don't
> think it's an improvement.
> Right now, `auto x` in a lambda parameter list means "secretly a
> template," so it was the obvious choice when secret templates were
> extended to work with plain old functions. It was a GCC extension
> long before it was in C++2a.
> (In fact, just last week I had to explain to an actual beginner
> student that one of his C++14 program's `auto`s was legit and the
> other was exploiting a non-standard GCC extension! Stupid GCC...)
Herbs mail told me what I am missing and my lack of knowledge over the
final version of concepts did to lead to that confusion on my end. Sorry.
>
> Has this been talked about or what is the general plan to get our
> community to move away from unconstrained template parameters and
> auto?
>
>
> - Whose community (yours in particular, or postulating some global C++
> community)?
> - /*Should*/ any community move away from unconstrained template
> parameters, and if so, why?
>
> If you don't like the visual similarity of
> void foo(Iterator auto x) // TWO WORDS GOOD
> void foo(auto x) // ONE WORD BAD
> then what would you say to
> template<Iterator It> void foo(It x) // NO CLASS GOOD
> template<class It> void foo(It x) // CLASS BAD
> ?
>
> I notice that `template<class It> void foo(It x)` doesn't contain the
> dreaded word "auto", but presumably you'd still consider it a "bad"
> unconstrained template, right? So it's not exactly the word "auto"
> that's causing you trouble...?

The game-changer here is actually the simple line in Herbs mail:

iterator auto first = vec.begin()

I did not know that concepts could also be used to constrain auto in
immediately deduced concept like statements, not only in later
instantiated template contexts. And as both were called auto, this
should have been somewhat obvious to me but it wasn't. In my mind,
concepts could only be used to constrain templates, and I never thought
of auto it= vec.begin(); as a template, but as a deduced type. So I did
not expect you to be able to constrain it, and worried about the task to
disambigaute between these two kinds.

Now everything is beautiful: The story to tell is just use auto, but
when you do and you have a named concept in mind and at hand, constrain
your auto by using the concept. You do that, by simply writing the
constraint before the auto. If that works for all auto contexts and no
asterisk is needed, this is really beautiful.

Martin