C++ 11是否支持模板中的类型递归？

Question

我想详细解释这个问题.在许多具有强类型系统的语言中(如Felix,Ocaml,Haskell),您可以通过组合类型构造函数来定义多态列表.这是Felix的定义:

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

在Ocaml:

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

在C中,这是递归的,但既不是多态的也不是组合的:

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

在C++中,如果C++支持类型递归,它将像这样完成:

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

给出了元组(又名对)和变体(但不是Boost中使用的破坏的)的合适定义.或者:

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

鉴于变体的定义略有不同,可能是可以接受的.甚至不可能在C++ <C++ 11中编写它,因为如果没有模板typedef,就没有办法获得多态性,并且没有typedef的合理语法,就无法在范围内获取目标类型.上面的using语法解决了这两个问题,但这并不意味着允许递归.

特别请注意,允许递归对ABI有重大影响,即名称修改(除非名称修改方案允许表示修复点,否则无法完成).

我的问题:需要在C++ 11中工作吗？[假设扩展不会导致无限大的结构]

---

编辑:为了清楚起见,要求是一般结构类型.例如,模板提供了精确的信息

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

是匿名的(结构上)类型,并且对显然是多态的.但是,C++ <C++ 11中的递归无法说明,即使使用指针也是如此.在C++ 11中,您可以声明递归,虽然使用模板typedef(使用新的using语法,=符号的LHS上的表达式在RHS的范围内).

具有多态性和递归的结构(匿名)类型是对类型系统的最低要求.

任何现代类型系统都必须支持多项式类型的仿函数,或者类型系统太过于无法进行任何类型的高级编程.为此所需的组合器通常由类型理论家说明如下:

1 | * | + | fix

其中1是单位类型,*是元组形成,+是变体形成,而修正是递归.这个想法很简单:

如果t是一个类型而u是一个类型,那么t + u和t*u也是类型

在C++中,struct unit {}为1,tuple为*,variant为+,可以使用using =语法获取fixpoints.这不是一个非常匿名的输入,因为fixpoint需要一个模板typedef.

---

编辑:只是C中多态类型构造函数的一个例子:

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

不幸的是,在C中,函数值不是组合的,并且指针形成受左值约束的约束,而类型组合的句法规则本身并不是组合的,但在这里我们可以说:

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

因此,可以递归地应用这些类型构造器(组合器)以获取新类型,而无需创建新的中间类型.在C++中,我们可以轻松修复语法问题:

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];

所以现在你可以写:

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

并且语法是组合的,以及输入.

Answer 1

不,那是不可能的.甚至禁止通过别名模板进行间接递归.

C++ 11,4.5.7/3:

别名模板声明中的type-id不应引用声明的别名模板.别名模板专业化生成的类型不得直接或间接地使用该专业化.[例如:

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

- 结束例子]

Answer 2

如果你想要这个,请坚持你的Felix,Ocaml或Haskell.你很容易意识到很少(没有？)成功语言的类型系统就像那三种一样丰富.在我看来,如果所有语言都相同,那么学习新语言就不值得了.

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

在C++中不起作用,因为别名模板没有定义新类型.它纯粹是一个别名,一个同义词,它等同于它的替代.这是一个功能,顺便说一句.

该别名模板等同于以下Haskell:

type List a = Either () (a, List a)

GHCi拒绝这一点,因为"类型同义词声明中的[循环]"是不允许的.我不确定这是否在C++中被彻底禁止,或者是否被允许但在替换时会导致无限递归.无论哪种方式,它都不起作用.

在C中定义的新类型++的方法是使用struct,class,union,和enum关键字.如果你想要类似下面的Haskell(我坚持Haskell的例子,因为我不知道其他两种语言),那么你需要使用这些关键字.

newtype List a = List (Either () (a, List a))