Content deleted Content added
Funkywizard (talk | contribs) Tags: Reverted Mobile edit Mobile web edit |
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.5 |
||
| (14 intermediate revisions by 11 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.
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==
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) {
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[]) {
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>▼
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():
{
$last = 0;
Line 314 ⟶ 321:
Fibonacci sequence with limit:
<syntaxhighlight lang="php">
function fibonacci(int $limit):
{
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
Line 491 ⟶ 498:
yield 2
n = 3
p = [2]
while True:
# If dividing n by all the numbers in p, up to and including sqrt(n),
Line 501 ⟶ 508:
</syntaxhighlight>
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 <code>yield from</code> 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>
| |||