Generátor (programování)

Generátor je v programování speciální funkce, kterou lze používat pro řízení opakování ve smyčkách. Všechny generátory jsou vlastně iterátory. Generátory se velmi podobají funkcím vracejícím pole tím, že mají parametry, lze je volat a generují posloupnosti hodnot. Na rozdíl od vytváření celých polí však generátory vydávají hodnoty po jedné, což šetří paměť, umožňuje pracovat s neomezenými sadami hodnot nebo s postupně vznikajícími hodnotami a dovoluje, aby volající mohl zpracovávat první hodnotu okamžitě. Jednoduše řečeno, generátor vypadá jako funkce ale se chová jako iterátor.

Generátory mohou být implementovány pomocí expresivnějších řídicích struktur, například korutin nebo kontinuací první třídy. Generátory jsou někdy označovány za semikorutiny, a lze je považovat za speciální (slabší) případ korutin, protože při vrácení hodnoty vždy předávají řízení zpátky volajícímu, zatímco při použití obecných korutin je třeba pro získání stejného chování provést skok do volající korutiny; viz srovnání korutin s generátory.

Použití

Generátory se nejčastěji používají pro řízení smyček. Při prvním vyvoláním generátoru je vytvořen objekt, který zapouzdřuje stav generátorové funkce na začátku iterátoru, s argumenty propojenými s odpovídajícími parametry. Tělo generátoru se pak provádí v kontextu tohoto iterátoru, dokud se nedojde ke speciální akci yield; v tom okamžiku se vrátí hodnota výrazu uvedeného v akci yield, která bude návratovou hodnotou generátoru. Jakmile provádění programu dosáhne opět místa vyvolání generátoru, pokračuje se v provádění těla generátoru za akcí yield, dokud se nedojde k další akci yield. Generátor může být ukončen akcí finish, což způsobí ukončení vnitřní smyčky generátoru. Ve složitějších situacích může být generátor používán manuálně mimo smyčku pro vytvoření iterátoru, který pak může být používán různými způsoby.

Protože generátory počítají a vydávají hodnoty pouze v případě potřeby, lze je použít pro reprezentaci sekvenčního přístupu k souborům pomocí datových proudů, které fungují jako posloupností, jejichž získání vcelku by bylo nákladné nebo nemožné. Díky tomu lze zahrnout i nekonečné posloupnosti a živé datové proudy.

Je-li žádoucí hladové vyhodnocování (primárně u konečných posloupností, protože jinak by vyhodnocování posloupnosti nikdy neskončilo), lze posloupnost buď převést na seznam nebo použít paralelní konstrukci, která místo generátoru vytváří seznam. Například v jazyce Python lze generátor g převést na seznam l příkazem l = list(g), zatímco v jazyce F# se výraz pro posloupnost seq { ... } vyhodnocuje odloženě (pro vytvoření generátoru), zatímco [ ... ] se vyhodnocuje hladově (pro vytvoření seznamu).

Pokud programovací jazyk disponuje generátory, lze všechny druhy smyček – například for a while – realizovat jediným typem smyčky s použitím vhodného generátoru. Například smyčku for x = 1 to 10 lze implementovat pomocí generátoru podobného pythonovskému for x in range(1, 10). Ukončení smyčky (příkaz break) lze implementovat jako odeslání povelu finish do generátoru následovaného příkazem continue pro provedení kódu, který se provádí před každým průchodem smyčkou a který následně provádění smyčky ukončí.

Dostupnost

Generátory se poprvé objevily v jazyce CLU (1975), staly se význačnou vlastností jazyka pro manipulace s řetězci Icon (1977) a nyní jsou dostupné v mnoha jazycích včetně jazyka Python, C#, Ruby i v novějších verzích jazyka ECMAScript (od ES6/ES2015). V CLU a C# se generátory nazývají iterators, v Ruby enumerators.

Lisp

Ani poslední standard jazyka Common Lisp generátory nativně neobsahuje, ale existují jejich různé implementace v podobě knihoven, jako například SERIES zdokumentovaném v CLtL2 nebo pygen.

CLU

Pro implementaci iterátorů přes uživatelem definované datové abstrakce se používá příkaz yield:

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;

Icon

V jazyce Icon je generátorem každý výraz (včetně smyček). Icon poskytuje mnoho vestavěných generátorů a dokonce implementuje část sémantiky logických výrazů pomocí generátorů (tímto způsobem je implementováno logické „OR“).

Vypsání druhých mocnin čísel od 0 do 20 lze provést pomocí korutiny takto:

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

