Gerador (programação de computador) - Generator (computer programming)

Na ciência da computação , um gerador é uma rotina que pode ser usada para controlar o comportamento de iteração de um loop . Todos os geradores também são iteradores . Um gerador é muito semelhante a uma função que retorna um array, em que um gerador tem parâmetros, pode ser chamado e gera uma sequência de valores. No entanto, em vez de construir uma matriz contendo todos os valores e retorná-los todos de uma vez, um gerador produz os valores um por vez, o que requer menos memória e permite que o chamador comece a processar os primeiros valores imediatamente. Resumindo, um gerador parece uma função, mas se comporta como um iterador .

Os geradores podem ser implementados em termos de construções de fluxo de controle mais expressivas , como corrotinas ou continuações de primeira classe . Geradores, também conhecidos como semicorrotinas, são um caso especial de (e mais fracos que) corrotinas, pois sempre devolvem o controle ao chamador (ao passar um valor de volta), em vez de especificar uma corrotina para a qual saltar; veja a comparação de co-rotinas com geradores .

Usos

Geralmente, os geradores são invocados dentro de loops. Na primeira vez que uma chamada de gerador é alcançada em um loop, um objeto iterador é criado que encapsula o estado da rotina do gerador em seu início, com argumentos vinculados aos parâmetros correspondentes . O corpo do gerador é então executado no contexto desse iterador até que uma ação de rendimento especial seja encontrada; naquele momento, o valor fornecido com a ação yield é usado como o valor da expressão de invocação. Na próxima vez que a mesma invocação do gerador for alcançada em uma iteração subsequente, a execução do corpo do gerador será retomada após a ação de rendimento , até que outra ação de rendimento seja encontrada. Além da ação de rendimento , a execução do corpo do gerador também pode ser encerrada por uma ação de término , em que o loop mais interno que envolve a invocação do gerador é encerrado. Em situações mais complicadas, um gerador pode ser usado manualmente fora de um loop para criar um iterador, que pode então ser usado de várias maneiras.

Como os geradores calculam seus valores produzidos somente sob demanda, eles são úteis para representar fluxos , como sequências que seriam caras ou impossíveis de calcular de uma só vez. Isso inclui, por exemplo, sequências infinitas e fluxos de dados ao vivo.

Quando uma avaliação rápida é desejável (principalmente quando a sequência é finita, caso contrário a avaliação nunca terminará), pode-se converter para uma lista ou usar uma construção paralela que cria uma lista em vez de um gerador. Por exemplo, em Python, um gerador gpode ser avaliado para uma lista lvia l = list(g), enquanto em F # a expressão de sequência seq { ... }avalia lentamente (um gerador ou sequência), mas [ ... ]avalia avidamente (uma lista).

Na presença de geradores, as construções de loop de uma linguagem - como for e while - podem ser reduzidas em um único loop ... construção de loop final; todas as construções de loop usuais podem então ser confortavelmente simuladas usando geradores adequados da maneira certa. Por exemplo, um loop variado como for x = 1 to 10pode ser implementado como iteração por meio de um gerador, como no Python for x in range(1, 10). Além disso, breakpode ser implementado como envio de acabamento para o gerador e, em seguida, uso continueno loop.

Linha do tempo

Os geradores apareceram pela primeira vez em CLU (1975), eram uma característica proeminente na linguagem de manipulação de strings Icon (1977) e agora estão disponíveis em Python (2001), C # , Ruby , as versões posteriores de ECMAScript (a partir de ES6 / ES2015) e outros línguas. Em CLU e C #, os geradores são chamados de iteradores e, em Ruby, de enumeradores .

Lisp

O padrão Common Lisp final não fornece geradores nativamente, mas existem várias implementações de biblioteca, como SERIES documentadas em CLtL2 ou pygen .

CLU

Uma declaração de rendimento é usada para implementar iteradores em abstrações de dados definidas pelo usuário.

string_chars = iter (s: string) yields (char);
  index: int := 1;
  limit: int := string$size (s);
  while index <= limit do
    yield (string$fetch(s, index));
    index := index + 1;
    end;
end string_chars;

for c: char in string_chars(s) do
   ...
end;

Ícone

Cada expressão (incluindo loops) é um gerador. A linguagem tem muitos geradores embutidos e até implementa algumas das semânticas lógicas usando o mecanismo do gerador ( disjunção lógica ou "OU" é feita dessa maneira).

