Generator (informatika)

U računarstvu, **generator** je specijalni potprogram koji može biti upotrebljen za kontrolu iteracijskog ponašanja ponavljanja . U suštini, svi generatori su iteratori. Generartor je veoma sličan funkciji koja vraća niz, u kojoj generator ima parametre, koja se može pozvati, i generisati sekvencu vrednosti. Međutim, umesto da se pravi niz koji sadrži sve te elemente i i vraća sve njih, poziv generatora vraća jednu i samo jednu vrednost, što zahteva manje memorije i dopušta programeru da počne sa procesuiranjem prvih nekoliko vrednosti odmah. Ukratko, generator liči na funkciju ali se ponaša kao iterator.

Generatori mogu biti implementirani u pogledu brže konstrukcije kontrole protoka, kao što su korutine ili nastavljanje prve-klase. Generatori, takođe poznati kao polu-korutine, su specijalni slučaj (i slabiji od) korutina, u smislu da uvek daju povratnu kontrolu programeru (kada se vraća vrednost), umesto da odredi putanju korutini, videti komparacija korutina sa geratorima. 

## Upotreba
Generatori se uglavnom izvršavaju unutar petlje. Prvi put kada se generator izvrši u petlji, iteretorni objekat je kreiran da enkapsulira stanje generatora na njegovom početku, sa argumentima vezanih za odgovarajuće parametre. Telo generatora je tada izvršavano u vidu iteratora sve do „yield“ naredbe; tada je vrednost obezbeđena operacijom „yield' korišćena kao vrednost prizvanog izraza. Sleći put kada se pozove generator u naknadnoj iteraciji, izvršavanje tela generatora se nastavlja nakon operacije „yield“, sve dok ne dođe do sledeće „yield“ operacije. U prilog operaciji „yield“, izvršavanje tela generatora se može završiti uz pomoć „finish“ naredbe, u kojoj se prekida ponavljanje u petlji generatora. U mnogo komplikovanijim situacijama, generatori mogu biti korišćeni izvan petlje da bi se napravila iteracija, koja onda može biti upotrebljena na razne načine.

Pošto generatori izvršavaju njihove date vrednosti samo na poziv funkcije "yield“, korisni su za predstavljanje toka, kao sekvence koje bi bile skupe ili nemoguće za izvršavanje odjednom. Ovo uključuje e.g. beskonačan broj sekvenci i tokova podataka.

Kada je željena procena poželjna (prvenstvetno kada je sekvenca konačna, jer se u suprotnom evaluacije nikad neće izvršiti), jedan može da se konvertuje u listu, ili da se koristi kao paralelni konstruktor koji kreira listu umesto generatora. Na primer u Pajtonu generator `g` može biti označen listom `l` kao `l = list(g)`, dok se u  F# ekspresija sekvenci `seq { ... }`  izvršava sporo (generator ili sekvenca) ali `[ ... ]` se izvršava efikasnije i poželjnije (lista).

U prisustvu generatora, konstrukcija petlje programa- kao što su for i while- može biti redukovana u jednu petlju...kraj konstrukcije petlje; sve obično korišćene konstrukcije petlji mogu biti stimulisane koristeći ispravno pogodan generator   . Na primer, rangirana petlja kao što je `for x = 1 to 10` može biti implementirana kao iteracija kroz generator, kao i u Pajtonu `for x in xrange(10, 1)`. Osim toga, `break` može biti implementirana tako što šalje naredbu * kraj*  generatoru i posle toga koristeći `continue` u petlji.

## Izgled
Generatori su se prvo pojavili u CLU  (1975), gde je istaknuta odlika u vidu manipulacije stringa u programskom jeziku Icon (Ajkon) (1977) a sada je dostupna u Pajtonu, C#, Rubi, nadolazećoj verziji ECMASkript (Harmonija/ES6) i drugim programima. U CLU i C#, generatori se nazivaju „iteratori“, a u programskom jeziku Rubi, "enumeratori".

### Lisp
Konačni Zajednički Lisp ne podržava prirodno generatore, još postoji varirajuća biblioteka implementacija, kao što su SERIJE dokumentovane u CLtL2 ili pajgenu (pygen).

### CLU (CLU)
Yield funkcija je korišćena da implementira iteratore preko korisničko-definisane abstrakcije podataka .
```text
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;
```


### Ajkon (Icon)
Svaka ekspresija (uključujući petlje) je generator. Program ima mnogo ugrađenih generatora, čak i neke logičko semantičke implementacije koriste mehanizam generatora (Disjunkcija ili "ILI" je urađena tako).

