programar - ¿Hay algún obstáculo en el lenguaje C++ que impida adoptar rangos D?

juego de naves en c++ codigo

Question

Esta es una pregunta cruzada de C ++ / D. El lenguaje de programación D tiene ranges que, en contraste con las bibliotecas de C ++ como Boost.Range , no se basan en pares de iteradores. El grupo de estudio oficial de rangos de C ++ parece haberse atascado al establecer una especificación técnica.

Pregunta : ¿el C ++ 11 actual o el próximo estándar de C ++ 14 tienen algún obstáculo que impida la adopción de rangos D, así como una versión adecuada de <algorithm> - al por mayor?

No sé D o sus rangos lo suficientemente bien, pero parecen perezosos y fáciles de componer, además de ser capaces de proporcionar un superconjunto de los algoritmos de STL. Dada su afirmación de éxito para D, parece muy bueno tenerla como una biblioteca para C ++. Me pregunto cómo fueron las características únicas de D (por ejemplo, combinaciones de cadenas, sintaxis de llamada de función uniforme) para implementar sus rangos, y si C ++ podría imitar eso sin demasiado esfuerzo (por ejemplo, C ++ 14 constexpr parece bastante similar a la evaluación de la función en tiempo de compilación de D )

Nota: Estoy buscando respuestas técnicas, no opiniones si los rangos D son el diseño correcto para tener como una biblioteca de C ++.

Answer 1

Mi conocimiento de C ++ 11 es mucho más limitado de lo que me gustaría, por lo que puede haber características más nuevas que mejoren las cosas que aún no conozco, pero hay tres áreas en las que puedo pensar en este momento que son al menos problemáticas: restricciones de plantilla, static if y tipo introspección.

En D, una función basada en rango usualmente tendrá una restricción de plantilla que indica qué tipo de rangos acepta (por ejemplo, rango de avance frente a rango de acceso aleatorio). Por ejemplo, aquí hay una firma simplificada para std.algorithm.sort :

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

Comprueba que el tipo que se pasa es un rango de acceso aleatorio, que se puede dividir en segmentos y que tiene una propiedad de length . Cualquier tipo que no cumpla con esos requisitos no se compilará con la sort , y cuando la restricción de la plantilla falla, deja claro al programador por qué su tipo no funciona con la sort (en lugar de simplemente dar un error de compilación desagradable en el medio). de la función de plantilla cuando no se compila con el tipo dado).

Ahora, si bien eso puede parecer una mejora de la facilidad de uso en lugar de dar un error de compilación cuando la sort no se compila porque el tipo no tiene las operaciones correctas, en realidad tiene un gran impacto en la sobrecarga de funciones, así como en la introspección de tipos. Por ejemplo, aquí hay dos de las sobrecargas de 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)
{...}

El primero acepta una aguja que es solo un elemento, mientras que el segundo acepta una aguja que es un rango de avance. Los dos pueden tener diferentes tipos de parámetros basados ​​puramente en las restricciones de la plantilla y pueden tener un código internamente diferente. Sin algo como las restricciones de plantilla, no puede tener funciones de plantilla que estén sobrecargadas en los atributos de sus argumentos (en lugar de estar sobrecargadas en los tipos específicos en sí), lo que hace que sea mucho más difícil (si no imposible) tener diferentes implementaciones basadas en el género de rango que se está utilizando (por ejemplo, rango de entrada vs rango de avance) u otros atributos de los tipos que se están utilizando. Se ha estado haciendo algo de trabajo en esta área en C ++ con conceptos e ideas similares, pero AFAIK, C ++ todavía no cuenta con las características necesarias para sobrecargar plantillas (ya sean funciones de plantilla o tipos de plantilla) en función de los atributos de sus tipos de argumento, más bien que especializarse en tipos de argumentos específicos (como ocurre con la especialización de plantillas).

Una característica relacionada sería static if . Es lo mismo que if , excepto que su condición se evalúa en el momento de la compilación, y si es true o false realmente determinará en qué rama se compila y no en qué rama se ejecuta. Le permite bifurcar el código según las condiciones conocidas en el momento de la compilación. p.ej

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

o

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 puede hasta cierto punto, evitar la necesidad de restricciones de plantilla, ya que esencialmente puede colocar las sobrecargas para una función de plantilla dentro de una sola función. p.ej

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

pero eso todavía produce errores más desagradables cuando falla la compilación y en realidad lo hace para que no pueda sobrecargar la plantilla (al menos con la implementación de D), porque la sobrecarga se determina antes de que se cree una instancia de la plantilla. Por lo tanto, puede usar static if para especializar partes de una implementación de plantilla, pero no le proporciona lo suficiente de lo que las restricciones de plantilla hacen que no necesite restricciones de plantilla (o algo similar).

