A.3. Optimization

change_begin
Series expressions are transformed into loops by pipelining them-the computation is converted from a form where entire series are computed one after the other to a form where the series are incrementally computed in parallel. In the resulting loop, each individual element is computed just once, used, and then discarded before the next element is computed. For this pipelining to be possible, a number of restrictions have to be satisfied. Before these restrictions are explained, it will be useful to consider a related issue.

The composition of two series functions cannot be pipelined unless the destination function consumes series elements in the same order that the source function produces them. Taken together, the series functions guarantee that this will always be true, because they all follow the same fixed processing order. In particular, they are all preorder functions-they process the elements of their series inputs and outputs in ascending order starting with the first element. Further, while it is easy for users to define new series functions, it is impossible to define one that is not a preorder function.

It turns out that most series operations can easily be implemented in a preorder fashion, the most notable exceptions being reversal and sorting. As a result, little is lost by outlawing non-preorder series functions. If some non-preorder operation has to be applied to a series, the series can be collected into a list or vector and the operation applied to this new data structure. (This is inefficient, but no less efficient than what would be required if non-preorder series functions were supported.)
change_end

Next: Basic Restrictions Up: Series Previous: Alteration of Series

AI.Repository@cs.cmu.edu