Štampanje kvadrata od 0 do 20 se postiže koristeći ko-rutine, pišući:  
```icon
local squares, j
   squares := create (seq(0) ^ 2)
   every j := |@squares do
      if j <= 20 then
         write(j)
      else
         break
```
Međutim, uglavnom se željeni generatori implementiraju sa *suspendovanom* ključnom rečju sa funkcijama kao što je *yield* ključna reč u CLU.

### C++
Moguće je uvesti generatore u C++ koristeći pre-procesorske makroe. Rezultirajući kod može imati aspekte različite od prirode C++, ali sintaksa generatora može biti vrlo neopterećena. Veoma dobar primer se može naći na. Komplet preprocesorskih makroa definisanih u ovom kodu dozvoljava generatore definisanih sintaksama kao u sledećem primeru :
```cpp
$generator(descent)
{
   // mesto za sve vrednosti korišćene u generatoru
   int i; // naš brojač

   // mesto konstrukcije našeg generatora, e.g. 
   // vrednost (int minv, int maxv) {...}
   
   // od $(emit)emitovanja do $(stop)stop je telo našeg generatora:
    
   $emit(int) // će emitovati celobrojne vrednosti. Poćetak tela generatora:
      for (i = 10; i > 0; --i)
         $yield(i); // poznato kao yield u Pajtonu,
                    // vraća sledeći broj u [1..10], preokrenut.
   $stop; // stop, kraj sekvence. Kraj tela generatora.
};
```
Ovo može biti izvršeno koristeći:
```cpp
int main(int argc, char* argv[])
{
  descent gen;
  for(int n; gen(n);) // "sledeći" poziv generatora
    printf("next number is %d\n", n);
  return 0;
}
```
Štaviše, C++11 dozvoljava svakoj petlji da bude primenjena u bilo kojoj klasi koja podržava `begin` i `end` funkcije. Onda je moguće napisati generator kao klase uz pomoć obe merne metode (`begin` and `end`) i iterativne metode (`operator!=`, `operator++` and `operator*`) u istoj klasi. Na primer, moguće je napisati sledeći proram:
```cpp
#uključujući <iostream>
int main()
{
    for (int i: range(10))
    {
        std::cout << i << std::endl;
    }
    return 0;
}
```
Osnovni domet implementacije bi trebalo da izgleda ovako:
```cpp
class range
{
private:
    int last;
    int iter;

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

    // Merne funkcije
    const range& begin() const { return *this; }
    const range& end() const { return *this; }

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


### Perl (Perl)
Perl nema prirodno ugrađene generatore, ali podržavanje je sponzorisano od strane Koro Generatora modul koji koristi Koro ko-rutine okvir. Primer korišćenja. 
```perl
koristiti striktno;
koristiti upozorenja;
# Aktivirati generator { BLOCK } i ''yield''
koristiti Koro::Generator;
# Niz upućuje na izvršavanje preko mojih $znakova = ['A'...'Z'];
# Novi generator se može nazvati ''coderef''.
my $letters = generator {
    my $i = 0;
    for my $letter (@$chars) {
        # uzmi sledeće slovo od $chars
        yield $letter;
    }
};
# Pozovi generator 15 puta.
print $letters->(), "\n" for (0..15);
```


### Tcl (Tcl)
U Tcl-y 8.6, mehanizam generatora počiva na imenovanju korutina.
```tcl
proc generator {body} {
    coroutine gen[incr ::disambiguator] apply  $body
}
# Koristiti jednostavnu 'for' petlju za stvaranje 
set count[generator {
    for {set i 10} {$i <= 20} {incr i} {
        yield $i
    }
}]
# Izvlači vrednosti iz generatora dok se ne iscrpe
while 1 {
    puts [$count]
}
```


### Haskel (Haskell)
U Haskelu, sa sporim određivanjem vrdnosti modelom, sve je generator- svaki datum kreiran sa ne-strogom konstrukcijom podataka je generisan na zahtev. Na primer,
```haskell
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
```
gde je `(:)` ne-stroga lista konstruktora, *protiv*, i `$` je samo *"pozovi-sa"* operator, korišćen za parentizaciju. Ovo koristi standarni adaptor funkcija,
```haskell
takeWhile p [] = []
takeWhile p (x:xs) | p x = x : takeWhile p xs
                   | otherwise = []
```
čije se ponovno pronađene vrednosti slažu sa iskazom, i prestaju sa traženjem novih vrednosti čim se izvrši jedna neodgovarajuća vrednost. Pristup zajedničkom skladištu je korišćeno kao univerzalan posrednik u Haskelu. Lista shvatanja može biti besplatno korišćena:
```haskell
test2 = mapM_ print $ takeWhile (<= 20) [x*x | x <- countfrom 10]
test3 = mapM_ print [x*x | x <- takeWhile (<= 20) $ countfrom 10]
```


### Raket (Racket)
Raket omogućava nekoliko pratećih objekata za generatore. Prvo, njena for-petlja ima formu rada sa sekvencama, koja je vrsta proizvođača:
```scheme
(for ([i (in-range 10 20)])
  (printf "i = ~s\n" i))
