是否存在阻止采用D范围的C++语言障碍？

Question

这是一个C++/D交叉问题.的d的编程语言具有范围件是在对比到C++库如Boost.Range -不是基于迭代器对.官方的C++ Ranges Study Group似乎陷入了制定技术规范的困境.

问题:当前的C++ 11或即将推出的C++ 14标准是否有任何阻碍采用D范围的障碍 - 以及<algorithm>- 批发的适当范围版本？

我不太了解D或它的范围,但它们似乎是懒惰和可组合的,并且能够提供STL算法的超集.鉴于他们声称D的成功,作为C++库可能会非常好.我想知道D的独特功能(例如字符串mixins,统一函数调用语法)是如何实现其范围的,以及C++是否可以模仿而不需要太多努力(例如C++ 14 constexpr看起来与D编译时功能评估非常相似)

注意:我正在寻求技术答案,而不是D系列作为C++库的正确设计.

Answer 1

我不认为C++中存在任何固有的技术限制,这使得无法在C++中定义D风格范围和相应算法的系统.最大的语言级问题是基于C++范围的for-loops需要begin()并且end()可以在范围上使用,但假设我们将使用D样式范围定义库的长度,扩展基于范围的for-loops来处理他们似乎是一个微小的变化.

我在C++中使用D风格范围的算法进行实验时遇到的主要技术问题是,我无法使算法与基于迭代器(实际上是游标)的实现一样快.当然,这可能只是我的算法实现,但我没有看到任何人在C++中提供一套合理的基于D风格的算法,我可以对其进行分析.性能很重要,C++标准库至少应提供弱效的算法实现(如果算法的通用实现在应用于数据结构时至少与其自定义实现一样快,则称其效率很低算法使用相同的编程语言使用相同的数据结构).我无法创建基于D风格范围的弱效算法,我的目标实际上是非常有效的算法(类似于弱效但允许任何编程语言并且只假设相同的底层硬件).

在尝试使用基于D风格的算法时,我发现算法比基于迭代器的算法更难实现,并且发现有必要处理kludges来解决它们的一些局限性.当然,并非C++中指定的当前方式算法中的所有内容都是完美的.关于我如何更改算法及其工作抽象的概述在may STL 2.0页面上.然而,这个页面并没有真正涉及范围,因为这是一个相关但有些不同的主题.我宁愿设想基于范围的迭代器(好的,真正的游标)而不是D风格的范围,但问题不在于此.

C++中所有范围抽象的一个技术问题是必须以合理的方式处理临时对象.例如,考虑以下表达式:

auto result = ranges::unique(ranges::sort(std::vector<int>{ read_integers() }));

在从属的是否ranges::sort()或ranges::unique()懒惰与否,需要被处理的临时范围的表示.仅提供源范围的视图不是这些算法中的任何一个的选项,因为临时对象将在表达式的末尾消失.一种可能性是移动范围,如果它作为r值进入,需要两者的不同结果,ranges::sort()并ranges::unique()区分实际参数的情况是临时对象或独立保持活动的对象.D没有这个特殊问题,因为它是垃圾收集的,因此,在任何一种情况下,源范围都将保持活跃.

上面的例子也显示了可能延迟评估算法的一个问题:因为任何类型,包括不能拼写出来的类型,都可以通过auto变量或模板化函数推导出来,没有什么可以强迫最终的懒惰评估.一种表达.因此,可以获得表达模板的结果,并且不会真正执行算法.也就是说,如果将l值传递给算法,则需要确保实际评估表达式以获得实际效果.例如,任何sort()改变整个序列的算法都可以清楚地进行原位突变(如果你想要一个版本不能就地复制容器并应用就地版本;如果你只有一个非in -place版本你不能避免额外的序列,这可能是一个直接的问题,例如,对于巨大的序列).假设它在某种程度上是懒惰的,对原始序列的l值访问提供了当前状态的峰值,这几乎肯定是一件坏事.这可能意味着对变异算法的懒惰评估无论如何都不是一个好主意.

在任何情况下,C++的某些方面使得不可能立即采用D-sytle范围,尽管相同的考虑因素也适用于其他范围抽象.因此,我认为这些考虑因素在某种程度上也超出了问题的范围.此外,第一个问题(添加垃圾收集)的明显"解决方案"不太可能发生.我不知道是否有解决D中的第二个问题.可能会出现第二个问题的解决方案(暂时称为运营商自动),但我不知道具体的提案或这样的功能实际上看起来如何喜欢.