Uživatelem definované generátory jsou však obvykle implementovány pomocí klíčového slova „suspend“, které funguje stejně jako klíčové slovo „yield“ v CLU.

C

V jazyce C nejsou generátorové funkce jako jazykový konstrukt, protože je však lze implementovat pomocí korutin, není obtížné je implementovat nad libovolnou knihovnou, která implementuje stackful korutiny, jako například libdill. Pokud na platformách podporujících POSIX není omezující cena přepnutí kontextu při každé iteraci a je vyžadován plný paralelismus místo slabší souběžnosti, lze implementovat velmi jednoduchý rámec pro funkční generátory pomocí Posix threads a anonymních rour.

C

Do C je možné na zavést generátory pomocí maker preprocesoru. Výsledný kód může mít velmi odlišné rysy od nativního C . Ale syntaxe generátoru může být naprosto nekomplikovaná. Velmi dobré příklady lze nalézt v , který definuje sadu preprocesorových maker umožňující definovat generátory s touto syntaxí:

$generator(descent)
{
   // místo pro všechny proměnné používané v generátoru
   int i; // náš čítač

   // konstruktor našeho generátoru, například 
   // descent(int minv, int maxv) {...}
   
   // tělo generátoru je mezi $emit a $stop:
    
   $emit(int) // bude vracet hodnoty typu int. Začátek těla generátoru.
      pro (i = 10; i > 0; --i)
         $yield(i); // jako yield v Pythonu,
                    // vrátí další číslo v obrácené posloupnosti [1..10].
   $stop; // stop, konec posloupnosti. Konec těla generátoru.
};

Iterace může vypadat takto:

int main(int argc, char* argv[])
{
  descent gen;
  for (int n; gen(n);) // vyvolání „get next“ generátoru
    printf("další číslo je %d\n", n);
  return 0;
}

C 11 navíc umožňuje provádět cyklus foreach na jakékoli třídě, která poskytuje funkce begin a end. Pak lze třídy vypadající jako generátory vytvářet definováním obou iterovatelných metod (begin a end) a metody iterátoru (operator!=, operator a operator*) ve stejné třídě. Například takto:

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

Základní implementace rozsahu může být následující:

class range
{
private:
    int posledni;
    int iter;

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

    // Iterativní funkce
    const range& begin() const { return *this; }
    const range& end() const { return *this; }

    // Funkce iterátoru
    bool operator!=(const range&) const { return iter < posledni; }
    void operator  () {   iter; }
    int operator*() const { return iter; }
};

Perl

Perl nativně generátory neposkytuje, ale lze použít modul Coro::Generator, který používá framework korutin Coro. Příklad použití:

use strict;
use warnings;
# Povolí generátor { BLOCK } a yield
use Coro::Generator;
# reference na pole, přes které lze iterovat
my $chars = ['A'...'Z'];

# Nový generátor, který lze volat jako coderef.
my $pismena = generator {
    my $i = 0;
    for my $pism (@$chars) {
        # získej další písmeno z $pismena
        yield $pism;
    }
};

# 15krát vyvolat generátor
print $pismena->(), "\n" for (0..15);

Tcl

V Tcl 8.6 používá mechanismus generátor založený na pojmenovaných korutinách.

proc generator {body} {
    coroutine gen[incr ::disambiguator] apply {{Script} {
        # Produkuje výsledek z [generator], jméno generátoru
        yield [info coroutine]
        # Vlastní generování
        eval $script
        # Ukončit smyčku volajícího pomocí výjimky 'break'
        return -code break
    }} $body
}

# Použití jednoduché 'for' smyčky pro skutečné generování
set count [generator {
    for {množina i 10} {$i <= 20} {incr i} {
        yield $i
    }
}]

# Načítej hodnoty z generátoru dokud není vyčerpaný
while 1 {
    puts [$count]
}

Haskell

V jazyce Haskell je díky odloženému vyhodnocování generátorem všechno - jakákoli data vytvořená nestriktním datovým konstruktorem se generují až v případě potřeby. Například

countfrom n = n : countfrom (n 1)

-- Příklad použití: vytisknout celá čísla od 10 do 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

kde (:) je nestriktní seznamový konstruktor, cons a $ jsou jen volané operátory, používané pro uzávorkování. Je použita standardní adaptorová funkce

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

která načítá hodnoty podle predikátu a přestane požadovat nové hodnoty jakmile se narazí na hodnotu, která nevyhovuje. V Haskellu se jako univerzální mediátor používá přístup ke sdílené paměti. Seznamové komprehense lze používat libovolně:

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

