jastrachan | 22 Apr 11:01 2004
Picon

Re: Generators take 2 (was Generator Expressions)


On 22 Apr 2004, at 05:00, Bruce Chapman wrote:
> James said:
>
>> BTW some background might help for those unaware of what all
>> this generators thing is. While its a big field and touches
>> on various topics like generators, coroutines, continuations,
>> backtracking, tail recursion along the way.
>>
>> The main aim in this use case (and similarly in the C# 2.0
>> spec)  is to offer a simple way to write iterators over data
>> in a simple way, where rather than having isNext() / next()
>> methods, you can just 'yield' each value when you're ready.
>>
>> Its a bit like the difference between pull and push based XML
>> parsing, kinda. Writing iterators is inside out and this
>> generators idea helps to write them the way our brains think
>> about them rather than the way we must structure them to
>> conform to java.util.Iterator.
>>
>> I think generators-as-iterators is fairly easily doable
>> without any wacky Thread stuff or support for full continuations etc.
>>
>> James
>> -------
>
> Hi all,
>
> Thanks James - I like the push vs pull explanation.
>
> I have been trying to follow this thread.
>
> There seems to be some aversion to using Threads. Is that pathological 
> or
> rational? Please explain.

Threads are fairly heavy-weight, whereas creating a new (temporary) 
object per generator is quite cheap these days. Though I guess my 
biggest fear of the theads-based implementation is considering using 
Groovy as a scripting & template language inside of a web server. 
Firstly in J2EE its considered to be bad practice to create your own 
threads, the container is meant to take care of all that. I think more 
concerning is the thought that each servlet request could end up 
creating a hundred threads just to render one page which seems kinda 
excessive.

For stand alone scripts I don't think its an issue - I'm more thinking 
of using Groovy inside J2EE containers which would make the Iterator 
solution more attractive.

> From my point of view, the easiest way to do this is to run the 
> generator in
> a separate thread.
>
> Object.wait() and Object.notify() are the way the JVM saves and 
> restores (or
> suspends and resumes) the call stack. Why do anything else that could
> possibly have corner cases that don't work.
>
> In Essence, creating the iterator starts the thread in the generator, 
> which
> immediately waits till the first next() or hasNext(), which kicks it 
> off.
> yield() passes its value to the now waiting (main) thread then waits 
> again
> till the main thread needs another value. It would seem much easier 
> than
> trying to save stack state then restore it using a continuations type 
> model.

I agree its easier to implement. Though since we're bytecode generating 
anyways I don't think the pure-Iterator approach is that hard. I guess 
we could implement both - the thread approach to start with then 
implement the pure-Iteartor/bytecode mangling one for J2EE containers?

> You probably want to use a Thread pool in the background, but it 
> certainly
> doesn't get close to being "wacky".

Apologies, didn't mean to be derogatory to the thread solution - its a 
perfectly sensible approach.

> I think of this Thread interaction as being like a newton's cradle 
> with 2
> balls. One is always waiting, and the other is always working. When the
> working Thread collides, momentum is conserved but transferred to the 
> other
> thread, and the other one starts running - back and forth. The 
> generator is
> coded like it is pushing the values, and the consumer code is coded 
> like it
> is pulling the values. Next() blocks till a result is available, 
> yield()
> blocks until another result is required.
>
> Based on this model I have written some Java code for a Generator 
> abstract
> superclass.

Cool

> I am using 1.5 beta1 because generics make this much simpler to
> understand and I can use the groovy looking 1.5 enhanced for loop 
> syntax,
> autoboxing/unboxing etc :).

Only downside is Groovy is still 1.4 based :(

> It works well and the use case code is pretty
> clean. The generator doesn't generate any more values than are 
> requested.
> yield() and fail() statements can be layers deep in the stack from the
> actual generate method so long as they are called on the generator 
> (think
> recursion, think helpers like failIfAfter5pm()! ).
>
> I even have it cleaning up an uncompleted iterator's generator thread 
> in the
> Iterator's finalize().  So BTW James - you need to add a 4th item to 
> the
> list of things (yield, fail, return) a generator can do. It can 
> complete
> abruptly (inside a yield() ) when the corresponding iterator is 
> finalized.
>
> My generator actually returns a ( new 1.5) java.lang.Iterable object 
> so that
> 	1	it works with the new 1.5 enhanced for loop syntax
> 	2	The generator can be used multiple times with the same
> argument(s).
>
>
> The API for the class looks like this
>
> /**
>  <at> param <T> The type of objects generated
>  <at> param <A> The type of the argument passed from the consumer to the
> generator.
> */
> public abstract class Generator<T,A> {
>     public Iterable<T> generate(A arg) {}
>     protected final void yield(T val) {}
>     protected final void fail() {}
>     abstract T generateElements(A arg);
> }
>
> You extend it and provide the generateElements method thus
>
>         // make a generator
>         Generator<Integer,Integer> g2 =
>             // generates a sequence of numbers whose square
>             // is less than arg
>             new Generator<Integer,Integer>(){
>                 Integer generateElements(Integer stop) {
>                     for(int i=0; i < stop; i++) {
>                         if( i*i < stop) {
>                             yield(i);
>                         } else {
>                             fail(); // terminates abruptly
>                         }
>                     }
>                     return null; // because I need to return something
>                 }
>             };
>         // consume the generator's output
>         for(int p : g2.generate(81)) {
>             System.out.println(p + " squared < 81");
>         }
>
> I haven't recoded that 8 queens solution yet, but it should work.
>
> Would you like the source posted and if so where?

Sure - though we can only accept 1.4 compliant code right now to add to 
the groovy project :(

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

Gmane