Существуют ли какие-либо препятствия в языке C ++, которые не позволяют использовать диапазоны D?

Я не думаю, что существует какое-либо неотъемлемое техническое ограничение в C ++, которое сделало бы невозможным определение системы диапазонов D-стиля и соответствующих алгоритмов в C ++. Самая большая проблема языкового уровня будет заключаться в том, что for-циклы C ++ на основе диапазонов требуют, чтобы begin() и end() могли использоваться в диапазонах, но предполагая, что мы перейдем к определению библиотеки с использованием диапазонов стиля D, расширяя for- на основе диапазонов. петли, чтобы справиться с ними, кажется незначительным изменением.

Основная техническая проблема, с которой я столкнулся при экспериментировании с алгоритмами на диапазонах D-стиля в C ++, заключалась в том, что я не мог сделать алгоритмы такими же быстрыми, как мои реализации на основе итератора (фактически, курсора). Конечно, это могут быть просто реализации моего алгоритма, но я не видел никого, кто предлагал бы разумный набор алгоритмов на основе диапазона D в C ++, против которого я мог бы профилировать. Производительность важна, и стандартная библиотека C ++ должна обеспечивать, по крайней мере, слабоэффективные реализации алгоритмов (общая реализация алгоритма называется слабоэффективной, если она работает по крайней мере так же быстро при применении к структуре данных как пользовательская реализация того же алгоритма с использованием той же структуры данных с использованием того же языка программирования). Мне не удалось создать слабоэффективные алгоритмы на основе диапазонов D-стиля, и моя цель - на самом деле сильно эффективные алгоритмы (аналогичные слабоэффективным, но допускающие любой язык программирования и только предполагающие то же самое базовое оборудование).

Экспериментируя с алгоритмами на основе диапазона D-стиля, я обнаружил, что эти алгоритмы намного сложнее реализовать, чем алгоритмы на основе итераторов, и счел необходимым иметь дело с кладжами, чтобы обойти некоторые из их ограничений. Конечно, не все в том виде, как в настоящее время описываются алгоритмы в C ++, также идеально. Примерный план того, как я хочу изменить алгоритмы и абстракции, с которыми они работают, может быть 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() алгоритм, изменяющий всю последовательность, явно выполняет мутацию на месте (если вы хотите, чтобы версия не выполняла это на месте, просто скопируйте контейнер и примените версию на месте; если у вас есть только не- на месте, вы не можете избежать лишней последовательности, которая может быть непосредственной проблемой, например, для гигантских последовательностей). Предполагая, что это в некотором роде ленивый доступ к исходной последовательности с l-значением обеспечивает пик текущего статуса, что почти наверняка плохо. Это может означать, что ленивая оценка изменяющихся алгоритмов в любом случае не такая уж и хорошая идея.

В любом случае, есть некоторые аспекты C ++, которые делают невозможным немедленное принятие диапазонов D-sytle, хотя те же соображения применимы и к другим абстракциям диапазонов. Я думаю, что эти соображения, таким образом, также несколько выходят за рамки вопроса. Кроме того, очевидного «решения» первой из проблем (добавить сборку мусора) вряд ли получится. Я не знаю, есть ли решение второй проблемы в D. Может появиться решение второй проблемы (предварительно названное operator auto), но мне не известно о конкретном предложении или как на самом деле будет выглядеть такая функция.

Кстати, исследовательская группа диапазонов на самом деле не увязла в каких-либо технических деталях. До сих пор мы просто пытались выяснить, какие проблемы мы на самом деле пытаемся решить, и в некоторой степени охватить область решения. Кроме того, группы вообще не выполняют никакой работы! Фактическая работа всегда выполняется отдельными людьми, часто очень немногими людьми. Поскольку основная часть работы на самом деле заключается в разработке набора абстракций, я ожидал, что основы любых результатов группы по изучению диапазонов будут составлять от 1 до 3 человек, которые имеют некоторое представление о том, что необходимо и как это должно выглядеть.

Мои знания 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
{}

or

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 для диапазона, в котором не было нарезки (например, диапазоны, возвращаемые _ 22_ не может иметь срезы), то результирующие диапазоны не будут срезаны. Для этого 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 if, ни один из которых не может быть заменен специализациями шаблонов, основанными на определенных типах, без необходимости писать новый специализированный шаблон для 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 ++ невозможно сделать что-либо даже отдаленно подобное. Но для разумной реализации диапазонов вам действительно нужно уметь делать такие вещи, как have isInputRange или проверять, компилируется ли конкретный тип с sort - is(typeof(sort(myRange))). Без этого вы не сможете специализировать реализации на основе того, какие типы операций поддерживает конкретный диапазон, вы не можете правильно пересылать атрибуты диапазона при его упаковке (а функции диапазона все время переносят свои аргументы в новые диапазоны) и вы даже не можете должным образом защитить свою функцию от компиляции с типами, которые с ней не работают. И, конечно же, результаты static if и ограничений шаблона также влияют на самоанализ типа (поскольку они влияют на то, что будет и что не будет компилироваться), поэтому эти три функции во многом взаимосвязаны.

На самом деле, основные причины, по которым диапазоны не очень хорошо работают в C ++, - это некоторые причины, по которым метапрограммирование в C ++ примитивно по сравнению с метапрограммированием в D. AFAIK, нет причин, по которым эти функции (или аналогичные) нельзя было добавить в C ++ и решить проблему, но до тех пор, пока в C ++ не появятся возможности метапрограммирования, аналогичные функциям D, диапазоны в C ++ будут серьезно нарушены.

Другие функции, такие как миксины и унифицированный синтаксис вызова функций, также могут помочь, но они далеко не такие фундаментальные. Миксины помогли бы в первую очередь уменьшить дублирование кода, а UFCS помогает в первую очередь сделать так, чтобы общий код мог просто вызывать все функции, как если бы они были функциями-членами, так что если тип определяет конкретную функцию (например, find), тогда это будет используется вместо более общей, бесплатной версии функции (и код по-прежнему работает, если такая функция-член не объявлена, потому что тогда используется бесплатная функция). UFCS принципиально не требуется, и вы даже можете пойти в противоположном направлении и отдать предпочтение бесплатным функциям для всего (как C ++ 11 сделал с begin и end), хотя для этого по сути требуется, чтобы бесплатные функции могли тестировать для существования функции-члена, а затем вызовите функцию-член изнутри, а не используя свои собственные реализации. Итак, вам снова понадобится самоанализ типа вместе с static if и / или ограничениями шаблона.

Как бы мне ни нравились диапазоны, на данный момент я в значительной степени отказался от попыток что-либо сделать с ними на C ++, потому что функций, которые делают их разумными, просто нет. Но если другие люди смогут понять, как это сделать, тем больше у них сил. Тем не менее, независимо от диапазонов, я бы хотел, чтобы C ++ получил такие функции, как ограничения шаблона, static if и самоанализ типов, потому что без них метапрограммирование способом менее приятным, до такой степени, что пока я это делаю все время в D, я почти никогда не делаю этого в C ++.