Why template parameters of dependent type names cannot be deduced, and what to do about it

Following the presentation a type by any other name at the CppCon, a great talk that shows how to incrementally refactor code using tooling and type aliases, I got interested in one of the observation made by Jon Cohen: template parameters of dependent type names cannot be deduced.

This short post aims at describing this issue and explaining why it is so. We will explain why C++ cannot do much better considering its type system and some basic mathematics. We will conclude by showing different ways to solve this issue, including one from Haskell.

 

Introducing the problem

---

Before we dive into the explanations, we first have to describe the issue raised by Jon Cohen and introduce the notion of dependent names in C++.

 

Dependent names

Inside the definition of a template, the meaning of some of the identifiers might depend on one or several template parameters. We call these identifiers dependent names. For instance in the following code, the meaning of const_iterator depends on the type T:

Because C++ syntax is overloaded, such a name could in theory refer to a static member as much as a type. To remove some of the ambiguity, dependent names are not considered as referring to types “unless the keyword typename is used or unless it was already established as a type name” (from cppreference.com).

This is why we have to add the typename keyword to make our previous code valid:

We will refer to these dependent names qualified with typename as dependent type names.

Note: This was a rather quick introduction to dependent names and dependent type names. The reader is encouraged to look at the cppreference.com or this blog post from Eli Bendersky for more detailed information on the subject.

 

Taking dependent type names as arguments

Dependent type names can appear inside the signature of function templates, as shown below in this over-constrained implementation of for_each:

While it may look fine on the surface, there is a problem here. Upon calling for_each, the compiler will be able to deduce the type of the iterator, but not be able to infer the template parameter T.

The net result is that the following code, which looks perfectly valid, will not compile: the compiler will complain that it is unable to “deduce the template parameter T”.

The problem is what Jon Cohen referred as “template parameters of dependent type names cannot be deduced” in his talk. And as he points out, this kind of error will likely confuse more than one newcomer to C++. Why can’t the compiler figure out the type of T?

 

Hidden dependent type names

The previous example featured a case in which the dependent type name was pretty easy to spot. The typename and the ::const_iterator appeared clearly. But it gets hard to spot when we introduce type aliases.

For instance, we can write an alias template container_t to select a different container depending on the type of element we would like to store in it (we do not use std::conditional_t to show we are dealing with dependent type names):

• If the type is copyable, we want to use a std::vector
• Otherwise we want to use a std::list

We can now define a function f which takes as parameter a container_t. As we can see, it gets really hard to spot that we are dealing with a dependent type name from the signature alone:

Despite being hidden, the problem still remains. The compiler will be unable to deduce the type of elements stored in the container:

This is precisely the tricky case that Jon Cohen raised in his presentation, and this one will most likely annoy C++ beginners for quite a long time.

 

Why the compiler cannot do much better

---

Let us now explain why the compiler cannot deduce the type of a parameter T from a type name that depends on the parameter T.

 

Type level functions

We can conceive a type name depending on a template parameter as the result of a function applied on the template parameter. The syntax is different, but it obey the same principle (*).

For instance, here is the type-level function that computes the common type between two or more types in C++, followed by what would the syntax of a normal function call:

Similarly, the const_iterator dependent type name can be seen as the result of the application of a type-level function on the vector class template:

(*): The syntax for calling a type-level function is what Odin Holmes refers as the “unicorn call syntax” as a reference to the “uniform call syntax” C++ standard proposal. We just replace `using` by `auto` and angle brackets by parentheses to get the normal call syntax.

 

Injective functions

A function f is injective is for all input x and y, f(x) == f(y) implies x == y. Translated in english, it means that feeding the function with different inputs lead to different outputs. For each outputs of the function, there is only one possible input that could have led to this output.

One interesting consequence is that if a function is not injective, there is no way we can find back the input value that led to a specific output (since there might be several inputs available).

If on the contrary a function is injective, we can build a reverse function on its image (the set of all possible outputs of the function) to find back the input element for a given output.

 

Type level function are not necessarily injective

Now the problem is that upon encountering a dependent type name, the compiler has no guaranty that the corresponding type-level function is injective or not. In fact, we have seen two examples of type-level functions, with one of them (std::common_type) clearly not being injective:

In fact, and if we consider that std::vector has an additional template parameters for the allocator, the const_iterator_t type-level function is clearly not injective either. We do not expect the iterator type to be different for different type of allocator.

 