Racket

Programovací jazyk Racket poskytuje několik příbuzných nástrojů pro generátory. Jeho for-cyklus dovoluje pracovat s posloupnostmi, což je druh producer:

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

a tyto posloupnosti jsou také hodnoty první třídy:

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

Některé posloupnosti jsou implementovány imperativně (se soukromým stavem proměnných) a některé jsou implementovány jako líné seznamy (které mohou být i nekonečné). Také nové definice struktur mohou mít vlastnost, která určuje, jak mohou být používány jako posloupnosti.

Racket také obsahuje generátorovou knihovnu pro tradičnější vytváření generátorů. Například

#lang racket
(require racket/generator)
(define (ints-from from)
  (generator ()
    (for ([i (in-naturals from)] ; nekonečná posloupnost celých čísel od 0
      (yield i))))
(define g (ints-from 10))
(list (g) (g) (g)) ; -> '(10 11 12)

Jádro jazyka Racket implementuje mocné vlastnosti kontinuace a poskytuje obecné (reentrantní) kontinuace, které lze skládat a také ohraničené kontinuace. S jejich použitím je generátorová knihovna implementována přímo jazyce v Racket.

PHP

PHP komunita implementovala generátory v PHP 5.5. Detaily lze nalézt v původním dokumentu RFC about Generator.

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

Ruby

Ruby obsahuje podporu generátorů od verze 1.9 ve formě vestavěné třídy Enumerator.

# Generátor vytvořený pomocí objektu Enumerator
chars = Enumerator.new(['A', 'B', 'C', 'Z'])

4.times { puts chars.next }

# Generátor vytvořený z bloku
count = Enumerator.new do |yielder|
  i = 0
  loop { yielder.yield i  = 1 }
end

100.times { puts count.next }

Java

Java měla od počátku standardní rozhraní pro implementaci iterátorů a od verze Java 5 je k dispozici konstrukce „foreach“, která umožňuje provádět smyčky přes objekty, které poskytují rozhraní java.lang.Iterable. Frameworky jako Java collections framework (JCF) obvykle poskytují iterátory pro všechny kolekce.)

Nicméně Java nemá generátory vestavěné v jazyce. To znamená, že vytváření iterátorů je často mnohem složitější než v jazycích s vestavěnými generátory, zvláště když logika vytváření je komplikovaná. Protože je třeba ukládat a obnovovat kompletní stav pokaždé, když se z iterátoru získává nová položka, není možné ukládat stav v lokálních proměnných nebo používat vestavěné funkce pro vytváření cyklů, jako kdyby generátory byly dostupné; namísto toho je třeba všechno simulovat manuálně pomocí cílových polí pro ukládání lokálního stavu a čítačů smyček.

I jednoduché iterátory vytvořené tímto způsobem bývají výrazně složitější než iterátory používající generátory, a obsahují velké množství pevného kódu.

Původní příklad by mohl v Javě 5 vypadat takto:

// Iterátor implementovavaný jako anonymní třída. Používá šablony, ale nevyžaduje je.
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 další() {
                return counter  ;
            }

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

Nekonečnou Fibonacciho posloupnost lze v Javě 5 zapsat jako Iterátor:

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();
            }
        };
    }
}
// toto lze používat takto...
for (int f: fibo) {
    System.out.println("Další Fibonacciho číslo je "   f);
    if (someCondition(f)) break;
}

V Java 8 lze vytvořit i nekonečné Fibonacciho posloupnosti pomocí rozhraní Stream:

IntStream.generovat(new IntSupplier() {
    int = 1, b = 2;

    public int getAsInt() {
        int temp =;
        a = b;
        b = a   temp;
        return temp;
    }
}).forEach(System.out::println);

Nebo Iterátor získat ze super-rozhraní BaseStream rozhraní Stream Javy 8.

public Iterable<Integer> fibonacci(int limit){
    return IntStream.generovat(new IntSupplier() {
        int = 1, b = 2;

        public int getAsInt() {
            int temp = a;
            a = b;
            b = a   temp;
            return temp;
        }
    }).limit(limit).boxed()::iterator;
}

// použití:
for (int f: fibonacci(10)) {
    System.out.println(f);
}

C#

Příklad generátoru v jazyce C# 2.0 (yield je dostupné od C# verze 2.0): Oba příklady využívají Generics, ale nevyžadují jej. Klíčové slovo yield také pomůže v implementaci přizpůsobitelné stavové iterace přes kolekce, jak se diskutuje v diskuzi.

