From: Jim Weirich Date: 2003-03-24T13:52:54+09:00 Subject: 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 jweirich@one.net 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)