6

我想详细解释这个问题。在许多具有强类型系统的语言(如 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 中编写它,因为没有模板类型定义,就无法获得多态性,并且没有类型定义的合理语法,就无法获得范围内的目标类型。上面的 using 语法解决了这两个问题,但这并不意味着允许递归。

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

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


编辑:为了清楚起见,要求是一般结构类型。模板正好提供,例如

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

是匿名(结构上)类型的,并且 pair 显然是多态的。然而,不能说明 C++ < C++11 中的递归,甚至不能用指针说明。在 C++11 中,您可以声明递归,尽管使用模板 typedef(使用新的 using 语法,= 符号的 LHS 上的表达式在 RHS 的范围内)。

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

任何现代类型系统都必须支持多项式类型函子,否则类型系统太笨拙而无法进行任何高级编程。为此所需的组合子通常由类型理论家陈述,例如:

1 | * | + | fix

其中 1 是单元类型,* 是元组形式,+ 是变体形式,fix 是递归。这个想法很简单:

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

在 C++ 中,struct unit{} 是 1,tuple 是 *,variant 是 +,并且可以使用 using = 语法获得固定点。这不是完全匿名的输入,因为固定点需要模板 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>>>

语法是组合的,打字也是。

4

5 回答 5

10

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

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

—结束示例]

于 2012-04-25T18:57:27.800 回答
10

如果你想要这个,坚持你的 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++ 中定义新类型的方法是使用structclassunionenum关键字。如果您想要类似以下 Haskell 的内容(我坚持使用 Haskell 示例,因为我不了解其他两种语言),那么您需要使用这些关键字。

newtype List a = List (Either () (a, List a))
于 2012-04-25T20:47:03.040 回答
2

我认为您可能需要查看您的类型理论,因为您的一些断言是不正确的。

让我们解决您的主要问题(和反手点) - 正如其他人指出的那样,您请求的类型的类型递归是不允许的。这并不意味着c++ 不支持类型递归。它很好地支持它。您请求的类型递归是类型名称递归,这是一种语法风格,实际上对实际类型系统没有影响。

C++ 允许通过代理进行元组成员递归。例如,c++ 允许

class A
{
    A * oneOfMe_;
};

那是具有实际后果的类型递归。(显然,没有内部代理表示,任何语言都无法做到这一点,因为否则大小是无限递归的)。

C++ 还允许翻译时多态性,它允许创建与您可以使用名称递归创建的任何类型一样的对象。名称递归仅用于向成员卸载类型或在类型系统中提供翻译时行为分配。类型标签、类型特征等是众所周知的 C++ 习惯用法。

为了证明类型名称递归不会向类型系统添加功能,只需要指出 c++ 的类型系统允许完全图灵完备的类型计算,使用编译时常量(及其类型列表)的元编程,通过简单的映射命名为常量。这意味着有一个函数 MakeItC++:YourIdeaOfPrettyName->TypeParametrisedByTypelistOfInts 可以生成您想要的任何图灵可计算类型系统。

如您所知,作为类型论的学生,变体是元组产品的对偶。在类型类别中,变体的任何属性都具有元组产品的双重属性,箭头反转。如果您始终使用对偶性工作,则不会获得具有“新功能”的属性(就类型计算而言)。所以在类型计算的层面上,你显然不需要变体。(这也应该从图灵完备性中显而易见。)

但是,就命令式语言的运行时行为而言,您确实会得到不同的行为。这是不好的行为。产品限制语义,变体放松语义。你永远不应该想要这个,因为它可以证明会破坏代码的正确性。静态类型编程语言的历史一直朝着在类型系统中越来越多地表达语义的方向发展,目标是编译器应该能够理解程序何时不是你想要的。目标是将编译器变成程序验证系统。

例如,使用类型单位,您可以表示特定值不仅仅是一个,int而是实际上是以米每平方秒为单位测量的加速度。分配一个以英尺/小时表示的速度除以分钟的时间跨度的值不应该只是将这两个值相除 - 它应该注意转换是必要的(并且要么执行它,要么编译失败,或者......做正确的事事物)。分配一个力应该编译失败。例如,对程序意义进行这些检查可能会给我们带来更多的火星探索。

变体是相反的方向。当然,“如果你编码正确,它们就可以正常工作”,但这不是代码验证的重点。他们可证明添加代码位点,其中不熟悉当前类型用法的不同工程师可以引入不正确的语义假设而不会翻译失败。而且,总是存在一种代码转换,它将命令式代码部分从不安全地使用变体的部分更改为使用经过语义验证的非变体类型的部分,因此它们的使用也“总是次优的”。