// Metoda, které načítá iterovatelný vstup (např. pole)
// a vrácí všechna sudá čísla.
public static IEnumerable<int> GetEven(IEnumerable<int> numbers) {
    foreach (int i in numbers) {
        if ((i % 2) == 0) {
            yield return i;
        }
    }
}

Lze použít i více příkazů yield return, které se pak provedou postupně při každé iteraci:

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

XL

V jazyce XL jsou iterátory základem smyčky '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

// Pamatujte, že I nemusí být deklarováno, protože je v iterátoru uvedeno 'var out'
// Implicitní deklarace I jako celočíselné proměnné je provedena zde
for I in 1..5 loop
    IO.WriteLn "I=", I

F#

Podrobnější informace naleznete v článku Seznamový výraz.

F# poskytuje generátory od verze 1.9.1 jako seznamové výrazy, které mohou definovat posloupnost (s odloženým vyčíslováním, se sekvenčním přístupem) pomocí seq { ... }, seznam (hladově vyčíslovaný, se sekvenčním přístupem) pomocí [ ... ] nebo pomocí pole (hladové vyčíslované, s indexovaným přístupem) pomocí [| ... |] obsahujícím kód, který generuje hodnoty. Například

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

vytváří posloupnost druhých mocnin čísel od 0 do 14 vyfiltrováním čísel z rozsahu 0 až 25.

Python

Generátory byly do jazyka Python zavedeny ve verzi 2.2. Příklad generátoru:

def countfrom(n):
    while True:
        yield n
        n  = 1

# Příklad použití: vytisknout celá čísla od 10 do 20.
# Cyklus skončí normálně, i když je funkce countfrom()
# napsaná jako nekonečná smyčka.

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

# Generátor produkující libovolný počet prvočísel podle potřeby:

def primes():
    yield 2
    n = 3
    p = []
    while True:
        # Funguje in Python 2.5  
        if not any(n % f == 0 for f in 
                     itertools.takewhile(lambda f: f*f <= n, p)): 
            yield n
            p.append(n)
        n  = 2

Na generátory lze v Pythonu pohlížet jako na iterátory, které obsahují zmrazený zásobníkový rámec. Kdykoli se vyvolá metoda iterátoru next(), Python obnoví zmrazený rámec, který bude použit pro provádění kódu, dokud se nenarazí na další příkaz yield. Generátor's rámec pak je zmrazený opět a yielded hodnota je returned do volajícímu.

PEP 380 (implementovaný v Pythonu 3.3) zavádí výraz yield from dovolující generátoru delegovat část své funkce na jiný generátor.

Generátorové výrazy

Python převzal syntaxi seznamových komprehenzí, které volají generátorový výraz pro vytváření generátorů. Následující ukázka rozšiřuje předchozí příklad použitím generátorového výrazu pro výpočet druhých mocnin z generátorové funkce countfrom:

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

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

ECMAScript

ECMAScript zavedl generátory ve verzi 6 (Harmony).

Nekonečnou Fibonacciho posloupnost lze napsat pomocí funkčního generátoru:

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

// zadání horní meze
for (let n of fibonacci(10)) {
    console.log(n);
}

// generátor bez horní meze
for (let n of fibonacci()) {
    console.log(n);
    if (n > 10000) break;
}

// ruční iterace
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

// vybere, kde přestat
for (let n of fibGen) {
    console.log(n);
    if (n > 10000) break;
}

R

V jazyce R lze pro vytváření generátorů použít balíček iterators.

library(iterators)

# Příklad ------------------
abc <- iter(c('a','b','c'))
nextElem(abc)

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Generator (computer programming) na anglické Wikipedii.

Související články

• Seznamová komprehenze – jiný konstrukt, které generuje posloupnost hodnot
• Iterátor – vychází z konceptu vytváření seznamu po jednom prvku
• Iteratee – další alternativa
• Odložené vyhodnocování – vytváření hodnot v případě potřeby
• Corecursion – získávání potenciálně nekonečných dat rekurzí místo yield
• Koprogram – dokonce více zobecnění podprogramů
• Continuation – zobecnění řídicích struktur

Externí odkazy

• MURER, Stephan; OMOHUNDRO, Stephen; STOUTAMIRE, David; SZYPERSKI, Clemens. ACM Transactions on Programming Languages and Systems. Leden 1996, roč. 18, čís. 1. Dostupné online. 

Autoritní data	BNF: cb122247630 (data) GND: 4129040-9 LCCN: sh85053846 NLI: 987007562694505171