Generators for Xtreams

While at Smalltalk Solutions 2011 in Las Vegas, a question was raised about Generators. Martin and I had no idea what Generators were, so we filed that one away for “later pontification”. Well, that later came this week when Nicolas Cellier posted about using generators and Xtreams to compute primes.

One criticism Nicolas raised was the lack of Generators in Xtreams. We wanted to understand what Generators were and why they needed to manipulate the stack to work. In the end, we decided it’s actually faster and easier to implement them using a second process and a couple of semaphores. Also, more portable.

So what do generators do? Well, possibly the simplest example is this:

1 to: 10 do: [:i | …do something…]

In this case, you cannot easily transform it in to a stream using [] reading, because you get stuck inside the iteration block, controlled by the #to:do: method. A generator allows you to push out elements piece-meal regardless of the nature of the code you’re running, eg:

readStream := [:out | 1 to: 10 do: [:i | out put: i ] ] reading

The block will begin running immediately, but as soon as it tries to write out a value on to the @out variable, it will halt execution until you attempt to read from @readStream. This makes it possible for Nicolas to re-write his example as:

primes := [:out | Integer primesUpTo: 100 do: [:prime | out put: prime ] ] reading.

Note that @out is actually a write stream, so you can use all the regular streaming API on it too, such as #write: instead of a single element #put:.

The last part of this story isn’t to do with generators at all, but about using buffers to make non-positionable information positionable. In the case of Nicolas’s primes, he wanted the last element on the stream. You can’t “skip to end, rewind one, read last element” on a non-positionable stream. But you can on a positionable stream.

The default buffer of a positionable stream is endless though, so it will record everything, allowing you to rewind right back to the start. In this case, that’s a complete waste. We also only produce one element at a time, because it’s coming from a generator. So, we can use a RingBuffer of size 1 as the buffer for positioning.

(primes positioning buffer: (RingBuffer new: 1 class: Array))
    -= 1;
    get

This is where the positioning API of Xtreams really becomes handy. We use #-= which means “From the end of the stream, rewind ‘n’ elements”. Now that we have a positioning buffer that always remembers the last element, we can skip to the end and rewind by one element and then call #get to fetch it.

The [:out | ] reading generator terminal is available in XtreamsDevelopment 508.