Generators Example

Generators in Vodka, like those provided by Python or Ruby, are functions that produce a sequence of values, yielding control to the caller/receiver each time a new value is generated. After the receiver has consumed the new value, the generator resumes after the yield statement. This way, sequential output from complex data structures can be produced in a forward manner, being consumed on the fly, without intermediate data-structures.

Due to the concurrent nature of the Vodka language, generators (and coroutines, as the implementation mechanism) are a natural fit. Instead of introducing a special yield keyword, we can yield control from any function, just by calling another function received as a parameter. Additional syntax, though, is provided on the consumer side, in order to facilitate generator comprehension. The code below shows a simple generator, and different syntax for printing the generated values to standard output. There is also a built-in syntax for generator literals, which allows the genTest generator to be written as [1,2,3].

new genTest;

def genTest(yield):
{
    yield(1);
    yield(2);
    yield(3);
    return();
}


# example usage

genTest(print);

genTest->foreach(print);

print x for x in genTest;

for x in genTest:
    print x;

Generators are especially powerful when combined through higher-order functions, and many of those that commonly appear in functional languages can be implemented straightforwardly. In the code below, we show a simple range operator that enables expressions like 3..7, and the higher-order function zip, which synchronizes multiple (in this case: two) source generators. Other generator combinators can be written accordingly, either from scratch or by composing existing ones with the help of generator comprehension statements (for ... in ...).

new `..`;
def `..`(x, y):
{
    new gen;
    def gen(yield):
    {
        new iter;
        def iter(n, false):
        {
            returnto.gen();
        }
        def iter(n, true):
        {
            yield(n);
            iter(n+1, n+1 <= y);
        }       
        iter(x, x <= y);
    }
    return gen;
}

new zip;
def zip(g1, g2):
{
    new gen;
    def gen(yield):
    {
        new r1;
        new r2;
        
        def r1(a1) & r2(a2):
        {
            yield(a1, a2);
            returnto.r1() &
            returnto.r2();
        }
        g1(r1) & g2(r2);
        return();
    }
    return gen;
}

map = fn gen, f: (f(x) for x in gen);

zipWith = fn (g1, g2), f: zip(g1, g2)->map(f);

cartesian = fn a, b: (x, y for x in a for y in b);

The code below shows some more example uses of generators. An important thing to remember is that generators are in fact functions (and thus first-class values), so generator comprehension expressions, too, can be treated as such.

# generators as values

oneToTen = 1..10;

oneFourNine = [1,4,9];

oddNumbers = i if i%2 == 1 for i in 1..10;


# reduction functions

sumOfSquares = sum(x*x for x in 1..10);

sameFringe = all((treeA->leaves(),treeB->leaves())->zipWith(`==`));


# printing square numbers: 1, 4, 9

for x, y in zip(1..3, 1..3):
    print(x * y);

(1..3, 1..3)->zipWith(`*`)->foreach(print);

[1,2,3]->map(fn x: x*x)->foreach(print);


# printing cartesian product: (1,1),(2,1),(1,2),(2,2),(1,3),(2,3)

for y in 1..3:
    for x in 1..2:
        print(x, y);

cartesian(1..2, 1..3)->foreach(print);

Another powerful abstraction are reduction operations (like sum, max or all) that are also common in functional programming languages. Together with the lazy nature of generators, they provide for a natural formulation and efficient implementation of solutions to non-trivial problems such as whether two trees have exactly the same inorder-sequence of leaves (known as the Samefringe-Problem) assuming in this example that the leave-generators produce a special end-of-fringe marker to guarantee termination.

new pull;

def pull(gen):
{
    new yield;
    new next;
    
    def yield(n) & next(r):
    {
        returnto.yield(r) &
        returnto.next(n);
    }
    
    gen(yield) & return(next);
}

next = pull(1..100);

print next();

next();
next();

print next();

next();
next();
next();
next();

print next();