A impressão de quadrados de 0 a 20 pode ser realizada usando uma co-rotina por escrito:

   local squares, j
   squares := create (seq(0) ^ 2)
   every j := |@squares do
      if j <= 20 then
         write(j)
      else
         break

No entanto, na maioria das vezes, os geradores personalizados são implementados com a palavra-chave "suspend", que funciona exatamente como a palavra-chave "yield" no CLU.

C

C não possui funções geradoras como uma construção de linguagem, mas, como são um subconjunto de corrotinas , é simples implementá-las usando qualquer framework que implemente corrotinas empilháveis, como libdill. Em plataformas POSIX, quando o custo de troca de contexto por iteração não é uma preocupação, ou paralelismo completo ao invés de mera simultaneidade é desejado, uma estrutura de função geradora muito simples pode ser implementada usando pthreads e pipes .

C ++

É possível introduzir geradores em C ++ usando macros de pré-processador. O código resultante pode ter aspectos muito diferentes do C ++ nativo, mas a sintaxe do gerador pode ser muito organizada. O conjunto de macros pré-processador definido nesta fonte permite geradores definidos com a sintaxe como no exemplo a seguir:

$generator(descent)
{
   int i;

   // place the constructor of our generator, e.g. 
   // descent(int minv, int maxv) {...}
   
   // from $emit to $stop is a body of our generator:
    
   $emit(int) // will emit int values. Start of body of the generator.
      for (i = 10; i > 0; --i)
         $yield(i); // similar to yield in Python,
                    // returns next number in [1..10], reversed.
   $stop; // stop, end of sequence. End of body of the generator.
};

Isso pode ser iterado usando:

int main(int argc, char* argv[])
{
  descent gen;
  for(int n; gen(n);) // "get next" generator invocation
    printf("next number is %d\n", n);
  return 0;
}

Além disso, o C ++ 11 permite que os loops foreach sejam aplicados a qualquer classe que forneça as funções begine end. Então, é possível escrever classes semelhantes a geradores definindo os métodos iteráveis ​​( begine end) e os métodos iteradores ( operator!=, operator++e operator*) na mesma classe. Por exemplo, é possível escrever o seguinte programa:

#include <iostream>
int main()
{
    for (int i: range(10))
    {
        std::cout << i << std::endl;
    }
    return 0;
}

Uma implementação de intervalo básico seria assim:

class range
{
private:
    int last;
    int iter;

public:
    range(int end):
        last(end),
        iter(0)
    {}

    // Iterable functions
    const range& begin() const { return *this; }
    const range& end() const { return *this; }

    // Iterator functions
    bool operator!=(const range&) const { return iter < last; }
    void operator++() { ++iter; }
    int operator*() const { return iter; }
};

Perl

Perl não fornece geradores nativamente, mas o suporte é fornecido pelo módulo Coro :: Generator que usa a estrutura de co-rotina Coro . Exemplo de uso:

use strict;
use warnings;
# Enable generator { BLOCK } and yield
use Coro::Generator;
# Array reference to iterate over
my $chars = ['A'...'Z'];

# New generator which can be called like a coderef.
my $letters = generator {
    my $i = 0;
    for my $letter (@$chars) {
        # get next letter from $chars
        yield $letter;
    }
};

# Call the generator 15 times.
print $letters->(), "\n" for (0..15);

Tcl

No Tcl 8.6, o mecanismo gerador é baseado em co-rotinas nomeadas .

proc generator {body} {
    coroutine gen[incr ::disambiguator] apply {{script} {
        # Produce the result of [generator], the name of the generator
        yield [info coroutine]
        # Do the generation
        eval $script
        # Finish the loop of the caller using a 'break' exception
        return -code break
    }} $body
}

# Use a simple 'for' loop to do the actual generation
set count [generator {
    for {set i 10} {$i <= 20} {incr i} {
        yield $i
    }
}]

# Pull values from the generator until it is exhausted
while 1 {
    puts [$count]
}

Haskell

Em Haskell , com seu modelo de avaliação preguiçoso , tudo é um gerador - cada dado criado com um construtor de dados não estrito é gerado sob demanda. Por exemplo,

countfrom n = n : countfrom (n+1)

-- Example use: printing out the integers from 10 to 20.
test1 = mapM_ print $ takeWhile (<= 20) $ countfrom 10

primes = 2 : 3 : nextprime 5  where
  nextprime n | b = n : nextprime (n+2)
              | otherwise = nextprime (n+2)
    where b = all ((/= 0).(rem n)) $ takeWhile ((<= n).(^2)) $ tail primes