顺便说一句,Ranges Study Group并没有因任何技术细节而陷入困境.到目前为止,我们只是试图找出我们实际尝试解决的问题,并在某种程度上确定解决方案空间的范围.此外,团体通常根本没有完成任何工作!实际工作总是由个人完成,通常由极少数人完成.由于工作的主要部分实际上是设计一组抽象,我希望Ranges Study Group的任何结果的基础都是由1到3个人完成的,他们对需要的东西以及它应该是什么样子有一些看法.

Answer 2

我的C++ 11知识比我想要的更有限,所以可能有更新的功能可以改进我还不知道的东西,但目前我可以想到三个方面这至少是有问题的:模板约束static if,和类型内省.

在D中,基于范围的函数通常会在其上具有模板约束,指示它接受哪种类型的范围(例如,前向范围与随机访问范围).例如,这是一个简化的签名std.algorithm.sort:

auto sort(alias less = "a < b", Range)(Range r)
    if(isRandomAccessRange!Range &&
       hasSlicing!Range &&
       hasLength!Range)
{...}

它检查传入的类型是随机访问范围,可以切片,还是具有length属性.任何不满足这些要求的类型都不会编译sort,当模板约束失败时,它会让程序员明白为什么它们的类型不能使用sort(而不是只是在中间给出一个讨厌的编译器错误).模板化函数无法使用给定类型进行编译时).

现在,虽然sort由于类型没有正确的操作而只是在编译失败时只是给出编译错误,这可能看起来像是一种可用性改进,但它实际上对函数重载以及类型内省有很大的影响.例如,这里有两个std.algorithm.find重载:

R find(alias pred = "a == b", R, E)(R haystack, E needle)
    if(isInputRange!R &&
       is(typeof(binaryFun!pred(haystack.front, needle)) : bool))
{...}


R1 find(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle)
    if(isForwardRange!R1 && isForwardRange!R2 &&
       is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool) &&
       !isRandomAccessRange!R1)
{...}

第一个接受仅为单个元素的针,而第二个接受针是前向范围的针.这两者可以完全基于模板约束而具有不同的参数类型,并且可以在内部具有完全不同的代码.如果没有像模板约束这样的东西,你就不能拥有在参数属性上重载的模板化函数(而不是在特定类型本身上重载),这使得基于的不同实现变得更加困难(如果不是不可能的话)正在使用的范围类型(​​例如输入范围与前向范围)或所使用类型的其他属性.在C++这个领域已经做了一些有关概念和类似想法的工作,但是AFAIK,C++仍然严重缺乏基于其参数类型的属性来重载模板(无论是模板化函数还是模板化类型)所需的特性.而不是专门针对特定的参数类型(与模板特化一样).

相关的功能将是static if.它是相同的if,除了它的条件在编译时被评估,以及它是否true或false将实际确定编译哪个分支而不是运行哪个分支.它允许您根据编译时已知的条件分支代码.例如

static if(isDynamicArray!T)
{}
else
{}

要么

static if(isRandomAccessRange!Range)
{}
else static if(isBidirectionalRange!Range)
{}
else static if(isForwardRange!Range)
{}
else static if(isInputRange!Range)
{}
else
    static assert(0, Range.stringof ~ " is not a valid range!");

static if可以在某种程度上消除模板约束的需要,因为您可以将模板化函数的重载放在单个函数中.例如

R find(alias pred = "a == b", R, E)(R haystack, E needle)
{
    static if(isInputRange!R &&
       is(typeof(binaryFun!pred(haystack.front, needle)) : bool))
    {...}
    else static if(isForwardRange!R1 && isForwardRange!R2 &&
       is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool) &&
       !isRandomAccessRange!R1)
    {...}
}

但是当编译失败时仍然会导致更糟糕的错误并且实际上使得你不能重载模板(至少使用D的实现),因为在模板实例化之前确定了重载.因此,您可以使用static if专门化模板实现的各个部分,但它并不能让您充分了解哪些模板约束使您不需要模板约束(或类似的东西).

