CSC/ECE 517 Summer 2008/wiki1 2 acmoore2

Ruby, like Java, has iterators to facilitate doing operations on each member of a set. Python has generators as well. Describe how generators differ from iterators, and find examples of code sequences using generators that would be awkward with iterators.

---

Iterators Defined

Any computer programmer with experience has realized the power of an iterator. As defined by Wikipedia.com an iterator is "an object which allows a programmer to traverse through all the elements of a collection, regardless of its specific implementation."[1]

For example, the programming language Java, has defined an iterator interface in their Java Collections Framework in java.util[2] There are three methods included in the interface which are defined below:

boolean hasNext() :  Returns true if the iteration has more elements. 
 
Object next() : Returns the next element in the iteration. 
 
void remove() : Removes from the underlying collection the last element returned by the iterator (optional operation)

[3]

We can further explore the operations of these iterator functions in the following section.

Iterator Examples

In the following Java example, an array arrayList has been defined and populated. The iterator is defined, itr, for arrayList and then the contents can easily be printed out by using an iterator.

//get an Iterator object for ArrayList using iterator() method.
Iterator itr = arrayList.iterator();

//use hasNext() and next() methods of Iterator to iterate through the elements
    System.out.println("Iterating through ArrayList elements...");
    while(itr.hasNext())
      System.out.println(itr.next());

[4]

Ruby, like Java allows for iterators and provides a mechinism for iteration. It allows for iteration over enumerations and arrays using blocks. Here is an example of a mixed bag array and then iterating over the array to print out the contents.

array = [1, 'hi', 3.14]
array.each { |item| puts item }
# => 1
# => 'hi'
# => 3.14

[5]

Generators Defined

As we have seen with iterators, the ability to traverse through a set or collection is a basic need of any programming language. Just as in Java, Ruby has a means of iteration by using a generator. As described in the wiki question, Python uses a variation on the iterator and uses generators. Wikipedia.com defines generators as "a special routine that can be used to control the iteration behaviour of a loop."[6]

A generator is compared to a function that returns an array. A generator can have parameters, it can be called, and in return it returns a sequence of values.[7] The differnce between a generator and any other function that returns an array is that the generator is used to return the results one at a time, allowing it to act as an iterator.

Python.com cites several benefits behind a generator. One improved area is the efficiency of memory use. The generator requires less memory by not having to store and send an entire collection or array rather passing one value at a time.[8] Another benefit cited by Python.com is high performance. Like an iterator, a generator returns one value at a time allowing for a process to start accessing the data earlier and faster than it would if it had to wait for the entire array to return.[9]

Generator Examples

Our first example can be drawn from Python. This generator will produce prime number indefinitely as seen in the code below.

# 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

[10]

Generators That Would Be Awkward with Iterators

An article by David Mertz in an ibm.com library discussed the advantage of generators and hence why generators can do some things that iterators can't.

A generator is a function that remembers the point in the function body where it last returned. Calling a generator function a second (or nth) time jumps into the middle of the function, with all local variables intact from the last invocation.[11]

He makes a comparison between generators and closures with a distinct difference. "Like a closure, a generator 'remembers' the state of its data. But a generator goes a bit further than a closure: a generator also 'remembers' its position within flow-control constructs."[12]

In the following example, is an example of how a generator is used manually, allowing it to be passed around a program and then called when and wherever needed.

from __future__ import generators   # only needed for Python 2.2
import random
def randomwalk_generator():
    last, rand = 1, random.random() # initialize candidate elements
    while rand > 0.1:               # threshhold terminator
        print '*',                  # display the rejection
        if abs(last-rand) >= 0.4:   # accept the number
            last = rand             # update prior value
            yield rand              # return AT THIS POINT
        rand = random.random()      # new candidate
    yield rand                      # return the final small element

[13]

A more simple approach is as follows:

gen = randomwalk_generator()
try:
    while 1: print gen.next(),
except StopIteration:
    pass

[14]

---

Conclusion

As has been shown, iterators and generators can both be powerful programming elements throughout any programming language. We can also see that the new age view of using generators does allow for uses that are similar to closures and difficult with iterators.

External References

[1] http://en.wikipedia.org/wiki/Iterator#Iterators_in_different_programming_languages

[2] http://java.sun.com/j2se/1.4.2/docs/api/java/util/Iterator.html

[3] http://java.sun.com/j2se/1.4.2/docs/api/java/util/Iterator.html

[4] http://www.java-examples.com/iterate-through-elements-java-arraylist-using-iterator-example

[5] http://en.wikipedia.org/wiki/Ruby_programming_language

[6] http://en.wikipedia.org/wiki/Generator_%28computer_science%29

[7] http://en.wikipedia.org/wiki/Generator_%28computer_science%29

[8] http://www.python.org/dev/peps/pep-0289

[9] http://www.python.org/dev/peps/pep-0289

[10] http://en.wikipedia.org/wiki/Generator_%28computer_science%29

[11] http://www.ibm.com/developerworks/library/l-pycon.html

[12] http://www.ibm.com/developerworks/library/l-pycon.html

[13] http://www.ibm.com/developerworks/library/l-pycon.html

[14] http://www.ibm.com/developerworks/library/l-pycon.html

---