Generators

A generator (as I will use the term here) is an object that can “generate” other objects on demand. They work like random generators, except that they need not generate numbers or do so randomly: you ask it for the next value, and it gives it to you.

The naive generator is simply a class that supports this method:

T Next();

Generators work a bit like iterators, but they are slightly different:

• Iterators work on both finite and infinite sequences, while generators are always (supposed to be) infinite.
• Iterators are typically used in loops to process elements in sequence on the spot. Generators are generally use over some time span (similar to how random numbers are often used in simulations).
• Iterators are usually restarted on each use; generators are rarely restarted.

The idea with generators is that they encapsulate state-tracking data that would otherwise pollute your class. In a tower defense game, for example, you may want to generate enemies that get progressively more difficult to beat. One way to implement this is to maintain a difficulty variable, and update it each time you make a monster:

var monster = new Monster(difficulty);

difficulty *= 1.1f;

In this simple example it is not so bad; but things become messy when the logic is more complicated and you have to generate more types of objects.

The alternative using generators is:

var monster = monsterGenerator.Next();

Once you have the concept of a generator, you can start doing some interesting things; very similar to the way LINQ in C# allows you to do some interesting things with sequences. We can build a framework to make more generators from existing ones, and indeed it resembles LINQ in many ways. Here are some of the core operations:

• Where: Makes a new generator that filters the elements of a source generator with a predicate.
• Select: Makes a new generator that applies a selector function to elements of a source generator.
• Zip: Makes a new generator that applies a selector function to elements of two or more generators.
• Choose: Makes a new generator that uses an integer generator to choose elements from a sequence.
• Choose: Makes a new generator that uses an integer generator to choose a generator from a sequence to generate an element from.
• RepeatEach: Makes a generator that generates each element of a source generator a number of times.

We also need some functions to make basic generators:

• Constant: Makes a generator that generates the same element each time (this is for example useful in functions that take generators instead of fixed values).
• Repeat: Makes a generator that generates a elements from a sequence and repeats the cycle over and over.
• Count: Makes a generator that generates integers from 0 to n-1 and repeats the cycle over and over.
• UniformRandomInt: Makes a generator that generates pseudo-random integers.
• UniformRandomFloat: Makes a generator that generates pseudo-random floats.
• Iterate: Makes a generator that uses a few initial elements, and a function repeatedly applied to the last few generated elements.
• Skip: Makes a new generator that skips over ‘n number of elements of a source generator.
• Pad: Makes a new generator padded (on the left) with elements from a sequence, or a value repeated a number of times.

And finally, a few convenience methods:

• Next(n): Returns the next n elements in an IEnumerable.
• MoveNext(n): Advances the generator n times.

Examples

To give you an idea of how these functions can be used to make new generators, here are some examples (I use [] for lists here):

Repeat the binary digits of 0, 1, …, 7

var digit0 = Count(2); // 0 1 0 1 0 1 ...
var digit1 = digit0.RepeatEach(2); // 0 0 1 1 0 0 1 1 0 0 ...
var digit2 = digit1.RepeatEach(2); //0 0 0 0 1 1 1 1 0 0 0 0...
var choice = Count(3); //0 1 2 0 1 2
var binary = Choose([digit2, digit1, digit0], choice);
// 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 ...

Random inside circle

var random = UniformRandomFloat(); 
var randomInsideCircle = random
   .Zip(random, (x, y) => new Vector(x, y))
   .Where(v => v.magnitude < 1)
   .Select(v => v*radius);

(I discuss the copying of source generators a bit later; for now: the two uses of the random generator will not generate the same elements.)

Fibonacci numbers

var fibonacci = Iterate(1, 1, (x, y) => x + y);

Implementation Issues

In C#, IEnumerables represent only a sequence. A generator, on the other hand, represents a sequence and a state. When we make a new generator from some source generator, we do not want a call to Next on the derived generator affect the state of the source generator.

An implementation that keeps references to source generators in derived generators can lead to unexpected results.

var count = Count(5);
var even = count.Select(x => x * 2);

Print(even.Next()); // 0
Print(even.Next()); // 2
Print(even.Next()); // 4
Print(count.Next()); // 3 - already advanced by "even".

To get generators to behave as we expect, we need to copy source generators (usually in the constructor of the derived generator).

In many cases it is convenient to look at the current value without advancing the generator. This is a bit like peeking at a stack or queue. To make this possible, it is necessary to split Next into to atomic operations: one to retrieve the current value, and one to advance the generator.

