Content deleted Content added
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.5 |
|||
(111 intermediate revisions by 64 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
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|
==Uses==
Line 19 ⟶ 20:
Because generators compute their yielded values only on demand, they are useful for representing [[Stream (computing)|streams]], 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 a [[List (abstract data type)|list]], or use a parallel construction that creates a list instead of a generator. For example, in Python a generator <code>g</code> can be evaluated to a list <code>l</code> via <code>l = list(g)</code>, while in [[F Sharp programming language|F#]] the
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
==Languages providing generators==
Generators first appeared in [[CLU (programming language)|CLU]] (1975),<ref>{{cite web
| last = Liskov
| first = Barbara
|
| date = April 1992
| title = A History of CLU
| url = http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-561.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
| archive-date = 2003-09-17
| url-status = dead
}}</ref> were a prominent feature in the string manipulation language [[Icon (programming language)|Icon]] (1977) and are now available in [[Python (programming language)|Python]] (2001),<ref name=python>
Python Enhancement Proposals:
[https://www.python.org/dev/peps/pep-0255/ PEP 255: Simple Generators],
Line 40 ⟶ 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]],
===Lisp===
The final [[Common Lisp]] standard does not natively provide generators, yet various library implementations exist, such as [
===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 |
<syntaxhighlight lang="text">
Line 70 ⟶ 74:
Printing squares from 0 to 20 can be achieved using a co-routine by writing:
<syntaxhighlight lang="icon">
local squares, j
squares := create (seq(0) ^ 2)
Line 78 ⟶ 82:
else
break
</syntaxhighlight>
However, most of the time custom generators are implemented with the "suspend" keyword which functions exactly like the "yield" keyword in CLU.
===
[[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++
<syntaxhighlight lang="cpp">$generator(descent) {
int i;
// place the constructor of our generator, e.g.
Line 113 ⟶ 104:
$emit(int) // will emit int values. Start of body of the generator.
for (i = 10; i > 0; --i)
$yield(i); //
// returns next number in [1..10], reversed.
$stop; // stop, end of sequence. End of body of the generator.
};</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>
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>
int main() {
for (int i: range(10)) {
std::cout << i << std::endl;
}
return 0;
}</syntaxhighlight>
A basic range implementation would look like that:
<syntaxhighlight lang="cpp">
class range {
private:
int last;
Line 169 ⟶ 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">
#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 196 ⟶ 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 228 ⟶ 240:
===Haskell===
In [[Haskell (programming language)|Haskell]], with its [[lazy evaluation]] model,
<syntaxhighlight lang="haskell">
countFrom :: Integer -> [Integer]
countFrom n = n : countFrom (n + 1)
from10to20 :: [Integer]
primes
primes = 2 : 3 : nextPrime 5
where
nextPrime n
| 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 246 ⟶ 263:
| otherwise = []
</syntaxhighlight>
which
<syntaxhighlight lang="haskell">
</syntaxhighlight>
Line 280 ⟶ 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;
$current = 1;
Line 298 ⟶ 318:
}
</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>
Any function which contains a <span style="font-family: 'Courier New';">yield</span> statement is automatically a generator function.
===Ruby===
Line 317 ⟶ 355:
</syntaxhighlight>
===
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 <
<syntaxhighlight lang="java">
record Pair(int a, int b) {};
Iterable<Integer> myIterable = Stream.iterate(new Pair(1, 1), p -> new Pair(p.b, p.a + p.b))
.map(p ->
myIterable.forEach(System.out::println);
</syntaxhighlight>
Or get an Iterator from the '''Java 8''' super-interface BaseStream of Stream interface.
<syntaxhighlight lang="java">
record Pair(int a, int b) {};
// Save the iterator of a stream that generates fib sequence
Iterator<Integer> myGenerator = Stream
// Generates Fib
.iterate(new Pair(1, 1), p -> new Pair(p.b,
.map(p ->
// Print the first 5 elements
for (int i = 0; i < 5;
System.out.println(myGenerator.next());
}
System.out.println("done with first iteration");
// Print the next 5 elements
for (int i = 0; i < 5;
System.out.println(myGenerator.next());
}
</syntaxhighlight>
Output:
<syntaxhighlight lang="
1
1
2
3
5
done with first iteration
8
13
21
34
55
</syntaxhighlight>
===C#===
An example C# 2.0 generator (the <code>yield</code> 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.<ref>{{Cite web|url=https://stackoverflow.com/a/15977474 |title=What is the yield keyword used for in C#?|website=stackoverflow.com|access-date=2018-01-01}}</ref>
<syntaxhighlight lang="csharp">
// Method that takes an iterable input (possibly an array)
// and returns all even numbers.
public static IEnumerable<int> GetEven(IEnumerable<int> numbers)
{ foreach (int
{
if (( {
yield return }
}
Line 445 ⟶ 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 474 ⟶ 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 |
<syntaxhighlight lang="fsharp">
seq { for b in 0 .. 25 do
Line 484 ⟶ 471:
===Python===
Generators were added to [[Python (programming language)|Python]] in version 2.2 in 2001.<ref name="python"/> An example generator:
<syntaxhighlight lang="python">
from typing import Iterator
def countfrom(n: int) -> Iterator[int]:
while True:
yield n
Line 493 ⟶ 482:
# Example use: printing out the integers from 10 to 20.
# Note that this iteration terminates normally, despite
# countfrom() being written as an infinite loop.
Line 503 ⟶ 492:
# Another generator, which produces prime numbers indefinitely as needed.
import itertools
def primes() -> Iterator[int]:
"""Generate prime numbers indefinitely as needed."""
yield 2
n = 3
p = [2]
while True:
#
if all(n % f > 0 for f
yield n
p.append(n)
Line 517 ⟶ 508:
</syntaxhighlight>
In Python, a generator can be thought of as an [[iterator]] that contains a frozen [[stack frame]].
PEP 380 (implemented in Python 3.3) adds the <
====Generator expressions====
Python has a syntax modeled on that of [[list comprehension]]s, 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 the <code>countfrom</code> generator function:
<syntaxhighlight lang="python">
squares = (n
for j in squares:
Line 537 ⟶ 528:
===ECMAScript===
[[ECMAScript|ECMAScript 6]] (a.k.a. Harmony)
An infinite Fibonacci sequence can be written using a function generator:
<syntaxhighlight lang="javascript">
function* fibonacci(limit) {
let [prev, curr] = [0, 1];
while (
yield curr;
[prev, curr] = [curr, prev + curr];
Line 551 ⟶ 541:
}
// bounded by upper limit 10
for (const n of fibonacci(10)) {
console.log(
}
// generator without an upper bound limit
for (const n of fibonacci()) {
console.log(n);
if (n > 10000) break;
}
// manually iterating
let fibGen = fibonacci();
console.log(fibGen.next().value); // 1
console.log(fibGen.next().value); // 1
console.log(fibGen.next().value); // 2
console.log(fibGen.next().value); // 3
console.log(fibGen.next().value); // 5
console.log(fibGen.next().value); // 8
// picks up from where you stopped
for (const n of fibGen) {
console.log(n);
if (n > 10000) break;
}
</syntaxhighlight>
===R===
The iterators package can be used for this purpose.<ref>
<syntaxhighlight lang="r">
Line 571 ⟶ 579:
nextElem(abc)
</syntaxhighlight>
===Smalltalk===
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">
goldenRatio := Generator on: [ :g | | x y z r |
x := 0.
y := 1.
[
z := x + y.
r := (z / y) asFloat.
x := y.
y := z.
g yield: r
] repeat
].
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 590 ⟶ 628:
[[Category:Programming constructs]]
[[Category:Articles with example Python (programming language) code]]
[[Category:Articles with example Haskell code]]
[[Category:Articles with example Ruby code]]
Line 599 ⟶ 637:
[[Category:Articles with example Racket code]]
[[Category:Iteration in programming]]
[[Category:Articles with example R code]]
|