Generator (computer programming): Difference between revisions

Revision as of 05:58, 4 March 2024

Latest revision as of 09:03, 12 August 2025

(12 intermediate revisions by 9 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 <iostreamgenerator>

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 257 ⟶ 263:

| otherwise = []

</syntaxhighlight>

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:

<syntaxhighlight lang="haskell">

squaresUnder20 = takeWhile (<= 20) [x * x | x <- countFrom 10]

Line 291 ⟶ 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].

Infinite Fibonacci sequence:

<syntaxhighlight lang="php">

function fibonacci(): \Generator

{

$last = 0;

Line 314 ⟶ 321:

Fibonacci sequence with limit:

<syntaxhighlight lang="php">

function fibonacci(int $limit): generatorGenerator

{

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

Line 454 ⟶ 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