Concepts and Overload Arguments

[toma...@gmail.com]

The new revision of the Concept Lite (N3701) paper prosed in the point 3.6 idea to allow use of overladed function identifier as agument to constrained function.
template<typename T>
T geometric_mean(initializer_list<T> list)
{
  T p = accumulate(list.begin(), list.end(), operator*);
  return root(list.size(), p);
}
While, I really like the idea, I think that it is a bit to rigoristic to limit if usage to the constrained function only (see examples bellow). The same problem may be resolved by introduction of the lifting expression []id as it was prosed in paper Lifting overload sets into function objects (N3617) paper. I think that will not negatively affect the idea of checking the constrain of the function, because in the cases well you allow the usage of the identifier (the constrained argument) it would be reduced to Unconstrained lambda + constrained template argument, which is already coverd in your poposal.
template<typename T>
T geometric_mean(initializer_list<T> list)
{
  T p = accumulate(list.begin(), list.end(), []operator*);
  return root(list.size(), p);
}

The support of the lifting operator, well be especially usefulN for the functions, where no meaningful constrain can be placed (on function invocation), example:
int foo(int);
double foo(double)

auto f = std::bind([]foo, _1);
The cleary benefit is that the bind will not require explicit type cast to avoid the ambiguity, furthermore it will allow the invocation of f to inline. Of course there should be constrains placed on operator() of functor generated as ther result of bind expression, so the line:
std::function<int(std::string)> g = f;
will result in the error mentioning that foo does not fulfill the Callable<int(std::string)> (I made, but I think the example is clean) concept.

Of course you may argue that there is not need to use bind, when the generalized lambda captures I introduced, but I think the usage of bind expression is more clearly stating the intent of the code. For example if you compare following simple bind example with co responding lambda:
std::bind([]foo, _1, expr, ref(a));
[e = expr, &a] (auto&& arg) -> decltype(auto) { return foo(_1, e, a); }
I see the bind usage really more elegant. I think that the difference when using bind vs lambda, is the same as a difference in code that uses hand written loop verus use of STL algorithm.


Another think I would like to discuss is that, how should the []id (or in your case overloaded argument) behave in the case of the member functions. Example from your paper:
T p = accumulate(list.begin(), list.end(), operator*);
T p = accumulate(list.begin(), list.end(), [](T a, T b) -> T { return operator*(a, b); });
suggest, that no operator* defined as the member of class T will be considered in this situation. I am right? If so would it apply only for build-in operators?

[Andrew Sutton]

I disagree that the lifted lambdas proposal solves the problem that
I'm trying to solve with constraints. I don't believe that it's a
general solution, and I don't think it ever will be. Not without
constraints (or concepts).

Solving this problem generally requires the compiler to synthesize an
expression involving the named overload set that is compatible with
the called function.

Suppose you have a bunch of functions with the same name and different
arguments:

bool f(int a);
bool f(int a, int b);
bool f(int a, int b, int c);

Easy to use:

f(0);
f(0, 0);
f(0, 0, 0);

But what if I try to use that as a lifted lambda?

sort(first, last, []f)

Which f is chosen? What expression is evaluated by sort()? The
specification actually seems to make the program ill-formed. Unless
I'm not reading it right.

Even better, what if *first refers to a type in a different namespace so

f(*first)

refers to none of the declarations above? How would []f work with ADL?
Not a big deal for the f's of the world, but significant if you're
writing []operator+ or []operator*.

The point of requiring constrained functions is that expected
signature can be deduced from that functions requirements. If sort()
requires that the function object support the syntax comp(x, y), then
the compiler can use that to synthesize a conforming expression that
follows the same rules as if you'd written:

