Stream Processing

Editor(s)

Boyer, Robert S. and Schneider, Edward S. and Steele, Guy L., Jr.

Abstract

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.

Meeting Name

1984 ACM Symposium on LISP and functional programming

Department(s)

Mathematics and Statistics

Document Type

Article - Conference proceedings

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 1984 Association for Computing Machinery (ACM), All rights reserved.

Publication Date

01 Jan 1984

Link to Full Text

Share

 
COinS