jastrachan | 21 Apr 13:22 2004
Picon

Re: Generators take 2 (was Generator Expressions)

I just took a look at how generators are designed in C# 2.0 which seem 
quite nice. Basically the trick is that a generator could return a new 
java.util.Iterator instance which maintains its own state.

e.g.

myGenerator() {
   yield 1
   for (x in 3..6) {
     yield x
   }
}

if I then did

     list = []
     for (x in myGenerator()) {
	list.add(x)
     }
     assert list == [1, 3, 4, 5, 6]

So what we'd need to do to implement these kinds of generators is...

* reserve 'yield' as a keyword (worth doing now just in case)
* any method which uses 'yield' must return any type, Iterator or 
Object. i.e. its a compile error for the return type to not support 
Iterator
* we then transform the AST of the method code to create an inner class 
which implements Iterator to walk through the 'yield' statements.

This basically means that all the local variable state in the method 
becomes state in the Iterator implementation class. Then the iterator 
class would need to maintain a kinda stack pointer to know where it was 
last time since the last yield statement.

In pseduo-code we transform the above generator method into something 
vaguely like

myGenerator() {
     return new Foo$myGenerator()
}

// inner class which implements the generator...

class Foo$myGenerator extends Generator {
     private Iterator iteratorForXLoop;
     private int lastSwitchPoint = 0;

    boolean hasNext() {
	switch (lastSwitchPoint) {
	    case 0:
		setNext(1)
		++ lastSwitchPoint
		return true
	    }
	    case 1:
		iteratorForXLoop = (3..6).iterator()
		for (x in iteratorForXLoop) {
		    setNext(x)
		    lastSwitchPoint = 2
		    return true
	
		    label2:
		}
		++ lastSwitchPoint
		return true

	    case 2:
		goto label2;

	    default:
		return false
	}
}

The basic trick is to store all local state inside the inner class as 
state which is available across each iteration loop and then we need to 
be able to jump back inside loops. I'm sure there could be some other 
issues in there somewhere - this is all just off the top of my head - 
but I'm sure at the bytecode level the above is easily possible. Though 
its gonna be quite hairy to do with the current bytecode generator.

I'm very keen as soon as possible to put in a Java AST abstraction we 
can use at the bytecode generator to make the bytecode generation of 
normal Java-like statements easy to do as well as of groovy things like 
closures (maybe modules soon too) and one day maybe generators as well. 
This will hopefully put an end to these awful verify exceptions we get 
in certain circumstances

James
-------
http://radio.weblogs.com/0112098/

Gmane