Let’s take F#, for example. The following is a simple F# sequence expression:
seq { yield 1 yield 2 yield! [3;4] yield 5 }
This expression creates an IEnumerable<int> which yields the elements 1 through 5 on-demand. If we wrap this expression in a Quotation and decompile it with Unquote, we can see its de-sugared form:
seq (Seq.delay (fun () -> Seq.append (Seq.singleton 1) (Seq.delay (fun () -> Seq.append (Seq.singleton 2) (Seq.delay (fun () -> Seq.append [3; 4] (Seq.delay (fun () -> Seq.singleton 5))))))))
Basically, what we get is a series a continuations, similar in concept to what monadic syntax gives in general in Haskell (and indeed, in F# too with the more general concept of computation expressions).
Understanding this, we realize that between standard Java Iterables, Groovy Closures (with a bit of dynamic delegation), and Groovy AST Transformations, we can have a similar generator syntax in Groovy.
First, we’ll implement a type Generator<E> implementing Iterable<E> which generates elements on-demand from a closure composed of nested continuations (no syntactic sugar yet, we’ll get there with AST Transformations later on):
With a static import for Generator.gen, we can create a Generator equivalent to our F# example like so:
First, notice that all of our calls to undefined yield and yieldAll methods are resolved via delegation to Generator yield and yieldAll methods (which return YieldResults, used internally by our Iterable impementation for keeping track of the next continuation). Starting from the root Closure supplied to gen, each call to Iterator.next() returns the first argument supplied to the yield or yieldAll method, saving the second continuation argument for the next next() call, continuing this way until a continuation which returns null ends iteration (with some look-ahead complexities accounted for to accommodate the hasNext() pattern, as well as some complexity flattening out elements supplied to yieldAll).
To demonstrate the on-demand nature of our generator, consider the following tests:
This is all well and good, but no one wants to write all those continuations by hand. We need some syntactic sugar here. This is where AST Transformations come in to play. We will write an AST Transformation which allows us to write our generator expressions like so:
We implement two AST Transformations: YieldTransformation, which de-sugars our generator closure, and GenTransformation, which extends YieldTransformation, constructing a Generator from the de-sugared generator closure:
Note that what we have here is indeed just a proof of concept: the YieldTransformation doesn’t yet handle if / then / else expressions for example (though those cases should be pretty straight forward having implemented the more difficult BlockStatement transformation).
It would be great to see a Generator feature like this brought natively to Groovy in the future (and without the need for AST Transformation, which requires the use of annotations on declaration expressions). The full power of on-demand generators like this become apparent when used in conjunction with on-demand Iterable transformation libraries such as Tim Yates' groovy-stream or my own Functional Java (yet to be ported for friendly use from Groovy).