The compiler cannot deduce the template parameter of a dependent type

To summarize, the compiler is pretty much unable to ensure that a type-level function is injective (*). So it cannot reasonably invert the type-level function and deduce a parameter type T given only a type which depends on that parameter (for there might be several valid T for this same output).

As a consequence, and given our bad for_each function template, the compiler will not be able to deduce the template parameter T given only an iterator:

There might be several T matching the const_iterator type provided as parameter, and consequently, the compiler cannot know which overload to select.

(*): And this is not even taking into account the possibility of explicit template specialization, which basically means that even so we could ensure a type-level function is injective, we could not guaranty it would stay that way.

 

This issue is not specific to C++

All languages that offer the possibility to compute types depending on some other value or types will face the same kind of issue. For instance, in Haskell, the same issue appears, although in a slightly different form.

The following code declares a type-class (interface or type-trait, if you wish) named Func, with a template parameter a. This type-class exposes a type alias Res which depends on the type parameter a.

We provide two instances (specialization, or implementation of the interface, if you wish) of this type-class for integer and string, which show how it looks like practically:

The “equivalent” (in very loose terms) code in terms of C++ would be something like:

Now if we try to define a function which takes a Res a as input, we get a compilation error which says that we cannot deduce the type parameter a from Res a:

The main difference with Haskell is that we get the compilation error at the very definition of the function, while the error occurs at the call site in C++.

 

Ways to circumvent the issue

---

There are different ways we can resolve the ambiguity on the compiler side, by giving it some hints on which specialization should be selected. Let us review some of them.

 

Relying on additional parameters

While the compiler cannot deduce the template parameter of a dependent type name, it is still perfectly able to deduce a template parameter if it appears somewhere else in the signature of the function.

In short, there is no need to give an hint to the compiler if there is something else in the template definition that allows to deduce the type, as shown in this awkward implementation of std::accumulate:

Thanks to the init parameter, the compiler is able to deduce the template parameter T. The following code compiles, and will correctly output 6:

But we do not always have this luxury of having this additional parameter that makes sense.

 

Explicit template specialization

If we cannot rely on an additional parameter to help the compiler deduce a template parameter, we can always help the compiler and explicitly provide it the template parameter it cannot infer.

We can for instance correct our previous example by explicitly requiring for the specialization of for_each for elements of type integers, and it will compile just fine:

But this is kind of annoying, and likely indicates a design issue. In general, a good rule of thumb is to try to fix our design by removing constraints, making the algorithm more generic (the less constraints, the more use cases an algorithm can satisfy), usually removing dependent type names along the way.

In our specific case, we can generalize our for_each function to take the iterator type as template parameter, just like as the STL does:

In addition, and in some instances, relying on explicit specialization is not very practical either: what if the template parameter to explicitly specialize is not the first one?

 

Proxy parameters

In some languages, such as Haskell, we cannot ask for an explicit template specialization: the template parameters have to be deduced from the arguments. The solution then is to fall back on the idea of providing the compiler an additional parameter, whose only purpose is to guide the compiler.

This parameter does not carry any runtime value. It is parameterized on the type needed to guide the type deduction, and its only purpose is to carry this type. We usually call it a proxy parameter:

Or, equivalently, in Haskell:

Thanks to the proxy guiding type deduction, the following code now compiles fine:

In some instances, this trick is useful in C++ as well, especially when explicit specialization is awkward (for instance if the template parameter to specialize is not the first one).

 

Injective type-level functions (Haskell only)

The last solution is to find a way to inform the compiler that the type-level function is injective.

Haskell gives us a way to do so, by letting us explicitly require that the dependent type has to be a brand new type, specific to the instantiation of the type-class, and not an alias to an existing type (by using data instead of type in the declaration below).

Here are two examples of instances (specialization, or implementation of the interface, if you wish) of this type-class for integer and string. In each case, we are required to create a new type (ResInt and ResString here) as output to the type-level function Res:

Now, and because the Haskell compiler knows that the Res type-level function is injective, it accepts the following function and will be able to automatically deduced a from its dependent type.

This is not the perfect solution: creating a new type is a sufficient condition for injectivity, but not a necessary one. So it is a bit over-constraining, but at least offers a solution to this annoying issue.

---

Follow @quduval