 | This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Generator" computer programming – news ·newspapers ·books ·scholar ·JSTOR(July 2007) (Learn how and when to remove this message) |
Incomputer science, agenerator is aroutine that can be used to control theiteration behaviour of aloop. All generators are alsoiterators.[1] A generator is very similar to afunction that returns anarray, in that a generator hasparameters, can be called, and generates a sequence of values. However, instead of building an array containing all the values and returning them all at once, a generatoryields the values one at a time, which requires lessmemory and allows the caller to get started processing the first few values immediately. In short, a generatorlooks like a function butbehaves like aniterator.
Generators can be implemented in terms of more expressivecontrol flow constructs, such ascoroutines or first-classcontinuations.[2] Generators, also known as semicoroutines,[3] are a special case of (and weaker than) coroutines, in that they always yield control back to the caller (when passing a value back), rather than specifying a coroutine to jump to; seecomparison of coroutines with generators.
Generators are usuallyinvoked inside loops.[4] The first time that a generator invocation is reached in a loop, an iteratorobject is created that encapsulates the state of the generator routine at its beginning, with arguments bound to the correspondingparameters. The generator's body is then executed in the context of that iterator until a specialyield action is encountered; at that time, the value provided with theyield action is used as the value of the invocation expression. The next time the same generator invocation is reached in a subsequent iteration, the execution of the generator's body is resumed after theyield action, until yet anotheryield action is encountered. In addition to theyield action, execution of the generator body can also be terminated by afinish action, at which time the innermost loop enclosing the generator invocation is terminated. In more complicated situations, a generator may be used manually outside of a loop to create an iterator, which can then be used in various ways.
Because generators compute their yielded values only on demand, they are useful for representingstreams, such as sequences that would be expensive or impossible to compute at once. These include e.g. infinite sequences and live data streams.
When eager evaluation is desirable (primarily when the sequence is finite, as otherwise evaluation will never terminate), one can either convert to alist, or use a parallel construction that creates a list instead of a generator. For example, in Python a generatorg can be evaluated to a listl vial = list(g), while inF# the sequence expressionseq { ... } evaluates lazily (a generator or sequence) but[ ... ] evaluates eagerly (a list).
In the presence of generators, loop constructs of a language – such as for and while – can be reduced into a single loop ... end loop construct; all the usual loop constructs can then be comfortably simulated by using suitable generators in the right way. For example, a ranged loop likefor x = 1 to 10 can be implemented as iteration through a generator, as in Python'sfor x in range(1, 10). Further,break can be implemented as sendingfinish to the generator and then usingcontinue in the loop.
Generators first appeared inCLU (1975),[5] were a prominent feature in the string manipulation languageIcon (1977) and are now available inPython (2001),[6]C#,[7]Ruby,PHP,[8]ECMAScript (as ofES6/ES2015), and other languages. In CLU and C#, generators are callediterators, and in Ruby,enumerators.
The finalCommon Lisp standard does not natively provide generators, yet various library implementations exist, such asSERIES documented in CLtL2 orpygen.
A yield statement is used to implement iterators over user-defined data abstractions.[9]
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;
Every expression (including loops) is a generator. The language has many generators built-in and even implements some of the logic semantics using the generator mechanism (logical disjunction or "OR" is done this way).
Printing squares from 0 to 20 can be achieved using a co-routine by writing:
localsquares,jsquares:=create(seq(0)^2)everyj:=|@squaresdoifj<=20thenwrite(j)elsebreak
However, most of the time custom generators are implemented with the "suspend" keyword which functions exactly like the "yield" keyword in CLU.
C does not have generator functions as a language construct, but, as they are a subset ofcoroutines, it is simple to implement them using any framework that implements stackful coroutines, such as libdill.[10] On POSIX platforms, when the cost ofcontext switching per iteration is not a concern, or fullparallelism rather than merelyconcurrency is desired, a very simple generator function framework can be implemented usingpthreads andpipes.
It is possible to introduce generators into C++ using pre-processor macros. The resulting code might have aspects that are very different from native C++, but the generator syntax can be very uncluttered.[11] The set of pre-processor macros defined in this source allow generators defined with the syntax as in the following example:
$generator(descent){inti;// place the constructor of our generator, e.g.// descent(int minv, int maxv) {...}// from $emit to $stop is a body of our generator:$emit(int)// will emit int values. Start of body of the generator.for(i=10;i>0;--i)$yield(i);// similar to yield in Python,// returns next number in [1..10], reversed.$stop;// stop, end of sequence. End of body of the generator.};
This can then be iterated using:
intmain(intargc,char*argv[]){descentgen;for(intn;gen(n);)// "get next" generator invocationprintf("next number is %d\n",n);return0;}
Moreover,C++11 allowsforeach loops to be applied to any class that provides thebegin andend functions. It's then possible to write generator-like classes by defining both the iterable methods (begin andend) and the iterator methods (operator!=,operator++ andoperator*) in the same class. For example, it is possible to write the following program:
#include<iostream>intmain(){for(inti:range(10)){std::cout<<i<<std::endl;}return0;}
A basic range implementation would look like that:
classrange{private:intlast;intiter;public:range(intend):last(end),iter(0){}// Iterable functionsconstrange&begin()const{return*this;}constrange&end()const{return*this;}// Iterator functionsbooloperator!=(constrange&)const{returniter<last;}voidoperator++(){++iter;}intoperator*()const{returniter;}};
Furthermore,C++20 formally introduced support for coroutines,[12] which can be used to implement generators.[13]C++23 introducedstd::generator in the standard library, making it much easier to implement generators. For example, a basic range generator can be implemented as:
#include<generator>std::generator<int>range(intn){for(inti=0;i<n;++i){co_yieldi;}}
It can be iterated usingforeach loops:
#include<iostream>intmain(){for(inti:range(10)){std::cout<<i<<std::endl;}return0;}
Perl does not natively provide generators, but support is provided by theCoro::Generator module which uses theCoro co-routine framework. Example usage:
usestrict;usewarnings;# Enable generator { BLOCK } and yielduseCoro::Generator;# Array reference to iterate overmy$chars=['A'...'Z'];# New generator which can be called like a coderef.my$letters=generator{my$i=0;formy$letter(@$chars){# get next letter from $charsyield$letter;}};# Call the generator 15 times.print$letters->(),"\n"for(0..15);
Example parallel to Icon uses Raku (formerly/aka Perl 6) Range class as one of several ways to achieve generators with the language.
Printing squares from 0 to 20 can be achieved by writing:
for (0 .. *).map(* **2) ->$i {lastif$i >20;say$i}
However, most of the time custom generators are implemented with "gather" and "take" keywords in a lazy context.
InTcl 8.6, the generator mechanism is founded on namedcoroutines.
procgenerator{body}{coroutinegen[incr::disambiguator]apply{{script}{# Produce the result of [generator], the name of the generatoryield[infocoroutine]# Do the generationeval$script# Finish the loop of the caller using a 'break' exceptionreturn-codebreak}}$body}# Use a simple 'for' loop to do the actual generationsetcount[generator{for{seti10}{$i<=20}{incri}{yield$i}}]# Pull values from the generator until it is exhaustedwhile1{puts[$count]}
InHaskell, with itslazy evaluation model, every datum created with anon-strict data constructor is generated on demand. For example,
countFrom::Integer->[Integer]countFromn=n:countFrom(n+1)from10to20::[Integer]from10to20=takeWhile(<=20)$countFrom10primes::[Integer]primes=2:3:nextPrime5wherenextPrimen|notDivisiblen=n:nextPrime(n+2)|otherwise=nextPrime(n+2)notDivisiblen=all((/=0).(remn))$takeWhile((<=n).(^2))$tailprimes
where(:) is a non-strict list constructor,cons, and$ is just a"called-with" operator, used for parenthesization. This uses the standard adaptor function,
takeWhilep[]=[]takeWhilep(x:xs)|px=x:takeWhilepxs|otherwise=[]
which walks down the list and stops on the first element that doesn't satisfy the predicate. If the list has been walked before until that point, it is just a strict data structure, but if any part hadn't been walked through before, it will be generated on demand. List comprehensions can be freely used:
squaresUnder20=takeWhile(<=20)[x*x|x<-countFrom10]squaresForNumbersUnder20=[x*x|x<-takeWhile(<=20)$countFrom10]
Racket provides several related facilities for generators. First, its for-loop forms work withsequences, which are a kind of a producer:
(for([i(in-range1020)])(printf"i = ~s\n"i))
and these sequences are also first-class values:
(define10-to-20(in-range1020))(for([i10-to-20])(printf"i = ~s\n"i))
Some sequences are implemented imperatively (with private state variables) and some are implemented as (possibly infinite) lazy lists. Also, new struct definitions can have a property that specifies how they can be used as sequences.
But more directly, Racket comes with a generator library for a more traditional generator specification. For example,
#langracket(requireracket/generator)(define(ints-fromfrom)(generator()(for([i(in-naturalsfrom)]); infinite sequence of integers from 0(yieldi))))(defineg(ints-from10))(list(g)(g)(g)); -> '(10 11 12)
Note that the Racket core implements powerful continuation features, providing general (re-entrant) continuations that are composable, and also delimited continuations. Using this, the generator library is implemented in Racket.
The community ofPHP implemented generators in PHP 5.5. Details can be found in the originalRequest for Comments: Generators.
Infinite Fibonacci sequence:
functionfibonacci():Generator{$last=0;$current=1;yield1;while(true){$current=$last+$current;$last=$current-$last;yield$current;}}foreach(fibonacci()as$number){echo$number,"\n";}
Fibonacci sequence with limit:
functionfibonacci(int$limit):Generator{yield$a=$b=$i=1;while(++$i<$limit){yield$a=($b=$a+$b)-$a;}}foreach(fibonacci(10)as$number){echo"$number\n";}
Any function which contains ayield statement is automatically a generator function.
Ruby supports generators (starting from version 1.9) in the form of the built-in Enumerator class.
# Generator from an Enumerator objectchars=Enumerator.new(['A','B','C','Z'])4.times{putschars.next}# Generator from a blockcount=Enumerator.newdo|yielder|i=0loop{yielder.yieldi+=1}end100.times{putscount.next}
Java has had a standard interface for implementing iterators since its early days, and since Java 5, the "foreach" construction makes it easy to loop over objects that provide thejava.lang.Iterable interface. (TheJava collections framework and other collections frameworks, typically provide iterators for all collections.)
recordPair(inta,intb){};Iterable<Integer>myIterable=Stream.iterate(newPair(1,1),p->newPair(p.b,p.a+p.b)).limit(10).map(p->p.a)::iterator;myIterable.forEach(System.out::println);
Or get an Iterator from theJava 8 super-interface BaseStream of Stream interface.
recordPair(inta,intb){};// Save the iterator of a stream that generates fib sequenceIterator<Integer>myGenerator=Stream// Generates Fib sequence.iterate(newPair(1,1),p->newPair(p.b,p.a+p.b)).map(p->p.a).iterator();// Print the first 5 elementsfor(inti=0;i<5;i++){System.out.println(myGenerator.next());}System.out.println("done with first iteration");// Print the next 5 elementsfor(inti=0;i<5;i++){System.out.println(myGenerator.next());}
Output:
11235done with first iteration813213455
An example C# 2.0 generator (theyield is available since C# version 2.0):Both of these examples utilize generics, but this is not required. yield keyword also helps in implementing custom stateful iterations over a collection as discussed in this discussion.[14]
// Method that takes an iterable input (possibly an array)// and returns all even numbers.publicstaticIEnumerable<int>GetEven(IEnumerable<int>numbers){foreach(intnumberinnumbers){if((number%2)==0){yieldreturnnumber;}}}
It is possible to use multipleyield return statements and they are applied in sequence on each iteration:
publicclassCityCollection:IEnumerable<string>{publicIEnumerator<string>GetEnumerator(){yieldreturn"New York";yieldreturn"Paris";yieldreturn"London";}}
InXL, iterators are the basis of 'for' loops:
import IO = XL.UI.CONSOLEiterator IntegerIterator (var out Counter : integer; Low, High : integer) written Counter in Low..High is Counter := Low while Counter <= High loop yield Counter += 1// Note that I needs not be declared, because declared 'var out' in the iterator// An implicit declaration of I as an integer is therefore made herefor I in 1..5 loop IO.WriteLn "I=", I
F# provides generators viasequence expressions, since version 1.9.1.[15] These can define a sequence (lazily evaluated, sequential access) viaseq { ... }, a list (eagerly evaluated, sequential access) via[ ... ] or an array (eagerly evaluated, indexed access) via[| ... |] that contain code that generates values. For example,
seq{forbin0..25doifb<15thenyieldb*b}
forms a sequence of squares of numbers from 0 to 14 by filtering out numbers from the range of numbers from 0 to 25.
Generators were added toPython in version 2.2 in 2001.[6] An example generator:
fromtypingimportIteratordefcountfrom(n:int)->Iterator[int]:whileTrue:yieldnn+=1# Example use: printing out the integers from 10 to 20.# Note that this iteration terminates normally, despite# countfrom() being written as an infinite loop.foriincountfrom(10):ifi<=20:print(i)else:break# Another generator, which produces prime numbers indefinitely as needed.importitertoolsdefprimes()->Iterator[int]:"""Generate prime numbers indefinitely as needed."""yield2n=3p=[2]whileTrue:# If dividing n by all the numbers in p, up to and including sqrt(n),# produces a non-zero remainder then n is prime.ifall(n%f>0forfinitertools.takewhile(lambdaf:f*f<=n,p)):yieldnp.append(n)n+=2
In Python, a generator can be thought of as aniterator that contains a frozenstack frame. Whenevernext() is called on the iterator, Python resumes the frozen frame, which executes normally until the nextyield statement is reached. The generator's frame is then frozen again, and the yielded value is returned to the caller.
PEP 380 (implemented in Python 3.3) adds theyield from expression, allowing a generator to delegate part of its operations to another generator or iterable.[16]
Python has a syntax modeled on that oflist comprehensions, called a generator expression that aids in the creation of generators.The following extends the first example above by using a generator expression to compute squares from thecountfrom generator function:
squares=(n*nfornincountfrom(2))forjinsquares:ifj<=20:print(j)else:break
ECMAScript 6 (a.k.a. Harmony) introduced generator functions.
An infinite Fibonacci sequence can be written using a function generator:
function*fibonacci(limit){let[prev,curr]=[0,1];while(!limit||curr<=limit){yieldcurr;[prev,curr]=[curr,prev+curr];}}// bounded by upper limit 10for(constnoffibonacci(10)){console.log(n);}// generator without an upper bound limitfor(constnoffibonacci()){console.log(n);if(n>10000)break;}// manually iteratingletfibGen=fibonacci();console.log(fibGen.next().value);// 1console.log(fibGen.next().value);// 1console.log(fibGen.next().value);// 2console.log(fibGen.next().value);// 3console.log(fibGen.next().value);// 5console.log(fibGen.next().value);// 8// picks up from where you stoppedfor(constnoffibGen){console.log(n);if(n>10000)break;}
The iterators package can be used for this purpose.[17][18]
library(iterators)# Example ------------------abc<-iter(c('a','b','c'))nextElem(abc)
Example inPharo Smalltalk:
TheGolden ratio generator below returns to each invocation 'goldenRatio next' a better approximation to the Golden Ratio.
goldenRatio:=Generatoron: [:g|| x y z r|x:=0.y:=1.[z:=x+y.r:= (z/y)asFloat.x:=y.y:=z.gyield:r]repeat].goldenRationext.
The expression below returns the next 10 approximations.
Charactercrjoin: ((1to:10)collect: [:dummy|rationext ]).
See more inA hidden gem in Pharo: Generator.
