Generator (computer science)

In computer science, a generator is a special routine that can be used to control the iteration behaviour of a loop. A generator is very similar to a function that returns an array, in that a generator has 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 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.

History

Generators first appeared in CLU (1975) [cite web
last = Liskov
first = Barbara
authorlink = Barbara Liskov
month = April
year = 1992
title = A History of CLU
url = http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-561.pdf
format = pdf] and are now available in Python [Python Enhancement Proposals: [http://www.python.org/dev/peps/pep-0255/ PEP 255: Simple Generators] , [http://www.python.org/dev/peps/pep-0289/ PEP 289: Generator Expressions] , [http://www.python.org/dev/peps/pep-0342/ PEP 342: Coroutines via Enhanced Generators] ] , C#, and JavaScript [cite web
url = http://developer.mozilla.org/en/docs/New_in_JavaScript_1.7#Generators
title = New In JavaScript 1.7
accessdate = 2006-10-10] . (In CLU and C#, generators are called "iterators".) Generators are also a prominent feature in the string manipulation language Icon.

Uses

Generators are usually invoked inside loops The Icon Programming Language utilizes generators to implement its goal directed evaluation. In Icon, generators can be invoked in contexts outside of the normal looping control structures.] . The first time that a generator invocation is reached in a loop, an iterator object is created that encapsulates the state of the generator routine at its beginning, with arguments bound to the corresponding parameters. The generator's body is then executed in the context of that iterator until a special "yield" action is encountered; at that time, the value provided with the "yield" action is used as the value of the invocation expression. The next time the same generator invocation is reached in a subsequent iteration, the execution of the generator's body is resumed after the "yield" action, until yet another "yield" action is encountered. In addition to the "yield" action, execution of the generator body can also be terminated by a "finish" action,at which time the innermost loop enclosing the generator invocation is terminated.

Because generators compute their yielded values only on demand, they are useful for representing sequences that are expensive to compute, or even infinite.

In the presence of generators, loop constructs of a language 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.

Python

An example Python generator:

def countfrom(n): 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.

def primes(): n = 2 p = [] while True: if not any( n % f = 0 for f in p ): yield n p.append( n ) n += 1

>>> f = primes()>>> f.next()2>>> f.next()3>>> f.next()5>>> f.next()7

This example works in Python >= 2.5 or using the any() function from the numpy module.

In Python, a generator can be thought of as an iterator that contains a frozen stack frame. Whenever the iterator's next() method is called, Python resumes the frozen frame, which executes normally until the next yield statement is reached. The generator's frame is then frozen again, and the yielded value is returned to the caller.

Generators can be implemented in terms of more expressive control flow constructs, such as coroutines or first-class continuations. [cite web
last = Kiselyov
first = Oleg
month = January
year = 2004
title = General ways to traverse collections in Scheme
url = http://okmij.org/ftp/Scheme/enumerators-callcc.html]

C#

An example C# 2.0 generator:

// Method that takes an iterable input (possibly an array)// and returns all even numbers.public static IEnumerable GetEven(IEnumerable numbers){ foreach (int i in numbers) { if ((i % 2) = 0) { yield return i; }

You may even use multiple yield return statements and the compiler will return them in order on each iteration:

public class CityCollection : IEnumerable{ public IEnumerator GetEnumerator() { yield return "New York"; yield return "Paris"; yield return "London";

Both of these examples utilise Generics, but this is not required. To use the yield keyword, you must using at least C# version 2.0. The current version of the C# language is 3.0.

XL

In XL, iterators are the basis of 'for' loops:

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 herefor I in 1..5 loop IO.WriteLn "I=", I

Other Implementations

Java does not have continuation or functionality out of the box, but generators can be implemented using threading. An abstract class that can be subclassed to write generators in Java can be found [http://smallwiki.unibe.ch/adriankuhn/yield4java/ here] .

Example of using it: Generator fibonacci = new Generator() { @Override public void run() { int a = 0, b = 1; while (true) { a = b + (b = a); yield(a); } } }; for (int x : fibonacci) { if (x > 20000) break; out.println(x); }

A previous attempt to implement the concept was made, using complex techniques likes bytecode manipulation (specifically, WebObject's ASM) and the new Java 5 feature of VM Instrumentation. That code was made public [http://code.google.com/p/infomancers-collections/ here] .

ee also

* List comprehension for another construct that generates a sequence of values
* Iterator for the concept of producing a list one element at a time
* Lazy evaluation for producing values when needed
* Corecursion for potentially infinite data by recursion instead of "yield"
* Coroutine for even more generalization from subroutine
* Continuation for generalization of control flow

References

* Stephan Murer, 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]