Stream Processing

Stream processing is a basic method of code optimization related to loop fusion that can improve the space and speed of iterative applicative expressions by a process of loop combination. It has been studied before in applications to program improvement and batch oriented database restructuring. Previous attempts at implementation have been either highly restrictive, have required manual intervention, or have involved naive strategies resulting in impractically slow running times. This paper defines a new model for a stream processing problem for handling a wide class of applicative expressions that can be evaluated by looping in an unordered way through a single set or tuple valued argument. This problem is formulated graph theoretically and shown to be NP-Hard, even in the presence of constraints. Two new efficient heuristic algorithms will be presented. The efficiency of these solutions allows stream processing to be applied dynamically as a database query optimization, and as an important component of a high level language optimizer. Our method of stream processing has been implemented and used effectively within the RAPTS transformational programming system