article · ACM Transactions on Programming Languages and Systems · 1989

I-structures: data structures for parallel computing

Arvind Arvind, Rishiyur S. Nikhil, Keshav Pingali

Cited by 362Abstract and details only

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.

Cite this paper

APA 7

Arvind, A., Nikhil, R. S., & Pingali, K. (1989). I-structures: data structures for parallel computing. ACM Transactions on Programming Languages and Systems, 11(4), 598–632. https://doi.org/10.1145/69558.69562

MLA 9

Arvind, Arvind, et al. “I-structures: data structures for parallel computing.” ACM Transactions on Programming Languages and Systems, vol. 11, no. 4, 1989, pp. 598–632, https://doi.org/10.1145/69558.69562.

Chicago

Arvind, Arvind, Rishiyur S. Nikhil, and Keshav Pingali. 1989. “I-structures: data structures for parallel computing.” ACM Transactions on Programming Languages and Systems 11 (4): 598–632. https://doi.org/10.1145/69558.69562.

Harvard

Arvind, A., Nikhil, R.S. and Pingali, K. (1989) ‘I-structures: data structures for parallel computing’, ACM Transactions on Programming Languages and Systems, 11(4), pp. 598–632. Available at: https://doi.org/10.1145/69558.69562.

BibTeX

@article{arvind1989structures,
  title = {{I-structures: data structures for parallel computing}},
  author = {Arvind, Arvind and Nikhil, Rishiyur S. and Pingali, Keshav},
  journal = {ACM Transactions on Programming Languages and Systems},
  volume = {11},
  number = {4},
  pages = {598--632},
  year = {1989},
  doi = {10.1145/69558.69562}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.