A generator, in the world of computer programming, is a function
that can return more than one result.
As in mathematics, a function in a computer program generally returns
one result when called with a particular set of parameters. (Included in
this "one result" concept are structured values such as records, lists,
etc.) For example, a function that returns the next integer greater than
its argument will return only one result. Even a square root function
that could return two real values given a real parameter (e.g., returning
3 and -3 as the square roots of 9) would still be regarded as returning a
single value, which would always be a list of two real numbers. (Standard
sqrt() functions, however, only return one number.)
A generator, on the other hand, will, when called with a particular set of
parameters, give you one result ... and another ... and another ... until
it has no more to give (or you tell it to
stop, already). Generators
are often spoken of in terms of the Icon programming language, which may
have been the first to use them (I'm not sure). Icon has an unusual aspect to
it: if it evaluates an expression and it turns out to be "unsuccessful"
(a Boolean result of false, and perhaps others -- I don't know the precise
definition of unsuccessful in Icon) it will try to
re-evaluate it, using new values for any generators that were involved, until
it's happy. (If at first you don't succeed, ....) It also provides a more
explicit method of repeatedly calling a generator, but its
reputation stems from its automatic usage of them.
But why go on about Icon when I can go off about Python? :)
Generators were added to Python in version 2.2. (Because a new keyword was
added to the language grammar, it is a transitional feature which must be
enabled via the __future__ mechanism. It will be official in version 2.3.)
The Python compiler now emits a generator function (rather than a "normal"
function) when it sees the keyword yield within the function body; it also
adds two slight semantic changes to a generator function:
-
return statements, if any, are not allowed to specify
a value to return
There is no tremendous reason for this. Some people think a return
statement should be able to say "Oh, and here's the final value". But
with the current restriction, they can simply put one last yield before
the return. I think Guido added this restriction in
the interest of keeping the implementation clean and simple.
-
yield is not allowed in the try-block of a
try...finally statement.
This is for the simple reason that there could be no guarantee that
the finally block would execute, since the generator might never be
resumed after the yield in the try.
Some people, even the great Tim Peters, are careful to mention that
Python generators are not real generators, like Icon's, though
it seems to me they quibble about
an implementation detail. The reason
is that when you call a Python generator function, you actually don't
get its first result back at all! You get an object of a new built-in type called
a generator-iterator. While this seems amazingly different than the
intuitive Icon behavior, the fact that the generator-iterator follows the
Python iteration protocol (also new in version 2.2) makes the typical use
of generators and iterators -- as the object of a for loop -- look exactly
the same.
In non-for loop contexts, you can still use the generator-iterator like
any other iterator: each call to its next() method returns
the next result from the generator function.
It must be time for an example. Suppose you want to write a function that
will read every writeup on Everything2 and return only the ones with a
reputation exceeding a threshold that you specify. Here's how you would
do it the old way:
def HighReps(rep):
highreps = []
for nodenum in range(E2.GetHighestNodeNumber()):
node = E2.GetNode(nodenum)
if node.reputation > rep:
highreps.append(node)
return highreps
This function returns a list of nodes with high reputations, just like you
wanted; you could store a local reference to the list for later use, or
iterate over it with a for loop:
highreps = HighReps(50)
for node in HighReps(50): print node
There are two important things to notice about this way of doing
things:
- The list might be very large
- You don't get to see any of the nodes you're looking for until they've
all been found
These are two disadvantages that generators are great at getting around.
Let's see the generator version of that same function:
def HighReps(rep):
for nodenum in range(E2.GetHighestNodeNumber()):
node = E2.GetNode(nodenum)
if node.reputation > rep:
yield node
The for loop above will still work exactly the same if it calls this new
version, except that the list of nodes never exists, and the printing of
the nodes will begin sooner (and possibly be
sporadic rather than
continuous as printing from the list would be). The assignment is
different now, though. With the generator function,
highreps = HighReps(50)
no longer returns a list, but a generator-iterator instead. We can use
it to fetch the first node that passes our high-reputation test:
node = highreps.next()
(This is the same node that we could get with highreps[0] with
the non-generator version.) Then we can call
next again to get
the second one. But here's another advantage of the generator solution:
we don't have to call it again! If we wanted
to just get five high-rep nodes, we could just call
next
five times, and then throw away the iterator. It won't be hurt that it
didn't get to run to completion, and its state (local variables, instruction
pointer, etc.) will get cleaned up when the iterator is reclaimed.
Indeed,
you could write a generator that will never complete; i.e., a list-constructing
version of it would try to generate an infinitely-long list. An example of
this would be a generator that generates prime numbers.
You could never
iterate over it to completion, but you could scoop up the first ten thousand
(or however many you want) values that it returns, or keep calling it until
the returned value meets some criterion that you have. Notice that to do
these things with a list-constructing version, you would either have to
pass it a parameter indicating how long a list you wanted to get back,
or have it know how to apply your criterion so it knows when to
stop finding values and return the list it has built. That makes the function
less generally usable in different circumstances. And this generality doesn't
even exclude the case where you actually do want the entire list. You can just
invoke the list type constructor, and there it is. E.g.,
highreps = list(HighReps(50))
Like all language features, generators are not a panacea, but they are
definitely a tool to reach for when you're uncomfortable about that huge
list you're constructing (and that you don't need all at one time), or
when you'd like to start getting results sooner (usually so you can begin
presenting them to the user). And, they often make your code simpler and
shorter to boot!