onde (:)é um construtor de lista não estrito, contras , e $é apenas um operador "chamado com" , usado para parênteses. Isso usa a função de adaptador padrão,

takeWhile p [] = []
takeWhile p (x:xs) | p x = x : takeWhile p xs
                   | otherwise = []

que recupera valores agradáveis ​​com um predicado e para de solicitar novos valores assim que um não agradável é encontrado. O acesso ao armazenamento compartilhado é usado como um mediador universal em Haskell. As compreensões de lista podem ser usadas livremente:

test2 = mapM_ print $ takeWhile (<= 20) [x*x | x <- countfrom 10]
test3 = mapM_ print [x*x | x <- takeWhile (<= 20) $ countfrom 10]

Raquete

Racket fornece vários recursos relacionados para geradores. Primeiro, suas formas de loop for funcionam com sequências , que são uma espécie de produtor:

(for ([i (in-range 10 20)])
  (printf "i = ~s\n" i))

e essas sequências também são valores de primeira classe:

(define 10-to-20 (in-range 10 20))
(for ([i 10-to-20])
  (printf "i = ~s\n" i))

Algumas sequências são implementadas imperativamente (com variáveis ​​de estado privadas) e algumas são implementadas como listas preguiçosas (possivelmente infinitas). Além disso, novas definições de estrutura podem ter uma propriedade que especifica como elas podem ser usadas como sequências.

Porém, mais diretamente, o Racket vem com uma biblioteca de gerador para uma especificação de gerador mais tradicional. Por exemplo,

#lang racket
(require racket/generator)
(define (ints-from from)
  (generator ()
    (for ([i (in-naturals from)]) ; infinite sequence of integers from 0
      (yield i))))
(define g (ints-from 10))
(list (g) (g) (g)) ; -> '(10 11 12)

Observe que o núcleo do Racket implementa recursos de continuação poderosos, fornecendo continuações gerais (reentrantes) que são combináveis, e também continuações delimitadas. Usando isso, a biblioteca do gerador é implementada no Racket.

PHP

A comunidade de PHP implementou geradores em PHP 5.5. Os detalhes podem ser encontrados na solicitação original de comentários: geradores .

Sequência infinita de Fibonacci:

function fibonacci()
{
    $last = 0;
    $current = 1;
    yield 1;
    while (true) {
        $current = $last + $current;
        $last = $current - $last;
        yield $current;
    }
}

foreach (fibonacci() as $number) {
    echo $number, "\n";
}

Sequência de Fibonacci com limite:

function fibonacci(int $limit):generator 
{
    yield $a = $b = $i = 1;
 
    while (++$i < $limit) {
        yield $a = ($b = $a + $b) - $a;
    }
}

foreach (fibonacci(10) as $number) {
    echo "$number\n";
}

Qualquer função que contenha uma declaração de rendimento é automaticamente uma função geradora.

Rubi

Ruby suporta geradores (a partir da versão 1.9) na forma da classe Enumerator embutida.

# Generator from an Enumerator object
chars = Enumerator.new(['A', 'B', 'C', 'Z'])

4.times { puts chars.next }

# Generator from a block
count = Enumerator.new do |yielder|
  i = 0
  loop { yielder.yield i += 1 }
end

100.times { puts count.next }

Java

Java teve uma interface padrão para implementar iteradores desde seus primeiros dias e, desde Java 5, a construção "foreach" facilita o loop sobre os objetos que fornecem a java.lang.Iterableinterface. (A estrutura de coleções Java e outras estruturas de coleções, normalmente fornecem iteradores para todas as coleções.)

No entanto, Java não possui geradores integrados à linguagem. Isso significa que criar iteradores costuma ser muito mais complicado do que em linguagens com geradores embutidos, especialmente quando a lógica de geração é complexa. Como todos os estados devem ser salvos e restaurados sempre que um item deve ser gerado por um iterador, não é possível armazenar o estado em variáveis ​​locais ou usar rotinas de loop integradas, como quando os geradores estão disponíveis; em vez disso, tudo isso deve ser simulado manualmente, usando campos de objeto para manter o estado local e os contadores de loop.

Mesmo iteradores simples construídos dessa maneira tendem a ser significativamente mais volumosos do que aqueles que usam geradores, com muito código clichê .

O exemplo original acima pode ser escrito em Java 5 como:

