I-structures: data structures for parallel computing
Arvind Arvind, Rishiyur S. Nikhil, Keshav K. Pingali · ACM Transactions on Programming Languages and Systems · 1989
It is difficult to achieve elegance, efficiency, and parallelism simultaneously in functional programs that manipulate large data structures. We demonstrate this through careful analysis of program examples using three common functional data-structuring approaches-lists using Cons, arrays using Update (both fine-grained operators), and arrays using make-array (a “bulk” operator). We then present I-structure as an alternative and show elegant, efficient, and parallel solutions for the program examples in Id, a language with I-structures. The parallelism in Id is made precise by means of an operational semantics for Id as a parallel reduction system. I-structures make the language nonfunctional, but do not lose determinacy. Finally, we show that even in the context of purely functional languages, I-structures are invaluable for implementing functional data abstractions.
Cited by 360 works. doi:10.1145/69558.69562
Authors
References
- Afips conference proceedings
- Proceedings of the 56th Annual ACM Symposium on Theory of Computing
- Dependence graphs and compiler optimizations
- Proceedings of the conference on Functional programming languages and computer architecture
- Advanced compiler optimizations for supercomputers
- The implementation of functional programming languages
- PFC: A Program to Convert Fortran to Parallel Form
- Making data structures persistent
- The Implementation of Functional Programming Languages (Prentice-hall International Series in Computer Science)
- Resource requirements of dataflow programs