Más bien, static if es excelente para hacer cosas como especializar solo una parte de la implementación de su función o para hacerlo de modo que un tipo de rango pueda heredar adecuadamente los atributos del tipo de rango que está ajustando. Por ejemplo, si llama a std.algorithm.map en una matriz de enteros, el rango resultante puede tener un corte (porque el rango de origen sí lo tiene), mientras que si llamó al map en un rango que no tuvo un corte (por ejemplo, los rangos devueltos por std.algorithm.filter no puede haber rebanado), entonces los rangos resultantes no tendrán rebanado. Para hacer eso, map usa static if compila en opSlice solo cuando el rango de origen lo admite. Actualmente, el código del map que hace esto parece

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);
}
}
}

Este es un código en la definición de tipo del tipo de retorno del map , y si ese código se compila o no depende completamente de los resultados de la static if s, ninguno de los cuales podría reemplazarse con especializaciones de plantilla basadas en tipos específicos sin tener que escriba una nueva plantilla especializada para el map para cada nuevo tipo que use con él (lo que obviamente no es sostenible). Para compilar en código basado en atributos de tipos en lugar de en tipos específicos, realmente necesita algo como static if (que C ++ no tiene actualmente).

El tercer elemento importante del que carece C ++ (y que he tratado más o menos en todo) es la introspección de tipos. El hecho de que pueda hacer algo como is(typeof(binaryFun!pred(haystack.front, needle)) : bool) o isForwardRange!Range es crucial. Sin la capacidad de verificar si un tipo particular tiene un conjunto particular de atributos o que una pieza particular de código se compila, ni siquiera se pueden escribir las condiciones de las restricciones de la plantilla y la static if usa. Por ejemplo, std.range.isInputRange ve algo como esto

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
}));
}

Comprueba que una pieza particular de código compila para el tipo dado. Si lo hace, entonces ese tipo puede usarse como un rango de entrada. Si no lo hace, entonces no puede. AFAIK, es imposible hacer algo tan vagamente como esto en C ++. Pero para implementar de manera segura los rangos, realmente necesita poder hacer cosas como tener isInputRange o probar si un tipo particular compila con sort - is(typeof(sort(myRange))) . Sin eso, no puede especializar implementaciones basadas en qué tipos de operaciones admite un rango en particular, no puede reenviar correctamente los atributos de un rango cuando lo ajusta (y las funciones de rango envuelven sus argumentos en nuevos rangos todo el tiempo), y ni siquiera puede proteger adecuadamente su función contra la compilación con tipos que no funcionarán con ella. Y, por supuesto, los resultados de las restricciones static if y de la plantilla también afectan la introspección de tipo (ya que afectan lo que compilará y lo que no compilará), por lo que las tres características están muy interconectadas.

En realidad, las razones principales por las que los rangos no funcionan muy bien en C ++ son algunas de las razones por las que la metaprogramación en C ++ es primitiva en comparación con la metaprogramación en D. AFAIK, no hay razón para que estas funciones (o las similares) no puedan agregarse a C ++ y solucionen el problema, pero hasta que C ++ tenga capacidades de metaprogramación similares a las de D, los rangos en C ++ se verán seriamente afectados.

Otras características, como los mixins y la Sintaxis de llamada de función uniforme también ayudarían, pero no son tan fundamentales. Los mixins ayudarían principalmente a reducir la duplicación de código, y UFCS ayudará principalmente a hacer que el código genérico pueda llamar a todas las funciones como si fueran funciones miembro, de modo que si un tipo define una función en particular (por ejemplo, find ) sería se usa en lugar de la versión más general de la función gratuita (y el código aún funciona si no se declara dicha función miembro, porque entonces se usa la función libre). El UFCS no es fundamentalmente requerido, e incluso podría ir en la dirección opuesta y favorecer las funciones gratuitas para todo (como hizo C ++ 11 con el begin y el end ), aunque para hacerlo bien, esencialmente se requiere que las funciones libres puedan probarse. para la existencia de la función miembro y luego llame a la función miembro internamente en lugar de usar sus propias implementaciones. Entonces, de nuevo, necesita introspección de tipo junto con restricciones static if y / o de plantilla.

Por mucho que me encanten los rangos, en este punto, me he dado por vencido al intentar hacer algo con ellos en C ++, porque las características para que estén sanos simplemente no están allí. Pero si otras personas pueden descubrir cómo hacerlo, más poder para ellos. Sin embargo, independientemente de los rangos, me encantaría ver que C ++ obtenga características tales como restricciones de plantilla, static if y tipo introspección, porque sin ellas, la metaprogramación es mucho menos placentera, hasta el punto de que mientras lo hago todo el tiempo en D, Casi nunca lo hago en C ++.

Answer 2

No creo que exista ninguna limitación técnica inherente en C ++ que haga imposible definir un sistema de rangos de estilo D y algoritmos correspondientes en C ++. El mayor problema de nivel de lenguaje sería que el rango basado for C ++ for -loops requiere que se pueda usar begin() y end() en los rangos, pero suponiendo que nos ocuparíamos de definir una biblioteca utilizando rangos de estilo D, extendiendo el rango -basado for -loops para tratar con ellos parece un cambio marginal.

