Does C++11 support types recursion in templates?

Question

I want to explain the question in detail. In many languages with strong type systems (like Felix, Ocaml, Haskell) you can define a polymorphic list by composing type constructors. Here's the Felix definition:

typedef list[T] = 1 + T * list[T];
typedef list[T] = (1 + T * self) as self;

In Ocaml:

type 'a list = Empty | Cons ('a, 'a list)

In C, this is recursive but neither polymorphic nor compositional:

struct int_list { int elt; struct int_list *next; };

In C++ it would be done like this, if C++ supported type recursion:

struct unit {};
template<typename T>
    using list<T> = variant< unit, tuple<T, list<T>> >;

given a suitable definition for tuple (aka pair) and variant (but not the broken one used in Boost). Alternatively:

    using list<T> = variant< unit, tuple<T, &list<T>> >;

might be acceptable given a slightly different definition of variant. It was not possible to even write this in C++ < C++11 because without template typedefs, there's no way to get polymorphism, and without a sane syntax for typedefs, there's no way to get the target type in scope. The using syntax above solves both these problems, however this does not imply recursion is permitted.

In particular please note that allowing recursion has a major impact on the ABI, i.e. on name mangling (it can't be done unless the name mangling scheme allows for representation of fixpoints).

My question: is required to work in C++11? [Assuming the expansion doesn't result in an infinitely large struct]

---

Edit: just to be clear, the requirement is for general structural typing. Templates provide precisely that, for example

pair<int, double>
pair<int, pair <long, double> >

are anonymously (structurally) typed, and pair is clearly polymorphic. However recursion in C++ < C++11 cannot be stated, not even with a pointer. In C++11 you can state the recursion, albeit with a template typedef (with the new using syntax the expression on the LHS of the = sign is in scope on the RHS).

Structural (anonymous) typing with polymorphism and recursion are minimal requirements for a type system.

Any modern type system must support polynomial type functors or the type system is too clumbsy to do any kind of high level programming. The combinators required for this are usually stated by type theoreticians like:

1 | * | + | fix

where 1 is the unit type, * is tuple formation, + is variant formation, and fix is recursion. The idea is simply that:

if t is a type and u is a type then t + u and t * u are also types

In C++, struct unit{} is 1, tuple is *, variant is + and fixpoints might be obtained with the using = syntax. It's not quite anonymous typing because the fixpoint would require a template typedef.

---

Edit: Just an example of polymorphic type constructor in C:

T*          // pointer formation
T (*)(U)    // one argument function type
T[2]        // array

Unfortunately in C, function values aren't compositional, and pointer formation is subject to lvalue constraint, and the syntactic rules for type composition are not themselves compositional, but here we can say:

if T is a type T* is a type
if T and U are types, T (*)(U) is a type
if T is a type T[2] is a type

so these type constuctors (combinators) can be applied recursively to get new types without having to create a new intermediate type. In C++ we can easily fix the syntactic problem:

template<typename T> using ptr<T> = T*;
template<typename T, typename U> using fun<T,U> = T (*)(U);
template<typename T> using arr2<T> = T[2];

so now you can write:

arr2<fun<double, ptr<int>>>

and the syntax is compositional, as well as the typing.

Answer 1

No, that is not possible. Even indirect recursion through alias templates is forbidden.

C++11, 4.5.7/3:

The type-id in an alias template declaration shall not refer to the alias template being declared. The type produced by an alias template specialization shall not directly or indirectly make use of that specialization. [ Example:

template <class T> struct A;
template <class T> using B = typename A<T>::U;
template <class T> struct A {
typedef B<T> U;
};
B<short> b; // error: instantiation of B<short> uses own type via A<short>::U

— end example ]