Generator (računarstvo)

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 npr. 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 apstrakcije podataka .

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:  

   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 :

$generator(descent)
{
   // место за све вредности коришћене у генератору
   int i; // наш бројач

   // место конструкције нашег генератора, нпр. 
   // вредност (int minv, int maxv) {...}
   
   // од $(emit)емитовања до $(stop)стоп је тело нашег генератора:
    
   $emit(int) // ће емитовати целобројне вредности. Поћетак тела генератора:
      for (i = 10; i > 0; --i)
         $yield(i); // познато као yield у Пајтону,
                    // враћа следећи број у [1..10], преокренут.
   $stop; // стоп, крај секвенце. Крај тела генератора.
};

Ovo može biti izvršeno koristeći:

int main(int argc, char* argv[])
{
  descent gen;
  for(int n; gen(n);) // "следећи" позив генератора
    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:

#укључујући <iostream>
int main()
{
    for (int i: range(10))
    {
        std::cout << i << std::endl;
    }
    return 0;
}

Osnovni domet implementacije bi trebalo da izgleda ovako:

class range
{
private:
    int last;
    int iter;

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

    // Мерне функције
    const range& begin() const { return *this; }
    const range& end() const { return *this; }

    // Функције итератора
    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. 

користити стриктно;
користити упозорења;
# Активирати генератор { BLOCK } и ''yield''
користити Коро::Генератор;
# Низ упућује на извршавање преко мојих $знакова = ['A'...'Z'];
# Нови генератор се може назвати ''coderef''.
my $letters = generator {
    my $i = 0;
    for my $letter (@$chars) {
        # узми следеће слово од $chars
        yield $letter;
    }
};
# Позови генератор 15 пута.
print $letters->(), "\n" for (0..15);

Tcl (Tcl)

U Tcl-y 8.6, mehanizam generatora počiva na imenovanju korutina.

proc generator {body} {
    coroutine gen[incr ::disambiguator] apply {{script} {
        # продукује резултат [генератора], име генератора
        yield [info corutine]
        # Уради стварање
        eval $script
        # Завршити петљу позива користећи 'break' изузетак.
        return -code break
    }} $body
}
# Користити једноставну 'for' петљу за стварање 
set count[generator {
    for {set i 10} {$i <= 20} {incr i} {
        yield $i
    }
}]
# Извлачи вредности из генератора док се не исцрпе
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,

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,

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:

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:

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

i ove sekvence su takođe vrednosti prve-klase:

(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,

#''ланг'' ракет
(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.

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.

# Генератор из Енумераторског објекта
chars = Enumerator.new(['A', 'B', 'C', 'Z'])

4.times { puts chars.next }
# Генератор из блока
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:

// Итератор је имплементиран као анонимна класа. Ово се користи генерички али није потребно.
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:

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();
            }
        };
    }
};
// ово се затим може користити као...
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:

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.

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();
    }
}

// ово се затим може користити као...
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. 

// Метода која узима мерни улаз (вероватно низ)
// и враћа све парне бројеве.
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:

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:

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

// Приметити да I не треба да буде декларисано, због декларисаног ''var out'' у итератору
// Имплицитна декларација I као целобројна вредност је направљена овде
for I in 1..5 loop
    IO.WriteLn "I=", I

F#

F# sadrži generatore preko ekspresija 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,

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:

def countfrom(n):
    while True:
        yield n
        n += 1
# Пример: штампа целобројне вредности од 10 до 20
# Приметити да се ова итерација престаје са извршавањем нормално, упркос
# countfrom() је написана као бесконачна петља.

for i in countfrom(10):
    if i <= 20:
        print(i)
    else:
        break
# Још један генератор, који производи просте бојеве неограничено, тј. колико је нама потребно.

def primes():
    yield 2
    n = 3
    p = []
    while True:
        # Ово ради у Пајтоновим верзијама 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):

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:

// инспирисано од стране: 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

Vidi još

• 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

Literatura

• Ralston, Anthony (2000). Encyclopedia of computer science. Nature Pub. Group. ISBN 978-1-56159-248-7. Pristupljeno 11. 5. 2013. CS1 održavanje: Format datuma (veza)
• Murer, Stephan; Omohundro, Stephen; Stoutamire, David; Szyperski, Clemens (1996). „Iteration abstraction in Sather”. ACM Transactions on Programming Languages and Systems. 18 (1): 1—15. S2CID 7334897. doi:10.1145/225540.225541.