En informática , un generador es una rutina que se puede utilizar para controlar el comportamiento de iteración de un bucle . Todos los generadores también son iteradores . [1] Un generador es muy similar a una función que devuelve una matriz , en el sentido de que un generador tiene parámetros , se puede llamar y genera una secuencia de valores. Sin embargo, en lugar de construir una matriz que contenga todos los valores y devolverlos todos a la vez, un generador produce los valores uno a la vez, lo que requiere menos memoria y permite que el llamador comience a procesar los primeros valores inmediatamente. En resumen, un generador parece una función pero se comporta como un iterador .
Los generadores se pueden implementar en términos de construcciones de flujo de control más expresivas , como corrutinas o continuaciones de primera clase . [2] Los generadores, también conocidos como semicorrutinas, [3] son un caso especial de (y más débiles que) las corrutinas, en el sentido de que siempre devuelven el control al llamador (cuando pasan un valor de vuelta), en lugar de especificar una corrutina a la que saltar; consulte la comparación de corrutinas con generadores .
Los generadores se invocan normalmente dentro de bucles. [4] La primera vez que se llega a una invocación de generador en un bucle, se crea un objeto iterador que encapsula el estado de la rutina del generador en su inicio, con argumentos vinculados a los parámetros correspondientes . El cuerpo del generador se ejecuta entonces en el contexto de ese iterador hasta que se encuentra una acción especial de rendimiento ; en ese momento, el valor proporcionado con la acción de rendimiento se utiliza como el valor de la expresión de invocación. La próxima vez que se llega a la misma invocación de generador en una iteración posterior, la ejecución del cuerpo del generador se reanuda después de la acción de rendimiento , hasta que se encuentra otra acción de rendimiento . Además de la acción de rendimiento , la ejecución del cuerpo del generador también puede terminarse mediante una acción de finalización , momento en el que se termina el bucle más interno que encierra la invocación del generador. En situaciones más complicadas, se puede utilizar un generador manualmente fuera de un bucle para crear un iterador, que luego se puede utilizar de varias maneras.
Debido a que los generadores calculan los valores obtenidos solo cuando se los solicita, son útiles para representar secuencias , como secuencias que serían costosas o imposibles de calcular de una sola vez. Estas incluyen, por ejemplo, secuencias infinitas y secuencias de datos en vivo.
Cuando se desea una evaluación ansiosa (principalmente cuando la secuencia es finita, ya que de lo contrario la evaluación nunca terminará), se puede convertir en una lista o usar una construcción paralela que crea una lista en lugar de un generador. Por ejemplo, en Python, un generador gse puede evaluar como una lista lmediante l = list(g), mientras que en F# la expresión de secuencia seq { ... }se evalúa de manera diferida (un generador o secuencia) pero [ ... ]se evalúa ansiosamente (una lista).
En presencia de generadores, las construcciones de bucle de un lenguaje (como for y while) se pueden reducir a una única construcción de bucle... fin de bucle; todas las construcciones de bucle habituales se pueden simular cómodamente utilizando generadores adecuados de la forma correcta. Por ejemplo, un bucle de rango como for x = 1 to 10se puede implementar como una iteración a través de un generador, como en Python for x in range(1, 10). Además, breakse puede implementar enviando finish al generador y luego usando continueen el bucle.
Los generadores aparecieron por primera vez en CLU (1975), [5] fueron una característica destacada en el lenguaje de manipulación de cadenas Icon (1977) y ahora están disponibles en Python (2001), [6] C# , [7] Ruby , PHP , [8] ECMAScript (a partir de ES6/ES2015 ) y otros lenguajes. En CLU y C#, los generadores se denominan iteradores y, en Ruby, enumeradores .
El estándar final Common Lisp no proporciona generadores de forma nativa, pero existen varias implementaciones de bibliotecas, como SERIES documentada en CLtL2 o pygen.
Una declaración de rendimiento se utiliza para implementar iteradores sobre abstracciones de datos definidas por el usuario. [9]
string_chars = iter (s: cadena) produce (carácter); índice: int := 1; límite: int := string$tamaño(s); mientras índice <= límite hacer rendimiento (cadena $fetch(s, índice)); índice := índice + 1; fin;fin cadena_caracteres;para c: char en string_chars(s) hacer ...fin;Cada expresión (incluidos los bucles) es un generador. El lenguaje tiene muchos generadores integrados e incluso implementa algunas de las semánticas lógicas mediante el mecanismo del generador ( la disyunción lógica o "OR" se realiza de esta manera).
La impresión de los cuadrados del 0 al 20 se puede lograr utilizando una co-rutina escribiendo:
Sin embargo, la mayoría de las veces los generadores personalizados se implementan con la palabra clave "suspend", que funciona exactamente como la palabra clave "yield" en CLU.
C no tiene funciones generadoras como una construcción del lenguaje, pero, como son un subconjunto de corrutinas , es simple implementarlas usando cualquier marco que implemente corrutinas apilables, como libdill. [10] En las plataformas POSIX, cuando el costo del cambio de contexto por iteración no es una preocupación, o se desea un paralelismo completo en lugar de meramente concurrencia , se puede implementar un marco de función generadora muy simple usando pthreads y pipes .
Es posible introducir generadores en C++ mediante macros de preprocesador. El código resultante puede tener aspectos muy diferentes al C++ nativo, pero la sintaxis del generador puede ser muy clara. [11] El conjunto de macros de preprocesador definidas en esta fuente permiten utilizar generadores definidos con la sintaxis que se muestra en el siguiente ejemplo:
$generador ( descenso ) { int i ; // coloca el constructor de nuestro generador, p. ej. // descent(int minv, int maxv) {...} // de $emit a $stop es un cuerpo de nuestro generador: $emit ( int ) // emitirá valores int. Inicio del cuerpo del generador. for ( i = 10 ; i > 0 ; -- i ) $yield ( i ); // similar a yield en Python, // devuelve el siguiente número en [1..10], invertido. $stop ; // stop, fin de la secuencia. Fin del cuerpo del generador. }; Esto se puede iterar usando:
int main ( int argc , char * argv []) { descent gen ; for ( int n ; gen ( n );) // invocación del generador "obtener el siguiente" printf ( "el siguiente número es %d \n " , n ); return 0 ; } Además, C++11 permite aplicar bucles foreachbegin a cualquier clase que proporcione las funciones y end. De esta forma, es posible escribir clases similares a generadores definiendo tanto los métodos iterables ( beginy end) como los métodos iteradores ( operator!=, operator++y operator*) en la misma clase. Por ejemplo, es posible escribir el siguiente programa:
#include <iostream> int main () { para ( int i : rango ( 10 )) { std :: cout << i << std :: endl ; } devolver 0 ; } Una implementación de rango básico se vería así:
rango de clase { privado : int último ; int iter ; público : rango ( int fin ) : último ( fin ), iter ( 0 ) {} // Funciones iterables const range & begin () const { return * this ; } const range & end () const { return * this ; } // Funciones del iterador bool operador != ( const rango & ) const { return iter < last ; } void operador ++ () { ++ iter ; } int operador * () const { return iter ; } }; Perl no proporciona generadores de forma nativa, pero el módulo Coro::Generator proporciona soporte, ya que utiliza el marco de trabajo de corrutinas Coro. Ejemplo de uso:
usar estricto ; usar advertencias ; # Habilitar generador { BLOCK } y rendimiento usar Coro::Generator ; # Referencia de matriz para iterar sobre my $chars = [ 'A' ... 'Z' ]; # Nuevo generador que puede llamarse como un coderef. my $letters = generator { my $i = 0 ; for my $letter ( @$chars ) { # obtener la siguiente letra de $chars yield $letter ; } }; # Llama al generador 15 veces. print $letters -> (), "\n" for ( 0 .. 15 ); El ejemplo paralelo a Icon utiliza la clase Range de Raku (anteriormente/también conocida como Perl 6) como una de varias formas de lograr generadores con el lenguaje.
La impresión de los cuadrados del 0 al 20 se puede lograr escribiendo:
para ( 0 .. *). map (* ** 2 ) -> $i { último si $i > 20 ; digamos $i}Sin embargo, la mayoría de las veces los generadores personalizados se implementan con las palabras clave "gather" y "take" en un contexto perezoso.
En Tcl 8.6, el mecanismo del generador se basa en corrutinas con nombre .
proc generator { body } { coroutine gen [ incr :: disambiguator ] apply {{ script } { # Produce el resultado de [generator], el nombre del generador yield [ info coroutine ] # Realiza la generación eval $script # Termina el bucle del llamador usando una excepción 'break' return - code break }} $body } # Utilice un bucle 'for' simple para realizar el recuento del conjunto de generación real [ generator { for {set i 10 } { $i <= 20 } { incr i } { yield $i } }] # Extrae valores del generador hasta que se agote mientras 1 { puts [ $count ] } En Haskell , con su modelo de evaluación diferida , cada dato creado con un constructor de datos no estricto se genera a pedido. Por ejemplo,
countFrom :: Entero -> [ Entero ] countFrom n = n : countFrom ( n + 1 ) de10a20 :: [ Entero ] de10a20 = takeWhile ( <= 20 ) $ countFrom 10 primos :: [ Entero ] primos = 2 : 3 : nextPrime 5 donde nextPrime n | notDivisible n = n : nextPrime ( n + 2 ) | de lo contrario = nextPrime ( n + 2 ) notDivisible n = all (( /= 0 ) . ( rem n )) $ takeWhile (( <= n ) . ( ^ 2 )) $ tail primos donde (:)es un constructor de lista no estricto, cons , y $es simplemente un operador "llamado con" , utilizado para paréntesis. Esto utiliza la función adaptadora estándar,
tomarMientras p [] = [] tomarMientras p ( x : xs ) | p x = x : tomarMientras p xs | de lo contrario = [] que recorre la lista y se detiene en el primer elemento que no satisface el predicado. Si la lista ya se ha recorrido hasta ese punto, es simplemente una estructura de datos estricta, pero si alguna parte no se ha recorrido antes, se generará a pedido. Las comprensiones de listas se pueden usar libremente:
cuadradosMenos de 20 = takeWhile ( <= 20 ) [ x * x | x <- contarDesde 10 ] cuadradosParaNumerosMenos de 20 = [ x * x | x <- takeWhile ( <= 20 ) $ contarDesde 10 ] Racket ofrece varias funciones relacionadas con los generadores. En primer lugar, sus formas de bucle for funcionan con secuencias , que son una especie de productor:
( para ([ i ( dentro del rango 10 20 )]) ( printf "i = ~s \n " i )) y estas secuencias también son valores de primera clase:
( define 10 a 20 ( dentro del rango 10 20 )) ( para ([ i 10 a 20 ]) ( printf "i = ~s \n " i )) Algunas secuencias se implementan de manera imperativa (con variables de estado privadas) y otras se implementan como listas perezosas (posiblemente infinitas). Además, las nuevas definiciones de estructuras pueden tener una propiedad que especifique cómo se pueden usar como secuencias.
Pero más directamente, Racket viene con una biblioteca de generadores para una especificación de generadores más tradicional. Por ejemplo,
#lang racket ( require racket/generator ) ( define ( ints-from from ) ( generator () ( for ([ i ( in-naturals from )]) ; secuencia infinita de enteros desde 0 ( yield i )))) ( define g ( ints-from 10 )) ( list ( g ) ( g ) ( g )) ; -> '(10 11 12) Tenga en cuenta que el núcleo de Racket implementa potentes funciones de continuación, que proporcionan continuaciones generales (reentrantes) que se pueden componer y también continuaciones delimitadas. Con esto, se implementa la biblioteca de generadores en Racket.
La comunidad de PHP implementó generadores en PHP 5.5. Puede encontrar más detalles en la Solicitud de comentarios original: Generadores.
Secuencia infinita de Fibonacci:
función fibonacci () : Generador { $último = 0 ; $actual = 1 ; rendimiento 1 ; mientras ( verdadero ) { $actual = $último + $actual ; $último = $actual - $último ; rendimiento $actual ; } }foreach ( fibonacci () como $número ) { echo $número , " \n " ; }Secuencia de Fibonacci con límite:
función fibonacci ( int $limit ) : Generador { rendimiento $a = $b = $i = 1 ; mientras ( ++ $i < $límite ) { rendimiento $a = ( $b = $a + $b ) - $a ; } }foreach ( fibonacci ( 10 ) como $número ) { echo " $número \n " ; }Cualquier función que contenga una declaración de rendimiento es automáticamente una función generadora.
Ruby admite generadores (a partir de la versión 1.9) en forma de la clase Enumerator incorporada.
# Generador a partir de un objeto Enumerador chars = Enumerator . new ( [ 'A' , 'B' , 'C' , 'Z' ] ) 4. veces { pone caracteres . siguiente } # Generador a partir de un bloque count = Enumerator . new do | yielder | i = 0 loop { yielder . yield i += 1 } end 100 . veces { pone count . siguiente } Java ha tenido una interfaz estándar para implementar iteradores desde sus inicios y, desde Java 5, la construcción "foreach" facilita la ejecución de bucles sobre objetos que proporcionan la java.lang.Iterableinterfaz. (El marco de colecciones de Java y otros marcos de colecciones suelen proporcionar iteradores para todas las colecciones).
registro Par ( int a , int b ) {}; Iterable < Integer > myIterable = Stream . iterate ( new Pair ( 1 , 1 ), p -> new Pair ( p . b , p . a + p . b )) . limit ( 10 ) . map ( p -> p . a ):: iterador ; myIterable . forEach ( System . out :: println );O bien obtenga un iterador de la superinterfaz BaseStream de Java 8 de la interfaz Stream.
registro Par ( int a , int b ) {}; // Guarda el iterador de un flujo que genera la secuencia Fib Iterator < Integer > myGenerator = Stream // Genera la secuencia Fib . iterate ( new Pair ( 1 , 1 ), p -> new Pair ( p . b , p . a + p . b )) . map ( p -> p . a ). iterator (); // Imprime los primeros 5 elementos para ( int i = 0 ; i < 5 ; i ++ ) { System . println ( myGenerator . next ()) ; } Sistema . out . println ( "terminado con la primera iteración" );// Imprime los siguientes 5 elementos para ( int i = 0 ; i < 5 ; i ++ ) { System . println ( myGenerator . next ()); } Producción:
1 1 2 3 5 terminado con la primera iteración 8 13 21 34 55Un ejemplo de generador de C# 2.0 ( yielddisponible desde la versión 2.0 de C#): Ambos ejemplos utilizan genéricos, pero esto no es obligatorio. La palabra clave yield también ayuda a implementar iteraciones con estado personalizadas en una colección, como se analiza en esta discusión. [12]
// Método que toma una entrada iterable (posiblemente una matriz) // y devuelve todos los números pares. public static IEnumerable < int > GetEven ( IEnumerable < int > numbers ) { foreach ( int number in numbers ) { if (( number % 2 ) == 0 ) { yield return number ; } } } Es posible utilizar múltiples yield returndeclaraciones y se aplican en secuencia en cada iteración:
clase pública CityCollection : IEnumerable < cadena > { IEnumerator público < cadena > GetEnumerator () { rendimiento de retorno "Nueva York" ; rendimiento de retorno "París" ; rendimiento de retorno "Londres" ; } } En XL , los iteradores son la base de los bucles 'for':
importar IO = XL.UI.CONSOLEiterador IntegerIterator (var out Counter : entero; Low, High : entero) escrito Counter en Low..High es Contador := Bajo mientras Contador <= Bucle alto producir Contador += 1// Tenga en cuenta que no es necesario declararlo, porque se declaró 'var out' en el iterador// Por lo tanto, aquí se hace una declaración implícita de I como un entero.para I en bucle 1..5 IO.WriteLn "Yo=", yoF# proporciona generadores a través de expresiones de secuencia , desde la versión 1.9.1. [13] Estas pueden definir una secuencia (evaluada de forma diferida, acceso secuencial) a través de seq { ... }, una lista (evaluada con entusiasmo, acceso secuencial) a través de [ ... ]o una matriz (evaluada con entusiasmo, acceso indexado) a través [| ... |]de que contienen código que genera valores. Por ejemplo,
seq { para b en 0 .. 25 hacer si b < 15 entonces rendimiento b * b } forma una secuencia de cuadrados de números del 0 al 14 filtrando números del rango de números del 0 al 25.
Los generadores se agregaron a Python en la versión 2.2 en 2001. [6] Un generador de ejemplo:
desde la escritura importar Iteradordef countfrom ( n : int ) -> Iterador [ int ]: mientras sea verdadero : rendimiento n n += 1# Ejemplo de uso: imprimir los números enteros del 10 al 20. # Tenga en cuenta que esta iteración termina normalmente, a pesar de que # countfrom() está escrito como un bucle infinito.para i en countfrom ( 10 ): si i <= 20 : imprimir ( i ) de lo contrario : romper# Otro generador, que produce números primos indefinidamente según sea necesario. import itertoolsdef primes () -> Iterador [ int ]: """Genera números primos indefinidamente según sea necesario.""" yield 2 n = 3 p = [ 2 ] while True : # Si dividir n por todos los números en p, hasta e incluyendo sqrt(n), # produce un resto distinto de cero, entonces n es primo. if all ( n % f > 0 for f in itertools . takewhile ( lambda f : f * f <= n , p )): yield n p . append ( n ) n += 2 En Python, un generador puede considerarse como un iterador que contiene un marco de pila congelado . Siempre next()que se llama a en el iterador, Python reanuda el marco congelado, que se ejecuta normalmente hasta que yieldse llega a la siguiente instrucción. Luego, el marco del generador se congela nuevamente y el valor obtenido se devuelve al que realiza la llamada.
PEP 380 (implementado en Python 3.3) agrega la yield fromexpresión, permitiendo que un generador delegue parte de sus operaciones a otro generador o iterable. [14]
Python tiene una sintaxis basada en la de las listas por comprensión , llamada expresión generadora, que ayuda a crear generadores. A continuación, se amplía el primer ejemplo anterior mediante el uso de una expresión generadora para calcular los cuadrados de la countfromfunción generadora:
cuadrados = ( n * n para n en countfrom ( 2 ))para j en cuadrados : si j <= 20 : imprimir ( j ) de lo contrario : romperECMAScript 6 (también conocido como Harmony) introdujo funciones de generador.
Una secuencia de Fibonacci infinita se puede escribir utilizando un generador de funciones:
función * fibonacci ( límite ) { let [ prev , curr ] = [ 0 , 1 ]; while ( ! límite || curr <= límite ) { yield curr ; [ prev , curr ] = [ curr , prev + curr ]; } } // delimitado por el límite superior 10 para ( const n de fibonacci ( 10 )) { console . log ( n ); } // generador sin límite superior para ( const n de fibonacci ()) { console . log ( n ); if ( n > 10000 ) break ; } // iterando manualmente let fibGen = fibonacci ( ); console.log ( fibGen.next ( ) ). value ); // 1 console.log ( fibGen.next ( ) ) . value ); // 1 console.log ( fibGen.next ( ) ) . value ) ; // 2 console.log ( fibGen.next ( ) ) . value ) ; // 3 console.log ( fibGen.next ( ) ) . value ) ; // 5 console.log ( fibGen.next ( ) ) . value ); // 8 // retoma desde donde lo dejaste para ( const n of fibGen ) { console . log ( n ); if ( n > 10000 ) break ; } El paquete iteradores se puede utilizar para este propósito. [15] [16]
biblioteca ( iteradores )# Ejemplo ------------------ abc <- iter ( c ( 'a' , 'b' , 'c' )) nextElem ( abc ) Ejemplo en Pharo Smalltalk :
El generador de proporción áurea que aparece a continuación devuelve en cada invocación 'goldenRatio next' una mejor aproximación a la proporción áurea.
goldenRatio := Generador en: [ : g | | xyzr | x := 0 . y := 1 .[ z := x + y . r := ( z / y ) asFloat . x := y . y := z . g rendimiento: r ] repetir
] .proporción áurea siguiente .La siguiente expresión devuelve las siguientes 10 aproximaciones.
Carácter cr unirse: (( 1 a: 10 ) recopilar: [ : dummy | proporción siguiente ]) .Ver más en Una joya oculta en Pharo: Generator.