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[1]. 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[2]. Generátory jsou někdy označovány za semikorutiny[3], 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[4]. 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)[5], 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[6], C#[7], 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[8]:
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[9]. 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 [10], 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[11], který používá framework korutin Coro[12]. 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[13].
// 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#
F# poskytuje generátory od verze 1.9.1 jako seznamové výrazy[14], 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[6]. 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[15].
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[16][17].
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.
- ↑ https://stackoverflow.com/questions/1022564/what-is-the-difference-between-an-iterator-and-a-generator
- ↑ KISELJOV, Oleg. General ways to traverse collections in Scheme [online]. Leden 2004. Dostupné online.
- ↑ Anthony Ralston. Encyclopedia of computer science. [s.l.]: Nature Pub. Group, 2000. Dostupné online. ISBN 978-1-56159-248-7.[nedostupný zdroj]
- ↑ Jazyk Icon využívá generátory pro implementaci cílově orientovaného vyhodnocování. V jazyce Icon lze generátory vyvolat i mimo řídicí struktury realizující cykly
- ↑ LISKOV, Barbara. A History of CLU [pdf]. Duben 1992 [cit. 2019-02-04]. Dostupné v archivu pořízeném dne 2003-09-17.
- ↑ a b Python Enhancement Proposals: PEP 255: Simple Generators, PEP 289: Generator Expressions, PEP 342: Coroutines via Enhanced Generators
- ↑ yield (C# Reference)
- ↑ LISKOV, B.; SNYDER, A.; ATKINSON, R. Abstraction mechanisms in CLU. Communications of the ACM. 1977. DOI 10.1145/359763.359789.
- ↑ Structured Concurrency for C [online]. [cit. 2019-02-04]. Dostupné v archivu pořízeném dne 2019-12-02.
- ↑ projeku CPP generators. www.codeproject.com [online]. [cit. 2019-02-04]. Dostupné v archivu pořízeném z originálu dne 2019-02-07.
- ↑ https://metacpan.org/module/Coro::Generator
- ↑ https://metacpan.org/module/Coro
- ↑ What is the yield keyword used for in C#? [online]. [cit. 2018-01-01]. Dostupné online.
- ↑ Some Details on F# Computation Expressions [online]. [cit. 2007-12-14]. Dostupné online.
- ↑ PEP 380 -- Syntax for Delegating to a Subgenerator
- ↑ http://stackoverflow.com/a/16028448/4745348
- ↑ http://cartesianfaith.wordpress.com/2013/01/05/infinite-generators-in-r/
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.
