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. +more 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 { . +more } 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). +more 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 [url=http://www. cs. +morecmu. edu/Groups/AI/html/cltl/clm/node347. html#SECTION003400000000000000000]SERIES[/url] zdokumentovaném v CLtL2 nebo [url=https://web. archive. org/web/20110723043455/http://cliki. net/pygen]pygen[/url].

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

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

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++. +more 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. +more 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. +more=, operator++ a operator*) ve stejné třídě. Například takto:.

#include int main { for (int i: range(10)) { std::cout 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

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

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 (

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. +more Seznamové komprehense lze používat libovolně:.

test2 = mapM_ print $ takeWhile (

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 [url=https://wiki.php.net/rfc/generators]RFC about Generator[/url].

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. +moreIterable. 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á. +more 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 { @Override public Iterator iterator { return new Iterator { int counter = 1;

@Override public boolean hasNext { return counter

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

Iterable fibo = new Iterable { @Override public Iterator iterator { return new Iterator { 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. +moreout. 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 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. +more0): 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. +more public static IEnumerable GetEven(IEnumerable 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 { public IEnumerator 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

F#

F# poskytuje generátory od verze 1. 9. +more1 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

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

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. +more 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

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 10000) break; }

// ruční iterace let fibGen = fibonacci; console. log(fibGen. +morenext. 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

Odkazy

Reference

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

Kategorie:Programovací konstrukce