Generando estructuras infinitas

Usando generadores e iteradores en Javascript

Todo el mundo ha experimientado alguna vez lo que sucede cuando intentamos ejecutar en nuestro ordenador un código como el siguiente:

while(true) {
  console.log('Hello infinite universe')
}

Y es que si no eres rápida con el Control-C/Z es posible que te veas en la necesidad de tener que matar el proceso o peor, reiniciar la maquina.

Lo infinito no gusta pero eso no implica que no podamos razonar sobre la indeterminación y pensar en abstracto. Es como si por ejemplo quiero hablar de todos los números naturales, no hace falta que me pase hasta el final del universo escribiendolos todos en un papel, basta con poner: ℕ. Este símbolo representa a todos los números naturales sin necesidad de tener que pasarnos la eternidad apuntando números.

En programación pasa un poco lo mismo. Si queremos por ejemplo abrir ficheros muy muy grandes que sabemos que no son infinitos pero que su tamaño a priori está indeterminado, tendremos que razonar con ellos sin poder representar toda la información que contienen de golpe. Es decir, de alguna forma tendremos que ir “generando” la información que ve el usuario sin gastarle toda su memoria RAM.

Y es que al igual que pasaba con los números naturales podemos representar la indeterminación y operar sobre ella sin evaluarla toda de golpe.

Hoy hablaremos de generadores. Abrocharse bien el cinturón porque vienen curvas.

Representando la inmensidad

Hoy nuestra protagonista ha ido a la oficina a currar porque el aire acondicionado es gratis allí jaja equisdé. Después de tomarse un café y estar un rato contestando emails le llega una notificación de una nueva tarea al tablón que le han asignado a ella como último bastión de esperanza en el equipo.

La tarea se enuncia de esta forma: Necesitamos representar los números naturales para después hacer cálculos sobre ellos.

Inmediatamente pone un comentario creyendo ser presa de alguna siniestra broma:

— ¿Todos los números?

— Si. Todos. Todos.

No cabe ninguna duda. Ha llegado el momento que tanto temía desde que leyó un artículo en https://elrincondelfront.substack.com sobre generadores y se dijo a si misma: “Muy bonito, ¿pero esto qué aplicación práctica tiene?”.

Hoy había llegado el día de extrapolar lo que alguien random había escrito en un blog a la cruda vida real.

Se serena un poco y empieza a pensar racionalmente sobre el problema:

No existe — se dice — espacio suficiente en el mundo para guardar todos los números naturales, pero eso no implica que no se puedan representar para que una vez que acotemos el dominio poder realizar cálculos sobre ellos. Es decir, puedo por ejemplo calcular los cuadrados de los primeros 100 numeros naturales pero para poder extraerlos tengo que generarlos a partir de un conjunto finito de números naturales.

Creando iteradores infinitos

Vamos a echarle una mano rápida refrescando el concepto de iteradores. Un Iterador es objeto que permite recorrer una colección para potencialmente ir sacando sus valores. Es decir si tenemos esta lista:

const list = [1,2,3];

Y saco su iterador:

const it = list[Symbol.iterator]();
it.next() // { value: 1, done: false }
it.next() // { value: 2, done: false }
it.next() // { value: 3, done: false }
it.next() // { value: undefined, done: true }

El alcance del iterador está definido desde el princpio porque pertenece a una lista definida con 3 elementos. Así cuando llego al último elemento la iteración termina y las futuras llamadas al método ‘next’ devolverán siempre undefined.

Esto es lo que utilizan internamente estructuras de control como for .. of. Que saben cuando parar la iteración mirando la propiedad done del iterador.

Ahora bien, ¿qué pasaría si tuvieramos un iterador que nunca devuelve un done a true? Pues que efectivamente tendriamos un iterador infinito. Vamos a implementarlo.

Definamos entonces un nuevo objeto que implemente el protocolo de iteración. Un iterable en JavaScript es cualquier objeto que tenga una función llamada Symbol.iterator que al invocarla devuelva un nuevo objeto con una función next que al llamarla nos devuelva un objeto con el valor y un booleano de si ha terminado o no la iteración:

Tenemos entonces un objeto que es iterable (porque implementa el protocolo iterator — esto es, tiene una función Symbol.iterator implementada —) y que una vez obtengamos su iterador y llamemos a next, va a ir produciendo valores de forma infinita sin que nunca la variable done se ponga a true:

Qué es un generador

Un generador es una corrutina. Una función que puede ejecutarse, devolver un valor, pausarse y volver a continuar por donde se había parado conservando el estado que tenia. Es por eso que a los generadores se les conoce también como “continuaciones”.

Además los generadores generan valores que pueden ser iterados. Así un generador es también un iterable.

Los generadores en JavaScript son funciones normal que se declaran con el carácter especial *:

function* gen() {}

Ahora para poder pausar la ejecución utilizamos la palabra reservada yield que en cierta forma funciona similar a un return. Devuelve el valor pero además pausa la ejecución de la función. La próxima vez que sea llamada continuará por la instrucción que hubiese por debajo del yield.

Cuando invocamos a un generador, obtenemos un objeto Generator que implementa el protocolo Iterator, por lo que para ir accediendo a las distinas “pausas” tendremos que ir haciendo uso de next:

function* gen() {
  yield 1;
  yield 2;
}

const it = gen();
it.next(); // { value: 1, done: false }
it.next(); // { value: 2, done: false }
it.next(); // { value: undefined, done: true } ya no hay mas yields

Como un generador implementa el protocolo Iterator, cualquier cosa que utilice este protocolo funcionará con generadores. Así por ejemplo podríamos usar el spread operator sobre nuestro generador:

const list = [...gen()];
console.log(list) // [1, 2];

Magia!.

Representando los numeros naturales

Volvemos con nuestra amiga que ya ha recordado lo que es un generador y por tanto sabe ya como representar todos los números naturales: con un generador infinito de números empezando en 0:

Como el yield pausa cada vez que se llama a next, no hay problemas de tener un bucle infinito ahí ya que siempre y cuando no llamemos a next un número infinito de veces, estaremos a salvo.

Ese generador representa una indeterminación. Pero no implica que no podamos trabajar con ella. Vamos a crear una función map que nos permita aplicar una función sobre un iterador infinito:

Recuerda que for .. of trabaja sobre iterables.

Si no pusieramos el yield volveriamos a encontrarnos el problema del bucle infinito ya que en nuestro caso iterable es un generador infinito. Por tanto le colocamos el yield sucedido de el resultado de aplicar la función sobre el valor. Y map a su vez es otro generador por lo que podriamos hacer esto y no pasaría nada:

Ahora tenemos un generador de números naturales duplicados:

naturalNumbersDoubled.next(); // { value: 0, done: false }
naturalNumbersDoubled.next(); // { value: 2, done: false }
naturalNumbersDoubled.next(); // { value: 4, done: false }

Evaluación perezosa

La clave de todo esto es que no estamos ejecutando nada. Si tratasemos de hacerlo sobre el conjunto infinito de números naturales ya sabrías lo que pasaría.

Cuando ejecutamos el método next del generador naturalNumbersDoubled estamos por un lado obteniendo el siguiente número natural y por el otro aplicando la función transformadora que le pasamos al map:

En resumen, esto es lo que está ocurriendo:

1. Llamamos al método next del generador naturalNumbersDoubled que se corresponde al generador del map.

   1. Se ejecuta el generador map hasta que se encuentra un yield u otro iterable.

   2. Nos encontramos un iterable en el for .. of. Esto es como si estuvisemos haciendo iterable.next(), por lo que ejecutamos el generador de iterable.

      1. Se ejecuta el generador iterable hasta que se encuentra un yield u otro iterable.

      2. Nos enecontramos un yield i++. Se pausa el generador y se devuelve el resultado de incrementar en 1 el contador i.

   3. Ya tenemos el valor de haber hecho iterable.next() por lo que seguimos con el cuerpo del for .. of.

   4. Nos encontramos un yield f(value). Se pausa el generador y se devuelve el resultado de aplicar el value sobre la función f.

2. Ya tenemos el resultado de haber hecho naturalNumbersDoubled.next().

Se llama evaluación perezosa porque no estamos calculando nada hasta que no se pide el valor, de tal forma que dejamos indicadas todas las potenciales operaciones que haremos sobre el conjunto infinito y en el mismo momento en el que requiramos algún valor de ese conjunto, lanzamos todos los cálculos.

Obteniendo valores del conjunto infinito

Vale, nuestra amiga ya tiene finiquitada la tarea pero con tanto hablar de generadores se ha venido arriba y le apetece seguir trasteando un poco.

Ya tiene una forma de representar números naturales pero como podría obtener datos de ese conjunto sin tener que llamar repetidamente al método next?.

Podría por ejemplo crearse una función take que dado un número de elementos a extraer y un iterable devolviese una lista finita con esos elementos:

Como los generadores son iterables podemos obtener su iterador invocando a la función Symbol.iterator. Así la función take iterará el número de veces que indique count para obtener esos valores del generador:

Incluso podría también hacer una utilidad para obtener solo el primer elemento:

O ya puestas, un nuevo iterable sin el primer elemento y así poder obtener el subconjunto de los números naturales sin el 0:

Como it es un iterable, podemos usar yield *it para propagar todos los elementos del iterador. Sino estaríamos devolviendo el iterador en si, y no queremos eso.

Finalmente lo ponemos en acción:

Conclusión

Como podemos ver el mundo de los generadores e iteradores es complejo pero tiene un potencial enorme. Nos habilita la posibilidad de poder representar estructuras que no se pueden evaluar de una vez, bien porque son muy grandes o porque directamente son infinitas.

Además de representarlas podemos operar sobre ellas en el supuesto de que todo el conjunto se pudiese evaluar, algo así como ocurre en matemáticas que podemos representar la suma de todos los numeros naturales sin hacer la suma realmente.

Con estas herramientas podriámos por ejemplo crear un generador de números aleatorios en pocas líneas y después con las utilidades take, first o rest ir extrayendo el subconjunto que quisieramos.

Espero que el artículo te haya animado a usar estas herramientas y a extrapolarlas a otros casos de uso. Las aplicaciones son infinitas.

Si te gustó mi artículo en El rincón del front déjame un like, si te encantó compártelo y si te flipó suscríbete para no perderte el siguiente! :)

[portada]: Foto de insung yoon