```
i ove sekvence su takođe vrednosti prve-klase:
```scheme
(define 10-to-20 (in-range 10 20))
(for ([i 10-to-20])
  (printf "i = ~s\n" i))
```
Neke sekvence su imperativno implementirane (sa skrivenim vrednostima varijabli) a neke su implementirane kao (verovatno beskonačne) lenje liste. Takođe, nova struktura definicije može imati moć koja određuje kako se mogu koristiti kao sekvence.

Ali više direktno, Raket ima laboratoriju generatora za tradicionalnu specifikaciju generatora. Na primer,
```scheme
#''lang'' raket
(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)
```
Primetiti da Raketovo jezgro implementira snažnu ponavljajuću karakteristiku, obezbeđujući opšta ponavljanja koja su kompatibilna ali takođe i ograničena. Koristeći ovo, biblioteka generatora je implementirana u Raketu.

### PHP (PHP)
Zajednica PHP-a je implementirala generatore u PHP 5.5. Detalji se mogu pornaći na RFC o generatorima.
```php
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";
}
```


### Rubi (Ruby)
Rubi podržava generatore (počevši od verzije 1.9) u formi ugrađene Enumeratorske klase.
```ruby
# Generator iz Enumeratorskog objekta
chars = Enumerator.new(['A', 'B', 'C', 'Z'])

4.times { puts chars.next }
# Generator iz bloka
count = Enumerator.new do |yielder
| i = 0
  loop { yielder.yield i += 1 }
end

100.times { puts count.next }
```


### Java
Java je imala standardni pristup za implementiranje iteratora još od ranih svojih dana, i od Jave 5, *foreach* konstrukcija čini to lakšim za ponavljanje preko objekata koje omogućava *java.lang.Iterable* pristup. ( Okvir java kolekcije i ostale okvirne kolekcije, proizvode iteratore za sve kolekcije.)

Međutim, Java nema ugrađene generatore. Ovo znači da je kreiranje iteratora češće mnogo komplikovanije nego u programima koji imaju ugrađene generatore, pogotovo kada je stvaranje kompleksno. Zbog toga što se sve vrednosti moraju snimiti i sačuvati svaki put kada se pozove stvar iz iteratora, nije moguće sačuvati vrednosti u lokalnim varijablama ili koristiti ugrađenu ponavljačku rutinu, kao kada su generatori dostupni; umesto toga, sve ovo mora biti manalno simulirano, koristeći polja da čuva lokalnu vrednost i broj ponavljanja.

Čak i jednostavni iteratori izgrađeni na ovaj način imaju tedenciju da budu značajno glomazniji od onih koji koriste generatori, sa mnogo opštenamenskih kodova.

Originalan primer se može napisati u **Java 7** kao:
```java
// Iterator je implementiran kao anonimna klasa. Ovo se koristi generički ali nije potrebno.
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);
}
```
Beskonačna Fibonačijeva sekvenca se takođe može mapisati kao iterator u **Java 7**:
```java
Iterable<Integer> fibo = new Iterable<Integer>() {
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int a = 1, b = 1;
            int total;

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

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

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
};
// ovo se zatim može koristiti kao...
for (int f: fibo) {
    System.out.println("next Fibonacci number is " + f);
    if (someCondition(f)) break;
}
```


Takođe, beskonačna Fibonačijeva sekvenca se može napisati i u **Java 8** koristeći tok pristupa:
```java
Stream.generate(new Supplier<Integer>() {
    int a = 1, b = 2;

    public Integer get() {
        int temp = a;
        a = b;
        b = a + temp;
        return temp;
    }
}).forEach(System.out::print);
```
Ili kao iterator iz Java 8 super-pristupa OsnovnogToka toka pristupa.
```java
public Iterable<Integer> fibonacci(int limit){
    return ()->{
        return Stream.generate(new Supplier<Integer>() {
            int a = 1, b = 2;

            public Integer get() {
                int temp = a;
                a = b;
                b = a + temp;
                return temp;
            }
        }).limit(limit).iterator();
    }
}

