I-structures: data structures for parallel computing
Authors:
- ArvindARArvind
Open Access
- 1 October 1989
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 11 (4) , 598-632
Abstract
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.Keywords
This publication has 11 references indexed in Scilit:
- Resource requirements of dataflow programsACM SIGARCH Computer Architecture News, 1988
- Accumulators: New logic variable abstractions for functional languagesLecture Notes in Computer Science, 1988
- A new array operationLecture Notes in Computer Science, 1987
- Advanced compiler optimizations for supercomputersCommunications of the ACM, 1986
- Dataflow ArchitecturesAnnual Review of Computer Science, 1986
- Making data structures persistent1986
- A semantic model of reference counting and its abstraction (detailed summary)1986
- Lambda lifting: Transforming programs to recursive equations1985
- Functional programing and the logical variable1985
- Dependence graphs and compiler optimizations1981