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.
Generators first appeared in CLU (1975) [1] and are now available in Python and C#. (In CLU and C#, generators are called iterators.)
Generators are usually invoked inside loops. 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.
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
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.
In programming languages that support current continuation capture and resumption, it may be possible to implement generators even if the language itself does not directly provide them. For instance, implementing generators in Scheme is a simple metaprogramming exercise, since the language provides both call/cc and a powerful macros facility.
See 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) [2]
- PEPs (Python Enhancement Proposals):
- Generators in Scheme:
- Why Java (and almost every other programming language) sucks by Ed Watkeys
- One more example of Python generators in Scheme by Will Farr
- General ways to traverse collections in Scheme by Oleg Kiselyov
- Towards the best collection traversal interface by Oleg Kiselyov
- Schematics Cookbook: Generating Iterators
- Python/Ruby style generators for PLT Scheme