El principal problema técnico que encontré al experimentar con algoritmos en rangos de estilo D en C ++ fue que no podía hacer los algoritmos tan rápidos como las implementaciones basadas en iteradores (en realidad, cursores). Por supuesto, estas podrían ser solo mis implementaciones de algoritmos, pero no he visto a nadie que ofrezca un conjunto razonable de algoritmos basados ​​en el rango de estilo D en C ++ contra los que pudiera hacer un perfil. El rendimiento es importante y la biblioteca estándar de C ++ debe proporcionar, al menos, implementaciones de algoritmos poco eficientes (una implementación genérica de un algoritmo se denomina débilmente eficiente si es al menos tan rápida cuando se aplica a una estructura de datos como una implementación personalizada del mismo algoritmo utilizando la misma estructura de datos utilizando el mismo lenguaje de programación). No pude crear algoritmos poco eficientes basados ​​en rangos de estilo D y mi objetivo son algoritmos muy eficientes (similares a los poco eficientes pero que permiten cualquier lenguaje de programación y solo asumiendo el mismo hardware subyacente).

Al experimentar con los algoritmos basados ​​en el rango del estilo D, los algoritmos eran mucho más difíciles de implementar que los algoritmos basados ​​en iteradores y encontré que era necesario lidiar con kludges para solucionar algunas de sus limitaciones. Por supuesto, tampoco todo lo que se especifica en los algoritmos actuales en C ++ es perfecto. Un resumen aproximado de cómo quiero cambiar los algoritmos y las abstracciones con las que trabajan está en la página de STL 2.0 . Sin embargo, esta página no trata mucho con los rangos, ya que este es un tema relacionado pero algo diferente. Preferiría imaginar rangos basados ​​en iteradores (bueno, realmente cursor) en lugar de rangos de estilo D, pero la pregunta no era sobre eso.

Un problema técnico que enfrentan todas las abstracciones de rango en C ++ es tener que lidiar con objetos temporales de una manera razonable. Por ejemplo, considera esta expresión:

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

Dependiendo de si ranges::sort() o ranges::unique() son perezosos o no, la representación del rango temporal debe ser tratada. El simple hecho de proporcionar una vista del rango de origen no es una opción para ninguno de estos algoritmos porque el objeto temporal desaparecerá al final de la expresión. Una posibilidad podría ser mover el rango si aparece como valor r, que requiere un resultado diferente para ambos ranges::sort() y ranges::unique() para distinguir los casos en que el argumento real sea un objeto temporal o un objeto objeto mantenido vivo independientemente. D no tiene este problema en particular porque se recolecta basura y, por lo tanto, el rango de origen se mantendría vivo en cualquier caso.

El ejemplo anterior también muestra uno de los problemas con el posible algoritmo evaluado perezoso: dado que cualquier tipo, incluidos los tipos que no pueden explicarse de otra manera, puede deducirse mediante variables auto o funciones de plantilla, no hay nada que obligue a la evaluación perezosa al final de una expresión. Por lo tanto, los resultados de las plantillas de expresión se pueden obtener y el algoritmo no se ejecuta realmente. Es decir, si se pasa un valor l a un algoritmo, es necesario asegurarse de que la expresión se evalúe realmente para obtener el efecto real. Por ejemplo, cualquier algoritmo sort() mute toda la secuencia hace claramente la mutación en el lugar (si desea que una versión no lo haga en el lugar, simplemente copie el contenedor y aplique la versión en el lugar; si solo tiene una La versión no en el lugar no puede evitar la secuencia adicional, que puede ser un problema inmediato, por ejemplo, para secuencias gigantescas. Suponiendo que sea perezoso de alguna manera, el acceso de valor l a la secuencia original proporciona un pico en el estado actual, lo que es casi seguro que es algo malo. Esto puede implicar que la evaluación perezosa de algoritmos de mutación no es una gran idea de todos modos.

En cualquier caso, hay algunos aspectos de C ++ que hacen que sea imposible adoptar inmediatamente los rangos D-sytle, aunque las mismas consideraciones también se aplican a otras abstracciones de rangos. Creo que estas consideraciones están, por lo tanto, algo fuera del alcance de la pregunta, también. Además, es poco probable que ocurra la "solución" obvia al primero de los problemas (agregar recolección de basura). No sé si hay una solución para el segundo problema en D. Puede surgir una solución para el segundo problema (el operador se ha denominado provisionalmente), pero no estoy al tanto de una propuesta concreta o de cómo se vería esa característica. me gusta.

Por cierto, el Grupo de estudio de rangos no está realmente atascado por ningún detalle técnico. Hasta ahora, simplemente tratamos de averiguar qué problemas estamos tratando de resolver y de explorar, en cierta medida, el espacio de la solución. Además, los grupos generalmente no hacen ningún trabajo, en absoluto! El trabajo real siempre es realizado por individuos, a menudo por muy pocos individuos. Dado que la mayor parte del trabajo consiste en diseñar un conjunto de abstracciones, esperaría que los fundamentos de cualquier resultado del Grupo de estudio de rangos estén a cargo de 1 a 3 personas que tengan una visión de lo que se necesita y de cómo debería ser.