变体的大多数运行时使用通常是更好地封装在运行时多态中的那些。运行时多态性具有静态验证的语义,可能具有相关的运行时不变检查,并且与变体不同(总和类型在一个代码轨迹中普遍声明)实际上支持开闭原则。由于需要在一个位置声明变体,因此每次向总和添加新的函数类型时都必须更改该位置。这意味着代码永远不会更改,因此可能会引入错误。但是,运行时多态性允许将新行为添加到与其他行为不同的代码位置中。

(此外,大多数真正的语言类型系统无论如何都不是分布式的。(a, b | c) =/= (a, b) | (a, c) 那么这里有什么意义呢?)

在没有获得该领域经验的情况下,我会谨慎地就什么使类型系统变得更好做出笼统的陈述,特别是如果你的观点是具有挑衅性和政治性并实施变革。我在您的帖子中没有看到任何实际上指向任何计算机语言的健康变化的内容。我没有看到功能、安全性或任何其他实际的现实问题得到解决。我完全喜欢类型理论。我认为每个计算机科学家都应该了解类别理论和编程语言的指称语义(领域理论、笛卡尔类别,所有好东西)。我认为,如果更多的人将 Curry-Howard 同构理解为本体论宣言,那么建构主义逻辑会得到更多尊重。

但这些都没有提供攻击 c++ 类型系统的理由。几乎每种语言都有合法的攻击——类型名称递归和变体可用性不是它们。


编辑:由于我关于图灵完整性的观点似乎没有被理解,也没有我对使用类型标签和特征来卸载类型计算的 c++ 方式的评论,也许一个例子是有序的。

现在,OP 声称希望在列表的用例中使用它,我之前在布局上的观点很容易处理。更好的是,只需使用 std::list。但从其他评论和其他地方来看,我认为他们真的希望这适用于 Felix->C++ 翻译。

所以,我认为 OP 认为他们想要的是

template <typename Type>
class SomeClass
{
    // ...
};

然后能够构建一个类型

SomeClass< /*insert the SomeClass<...> type created here*/ >

我已经提到这只是一个想要的命名约定。没有人想要类型名——它们是翻译过程的瞬态。真正想要的是您稍后在类型的结构组合中将使用 Type 做什么。它将用于类型名计算以生成成员数据和方法签名。

所以,在 C++ 中可以做的是

struct SelfTag {};

然后,当你想引用 self 时,只需将这个类型标签放在那里。

当进行类型计算有意义时,您有一个模板专业化SelfTag,它将替换SomeClass<SelfTag>而不是替换SelfTag类型计算的适当位置。

我的观点是,c++ 类型系统是图灵完备的——这比我认为每次我写的时候 OP 正在阅读的内容要多得多。 可以进行任何类型计算(给定编译器递归的约束),这确实意味着如果您在使用完全不同的语言的一个类型系统中遇到问题,您可以在此处找到翻译。我希望这能让事情更清楚地说明我的观点。回来说“好吧,你仍然不能在类型系统中做 XYZ”显然没有抓住重点。

于 2012-04-26T00:41:00.843 回答
0

C++ 确实有“奇怪地重复出现的模板模式”或 CRTP。但是,它并不特定于 C++11。这意味着您可以执行以下操作(从Wikipedia无耻地复制):

template <typename T>
struct base
{
    // ...
};
struct derived : base<derived>
{
    // ...
};
于 2012-04-25T19:22:19.287 回答
0

@jpalcek 回答了我的问题。但是,我的实际问题(如示例中所暗示的)可以在没有这样的递归别名的情况下解决:

// core combinators
struct unit;
struct point;
template<class T,class U> struct fix;
template<class T, class U> struct tup2;
template<class T, class U> struct var2;

template <> struct   
  fix<
    point,
    var2<unit, tup2<int,point> > 
  > 
{ 
  // definition goes here
};

使用 fix 和 point 类型来表示递归。我碰巧不需要定义任何模板,我只需要定义专业。我需要的是一个在两个不同的翻译单元中相同的名称,用于外部链接:名称必须是类型结构的函数。

@Ex0du5 提示考虑这一点。实际的解决方案也与多年前 Gabriel des Rois 的来信有关。我要感谢所有做出贡献的人。

于 2012-04-28T03:36:35.680 回答