// Iterator implemented as anonymous class.  This uses generics but doesn't need to.
for (int i: new Iterable<Integer>() {
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int counter = 1;

            @Override
            public boolean hasNext() {
                return counter <= 100;
            }

            @Override
            public Integer next() {
                return counter++;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
}) {
    System.out.println(i);
}

Uma sequência infinita de Fibonacci também pode ser escrita em Java 5 como um Iterador:

Iterable<Integer> fibo = new Iterable<Integer>() {
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int a = 1, b = 2;

            @Override
            public boolean hasNext() {
                return true;
            }

            @Override
            public Integer next() {
                int temp = a;
                a = b;
                b = a + temp;
                return temp;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
};
// this could then be used as...
for (int f: fibo) {
    System.out.println("next Fibonacci number is " + f);
    if (someCondition(f)) break;
}

Além disso, uma sequência infinita de Fibonacci também pode ser escrita usando a interface Java 8 Stream:

Iterable<Integer> myIterable = Stream
        // Generates Fib sequence
        .iterate(new Integer[]{ 1, 1 }, x -> new Integer[] { x[1], x[0] + x[1] })
        .map(x -> x[0])::iterator;
myIterable.forEach(System.out::println);

Ou obtenha um Iterator da superinterface Java 8 BaseStream da interface Stream.

// Save the iterator of a stream that generates fib sequence
Iterator<Integer> myGenerator = Stream
        // Generates Fib sequence
        .iterate(new Integer[]{ 1, 1 }, x -> new Integer[] { x[1], x[0] + x[1] })
        .map(x -> x[0]).iterator();

// Print the first 5 elements
for (int i = 0; i < 5; i++) {
    System.out.println(myGenerator.next());
}

System.out.println("done with first iteration");

// Print the next 5 elements
for (int i = 0; i < 5; i++) {
    System.out.println(myGenerator.next());
}

/* Output:
1
1
2
3
5
done with first iteration
8
13
21
34
55 */

C #

Um exemplo de gerador C # 2.0 (o yieldestá disponível desde C # versão 2.0): Ambos os exemplos utilizam genéricos, mas isso não é obrigatório. A palavra-chave yield também ajuda a implementar iterações com estado personalizadas em uma coleção, conforme discutido nesta discussão.

// Method that takes an iterable input (possibly an array)
// and returns all even numbers.
public static IEnumerable<int> GetEven(IEnumerable<int> numbers)
{
    foreach (int number in numbers)
    {
        if ((number % 2) == 0)
        {
            yield return number;
        }
    }
}

É possível usar várias yield returninstruções e elas são aplicadas em sequência em cada iteração:

public class CityCollection : IEnumerable<string>
{
    public IEnumerator<string> GetEnumerator()
    {
        yield return "New York";
        yield return "Paris";
        yield return "London";
    }
}

XL

No XL , os iteradores são a base dos loops 'for':

import IO = XL.UI.CONSOLE

iterator IntegerIterator (var out Counter : integer; Low, High : integer) written Counter in Low..High is
    Counter := Low
    while Counter <= High loop
        yield
        Counter += 1

// Note that I needs not be declared, because declared 'var out' in the iterator
// An implicit declaration of I as an integer is therefore made here
for I in 1..5 loop
    IO.WriteLn "I=", I

F #

F # fornece geradores por meio de expressões de sequência , desde a versão 1.9.1. Eles podem definir uma sequência (avaliada lentamente, acesso sequencial) via seq { ... }, uma lista (avaliada avidamente, acesso sequencial) via [ ... ]ou uma matriz (avaliada avidamente, acesso indexado) via [| ... |]que contém o código que gera valores. Por exemplo,

seq { for b in 0 .. 25 do
          if b < 15 then
              yield b * b }

forma uma sequência de quadrados de números de 0 a 14, filtrando os números do intervalo de números de 0 a 25.

Pitão

Geradores foram adicionados ao Python na versão 2.2 em 2001. Um exemplo de gerador:

from typing import Iterator

def countfrom(n: int) -> Iterator[int]:
    while True:
        yield n
        n += 1

# Example use: printing out the integers from 10 to 20.
# Note that this iteration terminates normally, despite
# countfrom() being written as an infinite loop.

for i in countfrom(10):
    if i <= 20:
        print(i)
    else:
        break

# Another generator, which produces prime numbers indefinitely as needed.
import itertools

def primes() -> Iterator[int]:
    yield 2
    n = 3
    p = []
    while True:
        # If dividing n by all the numbers in p, up to and including sqrt(n),
        # produces a non-zero remainder then n is prime.
        if all(n % f > 0 for f in itertools.takewhile(lambda f: f*f <= n, p)):
            yield n
            p.append(n)
        n += 2

Em Python, um gerador pode ser considerado um iterador que contém um frame de pilha congelado . Sempre que next()é chamado no iterador, o Python retoma o quadro congelado, que é executado normalmente até que a próxima yieldinstrução seja alcançada. O frame do gerador é então congelado novamente e o valor gerado é retornado ao chamador.

PEP 380 (implementado em Python 3.3) adiciona a yield fromexpressão, permitindo que um gerador delegue parte de suas operações a outro gerador ou iterável.

Expressões geradoras

Python tem uma sintaxe modelada na de compreensões de lista , chamada de expressão geradora que auxilia na criação de geradores. O seguinte estende o primeiro exemplo acima usando uma expressão geradora para calcular quadrados da countfromfunção geradora:

squares = (n * n for n in countfrom(2))

for j in squares:
    if j <= 20:
        print(j)
    else:
        break

ECMAScript

ECMAScript 6 (também conhecido como Harmony) introduziu funções geradoras.

Uma sequência infinita de Fibonacci pode ser escrita usando um gerador de função:

function* fibonacci(limit) {
    let [prev, curr] = [0, 1];
    while (!limit || curr <= limit) {
        yield curr;
        [prev, curr] = [curr, prev + curr];
    }
}

// bounded by upper limit 10
for (const n of fibonacci(10)) {
    console.log(n);
}

// generator without an upper bound limit
for (const n of fibonacci()) {
    console.log(n);
    if (n > 10000) break;
}

// manually iterating
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

// picks up from where you stopped
for (const n of fibGen) {
    console.log(n);
    if (n > 10000) break;
}

R

O pacote iterators pode ser usado para esse propósito.

library(iterators)

# Example ------------------
abc <- iter(c('a','b','c'))
nextElem(abc)

Conversa fiada

Exemplo em Pharo Smalltalk :

O gerador de proporção áurea abaixo retorna para cada invocação 'goldenRatio next' uma melhor aproximação da proporção áurea.

goldenRatio := Generator on: [ :g | | x y z r | 
	x := 0.
	y := 1.
	[  
		z := x + y.
		r := (z / y) asFloat.
		x := y.
		y := z.
		g yield: r
	] repeat	
].

goldenRatio next.

A expressão abaixo retorna as próximas 10 aproximações.

Character cr join: ((1 to: 10) collect: [ :dummy | ratio next ]).

Veja mais em Uma joia escondida em Pharo: Generator .

Veja também

Notas

  1. ^ Qual é a diferença entre um Iterador e um Gerador?
  2. ^ Kiselyov, Oleg (janeiro de 2004). "Formas gerais de percorrer coleções no Scheme" .
  3. ^ Anthony Ralston (2000). Enciclopédia de ciência da computação . Nature Pub. Grupo. ISBN 978-1-56159-248-7. Retirado em 11 de maio de 2013 .
  4. ^ A linguagem de programação de ícones utiliza geradores para implementar sua avaliação direcionada a metas. No Icon, os geradores podem ser chamados em contextos fora das estruturas de controle de loop normal.
  5. ^ Liskov, Barbara (abril de 1992). "A History of CLU" (PDF) . Arquivado do original (PDF) em 17/09/2003 . Página visitada em 05-01-2006 .
  6. ^ a b Python Enhancement Proposals: PEP 255: Simple Generators , PEP 289: Generator Expressions , PEP 342: Co-rotinas via Enhanced Generators
  7. ^ rendimento (referência C #)
  8. ^ Liskov, B .; Snyder, A .; Atkinson, R .; Schaffert, C. (1977). "Mecanismos de abstração em CLU". Comunicações da ACM . 20 (8): 564–576. CiteSeerX  10.1.1.112.656 . doi : 10.1145 / 359763.359789 . S2CID  17343380 .
  9. ^ "Concorrência estruturada para C" .
  10. ^ "Geradores em C ++" . 21 de setembro de 2008.
  11. ^ "Qual é a palavra-chave de rendimento usada em C #?" . stackoverflow.com . Recuperado em 01/01/2018 .
  12. ^ "Alguns detalhes sobre expressões de computação F #" . Página visitada em 2007-12-14 .
  13. ^ PEP 380 - Sintaxe para delegar a um subgerador
  14. ^ Funções geradoras em R
  15. ^ "Geradores infinitos em R" . 5 de janeiro de 2013.

Referências

  • Stephan Murer, Stephen Omohundro , David Stoutamire e Clemens Szyperski: abstração de iteração em Sather . ACM Transactions on Programming Languages ​​and Systems , 18 (1): 1-15 (1996) [1]