A couple of noteworthy things have happened since we floated the idea of a pythy syntax for functions. First, Paul Fultz came up with a library implementation of Pythy syntax. Wow! I’m not sure where this will lead but I’m eager to see what it feels like in practice (also check out some of his other git repos; there’s some really cool stuff in there).
Second, I just got finished collaborating on a proposal with Faisal Vali and Herb Sutter to include generic lambdas and pythy functions in the core language. After the upcoming Portland committee meeting, we should have a good sense of how much appetite there is on the committee for including these features in C++.
While we were writing that paper, we got some of our most helpful comments and insights from Mathias Gaunard. It was a pivotal moment when Mathias reminded us that we could create operator overload sets explicitly with inheritance and using declarations, and then used it to demonstrate “overloaded lambda expressions.”1
template <class F1, class F2> struct overload_set : F1, F2 { overload_set(F1 x1, F2 x2) : F1(x1), F2(x2) {} using F1::operator(); using F2::operator(); }; template <class F1, class F2> overload_set<F1,F2> overload(F1 x1, F2 x2) { return overload_set<F1,F2>(x1,x2); } auto f = overload( [](){return 1;}, [](int x){return x+1;} ); int x = f(); int y = f(2);
Since C++11 lambda expressions create function objects, this got me thinking again about narrowing the gap between function objects and ordinary function templates. Each one has its own great strength that isn’t shared by the other.
Two Great Tastes…
The great strength of function objects is that, even when they are generic, they remain first-class objects. Unlike ordinary function templates, they can be passed to and returned from functions, a trait whose importance is only increasing with the renaissance of higher-order functional programming:
#include <numeric> #include <utility> int c[] = {1,2,3}; template <class T> T mul1(T x, T y) { return x*y; } int x1 = std::accumulate( std::begin(c), std::end(c), 10, mul1 ); // ERROR! constexpr struct mul_t { template <class T> T operator()(T x, T y) const { return x*y; } } mul2 = {}; int x2 = std::accumulate( std::begin(c), std::end(c), 10, mul2 ); // OK
Algorithms on heterogeneous data types such as std::tuple and boost::variant especially rely on this capability.
Yes, generic function objects are syntactically heavy, but there’s at least some hope that N3418 will help deal with that. At one point during the writing of that paper I actually asked my co-authors whether function templates might be considered obsolete once we have generic lambdas. After all, why bother writing
template <class T> T min(T x, T y) { return y < x ? y : x; }
auto min = [](x,y) y < x ? y : x;
Of course I had forgotten that the real weakness of function objects is the lack of true overloading. Regular function templates can be overloaded liberally and non-intrusively. I can put as many as I want with the same name in a single namespace, and unlike function objects, they don’t need to be explicitly gathered into overload sets:
template <class T> int f(T*); // Same name? template <class T> int f(std::vector<T> const&); template <class U> int g(U& x) { return f(x); } // No problem! struct f1_t { template <class T> int operator()(T*) const; } h = {}; struct f2_t { template <class T> int operator()(T) const; } h = {}; // ERROR: can't redefine h!
True overloading (combined with argument-dependent lookup or ADL) remains the best way to deal with operators and, at least until we get first-class concepts in C++, to create generic “customization points.”2
…That Go Great Together?
This non-uniformity between function objects and function templates just doesn’t smell right, does it? I’d like to see if we can do something to bring the two approaches closer together, so you don’t have to choose between overloading and passing generic functions as arguments. N3418 goes a long way toward resolving syntactic differences, but what about the capability gap?
Sketching a Solution
Here are my initial thoughts about how we could address it:
- In actuality, maybe part of the capability gap should be preserved. After all, as I argued in N1691, ADL is currently a bit too liberal. Explicit control over where ADL kicks in could be useful, so maybe that should be incorporated into our method of overloading function objects.
- Another place I’m looking for inspiration is in Daveed Vandevoorde’s proposal for a
namespaceoperator. - Since function objects can store data and can already be “explicitly overloaded,” and because limiting ADL for ordinary functions would break code, it probably makes more sense to push function objects further toward functions rather than the other way around
- Participation of ADL and overloading should be determined at the point where a function object is created rather than where it is invoked. It wouldn’t do for the same object to have different behaviors in different call contexts, would it?
- Because there are still lots of ordinary function templates out there, it should be possible to combine them into overload sets with function objects.
Suppose the unqualified using-declaration proposed in N1691 were extended to apply to function objects, and decltype were extended to account for that? Then, something like this would be possible:
constexpr struct overloaded_f_t { template <class...T> auto operator()(T&&...x) -> decltype( using f; f(std::forward<T>(x)...) ) { using f; // bring in associated functions and function objects via ADL return f(std::forward<T>(x)...); } } overloaded_f = {}
Naturally, one wouldn’t want to write that out by hand, but it would give us a language foundation for defining the semantics of some syntax sugar such as:
auto overloaded_f = [](...) using f;
I haven’t given that syntax much thought; I’m sure someone can do better.
What do you think?
Is this a problem worth solving? What is my approach missing? What are your ideas? I’m looking forward to your comments!
-
See also this variadic implementation ↩
-
A customization point is an interface that can be implemented to specify how a type models a given concept. For example, “a
swapfunction defined in the type’s namespace” is a customization point for the Swappable concept. See C++11 §17.6.3.2 [swappable.requirements] ↩
Alsa it would be great to unify function objects and member function pointers (the purpose of mem_fun and a lot of hackery in boost::bind).
struct x { void f(int, int); };
Let &x::f be a function object with 2 overloads of operator():
void operator()(x*, int, int); void operator()(x&, int, int);
I really want polymorphic lambda support in C++, and that proposal looks really nice
Also I think lambdas need a way to refer themself, I guess you cannot use “this” as it is used by the capture system. It doesn’t even really need to be a keyword, since lambdas are most likely implemented as classes with an overloaded operator (), one way might be to supply each lambda with a 2nd function like “this_lambda”(or whatever) that just forwards back to the operator (). Probably require a minor change to argument lookup for lambda–
auto factorial = { return n <= 1 ? n : n * this_lambda(n-1); }
Here is Aaron’s attempt on this http://www.aaronmcdaid.com/2012/09/typeof-or-c-please-stop-holding-my-hand.html https://github.com/aaronmcdaid/plwt
One thing I think is missing from lambdas is the ability to use them as template type arguments.
Consider
typedef std::set<int, std::function> s1; s1 S1([](const& x1, const& x2) { return x1 < x2; });
I would like to be able to write this as
typedef std::set<int, [](const& x1, const& x2) { return x1 < x2; }> s2; s2 S2;
but that requires that I take the type of the lambda function and that is forbidden. Your addition of a conversion operator also fails to support this case. Why couldn’t the type of a lambda that capture no variables be deducible so that it could be used for template instantiation.
You can do this already:
template std::set<ValueType, Compare> make_set(Compare c) { return std::set<ValueType, Compare>(c); }
auto s2 = make_set([](int const& x1, int const& x2) { return x1 < x2; });
If our language was able to deduce template paramters of the class from arguments of constructor, we could do this even without helpers like make_set/make_pair/etc.
Since lambdas are already a syntatic sugar around constructing function-objects, why not extend the syntax slightly further? Why not transform
auto f = [](auto x) { /* … */ };into
struct mangled_name_from_compiler { template <typename Type_1> return_type operator()(Type_t x) const { /* ... */ } };Hi Bryan!
Did you read our proposal? It calls for almost exactly that.
I must have missed that, sorry!
Uck, the newlines got taken out! Repost:
I was actually the other day discovering a similar technique to this, though not for lambdas.
What i really want is to be able to call for_each with doThing1 (or in your example, f) and have the compiler figure which version to call. But in the meanwhile, doThing2 does exactly what I need.
Please correct me if this isn’t as relevant as I think it is.
Hey, splinter—
I hear ya. What you discovered was that function objects like
doThing2are first-class objects that can be passed to functions. Lambdas, being function objects, are just an instance of this idea (see the article). It would be nice, wouldn’t it, if passingdoThing1directly would generate a function object based on its overload set?P.S. I fixed up your formatting for you. Check out http://cpp-next.com/posting/ for next time, though.
I hope you guys understand the consequences of adding polymorphic lambda expressions, this is going to pretty much require C++ compilers to implement a version of the Hindley–Milner type inference algorithm, furthermore without some form of type constraints in the language (be it Concepts or something similar to type-classes) this is going to lead to a world of pain. In any-case who-ever is working on this proposal better keep mind how type constraints is going to interact with polymorphic lambda expressions.
By the way a template function using a template lambda function and invoking this a number of times with arguments of different types would be equivalent to a higher-order function which has a higher-rank type AKA higher-rank polymorphism, this would be a rank-2 type to be precise. Can we please stop bastardizing terminology in C++, e.g. “functors”.
Hey @sir_sgt_jeffrey_the_3rd, thanks for posting!
You make an interesting claim about the need for Hindley-Milner type inference, but I’d like to know what leads you to that conclusion. It’s seems to me that it’s trivial to demonstrate that no major new inference capabilities are required, since everything we’ve proposed is syntax sugar for existing template constructs—except for the fact that we presume support for local classes with template members, which I hope you’ll agree doesn’t affect deduction in any important way.
Your warning about the need for type constraints is especially interesting considering the fact that before this article, common wisdom in the C++ community was that the world-of-hurt would arise where polymorphic lambdas and type constraints mix! I think the same argument applies to this claim, though: we know that classes with templated function call operators work; being able to define them on-the-fly with a lambda expression isn’t going to change much.
In point 3 of the sketch you’ve written, “push function objects further toward function objects”. I think that needs to be “push function objects further toward functions.”
Thanks; fixed!