Generator (computer programming): Difference between revisions

Revision as of 00:22, 17 June 2020

Latest revision as of 09:03, 12 August 2025

(66 intermediate revisions by 33 users not shown)

Line 1:

{{Short description|Routine that generates a sequence of values}}

{{other uses|Generator (disambiguation)#Computing}}

{{Refimprove|date=July 2007}}

In [[computer science]], a '''generator''' is a [[subroutine|routine]] that can be used to control the [[iteration]] behaviour of a [[control flow#Loops|loop]]. All generators are also [[iterator]]s.<ref>[https://stackoverflow.com/q/1022564 What is the difference between an Iterator and a Generator?]</ref> A generator is very similar to a [[Function (computer programming)|function]] that returns an [[Array (data structure)|array]], in that a generator has [[Parameter (computer programming)|parameters]], 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 generator ''yields'' the values one at a time, which requires less [[Computer memory|memory]] and allows the caller to get started processing the first few values immediately. In short, a generator ''looks like'' a function but ''behaves like'' an [[iterator]].

Generators can be implemented in terms of more expressive [[control flow]] constructs, such as [[coroutine]]s or first-class [[continuation]]s.<ref>{{cite web

Line 11 ⟶ 12:

| title = General ways to traverse collections in Scheme

| url = http://okmij.org/ftp/Scheme/enumerators-callcc.html

}}</ref> Generators, also known as semicoroutines,<ref name="Ralston2000">{{cite book|author=Anthony Ralston|title=Encyclopedia of computer science|url=https://books.google.com/books?id=yQ9LAQAAIAAJ|accessdateaccess-date=11 May 2013|year=2000|publisher=Nature Pub. Group|isbn=978-1-56159-248-7}}</ref> 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; see [[Coroutine#Comparison with generatorsGenerators|comparison of coroutines with generators]].

==Uses==

Line 23 ⟶ 24:

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 like <code>for x = 1 to 10</code> can be implemented as iteration through a generator, as in Python's <code>for x in range(1, 10)</code>. Further, <code>break</code> can be implemented as sending ''finish'' to the generator and then using <code>continue</code> in the loop.

==Languages providing generators==

==Timeline==

Generators first appeared in [[CLU (programming language)|CLU]] (1975),<ref>{{cite web

| last = Liskov

| first = Barbara

| authorlinkauthor-link = Barbara Liskov

| date = April 1992

| title = A History of CLU

| url = http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-561.pdf

| format = pdf

| access-date = 2006-01-05

| archive-url = https://web.archive.org/web/20030917041834/http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-561.pdf

Line 44:

</ref> [[C Sharp (programming language)|C#]],<ref>

[http://msdn.microsoft.com/en-us/library/9k7k7cf0.aspx yield (C# Reference)]

</ref> [[Ruby (programming language)|Ruby]], the[[PHP]],<ref>{{Cite laterweb|url=https://www.php.net/manual/en/language.generators.overview.php|title versions= ofPHP: Generators overview - Manual}}</ref> [[ECMAScript]] (as of [[ECMAScript#6th_Edition_–_ECMAScript_2015|ES6/ES2015]]), and other languages. In CLU and C#, generators are called ''iterators'', and in Ruby, ''enumerators''.

===Lisp===

Line 52:

===CLU===

A yield statement is used to implement iterators over user-defined data abstractions.<ref name=Liskov1977>{{cite journal | citeseerx=10.1.1.112.656 | last1 = Liskov | first1 = B. | last2 = Snyder | first2 = A. | last3 = Atkinson | first3 = R. | last4 = Schaffert | first4 = C. | title = Abstraction mechanisms in CLU | journal = Communications of the ACM | volume = 20 | issue = 8 | year = 1977 | accessdatepages = 564–576 | access-date = <!-- 24 May 2013 --> | doi = 10.1145/359763.359789 | s2cid = 17343380 }}</ref>

<syntaxhighlight lang="text">

Line 74:

Printing squares from 0 to 20 can be achieved using a co-routine by writing:

<syntaxhighlight lang="icon">

<pre>

local squares, j

squares := create (seq(0) ^ 2)

Line 82:

else

break

</syntaxhighlight>

</pre>

However, most of the time custom generators are implemented with the "suspend" keyword which functions exactly like the "yield" keyword in CLU.

Line 88:

===C===

[[C (programming language)|C]] does not have generator functions as a [[language construct]], but, as they are a subset of [[coroutines]], it is simple to implement them using any framework that implements stackful coroutines, such as libdill.<ref>{{cite web|url=http://libdill.org|title=Structured Concurrency for C}}</ref>. On POSIX platforms, when the cost of [[context switching]] per iteration is not a concern, or full [[Parallel_computing|parallelism]] rather than merely [[Concurrency (computer_science)|concurrency]] is desired, a very simple generator function framework can be implemented using [[pthreads]] and [[Anonymous_pipe|pipes]].

===C++===

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.<ref>{{Cite web|url = http://www.codeproject.com/KB/cpp/cpp_generators.aspx|title = Generators in C++|date = 21 September 2008|access-date = 9 January 2012|archive-date = 7 February 2019|archive-url = https://web.archive.org/web/20190207185018/https://www.codeproject.com/KB/cpp/cpp_generators.aspx|url-status = dead}}</ref> The set of pre-processor macros defined in this source allow generators defined with the syntax as in the following example:

<syntaxhighlight lang="cpp">$generator(descent) {

$generator(descent)

{

int i;

Line 109 ⟶ 107:

// returns next number in [1..10], reversed.

$stop; // stop, end of sequence. End of body of the generator.

};</syntaxhighlight>

};

</syntaxhighlight>

This can then be iterated using:

<syntaxhighlight lang="cpp">int main(int argc, char* argv[]) {

int main(int argc, char* argv[])

{

descent gen;

for (int n; gen(n);) // "get next" generator invocation

printf("next number is %d\n", n);

return 0;

}</syntaxhighlight>

}

</syntaxhighlight>

Moreover, [[C++11]] allows [[foreach loop]]s to be applied to any class that provides the <code>begin</code> and <code>end</code> functions. It's then possible to write generator-like classes by defining both the iterable methods (<code>begin</code> and <code>end</code>) and the iterator methods (<code>operator!=</code>, <code>operator++</code> and <code>operator*</code>) in the same class. For example, it is possible to write the following program:

<syntaxhighlight lang="cpp">#include <iostream>

#include <iostream>

int main() {

for (int i: range(10)) {

{

for (int i: range(10))

{

std::cout << i << std::endl;

}

return 0;

}</syntaxhighlight>

}

</syntaxhighlight>

A basic range implementation would look like that:

<syntaxhighlight lang="cpp">

class range {

{

private:

int last;

Line 162 ⟶ 152:

int operator*() const { return iter; }

};

</syntaxhighlight>Furthermore, [[C++20]] formally introduced support for coroutines,<ref>{{Cite web |title=Coroutines (C++20) - cppreference.com |url=https://en.cppreference.com/w/cpp/language/coroutines.html |access-date=2025-07-16 |website=en.cppreference.com}}</ref> which can be used to implement generators.<ref>{{Cite web |last=Carter |first=Casey |last2=Baker |first2=Lewis |last3=Jabot |first3=Corentin |title=std::generator implementation in C++20 |url=https://godbolt.org/z/5hcaPcfvP |access-date=2025-07-16 |website=godbolt.org |language=en}}</ref> [[C++23]] introduced [https://en.cppreference.com/w/cpp/coroutine/generator.html std::generator] in the standard library, making it much easier to implement generators. For example, a basic range generator can be implemented as:<syntaxhighlight lang="cpp">

</syntaxhighlight>

#include <generator>

std::generator<int> range(int n) {

for (int i = 0; i < n; ++i) {

co_yield i;

}

}

</syntaxhighlight>It can be iterated using [[foreach loop]]s:<syntaxhighlight lang="cpp">#include <iostream>

int main() {

for (int i: range(10)) {

std::cout << i << std::endl;

}

return 0;

}</syntaxhighlight>

===Perl===

Line 189 ⟶ 194:

</syntaxhighlight>

===Raku===

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:

<syntaxhighlight lang="raku">

for (0 .. *).map(* ** 2) -> $i {

last if $i > 20;

say $i

}

</syntaxhighlight>

However, most of the time custom generators are implemented with "gather" and "take" keywords in a lazy context.

===Tcl===

Line 221 ⟶ 240:

===Haskell===

In [[Haskell (programming language)|Haskell]], with its [[lazy evaluation]] model, everything is a generator - every datum created with a [[Non-strict evaluation|non-strict]] data constructor is generated on demand. For example,

<syntaxhighlight lang="haskell">

countFrom :: Integer -> [Integer]

countfrom n = n : countfrom (n+1)

countFrom n = n : countFrom (n + 1)

from10to20 :: [Integer]

-- Example use: printing out the integers from 10 to 20.

test1from10to20 = mapM_ print $ takeWhile (<= 20) $ countfromcountFrom 10

primes = 2 : 3 : nextprime 5 where[Integer]

primes = 2 : 3 : nextPrime 5

nextprime n | b = n : nextprime (n+2)

where

| otherwise = nextprime (n+2)

nextPrime n

where b = all ((/= 0).(rem n)) $ takeWhile ((<= n).(^2)) $ tail primes

| notDivisible n = n : nextPrime (n + 2)

| otherwise = nextPrime (n + 2)

notDivisible n =

all ((/= 0) . (rem n)) $ takeWhile ((<= n) . (^ 2)) $ tail primes

</syntaxhighlight>

where <code>(:)</code> is a non-strict list constructor, ''cons'', and <code>$</code> is just a ''"called-with"'' operator, used for parenthesization. This uses the standard adaptor function,

Line 239 ⟶ 263:

| otherwise = []

</syntaxhighlight>

which re-fetcheswalks valuesdown agreeablethe withlist aand stops on the first element that doesn't satisfy the predicate,. andIf stopsthe requestinglist newhas valuesbeen aswalked soonbefore asuntil athat non-agreeablepoint, oneit is encountered.just Thea sharedstrict storage[[data accessstructure]], isbut usedif asany apart hadn't been walked through before, it will universalbe mediatorgenerated inon Haskelldemand. List comprehensions can be freely used:

<syntaxhighlight lang="haskell">

test2squaresUnder20 = mapM_ print $ takeWhile (<= 20) [x * x | x <- countfromcountFrom 10]

test3squaresForNumbersUnder20 = mapM_ print [x * x | x <- takeWhile (<= 20) $ countfromcountFrom 10]

</syntaxhighlight>

Line 273 ⟶ 297:

===PHP===

[[File:UML generator in PHP.svg|thumb|UML class diagram depiction of the inheritance chain of the Generator class in PHP]]

The community of PHP implemented generators in PHP 5.5. Details can be found in the original [https://wiki.php.net/rfc/generators Request for Comments: Generators].

The community of [[PHP]] implemented generators in PHP 5.5. Details can be found in the original [https://wiki.php.net/rfc/generators Request for Comments: Generators].

Infinite Fibonacci sequence:

<syntaxhighlight lang="php">

function Fibonaccifibonacci(): {Generator

{

$last = 0;

$current = 1;

Line 289 ⟶ 316:

foreach (fibonacci() as $number) {

echo $number, "\n";

}

</syntaxhighlight>

Fibonacci sequence with limit:

<syntaxhighlight lang="php">

function fibonacci(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";

}

</syntaxhighlight>

Line 313 ⟶ 356:

===Java===

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 the <ttcode>java.lang.Iterable</ttcode> interface. (The [[Java collections framework]] and other collections frameworks, typically provide iterators for all collections.)

<syntaxhighlight lang="java">

However, [[Java (programming language)|Java]] does not have generators built into the language. This means that creating iterators is often much trickier than in languages with built-in generators, especially when the generation logic is complex. Because all state must be saved and restored every time an item is to be yielded from an iterator, it is not possible to store state in local variables or use built-in looping routines, as when generators are available; instead, all of this must be manually simulated, using object fields to hold local state and loop counters.

record Pair(int a, int b) {};

Even simple iterators built this way tend to be significantly bulkier than those using generators, with a lot of [[boilerplate code]].

Iterable<Integer> myIterable = Stream.iterate(new Pair(1, 1), p -> new Pair(p.b, p.a + p.b))

The original example above could be written in '''Java 5''' as:

.limit(10)

<syntaxhighlight lang="java">

.map(p -> p.a)::iterator;

// Iterator implemented as anonymous class. This uses generics but doesn't need to.

for (int i: new Iterable<Integer>() {

@Override

public Iterator<Integer> iterator() {

return new Iterator<Integer>() {

int counter = 1;

myIterable.forEach(System.out::println);

@Override

public boolean hasNext() {

return counter <= 100;

}

@Override

public Integer next() {

return counter++;

}

@Override

public void remove() {

throw new UnsupportedOperationException();

}

};

}

}) {

System.out.println(i);

}

</syntaxhighlight>

Or get an Iterator from the '''Java 8''' super-interface BaseStream of Stream interface.

An infinite Fibonacci sequence could also be written in '''Java 5''' as an Iterator:

<syntaxhighlight lang="java">

Iterable<Integer> fibo = new Iterable<Integer>() {

@Override

public Iterator<Integer> iterator() {

return new Iterator<Integer>() {

int a = 1, b = 2;

record Pair(int a, int b) {};

@Override

public boolean hasNext() {

return true;

}

// Save the iterator of a stream that generates fib sequence

@Override

Iterator<Integer> myGenerator = Stream

public Integer next() {

// Generates Fib int temp = a;sequence

.iterate(new Pair(1, 1), p -> new Pair(p.b, p.a =+ p.b;))

.map(p -> b = p.a + temp).iterator();

return temp;

}

// Print the first 5 elements

@Override

for (int i = 0; i < 5; public void remove(i++) {

System.out.println(myGenerator.next());

throw new UnsupportedOperationException();

}

};

}

};

// this could then be used as...

for (int f: fibo) {

System.out.println("next Fibonacci number is " + f);

if (someCondition(f)) break;

}

</syntaxhighlight>

System.out.println("done with first iteration");

Also an infinite Fibonacci sequence could also be written using '''Java 8''' Stream interface:

<syntaxhighlight lang="java">

IntStream.generate(new IntSupplier() {

int a = 1, b = 2;

// Print the next 5 elements

public int getAsInt() {

for (int i = 0; i < 5; inti++) temp = a;{

System.out.println(myGenerator.next());

a = b;

}

b = a + temp;

return temp;

}

}).forEach(System.out::println);

</syntaxhighlight>

Output:

Or get an Iterator from the '''Java 8''' super-interface BaseStream of Stream interface.

<syntaxhighlight lang="javaconsole">

1

public Iterable<Integer> fibonacci(int limit){

1

return IntStream.generate(new IntSupplier() {

2

int a = 1, b = 2;

3

5

public int getAsInt() {

done with first iteration

int temp = a;

8

a = b;

13

b = a + temp;

21

return temp;

34

}

55

}).limit(limit).boxed()::iterator;

}

// this could then be used as...

for (int f: fibonacci(10)) {

System.out.println(f);

}

</syntaxhighlight>

Line 426 ⟶ 416:

// Method that takes an iterable input (possibly an array)

// and returns all even numbers.

public static IEnumerable<int> GetEven(IEnumerable<int> numbers)
{

foreach (int inumber in numbers) {

{
if ((inumber % 2) == 0) {

{
yield return inumber;

}

}

Line 437 ⟶ 430:

It is possible to use multiple <code>yield return</code> statements and they are applied in sequence on each iteration:

<syntaxhighlight lang="csharp">

public class CityCollection : IEnumerable<string>
{

public IEnumerator<string> GetEnumerator() {

{

yield return "New York";

yield return "Paris";

Line 466 ⟶ 461:

===F#===

{{further information|Sequence expression}}

[[F Sharp (programming language)|F#]] provides generators via ''[[sequence expression]]s,'' since version 1.9.1.<ref name="seq">{{cite web | url = http://blogs.msdn.com/dsyme/archive/2007/09/22/some-details-on-f-computation-expressions-aka-monadic-or-workflow-syntax.aspx | title = Some Details on F# Computation Expressions | accessdateaccess-date = 2007-12-14}}</ref> These can define a sequence (lazily evaluated, [[sequential access]]) via <code>seq { ... }</code>, a list (eagerly evaluated, sequential access) via <code>[ ... ]</code> or an array (eagerly evaluated, indexed access) via <code>[| ... |]</code> that contain code that generates values. For example,

<syntaxhighlight lang="fsharp">

seq { for b in 0 .. 25 do

Line 500 ⟶ 495:

def primes() -> Iterator[int]:

"""Generate prime numbers indefinitely as needed."""

yield 2

n = 3

p = [2]

while True:

# If dividing n by all the numbers in p, up to and including sqrt(n),

# produces a non-zero remainder then n is prime.

if all(n % f > 0 for f in itertools.takewhile(lambda f: f * f <= n, p)):

yield n

p.append(n)

Line 514 ⟶ 510:

In Python, a generator can be thought of as an [[iterator]] that contains a frozen [[stack frame]]. Whenever <code>next()</code> is called on the iterator, Python resumes the frozen frame, which executes normally until the next <code>yield</code> 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 the <ttcode>yield from</ttcode> expression, allowing a generator to delegate part of its operations to another generator or iterable.<ref name="pep380">[https://www.python.org/dev/peps/pep-0380/ PEP 380 -- Syntax for Delegating to a Subgenerator]</ref>

====Generator expressions====

Line 574 ⟶ 570:

===R===

The iterators package can be used for this purpose.<ref>[https://stackoverflow.com/a/16028448 Generator functions in R]</ref><ref>{{Cite web|url=http://cartesianfaith.wordpress.com/2013/01/05/infinite-generators-in-r/|title=Infinite generators in R|date=5 January 2013}}</ref>

<syntaxhighlight lang="r">

Line 587 ⟶ 583:

Example in [[Pharo|Pharo Smalltalk]]:

The [[Golden ratio]] generator below returns to each invocation 'goldenRatio next' a better approximation to the Golden Ratio.

<syntaxhighlight lang="Smalltalk">

Line 603 ⟶ 601:

goldenRatio next.

</syntaxhighlight>

The expression below returns the next 10 approximations.

<syntaxhighlight lang="Smalltalk">

Character cr join: ((1 to: 10) collect: [ :dummy | ratio next ]).

</syntaxhighlight>

See more in [https://medium.com/concerning-pharo/pharos-hidden-gem-generator-c51ef88aec26 A hidden gem in Pharo: Generator].

==See also==

Line 622 ⟶ 628:

[[Category:Programming constructs]]

[[Category:Articles with example Python (programming language) code]]

[[Category:Articles with example Haskell code]]

[[Category:Articles with example Ruby code]]