// ovo se zatim može koristiti kao...
for (int f: fibonacci(10)) {
    System.out.println(f);
}
```


### C#
Primer C# 2.0 generatora ( `yield` je dostušam od C# verzije 2.0):
Oba ova primera se koriste generički, ali ne moraju. 
```csharp
// Metoda koja uzima merni ulaz (verovatno niz)
// i vraća sve parne brojeve.
public static IEnumerable<int> GetEven(IEnumerable<int> numbers) {
    foreach (int i in numbers) {
        if ((i % 2) == 0) {
            yield return i;
        }
    }
}
```
Moguće je koristiti više puta `yield return` funkciju i one se nalaze u sekvenci svake iteracije:
```csharp
public class CityCollection : IEnumerable<string> {
    public IEnumerator<string> GetEnumerator() {
        yield return "New York";
        yield return "Paris";
        yield return "London";
    }
}
```


### HL(XL)
U HL-u, iteratori su osnova "for" petlje:
```text
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

// Primetiti da I ne treba da bude deklarisano, zbog deklarisanog ''var out'' u iteratoru
// Implicitna deklaracija I kao celobrojna vrednost je napravljena ovde
for I in 1..5 loop
    IO.WriteLn "I=", I
```


### F#
F# sadrži generatore preko e*kspresija sekvence,* od verzije1.9.1. Ovo može definisati sekvencu (sporu, sekvencijalnog pristupa) preko `seq { ... }`, liste (brza, sekvencijalnog pristupa) preko `[ ... ]` ili niza (brz, indeksnog pristupa) preko `[| ... |]` koja sadrži kod koji generiše vrednosti. Na primer,
```fsharp
seq { for b in 0 .. 25 do
          if b < 15 then
              yield b * b }
```
forma sekvence kvadrata brojeva od 0 do 14, ispitivanjem brojeva u rasponu od 0. do 25.

### Pajton (Python)
Generatori su dodati u Pajton u verziji 2.2. Primer generatora:
```python
def countfrom(n):
    while True:
        yield n
        n += 1
# Primer: štampa celobrojne vrednosti od 10 do 20
# Primetiti da se ova iteracija prestaje sa izvršavanjem normalno, uprkos
# countfrom() je napisana kao beskonačna petlja.

for i in countfrom(10):
    if i <= 20:
        print(i)
    else:
        break
# Još jedan generator, koji proizvodi proste bojeve neograničeno, tj. koliko je nama potrebno.

def primes():
    yield 2
    n = 3
    p = []
    while True:
        # Ovo radi u Pajtonovim verzijama 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
```
U Pajtonu, generator može biti misao iteratora koji sadrži nepromenljiv (zaleđen) okvir skladišta  . Kad god je iteratorova `next()` metoda pozvana, Pajton nastavlja nepromenljiv okvir, koji se izvršava normalno sve dok ne stigne do `yield` funkcije. Generatorov okvir je zaleđen ponovo, i pozvana vrednost je vraćena pozivaocu (korisniku).

PEP (PEP) 380 (ubačen u Pajton 3.3) dodaje yield from ekspresiju, koja dozvoljava generatoru da proverava deo njegovih operacia za drugi generator .

#### Ekspresije Generatora
Pajton ima modeliranu sintaksu po uzoru na listu spoznaja, koja se naziva ekspresija generatora i koja pomaže u kreiranju generatora. Sledeći primer pokazuje korišćenje ekspresije generatora da se izračuna kvadrat iz brojača (funkcije generatora):
```python
squares = ( n*n for n in countfrom(2) )

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


### ECMASkript (ECMAScript)
ECMASkript 6 (poznata kao Harmonija) će imati funkcije generatora.

Beskonačna Fibonačijeva sekvecna se može napisati koristeći funkciju generatora:
```javascript
// inspirisano od strane: http://wiki.ecmascript.org/doku.php?id=harmony:generators
function* fibonacci() {
    let [prev, curr] = [0, 1];
    while (true) {
        yield curr;
        [prev, curr] = [curr, prev + curr];
    }
}

var gen = fibonacci();
console.log(gen.next().value); // 1
console.log(gen.next().value); // 1
console.log(gen.next().value); // 2
console.log(gen.next().value); // 3
console.log(gen.next().value); // 5
console.log(gen.next().value); // 8
```


## Povezano
* Lista želja za ostale konstrukcije koje sadrže sekvence vrednosti
* Iterator za koncept stvaranja jednog elementa liste u vremenu
* Iterejtee za alternativu
* Spora dodela vrednosti za proizvodnju vrednosti kada su potrebne
* Ko-rekurzija za potencijalno beskonačnu vrednost uz pomoć rekurzije umesto "yield"
* Korutine za još veću generalizovaciju od sabrutine
* Nastavljanje za generalizaciju kontrole protoka

## Reference

## Literatura
* Stefan Murer, Stiv Omohundro, Dejvid Stotumaer i Klemens Siperski: abstrakcija iteracije u Sateru. *ACM Transakcije na Programske jezike i Sisteme*, 18(1):1-15 (1996) http://portal.acm.org/citation.cfm?doid=225540.225541