This makes the Generator class look very much like an IEnumerator (it supports Current and MoveNext). But because generators are infinite, it is not necessary to return whether there is a next element (there always is); nor is it necessary to keep the generator in a “before first” state; it is always OK to go directly to the first state.

It is possible to construct “impossible” generators:

var impossible = Constant(0).Where(x > 0);

This generator will go into an infinite loop and never generate a single element. Unfortunately, it is not possible to detect cases like this automatically. One way to deal with this is to maintain a “time-out” counter in generators where this can happen, and throw an exception when the counter reaches a threshold.

It is also possible to create generators that will overflow:

var count = Iterate(0, x => x + 1); //will eventually overflow

In example like that the overflow is expected. However, a user of the method below may not expect the returned generator to overflow:

static IGenerator<float> Average(this IGenerator source)
{
   var sourceCopy = sournce.Clone();
   var sum = Iterate(0, x => x + sourceCopy.Next());//Not a good way!
   var count = Iterate(1, x + 1).Pad(1, 1);
   var average = sum.Zip(count, (x, y) => x / y);
}

so it is important to mark potentially unsafe generators.

Laziness can also produce unexpected results if you are not careful. In an earlier implementation, I made the Next(n) method a lazy IEnumerable, like this:

public IEnumberable<T> Next(this IGenerator<T> source, int n)
{
   for(int i = 0; i < n; i++) yield return next;
}

This scheme allows you to distribute computations over time, and pad with arbitrary large sequences. However, the problem is that calls to next may be made in the incorrect order, giving unexpected results. For example:

var count = Count(100);
var first50 = count.Next(50);
var second50 = count.Next(50);
var element101 = count.Next();

foreach(var element in second50)
   Print(element); //prints 1, 2, 3, 4, ..., 50!

foreach(var element in first50)
   Print(element) // prints 51, 52, ..., 100!

Print(element101) // prints 0!

foreach(var element in second50)
   Print(element); // prints 101, 102, ..., 150!

The problem is that Next is only called once the element is retrieved from the IEnumerable. And if the elements are retrieved more than once, then the elements change!

So far I have not found a good solution for this; it looks like you may need to evaluate the elements immediately.

Limitations

You may recognize the image at the top of this post as a dragon curve. Iterations of this curve can be constructed with a sequence called the paper folding sequence or dragon curve sequence (interpreted as left and right turns by 90 degrees followed by moving forward by a fixed amount, LOGO style): 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 …

This sequence have a simple description:

Take the alternating sequence 1 0 1 0 1 0, add a blank between each two elements: 1 ( ) 0 ( ) 1 ( ) 0 ( ) 1 ( ) 0. Then fill in the paper folding sequence in the blanks; a few steps are shown below:

1. 1 (1) 0 ( ) 1 ( ) 0 ( ) 1 ( ) 0
2. 1 (1) 0 (1) 1 ( ) 0 ( ) 1 ( ) 0
3. 1 (1) 0 (1) 1 (0) 0 ( ) 1 ( ) 0
4. 1 (1) 0 (1) 1 (0) 0 (1) 1 ( ) 0
5. 1 (1) 0 (1) 1 (0) 0 (1) 1 (1) 0

You basically use parts of the sequence already constructed to construct the rest. The sequence is defined recursively.

S(n) = 1 if n mod 4 == 0
     = 0 if n mod 4 == 2
     = S((n + 1)/2) otherwise

I would have like to be able to construct this sequence something like this:

IGenerator<int> paperFoldingSequence;
paperFoldingSequence = Count(2).Interleave(paperFoldingSequence);

Because elements are generated one by one, it should be possible. And indeed it is. Normally, a copy is made of the source sequence when constructing the derived sequence. In this case, it leads to an infinite loop (as the copy calls the constructor, which makes a copy that calls the constructor…). However, it is possible to delay making the copy until an element is actually required from the sequence. This works; but there is a problem; every two iterations a new copy of the sequence is made.

I don’t think there is a way around this; in practice the memory overhead can be reduced by using a queue to enqueue elements as they are generated and dequeue them as they are required (so that you do not need to create copies every two elements). The memory still grows at the same proportion – but this way it’s by one floats every two iterations instead of one generator every two iterations.

The downside is that this cannot be expressed in a general way (at least, not anything sensible I could come up with), so you have to define the generator as its own class, and cannot build it from the generator functions as shown above.

Code

The C# code for this will be part of our free Unity Extensions package, but you can check out a version of it below.

It does not require Unity, but it does depend on a random number implementation (you can just drop System.Random in place of IRandom).

Generators.cs