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

Ответ 1

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

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

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

Одна техническая проблема: все абстракции диапазона в С++ do face имеют дело с временными объектами разумным образом. Например, рассмотрим это выражение:

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-value обеспечивает пик в текущем состоянии, что почти наверняка плохо. Это может означать, что ленивая оценка алгоритмов мутации не является такой замечательной идеей.

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

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

Ответ 2

Знание My С++ 11 гораздо более ограниченное, чем я хотел бы, так что могут быть более новые функции, которые улучшают вещи, о которых я еще не знаю, но есть три области, которые я могу придумать на данный момент, которые по крайней мере проблематичны: ограничения шаблона, static if и тип introspection.

В 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)
{...}

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

Связанная функция будет 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 if s, ни один из которых не может быть заменен специалистами шаблонов на основе конкретных типы без необходимости писать новый специализированный шаблон для map для каждого нового типа, который вы используете с ним (что, очевидно, не является приемлемым). Для компиляции кода, основанного на атрибутах типов, а не с конкретными типами, вам действительно нужно что-то вроде static if (которого С++ в настоящее время не имеет).

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

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

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

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