Generator (computer programming): Difference between revisions

Revision as of 20:37, 22 November 2022

Latest revision as of 09:03, 12 August 2025

(37 intermediate revisions by 20 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 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

Line 87 ⟶ 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 108 ⟶ 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 161 ⟶ 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 197 ⟶ 203:

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

last if $i > 20;

say $i

}

</syntaxhighlight>

Line 234 ⟶ 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 252 ⟶ 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 286 ⟶ 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 fibonacci(): Generator

{

$last = 0;

Line 309 ⟶ 321:

Fibonacci sequence with limit:

<syntaxhighlight lang="php">

function fibonacci(int $limit):generator Generator

{

yield $a = $b = $i = 1;

Line 346 ⟶ 358:

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 <code>java.lang.Iterable</code> 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;

}

@Override

public Integer next() {

int temp = a;

a = b;

b = a + temp;

return temp;

}

@Override

public void remove() {

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>

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

<syntaxhighlight lang="java">

Iterable<Integer> myIterable = Stream

// Generates Fib sequence

.iterate(new Integer[]{ 1, 1 }, x -> new Integer[] { x[1], x[0] + x[1] })

.map(x -> x[0])::iterator;

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

</syntaxhighlight>

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

<syntaxhighlight lang="java">

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

Iterator<Integer> myGenerator = Stream

// Generates Fib sequence

.iterate(new Integer[]{ Pair(1, 1 }), xp -> new Integer[] { x[1]Pair(p.b, x[0]p.a + x[1] }p.b))

.map(xp -> x[0]p.a).iterator();

// Print the first 5 elements

Line 443 ⟶ 392:

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

}

</syntaxhighlight>

/* Output:

<syntaxhighlight lang="console">

1

1

Line 455 ⟶ 406:

21

34

55 */

</syntaxhighlight>

Line 510 ⟶ 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 | access-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 544 ⟶ 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)