Using generators on the primeFactorsFactorial example

Last example algorithm, primeFactorsFactorial did involve enumerating of several collections:

• The collection of primes up to n
• The collection of powers of these primes

An alternative is to work with a stream that generates each item on the fly, rather than collecting the whole sequence of values, and then pipe to other kind of streams that transform the values. This technique has two advantages:

1. avoiding allocation of large auxiliary collections that will later be thrown out, can help some algorithms to scale up.
2. piping could theoretically enable parallel execution if we had a multi-threaded VM (though in fact we keep some collections, the optimal performance being often reached by tuning some buffers size, since the cost of inter thread synchronisation is not null)

This does not really apply to our prime factors decomposition since the collection of primes are not huge, but we have this example available, let's use it and see how it would be possible in Squeak.

First, Squeak provides an primesUpTo:do: taking a block as argument. That's all we need.

We can transform this block into a stream using a Generator. Let see in class comment how to use it:

    | generator |
    generator := Generator on: [:g| Integer primesUpTo: 100 do:[:prime| g yield: prime]].
    [generator atEnd] whileFalse:[Transcript show: generator next].

OK, so a new Generator is associated to an outer block, [:g| Integer primesUpTo: 100 do:[:prime| g yield: prime]], which tells which method to execute to produce the sequence of values.

The inner block [:prime| g yield: prime] just tells the generator that a new prime is available. 

Each time we ask for generator next, the generator machinery arranges to advance the execution of outer block until it reaches execution of the inner block, and then switch back and return the prime provided to this block.

This is known as the coroutine technique, and implemented by using a clever a simple hack manipulating the call stack. Look at the implementation by yourself.

Note that a Generator now understand value: and can be used directly in place of the inner block, try (Generator on: [:g| Integer primesUpTo: 100 do: g]) contents.

Can we apply this to our primeFactorFactorial?

primeFactorFactorialViaGenerator
    | generator |
    generator := Generator on: [:g | Integer primesUpTo: self + 1 do: g].
    ^ (generator collect: [:p | p raisedToInteger: self - (self sumDigitsInBase: p) // (p - 1)]) product

Hmm, it will not work, because a Generator understands only one iteration operator, do:, but not collect: Squeak streams are a pity.

More over, the collect: operation if implemented by means of do: would not be lazy but rather produce the whole collection of powers. We would have only eliminated the first collection of primes, but not the collection of powers of primes.

One good and recent framework - Xtream - It is an interesting alternative and provides the lazy operations we're looking for; follow the squeaksource link to get download instructions. Let's see how we can lazily pipe the operations through streams:

primeFactorFactorialViaGeneratorAndXtream
    | generator stream factorial |
    generator := Generator on: [:g | Integer primesUpTo: self + 1 do: g].
    stream := ((XTBlockClosureReadStream
                on: [generator atEnd
                        ifTrue: [Incomplete raise]
                        ifFalse: [generator next]])
                collecting: [:p | p raisedToInteger: self - (self sumDigitsInBase: p) // (p - 1)])
                injecting: 1 into: [:product :power | product * power].
    ^ [[factorial := stream get] repeat]
        on: Incomplete
        do: [factorial]

Unfortunately Xtream has no Generator, so we have to wrap it up in a BlockClosureReadStream.

Another problem is that injecting:into: is not reducing the stream to a single element, instead it answers a stream of all the intermediate results. Since we only need the last one, we have to repeat the operation by ourself, capture and answer the last element when the stream starves (we catch this Incomplete exception).

Once I proposed an alternative selector ^[stream get] repeatUntil: Incomplete, with a slight modification, this would have been useful; or maybe we could just extend XTReadStream to respond to last.

Let see how the generator variant performs:

Smalltalk garbageCollect.
Time millisecondsToRun: [1 to: 3000 do: [:x | x primeFactorFactorialViaGeneratorAndXtream] ]
-> 22835 22529

This is to be compared to the 19136ms of naive form. Well, that was expected, we eliminated the intermediate collections, but they did not cost that much in this case. Instead we pay a price for indirection and maybe also the Generator trick forces COG VM to un-optimize some portions. But that doesn't matter, we saw some smart streaming techniques.

A more difficult exercise would be to transform a divide and conquer recursive product evaluation variant into a streaming equivalence... Yet I do not know how, but if I find it, this will be another post.