sort(first, last, [](auto x, auto y) { f(x, y); }

Overload resolution rules will apply here just like they would at any
other point in the program.

So, yes... the feature requires that your functions are constrained.
But that gives us a general solution. Plus, I don't have to write [].

> Another think I would like to discuss is that, how should the []id (or in
> your case overloaded argument) behave in the case of the member functions.
> Example from your paper:
> T p = accumulate(list.begin(), list.end(), operator*);
> T p = accumulate(list.begin(), list.end(), [](T a, T b) -> T { return
> operator*(a, b); });
> suggest, that no operator* defined as the member of class T will be
> considered in this situation. I am right? If so would it apply only for
> build-in operators?

I'd forgotten that C++ doesn't really work the way I want. The
synthesized expression should be "a * b", but that's a special case
for named operators. I suppose we'll need special rewrite rules.

Andrew

[toma...@gmail.com]

W dniu czwartek, 11 lipca 2013 21:32:51 UTC+2 użytkownik Andrew Sutton napisał:

I disagree that the lifted lambdas proposal solves the problem that
I'm trying to solve with constraints. I don't believe that it's a
general solution, and I don't think it ever will be. Not without
constraints (or concepts).

Solving this problem generally requires the compiler to synthesize an
expression involving the named overload set that is compatible with
the called function.

Suppose you have a bunch of functions with the same name and different
arguments:

  bool f(int a);
  bool f(int a, int b);
  bool f(int a, int b, int c);

Easy to use:

  f(0);
  f(0, 0);
  f(0, 0, 0);

But what if I try to use that as a lifted lambda?

  sort(first, last, []f)

Which f is chosen? What expression is evaluated by sort()? The
specification actually seems to make the program ill-formed. Unless
I'm not reading it right.

According to the proposal i mentioned,  this would be equivalent to:
sort(first, last, [](auto&&... args) -> delctype(auto) { return f(std::forward<decltype(args)>(args)...); });
So, I see no problem there. The args will have type [int, in], so the expression in the return statement would be f(int, int). If we omit the case of the build-in operators the whole proposal can be summarized in:
#define LIFT(id) [](auto&&... args) -> delctype(auto) { return id(std::forward<decltype(args)>(args)...); }
sort(first, last, LIFT(f));
That is working in current C++14 standard.

Even better, what if *first refers to a type in a different namespace so

  f(*first)

refers to none of the declarations above? How would []f work with ADL?
Not a big deal for the f's of the world, but significant if you're
writing []operator+ or []operator*.

The lambda generated from the []f, will contain return f(*first) invocation and use ADL. No problem there.
 

The point of requiring constrained functions is that expected
signature can be deduced from that functions requirements. If sort()
requires that the function object support the syntax comp(x, y), then
the compiler can use that to synthesize a conforming expression that
follows the same rules as if you'd written:

  sort(first, last, [](auto x, auto y) { f(x, y); }

Overload resolution rules will apply here just like they would at any
other point in the program.

The point of proposal I mentonied is to use varidatic lambdas [](auto&&...) {}, so everythink will work as in your examples.
 

So, yes... the feature requires that your functions are constrained.
But that gives us a general solution. Plus, I don't have to write [].

So you would like to drop support for the bind, because of saving to characters in the code?
 

> Another think I would like to discuss is that, how should the []id (or in
> your case overloaded argument) behave in the case of the member functions.
> Example from your paper:
> T p = accumulate(list.begin(), list.end(), operator*);
> T p = accumulate(list.begin(), list.end(), [](T a, T b) -> T { return
> operator*(a, b); });
> suggest, that no operator* defined as the member of class T will be
> considered in this situation. I am right? If so would it apply only for
> build-in operators?


I'd forgotten that C++ doesn't really work the way I want. The
synthesized expression should be "a * b", but that's a special case
for named operators. I suppose we'll need special rewrite rules.

This is why we need []operator+ instead of my simple LIFT macro.

 

[Andrew Sutton]

>
> According to the proposal i mentioned, this would be equivalent to:
> sort(first, last, [](auto&&... args) -> delctype(auto) { return
> f(std::forward<decltype(args)>(args)...); });
> So, I see no problem there. The args will have type [int, in], so the
> expression in the return statement would be f(int, int). If we omit the case
> of the build-in operators the whole proposal can be summarized in:

I see.

> So you would like to drop support for the bind, because of saving to
> characters in the code?

I don't understand why the call to bind() requires extra annotation.

Andrew

[toma...@gmail.com]

Consider to following code:
int f(int);
double f(double);

std::bind(&f, _1);
This code will fail to compile and emit error about taking the address of overloaded function. The problem may be solved by doing an explicit cast:
std::bind(static_cast<int(*)(int)>(f), _1);
But writing such cast is a bit tedious, also it kill the polymorphism of f (we selected one of the overloads). We may try to fix the problem by writing:
std::bind([](auto&& a) -> decltype(auto) { return f(std::forward<delctype(auto)>(a));
Or more generally:
std::bind([](auto...&& a) -> decltype(auto) { return f(std::forward<delctype(auto)>(a)...);
This even more tedious than cast and doesn't work as expected for build-in operators. But gives a bonus of in-lining (hard, near to impossible whit invoking function via pointer). So the idea is to allow write:
std::bind([]f, _1);


Second problem with the bind, is that I think that there is no really a clean way to write a Concept for the first argument (functor of bind). For example:
auto f = std::bind(foo, _2, expr, ref(a), _1);
The requirements place of f, should be:
  - has operator() that accpets 4 arguments, two (1st, 4th) with unknow type at this moment, 2nd compatible with decay(expr), and 3rd compatible with a reference.
But in case of invocation of f, or matching it agains constraint you will konw the types provided to _1, _2, so it will be reduced to checking if foo is invokable with four know arguments. Example.
f(T1{}, T2{}) -> foo should be Callable<T2&&, decay_t<decltype(expr)>, decltype(a)&, T1&&>
So there is no clean way to make bind constrained and then your mechanism of overloaded arguments will not work.

[toma...@gmail.com]

> So you would like to drop support for the bind, because of saving to
> characters in the code?

I don't understand why the call to bind() requires extra annotation.

And of course any existing non-constrained code, that would benefit form passing overloaded functions sets as arguments.

[Bjarne Stroustrup]

On 7/11/2013 8:37 PM, toma...@gmail.com wrote:

I am having a hard time convincing myself that
    (1) optimizers can consistently and without heroic efforts implement []f without runtime overhead
    (2) that []f isn't mission creep relative to specifying template argument requirements and using the information provided.
    (3) that []f is a helpful notation compared to ``plain'' f as an argument

--
You received this message because you are subscribed to the Google Groups "SG8 - Concepts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to concepts+u...@isocpp.org.
To post to this group, send email to conc...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/concepts/.
 
 

[toma...@gmail.com]

On Friday, July 12, 2013 10:20:32 AM UTC+2, Bjarne Stroustrup wrote:

On 7/11/2013 8:37 PM, toma...@gmail.com wrote:

I am having a hard time convincing myself that
    (1) optimizers can consistently and without heroic efforts implement []f without runtime overhead

GCC 4.8.1 has no problem with inlining the following code (I checked the assemlby):
#include <utility>
#include <functional>
#include <iostream>

inline void foo(int i) { std::cout << i; }
inline void foo(double d){ std::cout << d; }

struct foo_wrapper
{
  template<typename... Ts>
  auto operator()(Ts&&... ts) const
    -> decltype(foo(std::forward<Ts>(ts)...))
  { return foo(std::forward<Ts>(ts)...); }
};

int main()
{
  std::bind(foo_wrapper(), std::placeholders::_1)(1); //inlined to std::cout << 1;
};
So I see no reason to have any problems (with current implementation to inline):
std::bind([](auto&&... ts) -> decltype(foo(std::forward<Ts>(ts)...)) { return foo(std::forward<decltype(ts)>(ts)...); }, std::placeholders::_1)(1);
And then:
std::bind([]f, std::placeholders::_1)(1);
Am I missing something?
 

    (2) that []f isn't mission creep relative to specifying template argument requirements and using the information provided.

I also thinks so, but the the current concept-lite proposal contains similar functionally but without using the []id syntax, so I don't get you point. My suggestion was that we should go with solution proposed in separate Lifting overload sets into function objects (N3617) paper and do not propose the overloaded arguments as part of concept lite.
 

    (3) that []f is a helpful notation compared to ``plain'' f as an argument

The problem is that, the line:
std::sort(v.begin(), v.end(), f);
Has now well defined semantic and is equivalent to:
std::sort(v.begin(), v.end(), &f);
And if the f is overloaded then the second invocation may result is ambiguity error, but if f has one definition the code now works. Your proposal will silently change the generated code, if the sort get the constrained. So to avoid this ambiguity, the proposal invent the syntax:
std::sort(v.begin(), v.end(), []f);
Which can work in both constrained and unconstrained argument context.

I don't really like the plain function name (f) syntax that you proposed, because it now has clean meaning.

[toma...@gmail.com]

On 7/11/2013 8:37 PM, toma...@gmail.com wrote:

I am having a hard time convincing myself that
    (1) optimizers can consistently and without heroic efforts implement []f without runtime overhea

I think I miss your point in my answer before. Both solutions proposed in Concept-Lite and Lifting operator paper uses generic lambda to represent set of overloaded functions (I take this conclusion for your paper example) one that takes specified number of auto parameters and one varidatic, but the code generated from the both inpolicit specializations of it in the constrain concept will be probably the same. In that context I does no see how you proposal will allow optimizer to behave better.

Furthermore, if we discuss the run-time cost of wrapping function into functor, I think the []syntax is more appropriate. Using lambda introducer ([]) clearly states that the closure object will be created in that context (so all run-time overheads as the same as for pointer), but stand alone identifier suggest some magical version of polymorphic function pointer (please remember that at this moment using of id means pointer in every context), so user may think that the overhead will be the same as for functions pointers and no inlining is possible.

    (3) that []f is a helpful notation compared to ``plain'' f as an argument

How orthogonal would be the overloaded argument functionality with id syntax to the usage of the constrain, would it apply when concept name will be used as the placeholder (example. Predicate<int> f = &foo). If so consider the following code:
auto f = foo; //uses auto var = syntax suggested by the Herb,
              //deduces function pointer
if (check_something())
   f = nullptr;
if (f)
   f(1);
Then if the user encouraged by your proposal will use concept instead of auto:
Function<int> f = foo; //creates some closure,
if (check_something())
   f = nullptr;       //error: closures are not assingable
if (f)                //error: lambda has no operator bool
   f(1);
So the user code may break with the usage of the constrain, futhermore I think it would be surprising if the auto f = foo and Function<(int)> f = foo would create variable with different types. The same problem may be reproduced for constrained argument - simple put the example code in the function that takes f as parameter. The []id syntax has no such problems:
auto f = foo; //function pointer, as it is now
Function<int> f = foo; //function pointer
auto f = []foo; //closure
Function<int> f = []foo; //closure

[toma...@gmail.com]

Would it be feasible to make the constrains and lifting expression ([]id) work together by generating a constrained lambda with ad-hoc constrain instead of over-generic one?
I mean that []id would be equivalent to:
[](auto&&... args) -> decltype(id(std::forward<decltype(args)...))
  requires requires(auto&&... args) { id(std::forward<decltype(args)>(args)...); }

  { return id(std::forward<decltype(args)>(args)...); }

Instead of:
[](auto&&... args) -> decltype(id(std::forward<decltype(args)>(args)...))

  { return id(std::forward<decltype(args)>(args)...); }

Note that in contrast to proposal that I originally mentioned []id will not try to invoke id member function of first argument or try invoking (*first_argument).id;

I think the following approach may give us benefits of both worlds: better diagnostic (the validty of the exprssion is checked in both cases via decltype()) and allow usage of lifting expression with existing non-constrained templates or in situation when checking must be postponed until invocation of result (bind).

Also to support both member and free function operators, the []operator+ could be defined as:
[](auto&& arg1, auto&& arg2) -> delctype(std::forward<delctype(arg1)>(arg1)+std::forward<delctype(arg2)>(arg2))
  requires requires(auto&& arg1, auto&& arg2) { std::forward<delctype(arg1)>(arg1)+std::forward<delctype(arg2)>(arg2); }
  { return std::forward<delctype(arg1)>(arg1)+std::forward<delctype(arg2)>(arg2) };

[Andrew Sutton]

> Would it be feasible to make the constrains and lifting expression ([]id)
> work together by generating a constrained lambda with ad-hoc constrain
> instead of over-generic one?
>
> I mean that []id would be equivalent to:
>
> [](auto&&... args) -> decltype(id(std::forward<decltype(args)...))
> requires requires(auto&&... args) {
> id(std::forward<decltype(args)>(args)...); }
> { return id(std::forward<decltype(args)>(args)...); }
>

> I think the following approach may give us benefits of both worlds: better
> diagnostic (the validty of the exprssion is checked in both cases via
> decltype()) and allow usage of lifting expression with existing
> non-constrained templates or in situation when checking must be postponed
> until invocation of result (bind).

I suspect that an implementation could lift constraints generic
lambdas in order to improve diagnostics, but I don't think it should
be required for implementors to do that.

This is not viable for unconstrained function templates in general,
since overloading is predicated on the comparison of those
constraints. Effectively, this would define overloading in terms a
function's implementation, which strikes me as being a Bad Thing.

Andrew