Iteration styles (was Ruby lecture slides)

On Sun, 2003-03-23 at 19:54, Greg McIntyre wrote:
> Okay, so what if, instead of saying "This functionality has been added
> to Python recently as generators," I said that "This functionality has
> been added to Python recently using generators"? I mean. If generators
> are a more powerful and general construct, they should be able to do
> what Ruby blocks can, plus more.

I don't think you can say blocks are more powerful than generators, nor
that generators are more powerful than blocks.  Its like claiming that
multiplication is more powerful than addition.

I think the key point is not blocks vs generators, but the *style* of
iteration in each language.  It is the basic choices about iteration
style that gives rise to blocks and generators.

Python (tends) to use a style of iteration I call external iterators
(terminology in the industry varies, so be aware).  The C language
designers noticed that a loop can be defined by initialize / test /
increment code fragments.  Likewise, an external iterator captures these
operations as methods in an object.  In Python (IIRC) the next() method
both returns the next object and advances the iterator and an exception
is used to signal the end of the iteration.

An external iterator object keeps its state separate from the object it
is iterating.  Multiple external iterators (referencing the same
collection) may exist at any one time.  The user may call next
explicitly, but I believe that Python is knowledgable about iterators
and will automatically use an iterator in a for statement.

External iterators are conceptually simple and easy to use.  Many
languages (e.g. C++, Java) use this style of iterator.

Here is an external iterator for Fibonacci numbers (in Ruby ... my
Python knowledge is too weak for public review :-)

  class FibIterator
    def initialize
      @x = 0
      @y = 1
    end
    def next
      @x, @y = @y, @x + @y
      @x
    end
  end

  fib = FibIterator.new
  9.times { print fib.next, " " }
  puts

The one annoying aspect of external iterators is that the logic for
iteration is spread across several methods of the iterator class.  Also,
the iterator class must be intimate with the details of the class it is
iterating over.

Internal iterators address this to some degree.  Instead of putting
initialize/test/increment into different methods, internal iterators put
the logic in a single method and have the client supply the "work"
code.  There are a number of ways to do this, but by far the simpliest
is to supply an anonymous function that is passed to the iterating
method.  This is the approach Ruby uses.

Here is an interal Fibonacci iterator in Ruby.

  def fibs(n)
    x = 0
    y = 1
    n.times do
      x, y = y, x + y
      yield(x)
    end
  end

It turns out that most loops can be expressed as a small number of
variations on basic internal iterator theme.  In Ruby, we give those
variations names (collect, select, reduce, find, find_all, etc.).  It is
not uncommon to write a Ruby program without using any explicit loops at
all.  This is a very powerful idiom.

Another advantage of internal iterators is that they are harder to
abuse.  Since the looping logic is encapsulated, you can't accidently
call next() beyond the end of the loop.

On the other hand, internal iterators have trouble with certain types of
algorithms.  The biggest stumbling block is that it is difficult to walk
two sequences in parallel using internal iterators.

Nevertheless, internal iterators are a powerful mechanism, and the Ruby
library is designed with internal iterators in mind.

So where do generators come in?  A generator is simply an external
iterator where the logic is written in an internal iterator style.  In
Python, a function that invokes "yield" really doesn't execute the body
of a function at all, but instead returns an iterator whose next()
function is tied to the function body.  When next() is called on this
iterator, the body executes until it hits yield.  Yield causes the given
value to be returned as the value of next.  When next() is called again,
the iterator will pick up where it left off with the code immediately
following the yield.

Here is the generator version of the Fibonacci sequence. (I'll paste in
the version from the Python recipe page)

  def fib():
    x = 0
    y = 1
    while 1:
        x, y = y, x + y
        yield x

  g = fib()
  for i in range(9):
    print g.next()

To accomplish this trick, generators do magic on the return stack.  I
don't recall the details, but conceptually you have two independent call
stacks, one for the calling code and one for the generator (note that I
said conceptually.  I think is real life Python does something tricky
that avoids the need for two actual stacks, but that's an optimization
detail).  In a very real sense, a generator is a very limited form of
coroutines.

So, generators are a way of having the flexibility of external iterators
with the convience of writing them in a single method like an internal
iterator.

Can Ruby do external iterators?  Sure, they are easy to write.  If we
hit one of those rare problems that really require external iterators,
we can write one and use it with no problem.  In general, there is no
need to resort to anything fancy (e.g. coroutines, generators or
continuations).

Now the Ruby library does assume most everything has an internal
iterator.  This is still no problem because it is easy to turn an
external iterator into an internal one if needed.

No, the real interesting question is how do you turn an existing
internal iterator into an external one ... that is without rewriting the
iteration logic.

This is possible in Ruby, but it requires that we be able to return from
a function in such a way we can resume the function at the return point
(exactly as generators do).  We don't have generators in Ruby, but we do
have a very powerful, mind-bending capability called continuations. 
Someday I would like to write up how do use continutations to do this,
but this note is already too long.  Suffice it to say that we can use
continuations to implement generator capability in about 20 lines of
code.  

So, if we need external iterators AND we have a container class that
only provides internal iterators AND we don't want to duplicate the loop
iteration logic, THEN we can use generators (implemented in
continuations) to get the effect we want.

So which way is better?  I find it is fascinating that both Ruby and
Python have almost equivalent power in its iteration, they have just
taken different paths to get there.

-- 
-- Jim Weirich     [e-mail]    http://w3.one.net/~jweirich
---------------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct, 
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)