Editing Generator (computer programming) (section)

==Languages providing generators==

Generators first appeared in [[CLU (programming language)|CLU]] (1975),<ref>{{cite web
| last = Liskov
| first = Barbara
| author-link = Barbara Liskov
| 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],
[https://www.python.org/dev/peps/pep-0289/ PEP 289: Generator Expressions],
[https://www.python.org/dev/peps/pep-0342/ PEP 342: Coroutines via Enhanced Generators]
</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 [https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node347.html#SECTION003400000000000000000 SERIES] documented in CLtL2 or [https://web.archive.org/web/20110723043455/http://cliki.net/pygen pygen].

===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 | pages = 564–576 | access-date = <!-- 24 May 2013 --> | doi = 10.1145/359763.359789 | s2cid = 17343380 }}</ref>

<syntaxhighlight lang="text">
string_chars = iter (s: string) yields (char);
  index: int := 1;
  limit: int := string$size (s);
  while index <= limit do
    yield (string$fetch(s, index));
    index := index + 1;
    end;
end string_chars;

for c: char in string_chars(s) do
   ...
end;
</syntaxhighlight>

===Icon===

Every expression (including loops) is a generator. The language has many generators built-in and even implements some of the logic semantics using the generator mechanism ([[logical disjunction]] or "OR" is done this way).

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)
   every j := |@squares do
      if j <= 20 then
         write(j)
      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++, 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}}</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;

   // place the constructor of our generator, e.g. 
   // descent(int minv, int maxv) {...}
   
   // from $emit to $stop is a body of our generator:
    
   $emit(int) // will emit int values. Start of body of the generator.
      for (i = 10; i > 0; --i)
         $yield(i); // similar to yield in Python,
                    // 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;
    int iter;

public:
    range(int end):
        last(end),
        iter(0)
    {}

    // Iterable functions
    const range& begin() const { return *this; }
    const range& end() const { return *this; }

    // Iterator functions
    bool operator!=(const range&) const { return iter < last; }
    void operator++() { ++iter; }
    int operator*() const { return iter; }
};
</syntaxhighlight>

===Perl===

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:

<syntaxhighlight lang="perl">
use strict;
use warnings;
# Enable generator { BLOCK } and yield
use Coro::Generator;
# Array reference to iterate over
my $chars = ['A'...'Z'];

# New generator which can be called like a coderef.
my $letters = generator {
    my $i = 0;
    for my $letter (@$chars) {
        # get next letter from $chars
        yield $letter;
    }
};

# Call the generator 15 times.
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===

In [[Tcl]] 8.6, the generator mechanism is founded on named [[coroutine]]s.

<syntaxhighlight lang="tcl">
proc generator {body} {
    coroutine gen[incr ::disambiguator] apply {{script} {
        # Produce the result of [generator], the name of the generator
        yield [info coroutine]
        # Do the generation
        eval $script
        # Finish the loop of the caller using a 'break' exception
        return -code break
    }} $body
}

# Use a simple 'for' loop to do the actual generation
set count [generator {
    for {set i 10} {$i <= 20} {incr i} {
        yield $i
    }
}]

# Pull values from the generator until it is exhausted
while 1 {
    puts [$count]
}
</syntaxhighlight>

===Haskell===

In [[Haskell (programming language)|Haskell]], with its [[lazy evaluation]] model, 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)

from10to20 :: [Integer]
from10to20 = takeWhile (<= 20) $ countFrom 10

primes :: [Integer]
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,
<syntaxhighlight lang="haskell">
takeWhile p [] = []
takeWhile p (x:xs) | p x = x : takeWhile p xs
                   | 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]
squaresForNumbersUnder20 = [x * x | x <- takeWhile (<= 20) $ countFrom 10]
</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:
<syntaxhighlight lang="racket">
(for ([i (in-range 10 20)])
  (printf "i = ~s\n" i))
</syntaxhighlight>
and these sequences are also first-class values:
<syntaxhighlight lang="racket">
(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,
<syntaxhighlight lang="racket">
#lang racket
(require racket/generator)
(define (ints-from from)
  (generator ()
    (for ([i (in-naturals from)]) ; infinite sequence of integers from 0
      (yield i))))
(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;
    yield 1;
    while (true) {
        $current = $last + $current;
        $last = $current - $last;
        yield $current;
    }
}

foreach (fibonacci() as $number) {
    echo $number, "\n";
}
</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.

<syntaxhighlight lang="ruby">
# Generator from an Enumerator object
chars = Enumerator.new(['A', 'B', 'C', 'Z'])

4.times { puts chars.next }

# Generator from a block
count = Enumerator.new do |yielder|
  i = 0
  loop { yielder.yield i += 1 }
end

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 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">

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 Pair(int a, int b) {};

// 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 = 0; i < 5; 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>

<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 number in numbers)
    {
        if ((number % 2) == 0)
        {
            yield return number;
        }
    }
}
</syntaxhighlight>

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";
        yield return "London";
    }
}
</syntaxhighlight>

===XL===
In [[XL (programming language)|XL]], iterators are the basis of 'for' loops:

<syntaxhighlight lang="text">
import IO = XL.UI.CONSOLE

iterator IntegerIterator (var out Counter : integer; Low, High : integer) written Counter in Low..High is
    Counter := Low
    while Counter <= High loop
        yield
        Counter += 1

// Note that I needs not be declared, because declared 'var out' in the iterator
// 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
        n += 1

# Example use: printing out the integers from 10 to 20.
# Note that this iteration terminates normally, despite
# countfrom() being written as an infinite loop.

for i in countfrom(10):
    if i <= 20:
        print(i)
    else:
        break

# 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),
        # 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)
        n += 2
</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>

====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 * n for n in countfrom(2))

for j in squares:
    if j <= 20:
        print(j)
    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].