相反,static if它非常适合做一些事情,比如专门设计一个函数的实现,或者使它成为一个范围类型可以正确地继承它包装的范围类型的属性.例如,如果调用std.algorithm.map一个整数数组,结果范围可以有切片(因为源范围有),而如果你调用map了没有切片的范围(例如返回的范围std.algorithm.filter不能切片) ),然后结果范围将没有切片.为此,仅在源范围支持时才map使用static if编译opSlice.目前,map执行此操作的代码看起来像

static if (hasSlicing!R)
{
    static if (is(typeof(_input[ulong.max .. ulong.max])))
        private alias opSlice_t = ulong;
    else
        private alias opSlice_t = uint;

    static if (hasLength!R)
    {
        auto opSlice(opSlice_t low, opSlice_t high)
        {
            return typeof(this)(_input[low .. high]);
        }
    }
    else static if (is(typeof(_input[opSlice_t.max .. $])))
    {
        struct DollarToken{}
        enum opDollar = DollarToken.init;
        auto opSlice(opSlice_t low, DollarToken)
        {
            return typeof(this)(_input[low .. $]);
        }

        auto opSlice(opSlice_t low, opSlice_t high)
        {
            return this[low .. $].take(high - low);
        }
    }
}

这是map返回类型的类型定义中的代码,该代码是否编译完全取决于static ifs 的结果,其中任何一个都不能替换为基于特定类型的模板特化而不必编写新的map与您一起使用的每种新类型的专用模板(显然不是站得住脚的).为了在代码中基于类型的属性而不是特定类型进行编译,你真的需要类似的东西static if(C++当前没有).

C++缺乏的第三个主要项目(我或多或少都涉及到它)是类型内省.事实上,你可以做一些类似is(typeof(binaryFun!pred(haystack.front, needle)) : bool)或isForwardRange!Range至关重要的事情.如果没有能力检查特定类型是否具有特定的属性集或者是否编译了特定的代码,您甚至无法编写模板约束和static if使用的条件.例如,std.range.isInputRange看起来像这样

template isInputRange(R)
{
    enum bool isInputRange = is(typeof(
    {
        R r = void;       // can define a range object
        if (r.empty) {}   // can test for empty
        r.popFront();     // can invoke popFront()
        auto h = r.front; // can get the front of the range
    }));
}

它检查特定的代码片段是否针对给定类型进行编译.如果是,则该类型可以用作输入范围.如果没有,那就不行了.AFAIK,在C++中甚至不可能像这样模糊地做任何事情.但要明智地实现范围,你真的需要能够做类似的东西isInputRange或测试特定类型是否编译sort- is(typeof(sort(myRange))).如果没有这个,你就不能根据特定范围支持的操作类型来专门化实现,在包装时你不能正确转发范围的属性(并且范围函数一直将它们的参数包装在新的范围中),以及你甚至无法正确保护你的功能,防止使用不能使用它的类型进行编译.当然,static if模板约束的结果也会影响类型内省(因为它们会影响将要编译的内容),因此三个特征之间存在很大的相互关联.

实际上,范围在C++中不能很好地工作的主要原因是与D中的元编程相比,C++中的元编程是原始的一些原因.AFAIK,没有理由不能将这些功能(或类似功能)添加到C++中并修复问题,但是在C++具有类似于D的元编程功能之前,C++中的范围将严重受损.

其他功能,如mixins和Uniform Function Call Syntax也会有所帮助,但它们远没有那么基本.Mixins主要帮助减少代码重复,UFCS主要帮助实现它,使得通用代码可以像调用成员函数一样调用所有函数,这样如果一个类型恰好定义了一个特定的函数(例如find)那么就会使用它而不是更通用的自由函数版本(如果没有声明这样的成员函数,代码仍然有效,因为那时使用自由函数).UFCS并不是从根本上要求的,你甚至可以朝着相反的方向前进并支持所有内容的自由函数(比如C++ 11用的begin和end),尽管这样做很好,它本质上要求自由函数能够测试存在成员函数,然后在内部调用成员函数而不是使用自己的实现.因此,您需要再次键入内省static if和/或模板约束.

尽管我喜欢范围,但在这一点上,我几乎已经放弃了尝试用C++做任何事情,因为让它们健全的功能并不存在.但是,如果其他人能够弄清楚如何去做,那就更有力了.无论范围的,虽然,我很乐意看到C++增益功能,如模板的约束,static if并键入反省,因为没有他们,元编程的方式不太愉快,给点意见,虽然我做这一切的时候在d,我几乎永远不要用C++做.