Content deleted Content added
→Uses: example of loop construct |
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.5 |
||
| (146 intermediate revisions by 81 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=
==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.
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
| 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 38 ⟶ 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]], [[PHP]],<ref>{{Cite web|url=https://www.php.net/manual/en/language.generators.overview.php|title = PHP: 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===
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 |
<
string_chars = iter (s: string) yields (char);
index: int := 1;
Line 61 ⟶ 67:
...
end;
</syntaxhighlight>
===Icon===
Line 68 ⟶ 74:
Printing squares from 0 to 20 can be achieved using a co-routine by writing:
<
local squares, j
squares := create (seq(0) ^ 2)
Line 76 ⟶ 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===
[[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++
<
int i;
// place the constructor of our generator, e.g.
Line 97 ⟶ 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:
<
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:
<
int main() {
for (int i: range(10)) {
std::cout << i << std::endl;
}
return 0;
}</syntaxhighlight>
A basic range implementation would look like that:
<
class range {
private:
int last;
Line 153 ⟶ 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 159 ⟶ 173:
Perl does not natively provide generators, but support is provided by the [https://metacpan.org/module/Coro::Generator Coro::Generator] module which uses the [https://metacpan.org/module/Coro Coro] co-routine framework. Example usage:
<
use strict;
use warnings;
#
use Coro::Generator;
#
my $chars = ['A'...'Z'];
#
my $letters = generator {
};
#
print $letters->(), "\n" for (0..15);
</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 186 ⟶ 213:
In [[Tcl]] 8.6, the generator mechanism is founded on named [[coroutine]]s.
<
proc generator {body} {
coroutine gen[incr ::disambiguator] apply {{script} {
Line 209 ⟶ 236:
puts [$count]
}
</syntaxhighlight>
===Haskell===
In [[Haskell (programming language)|Haskell]], with its [[lazy evaluation]] model,
<
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,
<
takeWhile p [] = []
takeWhile p (x:xs) | p x = x : takeWhile p xs
| otherwise = []
</syntaxhighlight>
which
<
</syntaxhighlight>
===Racket===
[[Racket (programming language)|Racket]] provides several related facilities for generators. First, its for-loop forms work with ''sequences'', which are a kind of a producer:
<
(for ([i (in-range 10 20)])
(printf "i = ~s\n" i))
</syntaxhighlight>
and these sequences are also first-class values:
<
(define 10-to-20 (in-range 10 20))
(for ([i 10-to-20])
(printf "i = ~s\n" i))
</syntaxhighlight>
Some sequences are implemented imperatively (with private state variables) and some are implemented as (possibly infinite) lazy lists. Also, new struct definitions can have a property that specifies how they can be used as sequences.
But more directly, Racket comes with a generator library for a more traditional generator specification. For example,
<
#lang racket
(require racket/generator)
Line 261 ⟶ 293:
(define g (ints-from 10))
(list (g) (g) (g)) ; -> '(10 11 12)
</syntaxhighlight>
Note that the Racket core implements powerful continuation features, providing general (re-entrant) continuations that are composable, and also delimited continuations. Using this, the generator library is implemented in Racket.
===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;
$current = 1;
Line 280 ⟶ 315:
foreach (fibonacci() as $number) {
echo $number
}
</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===
Ruby supports generators (starting from version 1.9) in the form of the built-in Enumerator class.
<
# Generator from an Enumerator object
chars = Enumerator.new(['A', 'B', 'C', 'Z'])
Line 301 ⟶ 353:
100.times { puts count.next }
</syntaxhighlight>
===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
<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))
.limit(10)
.map(p -> p.a)::iterator;
myIterable.forEach(System.out::println);
</syntaxhighlight>
Or get an Iterator from the '''Java 8''' super-interface BaseStream of Stream interface.
<syntaxhighlight lang="java">
record
// Save the iterator of a stream that generates fib sequence
Iterator<Integer> myGenerator = Stream
// Generates Fib sequence
.iterate(new Pair(1, 1), p -> new Pair(p.b, p.a + p.b))
.map(p -> p.a).iterator();
// Print the first 5 elements
for (int i =
System.out.println(myGenerator.next());
}
System.out.println("done with first iteration");
// Print the next 5 elements
for (int i = 0; i < 5; i++) {
System.out.println(myGenerator.next());
}
</syntaxhighlight>
Output:
<syntaxhighlight lang="console">
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>
<
// 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 }
}
}
</syntaxhighlight>
It is possible to use multiple <code>yield return</code> statements and they are applied in sequence on each iteration:
<
public class CityCollection : IEnumerable<string>
{ public IEnumerator<string> GetEnumerator()
{
yield return "New York"; yield return "Paris";
yield return "London";
}
}
</syntaxhighlight>
===XL===
In [[XL (programming language)|XL]], iterators are the basis of 'for' loops:
<
import IO = XL.UI.CONSOLE
Line 410 ⟶ 456:
// An implicit declaration of I as an integer is therefore made here
for I in 1..5 loop
IO.WriteLn "I=", I
</syntaxhighlight>
===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
if b < 15 then
yield b * b }
</syntaxhighlight>
forms a sequence of squares of numbers from 0 to 14 by filtering out numbers from the range of numbers from 0 to 25.
===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 424 ⟶ 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 434 ⟶ 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 dividing n by all the numbers in p, up to and including sqrt(n),
if all(n % f > 0 for f
yield n
p.append(
n += 2
</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
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:
<
squares = (n
for j in squares:
Line 464 ⟶ 524:
else:
break
</syntaxhighlight>
===ECMAScript===
[[ECMAScript|ECMAScript 6]] (a.k.a. Harmony) introduced generator functions.
An infinite Fibonacci sequence can be written using a function generator:
<syntaxhighlight lang="javascript">
function* fibonacci(limit) {
let [prev, curr] = [0, 1];
while (!limit || curr <= limit) {
yield curr;
[prev, curr] = [curr, prev + curr];
}
}
// bounded by upper limit 10
for (const n of fibonacci(10)) {
console.log(n);
}
// 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>[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">
library(iterators)
# Example ------------------
abc <- iter(c('a','b','c'))
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 480 ⟶ 624:
==References==
* Stephan Murer, [[Steve Omohundro|Stephen Omohundro]], David Stoutamire and Clemens Szyperski: Iteration abstraction in [[Sather]]. ''ACM Transactions on Programming Languages and Systems'', 18(1):1-15 (1996) [http://portal.acm.org/citation.cfm?doid=225540.225541]
{{Authority control}}
[[Category:Programming constructs]]
[[Category:Articles with example Python (programming language) code]]
[[Category:Articles with example Haskell code]]
[[Category:Articles with example Ruby code]]
Line 491 ⟶ 637:
[[Category:Articles with example Racket code]]
[[Category:Iteration in programming]]
[[Category:Articles with example R code]]
| |||