Octubre de 2017
Volumen 32, número 10
C++: de los algoritmos a las corrutinas de C++
Por Kenny Kerr
Hay un algoritmo de biblioteca estándar de C++ llamado iota que siempre me ha intrigado. Tiene un nombre curioso y una función interesante. La palabra iota es el nombre de una letra del alfabeto griego. Se suele usar en inglés para referirse a una cantidad muy pequeña y, a menudo, la cantidad negativa, no la inferior, y procede de una cita del Evangelio de Mateo (Nuevo Testamento). Esta idea de cantidad muy pequeña está relacionada con la función del algoritmo iota. Su función es completar un rango con valores que se incrementan en una pequeña cantidad. Para ello, se almacena el valor inicial y se incrementa hasta que se completa el rango. De esta forma:
#include <numeric>
int main()
{
int range[10];
// Range: Random missile launch codes
std::iota(std::begin(range), std::end(range), 0);
// Range: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
}
A menudo se dice que los desarrolladores de C++ deberían eliminar todos los bucles for vacíos y reemplazarlos por algoritmos. Ciertamente, el algoritmo iota cumple las condiciones, ya que sustituye el bucle for que cualquier desarrollador de C o C++ ha escrito, sin duda, miles de veces. Puede imaginar el posible aspecto de la implementación de la biblioteca estándar de C++:
namespace std
{
template <typename Iterator, typename Type>
void iota(Iterator first, Iterator last, Type value)
{
for (; first != last; ++first, ++value)
{
*first = value;
}
}
}
Sin duda, no le gustaría verse atrapado en la revisión de este código. A menos que sea un desarrollador de bibliotecas, por supuesto. El algoritmo iota me ahorra el trabajo de escribir ese bucle for, y eso es fantástico, pero, ¿sabe una cosa? Nunca lo he usado en la fase de producción. Normalmente, sucede lo siguiente: Necesito un rango de valores. Eso es algo tan fundamental en informática que debe existir un algoritmo estándar para ello. De nuevo, exploro la lista de bit.ly/2i5WZRc y descubro iota. Veo que necesita un rango para completarlo con valores. Veamos, cuál es el rango más económico que puedo encontrar... A continuación, elaboro un listado para comprobar que está todo bien mediante... un bucle for:
#include <numeric>
#include <stdio.h>
int main()
{
int range[10];
std::iota(std::begin(range), std::end(range), 0);
for (int i : range)
{
printf("%d\n", i);
}
}
Sinceramente, lo único que me gusta de este código es el bucle for basado en rango. El problema es, sencillamente, que no necesito ni quiero ese rango. No quiero tener que crear un contenedor que contenga los valores para poder iterarlos. ¿Qué pasa si necesito muchos más valores? Prefiero escribir el bucle for por mí mismo:
#include <stdio.h>
int main()
{
for (int i = 0; i != 10; ++i)
{
printf("%d\n", i);
}
}
Además, para echar sal en la herida, esto implica escribir mucho menos. Desde luego, sería agradable que hubiera una función similar a iota que pudiera generar, de alguna manera, un rango de valores que un bucle for basado en rango pudiera consumir sin necesidad de usar un contenedor. Recientemente, estaba examinando un libro sobre el lenguaje Python y observé que tiene una función integrada denominada range. Puedo escribir el mismo programa en Python así:
for i in range(0, 10):
print(i)
Cuidado con esa sangría. Es la forma de representar instrucciones compuestas en el lenguaje Python. He leído que Python recibe su nombre de una comedia británica, no de la serpiente no venenosa. Pero creo que el autor no estaba de broma. De todos modos, me encanta la naturaleza sucinta de este código. Seguro que puedo conseguir algo en estas líneas en C++. De hecho, es lo que me gustaría que proporcionara el algoritmo iota. Básicamente, necesito un algoritmo de rango con un aspecto similar a este:
template <typename T>
generator<T> range(T first, T last)
{
return{ ... };
}
int main()
{
for (int i : range(0, 10))
{
printf("%d\n", i);
}
}
Que yo sepa, esta función no existe, así que la tendremos que crear. El primer paso consiste en aproximarse al algoritmo con algo confiable que pueda servir como base para las pruebas. El vector C++ estándar resulta útil en estos casos:
#include <vector>
template <typename T>
std::vector<T> range(T first, T last)
{
std::vector<T> values;
while (first != last)
{
values.push_back(first++);
}
return values;
}
También hace un buen trabajo a la hora de ilustrar por qué no es recomendable crear un contenedor en primer lugar o, incluso, cuál sería su tamaño, en su caso. ¿Por qué debería haber un extremo? Resulta útil porque permite comparar fácilmente la salida de este generador de rangos con una alternativa más eficiente. Pues bien, resulta que escribir un generador más eficiente no es tan difícil. Eche un vistazo a la Figura 1.
Figura 1 Generador clásico
template <typename T>
struct generator
{
T first;
T last;
struct iterator{ ... };
iterator begin()
{
return{ first };
}
iterator end()
{
return{ last };
}
};
template <typename T>
generator<T> range(T first, T last)
{
return{ first, last };
}
Simplemente, la función de rango crea un generador inicializado con el mismo par de valores delimitadores. A continuación, el generador puede usar esos valores para producir iteradores ligeros mediante las funciones miembro convencionales begin y end. La parte más pesada es especificar la implementación de iteradores reutilizables en gran medida. El iterador puede, simplemente, contener un valor determinado e incrementarlo como sea necesario. También debe proporcionar un conjunto de alias de tipo para describirse para los algoritmos estándares. Esto no es estrictamente necesario para el sencillo bucle for basado en rango, pero compensa incluirlo como prueba futura:
template <typename T>
struct generator
{
struct iterator
{
T value;
using iterator_category = std::input_iterator_tag;
using value_type = T;
using difference_type = ptrdiff_t;
using pointer = T const*;
using reference = T const&;
Incrementar el iterador puede incrementar el valor subyacente. El formulario posterior al incremento se puede eliminar de forma segura:
iterator& operator++()
{
++value;
return *this;
}
iterator operator++(int) = delete;
Otra función igual de importante que proporciona un iterador es la comparación. Un bucle for basado en rango la usaría para determinar si se alcanzó el fin del rango:
bool operator==(iterator const& other) const
{
return value == other.value;
}
bool operator!=(iterator const& other) const
{
return !(*this == other);
}
Finalmente, un bucle for basado en rango tendría que desreferenciar el iterador para volver al valor actual del rango. Podría eliminar el operador de llamada de miembro porque no es necesario para el bucle for basado en rango, pero eso limitaría innecesariamente la utilidad de los generadores que deben usar otros algoritmos:
T const& operator*() const
{
return value;
}
T const* operator->() const
{
return std::addressof(value);
}
Puede que el generador y la función de rango asociada se usen con objetos de tipo número, en lugar de con primitivos simples. En ese caso, también podría usar la aplicación auxiliar address of, en caso de que los objetos de tipo número provocaran problemas con la sobrecarga de operador. Y eso es todo lo que se necesita. Ahora, mi función de rango funciona como debe:
template <typename T>
generator<T> range(T first, T last)
{
return{ first, last };
}
int main()
{
for (int i : range(0, 10))
{
printf("%d\n", i);
}
}
Por supuesto, esto no es especialmente flexible. He producido el algoritmo iota de mis sueños, pero sigue siendo una pequeña parte de lo que sería posible si cambiara de enfoque y usara corrutinas. La cuestión es que las corrutinas permiten escribir todo tipo de generadores de una forma mucho más sucinta y sin tener que escribir una nueva plantilla de clase de generador para cada tipo de rango que quiera producir. Imagine que solo tuviera que escribir un generador para tener una variedad de funciones de tipo rango que permitieran producir distintas secuencias a petición. Eso es lo que permiten las corrutinas. En lugar de insertar el conocimiento de la generación iota original en el generador, puede insertarlo directamente en la función de rango y tener una única plantilla de clase de generador que funcione como nexo entre el productor y el consumidor. Hagámoslo.
Para empezar, incluiré el encabezado de corrutina, que proporciona la definición de la plantilla de clase coroutine_handle:
#include <experimental/coroutine>
Usaré coroutine_handle para permitir la interacción del generador con la máquina de estado representada mediante una corrutina. Esto realizará consultas y reanudaciones como sea necesario para permitir que un bucle for basado en rango, o cualquier otro bucle, en su caso, dirija el progreso de la corrutina y produzca un modelo de consumo de datos basado en la extracción, en lugar de la inserción. En algunos aspectos, el generador es similar al generador clásico de la Figura 1. La gran diferencia es que, en lugar de actualizar valores directamente, solo hace avanzar la corrutina. La Figura 2 representa el esquema.
Figura 2 Generador de corrutinas
template <typename T>
struct generator
{
struct promise_type{ ... };
using handle_type = std::experimental::coroutine_handle<promise_type>;
handle_type handle{ nullptr };
struct iterator{ ... };
iterator begin()
{
...
handle.resume();
...
}
iterator end()
{
return nullptr;
}
};
Pero aún quedan cosas que ver aquí. No solo hay un iterador que permite que el bucle for basado en rango interactúe con el generador desde fuera, sino que también hay un elemento promise_type que permite que la corrutina interactúe con el generador desde dentro. En primer lugar, un poco de mantenimiento: Recuerde que la función que genera valores no devolverá un generador directamente, sino que permitirá que un desarrollador use instrucciones co_yield para desviar valores de la corrutina, a través del generador, al sitio de llamada. Considere el generador más sencillo:
generator<int> one_two_three()
{
co_yield 1;
co_yield 2;
co_yield 3;
}
Observe que el desarrollador nunca crea explícitamente el tipo de devolución de corrutina. Ese es el rol del compilador de C++ cuando une la máquina de estado que representa este código. Básicamente, el compilador de C++ busca promise_type y lo usa para construir un marco lógico de corrutina. No se preocupe, el marco de corrutina desaparecerá probablemente cuando el compilador de C++ acabe de optimizar el código, en algunos casos. En cualquier caso, promise_type se usa luego para inicializar el generador que se devuelve al autor de llamada. Dado promise_type, puedo obtener el manipulador que representa la corrutina para que el generador la pueda dirigir hacia adentro desde fuera:
generator(promise_type& promise) :
handle(handle_type::from_promise(promise))
{
}
Por supuesto, coroutine_handle es una construcción de un nivel bastante bajo y no me gustaría que un desarrollador que se aferre a un generador pudiera dañar accidentalmente la máquina de estado dentro de una corrutina activa. La solución consiste, simplemente, en implementar una semántica de transferencia de recursos y prohibir las copias. Algo así (antes, le asignaré un constructor predeterminado y eliminaré expresamente los miembros de la copia especial):
generator() = default;
generator(generator const&) = delete;
generator &operator=(generator const&) = delete;
A continuación, implementaré la semántica de transferencia de recursos, simplemente, transfiriendo el valor del manipulador de la corrutina para que nunca haya dos generadores que apunten a la misma corrutina en ejecución, como se muestra en la Figura 3.
Figura 3 Implementación de la semántica de transferencia de recursos
generator(generator&& other) : handle(other.handle)
{
other.handle = nullptr;
}
generator &operator=(generator&& other)
{
if (this != &other)
{
handle = other.handle;
other.handle = nullptr;
}
return *this;
}
Ahora, dado que la corrutina se dirige desde fuera, es importante recordar que el generador también tiene la responsabilidad de destruir la corrutina:
~generator()
{
if (handle)
{
handle.destroy();
}
}
De hecho, esto está más relacionado con el resultado de final_suspend en promise_type, pero me reservo eso para otro día. Pero basta de registros, por ahora. Observemos ahora el elemento promise_type del generador. El elemento promise_type resulta práctico para situar un estado, de modo que se incluya en cualquier asignación que se haga para el marco de corrutina por parte del compilador de C++. Entonces, el generador es solo un objeto ligero que puede desplazarse fácilmente y volver a hacer referencia al estado según sea necesario. Solo hay dos datos que necesito conducir de la corrutina al autor de llamada. El primero es el valor que se debe devolver y, el segundo, cualquier excepción que se haya producido:
#include <variant>
template <typename T>
struct generator
{
struct promise_type
{
std::variant<T const*, std::exception_ptr> value;
Aunque es opcional, tiendo a encapsular los objetos exception_ptr dentro de std::optional porque la implementación de exception_ptr en Visual C++ consume muchos recursos. Incluso un elemento exception_ptr vacío llama a CRT durante la construcción y la destrucción. Encapsularlo dentro de optional de forma eficiente evita esa sobrecarga. Un modelo de estado más preciso sería usar una variante, como acabo de ilustrar, para que contenga el valor actual o exception_ptr, ya que se excluyen mutuamente. El valor actual apunta simplemente al valor que se devuelve dentro de la corrutina. Esta acción es segura porque la corrutina se suspenderá mientras se lee el valor y el objeto temporal que se devuelva se conservará de forma segura mientras el valor se observa fuera de la corrutina.
Cuando una corrutina vuelve inicialmente al autor de llamada, pide a promise_type que produzca el valor devuelto. Dado que el generador se puede construir proporcionando una referencia a promise_type, puedo devolver dicha referencia aquí simplemente:
promise_type& get_return_object()
{
return *this;
}
Una corrutina que produce un generador no es la típica corrutina que habilita la simultaneidad y, a menudo, es el generador el que dicta la vigencia y ejecución de la corrutina. Como tal, indico al compilador de C++ que la corrutina se debe suspender inicialmente para que el generador pueda controlar su paso por la corrutina, por decirlo así:
std::experimental::suspend_always initial_suspend()
{
return {};
}
Del mismo modo, indico que la corrutina se suspenderá después de realizar la devolución, en lugar que hacer que se destruya automáticamente:
std::experimental::suspend_always final_suspend()
{
return {};
}
Esto garantiza que, una vez completada la corrutina, podré consultar su estado igualmente, a través del elemento promise_type asignado dentro el marco de la corrutina. Esto es fundamental para que pueda leer exception_ptr en caso de error o, simplemente, para saber que la corrutina ha finalizado. Si la corrutina se destruye automáticamente al completarse, ni siquiera podría consultar coroutine_handle, por no hablar de promise_type, después de una llamada para reanudar la corrutina en su punto de suspensión final. Ahora, se puede capturar el valor que se debe devolver de un modo bastante directo:
std::experimental::suspend_always yield_value(T const& other)
{
value = std::addressof(other);
return {};
}
Solo tengo que volver a usar la práctica aplicación auxiliar address of. El elemento promise_type también debe proporcionar una función return_void o return_value. Aunque no se usa en este ejemplo, sugiere que co_yield no es más que una abstracción de co_await:
void return_void()
{
}
Más adelante hablaremos sobre eso. A continuación, incluiré una pequeña defensa contra el uso indebido para que al desarrollador le resulte más fácil detectar qué ha salido mal. Un generador que produce valores implica que, a menos que la corrutina se complete, habrá un valor disponible que se podrá leer. Si una corrutina incluyera una expresión co_await, posiblemente, podría suspenderse sin que hubiera un valor presente y no habría ninguna forma de transmitir este hecho al autor de llamada. Por este motivo, evito que un desarrollador pueda escribir una instrucción co_await de este modo:
template <typename Expression>
Expression&& await_transform(Expression&& expression)
{
static_assert(sizeof(expression) == 0,
"co_await is not supported in coroutines of type generator");
return std::forward<Expression>(expression);
}
Al encapsular promise_type, solo necesito ocuparme de detectar, por así decirlo, cualquier excepción que se haya devuelto. El compilador de C++ se asegurará de que se llame al miembro unhandled_exception de promise_type:
void unhandled_exception()
{
value = std::current_exception();
}
A continuación, para facilitar la implementación, puedo proporcionar una función práctica para devolver de nuevo la excepción en el contexto adecuado (este paso es opcional):
void rethrow_if_failed()
{
if (value.index() == 1)
{
std::rethrow_exception(std::get<1>(value));
}
}
Pero ya basta de promise_type. Ahora tengo un generador de funciones, pero agregaré un sencillo iterador para poder dirigirlo fácilmente desde un bucle for basado en rango. Como antes, el iterador tendrá alias de tipo reutilizable para describirse para algoritmos estándar. Sin embargo, el iterador conserva simplemente coroutine_handle:
struct iterator
{
using iterator_category = std::input_iterator_tag;
using value_type = T;
using difference_type = ptrdiff_t;
using pointer = T const*;
using reference = T const&;
handle_type handle;
Incrementar el iterador conlleva una mayor implicación que el iterador de iota más sencillo, ya que se trata del punto principal en que el generador interactúa con la corrutina. Incrementar el iterador implica que el iterador es válido y que se puede incrementar. Dado que el iterador “end” contiene un manipulador nullptr puedo proporcionar simplemente una comparación de iterador:
bool operator==(iterator const& other) const
{
return handle == other.handle;
}
bool operator!=(iterator const& other) const
{
return !(*this == other);
}
Asumiendo que se trata de un iterador válido, en primer lugar, reanudo la corrutina y permito que se ejecute y devuelva su siguiente valor. A continuación, debo comprobar si su ejecución ha llevado a la corrutina al final. En tal caso, es necesario propagar cualquier excepción que se haya generado dentro de la corrutina:
iterator &operator++()
{
handle.resume();
if (handle.done())
{
promise_type& promise = handle.promise();
handle = nullptr;
promise.rethrow_if_failed();
}
return *this;
}
iterator operator++(int) = delete;
De lo contrario, se considera que el iterador ha llegado a su fin y su manipulador, simplemente, se borra para que se pueda volver a comparar correctamente con el iterador final. Es necesario prestar atención y borrar el manipulador de corrutina antes de devolver cualquier excepción no detectada a fin de evitar que alguien pueda reanudar accidentalmente la corrutina en el punto de suspensión final, ya que esto daría pie a un comportamiento indefinido. La función miembro begin del generador aplica prácticamente la misma lógica para garantizar que se pueda propagar de forma coherente cualquier excepción que se devuelva antes de alcanzar el primer punto de suspensión:
iterator begin()
{
if (!handle)
{
return nullptr;
}
handle.resume();
if (handle.done())
{
handle.promise().rethrow_if_failed();
return nullptr;
}
return handle;
}
La diferencia principal es que begin es un miembro del generador, que es el propietario del manipulador de la corrutina y, por lo tanto, no debe borrar el manipulador de corrutina. Finalmente, de una forma bastante sencilla, puedo implementar la desreferencia de iterador devolviendo una referencia al valor actual almacenado en promise_type:
T const& operator*() const
{
return *std::get<0>(handle.promise().value);
}
T const* operator->() const
{
return std::addressof(operator*());
}
Y listo. Ahora puedo crear todo tipo de algoritmos y producir una variedad de secuencias generadas con este generador generalizado. La Figura 4 muestra el aspecto del generador de rango inspirador.
Figura 4 Generador de rango inspirador
template <typename T>
generator<int> range(T first, T last)
{
while (first != last)
{
co_yield first++;
}
}
int main()
{
for (int i : range(0, 10))
{
printf("%d\n", i);
}
}
Pero, ¿quién necesita un rango limitado? Dado que ahora tengo un modelo de extracción, puedo dejar que el autor de llamada decida cuándo es suficiente, como se muestra en la Figura 5.
Figura 5 Generador sin límites
template <typename T>
generator<int> range(T first)
{
while (true)
{
co_yield first++;
}
}
int main()
{
for (int i : range(0))
{
printf("%d\n", i);
if (...)
{
break;
}
}
}
Las posibilidades son infinitas. Por supuesto, queda mucho que decir sobre los generadores y las corrutinas, y yo solo he abordado una pequeña parte aquí. Únase en la próxima ocasión para conocer mejor las corrutinas en C++. Puede consultar el ejemplo completo de este artículo en Compiler Explorer: godbolt.org/g/NXHBZR.
Kenny Kerr es autor, programador de sistemas y creador de C++/WinRT. También trabaja como ingeniero en el equipo de Windows en Microsoft, donde diseña el futuro de C++ para Windows, que permite que los desarrolladores escriban fantásticos componentes y aplicaciones de alto rendimiento muy fácilmente.
Gracias al siguiente experto técnico por su ayuda en la revisión de este artículo: Gor Nishanov