It’s Sunday morning on the 256th day of the year as I write this. Please join me in a daydream thought experiment, if you will. (Potential controversy ahead.)
“A higher-order function is a function that does at least one of the following: takes one or more functions as arguments, or returns a function as its result.”
A metafunction, for our purposes, is a function that works on types instead of values. An example is std::optional. You give it a type, say int; it gives you back another type, std::optional<int>. A higher-order metafunction therefore is a metafunction that either takes one or more metafunctions as arguments, or returns a metafunction as its result.
Aside 0: (Yes, this is the type of post this is going to be…) Most weeks I spend at least some time as a professional metaprogrammer. In my opinion, metaprogramming is what makes C++ extraordinary. Templates, and especially variadic templates, are a source of power and expression available to C++ that is in very few other languages (so far). Among ex-C++ programmers I know who now work mainly in other languages, the number one complaint I’ve heard is that that power and expressivity is just not available to them any more, making everything more annoying. I don’t really understand why some other languages have apparently decided variadic generics aren’t a huge deal. They absolutely are. Anyway, back to the plot…
Around 20 years ago, the C++ community was struggling with higher-order functions. Functions in C++ (and indeed in C) are not really first-class citizens in value-world. We aren’t allowed to copy, pass, or otherwise deal in function values; we can only wrangle pointers to them. A large limitation is that we can’t define new functions inside other functions. (Yes, I know there is a GNU C extension. It’s not C++.) This makes things like composition and partial application difficult.
“Well,” we thought, “if we can’t treat functions as proper values, we must make proper values that behave like functions.” And so we did. Class types have always (being in C++98 counts as always) had the function call operator, operator(), and local classes can be defined inside functions or function templates. Thus back in the aughts we had a number of libraries — not to mention ad-hoc in-house APIs — that used various techniques to get around the difficulties of wrangling functions.
All this led eventually to a recognition that libraries weren’t cutting it, and in C++11 we got lambda expressions so that the language could short-circuit all that complexity and boilerplate for us, and give us a first-class closure object value that behaved like a function. Also for some reason in C++11 we also got std::bind, a holdover from the library attempts that was almost immediately obsolete.
“Classic bind is bad. Don’t use it. It’s hard to understand, hard to optimize, and lambdas are better in basically every way.” — Stephan T. Lavavej
(There was a short period of time between C++11 and C++14 where std::bind was still useful over lambdas in certain situations, but with C++14’s init-capture allowing capture-by-move, that need pretty much disappeared. The only weak argument left for std::bind is some cases of brevity. If you are stuck with C++11, I’m sorry.)
It seems to me that metafunctions are in much the same situation today as functions were ~20 years ago. We have libraries that jump through hoops to do metafunction composition, partial application, etc. All the same sorts of things that we used to try and do with Boost.Lambda, Boost.Bind and friends.
The root cause of the problem is this: templates are not types. (At least in value-world we get pointers to functions, so we could pretend that functions were values; in type-world we can’t even do that.)
We can pass types to templates, or we can pass templates to templates, but we have to maintain a strict knowledge of which is which. Contrast this to value-world, where we can pass a deduced type T that might be a “regular value” or might be a function (pointer). We can define templates inside templates. But we can’t return them. We can’t say:
// definition
using my_pair = std::tuple;
// call
using P = my_pair<A, B>;We can only return types, so we have to say:
// definition
template <typename T, typename U>
using my_pair = std::tuple<T, U>;
// call
using P = my_pair<A, B>;Well now, let’s dream a bit, the same way we did back in the day in value-world: if templates can’t be types, we must make types that behave like templates. In value-world, we do this by imbuing objects with operator(). In type-world, it seems analogous to imbue types with operator<>.
// definition
struct my_pair {
template <typename T, typename U>
using operator<> = std::tuple<T, U>;
};
// call
using P = my_pair<A, B>;(If you’re balking at the idea of an operator that doesn’t work on values, consider that we already have new — which works at least partially on types — and the scope resolution operator :: — which works on… scopes. This is just another metaoperator!)
In value-world today, we still have all the limitations on functions that we used to: we got around it by making first-class values that behave like functions. This is the same approach. In type-world today, we have limitations on metafunctions, so let’s get around it by making types that behave like metafunctions. We can pass types homogeneously. We can return types. We can define types inside of other types. Types are first class values in the metaprogramming world.
This would perhaps already improve metaprogramming. For a start, it would replace the convention-driven form of “quoted metafunctions” with a form that is supported by the language. But you know what’s coming now: so far this only takes us to the level of C++98. Of course we want metalambdas.
using pair_with_int = [T = int] <typename U> std::pair<T, U>;“All lambdas are divided into three parts.” — Julius Caesar, De Bello Lambdarum
Just like value-world lambda expressions, metalambdas have three parts:
- the capture clause:
[T = int] - the parameter list:
<typename U> - the body:
std::pair<T, U>
(Syntax quibbles deferred. The structure is the point.) The result is the compiler synthesis of a type:
struct pair_with_int {
using T = int;
template <typename U>
using operator<> = std::pair<T, U>;
};This now is a massive improvement for metaprogramming. Now we can:
- pass metafunctions like regular first-class metavalues
- define local metafunctions easily
- return metafunctions from metafunctions
Aside 1: can universal template parameters achieve some of this?
Maybe. Universal template parameters could perhaps handle passing templates and types homogeneously. I’m not au fait with the latest work here. But also, UTPs are at most half the story: they aren’t going to give us the power to return templates. I get the feeling that some useful parts of the UTP paper have been carved off, and perhaps reflection asphyxiated work on the rest. Which raises the question:
Aside 2: can reflection achieve some or all of this?
Some, maybe. All, probably not. It’s true that because std::meta::info is type-erased, it’s like a universal argument. It can encode types and templates in the same type of thing. You still have to remember to apply ^^ at all the call sites. And — annoyingly — sometimes you have to sprinkle dealias around. But given that, we can pass and return types and templates homogeneously. Reflection can also take advantage of value-world machinery to get around the type-world limitations, but it requires us to stay in value-world, only to emerge at the end.
Aside 2a (Yep!) There is always a penalty or limitation to coming out of a monad, e.g. a branch (std::optional) or a wait (senders). In the case of reflection, the limitation is lack of constexpr function parameters: we can’t get out at all, or alternatively can only come back out of the monad where we’re already outside it, at the topmost call level. [pop aside stack]
Reflection also has a fundamental limitation: it can’t do things that (in theory) the language can’t express “normally”. Which means it’s still stuck translating the current state of metaprogramming. So ultimately it’s complementary to the idea of operator<> rather than antithetical, or offering a strictly better alternative.
Besides, we haven’t yet followed this all the way, there’s more… (More controversy ahead.)
Something value-world functions can do that type-world functions can’t is participate in overload sets. This doesn’t work:
template <typename T, typename U>
using fn = std::pair<T, U>;
template <typename... Ts>
requires (sizeof...(Ts) != 2)
using fn = std::tuple<Ts...>;
// error: conflicting declaration of fnAnd neither (trying to be more tricksy) does this:
struct A {
template <typename T, typename U>
using fn = std::pair<T, U>;
};
struct B {
template <typename... Ts>
requires (sizeof...(Ts) != 2)
using fn = std::tuple<Ts...>;
};
struct C : A, B {};
using P = C::fn<int, float>;
// error: reference to C::fn is ambiguousYes, C here could provide its own fn, and route to A‘s or B‘s as appropriate, but this is assuming it has knowledge of A and B that perhaps it doesn’t. Once we have the ability to wrangle metafunctions more easily, perhaps we want to be able to overload them. After all, just like in value-world, we could write same-named metafunctions with different arities, and/or with different constraints on their parameters. Overload sets exist because they are useful (and arguably should be thought of instead of functions as the fundamental thing).
Having overload sets in type-world means, again just like in value-world, that we need a way to determine what the best overload is for a given call. We have an idea of the rules already, but yes, that’s a whole thing.
Another thing we might want (or some of us might not!) for metafunctions is ADL. I leave that consideration as a thought exercise for the reader. Although I would note in passing that as working metaprogrammer, I have multiple times run into the limitations of not having ADL in type-world. I also leave for further dreams the consideration of constant template parameters as another axis: templates don’t have to have types as their parameters of course!
You can see how this idea could be hammered out and built upon over the course of several updates to C++. It’ll almost certainly never happen. But we can dream of “operator angles” and a simpler metaprogramming future.