{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T05:06:54Z","timestamp":1773983214191,"version":"3.50.1"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[1989,10,1]],"date-time":"1989-10-01T00:00:00Z","timestamp":623203200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[1989,10]]},"abstract":"<jats:p>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 \u201cbulk\u201d 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.<\/jats:p>","DOI":"10.1145\/69558.69562","type":"journal-article","created":{"date-parts":[[2002,10,7]],"date-time":"2002-10-07T13:52:47Z","timestamp":1033998767000},"page":"598-632","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":234,"title":["I-structures: data structures for parallel computing"],"prefix":"10.1145","volume":"11","author":[{"family":"Arvind","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge"}]},{"given":"Rishiyur S.","family":"Nikhil","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge"}]},{"given":"Keshav K.","family":"Pingali","sequence":"additional","affiliation":[{"name":"Cornell Univ., Ithaca, NY"}]}],"member":"320","published-online":{"date-parts":[[1989,10]]},"reference":[{"key":"e_1_2_1_4_2","first-page":"225","volume-title":"Annual Reviews in Computer Science","volume":"1","author":"ARVIND LLER","year":"1986","unstructured":"ARVIND , AND CU LLER , D. E. Dataflow architectures . In Annual Reviews in Computer Science , vol. 1 . Annual Reviews Inc., Palo Alto, Calif. , 1986 , pp. 225 - 253 . ARVIND, AND CULLER, D.E. Dataflow architectures. In Annual Reviews in Computer Science, vol. 1. Annual Reviews Inc., Palo Alto, Calif., 1986, pp. 225-253."},{"key":"e_1_2_1_5_2","volume-title":"IEEE Trans. Comput., 1989. To be published. An earlier version appeared in Proceedings of the PARLE Conference","author":"ARVIND H1L","year":"1987","unstructured":"ARVIND , AND NIK H1L , R. S. Executing a program on the MIT tagged-token datafiow architecture . IEEE Trans. Comput., 1989. To be published. An earlier version appeared in Proceedings of the PARLE Conference ( Eindhoven, The Netherlands , June 15-19, 1987 ). Springer-Verlag LNCS 259, New York, 1987. ARVIND, AND NIKH1L, R.S. Executing a program on the MIT tagged-token datafiow architecture. IEEE Trans. Comput., 1989. To be published. An earlier version appeared in Proceedings of the PARLE Conference (Eindhoven, The Netherlands, June 15-19, 1987). Springer-Verlag LNCS 259, New York, 1987."},{"key":"e_1_2_1_11_2","volume-title":"Proceedings of the 15th Annual International Symposium on Computer Architecture","author":"CULLER D. E.","year":"1988","unstructured":"CULLER , D. E. , AND ARVINO . Resource requirements of datafiow programs . In Proceedings of the 15th Annual International Symposium on Computer Architecture ( Honolulu, Hawaii , May 1988 ). CULLER, D. E., AND ARVINO. Resource requirements of datafiow programs. In Proceedings of the 15th Annual International Symposium on Computer Architecture (Honolulu, Hawaii, May 1988)."},{"key":"e_1_2_1_12_2","first-page":"109","volume-title":"Proceedings of the 18th Annual ACM Symposium on Theory of Computing","author":"DRISCOLL J.","year":"1986","unstructured":"DRISCOLL , J. , SARNAK , N. , SLEATOR , D. , AND TARJAN , R. Making data structures persistent . In Proceedings of the 18th Annual ACM Symposium on Theory of Computing ( Berkeley, Calif. , May 1986 ), pp. 109 - 121 . 10.1145\/12130.12142 DRISCOLL, J., SARNAK, N., SLEATOR, D., AND TARJAN, R. Making data structures persistent. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing (Berkeley, Calif., May 1986), pp. 109-121. 10.1145\/12130.12142"},{"key":"e_1_2_1_13_2","first-page":"629","volume-title":"AFIPS Conference Proceedings","volume":"48","author":"GOSTELOW K. P.","year":"1979","unstructured":"GOSTELOW , K. P. , AND THOMAS , R.E. A view of datafiow . In AFIPS Conference Proceedings , vol. 48 , 1979 , pp. 629 - 636 . GOSTELOW, K. P., AND THOMAS, R.E. A view of datafiow. In AFIPS Conference Proceedings, vol. 48, 1979, pp. 629-636."},{"key":"e_1_2_1_14_2","first-page":"351","volume-title":"Proceedings of the 1986 ACM Conference on Lisp and Functional Programming","author":"HUDAK P.","year":"1986","unstructured":"HUDAK , P. A semantic model of reference counting and its abstraction . In Proceedings of the 1986 ACM Conference on Lisp and Functional Programming ( Cambridge, Mass. , Aug. 1986 ), pp. 351 - 363 . 10.1145\/319838.319876 HUDAK, P. A semantic model of reference counting and its abstraction. In Proceedings of the 1986 ACM Conference on Lisp and Functional Programming (Cambridge, Mass., Aug. 1986), pp. 351-363. 10.1145\/319838.319876"},{"key":"e_1_2_1_15_2","volume-title":"Proceedings of the 4th IEEE Symposium on Logic in Computer Science (Asilomar, Calif.","author":"JAOADEESAN R.","year":"1989","unstructured":"JAOADEESAN , R. , PANANOADEN , P. , AND PINGALI , K. K. A fully abstract semantics for a functional language with logic variables . In Proceedings of the 4th IEEE Symposium on Logic in Computer Science (Asilomar, Calif. , June 5-8, 1989 ). JAOADEESAN, R., PANANOADEN, P., AND PINGALI, K. K. A fully abstract semantics for a functional language with logic variables. In Proceedings of the 4th IEEE Symposium on Logic in Computer Science (Asilomar, Calif., June 5-8, 1989)."},{"key":"e_1_2_1_16_2","volume-title":"Proceedings of the Conference on Functional Programming Languages and Computer Architecture","author":"JOHNSSON T.","year":"1985","unstructured":"JOHNSSON , T. Lambda lifting: transforming programs to recursive equations . In Proceedings of the Conference on Functional Programming Languages and Computer Architecture ( Nancy, France , Sept. 1985 ). Springer-Verlag LNCS 201, New York, 1985. JOHNSSON, T. Lambda lifting: transforming programs to recursive equations. In Proceedings of the Conference on Functional Programming Languages and Computer Architecture (Nancy, France, Sept. 1985). Springer-Verlag LNCS 201, New York, 1985."},{"key":"e_1_2_1_17_2","volume-title":"of Computer Science","author":"KELLER R. M.","year":"1983","unstructured":"KELLER , R. M. FEL (function equation language) programmer's guide. Tech. Rep., AMPS Tech. Memo. 7, Dept. of Computer Science , University of Utah , Salt Lake City, April 1983 . KELLER, R. M. FEL (function equation language) programmer's guide. Tech. Rep., AMPS Tech. Memo. 7, Dept. of Computer Science, University of Utah, Salt Lake City, April 1983."},{"key":"e_1_2_1_18_2","first-page":"207","volume-title":"Proceedings of the 8th Annual ACM Symosium on Principles of Programming Languages. ACM","author":"KUCK D. J.","year":"1981","unstructured":"KUCK , D. J. , KUHN , R. , PADUA , D. , LEASURE , B. , AND WOLFE , M. Dependence graphs and compiler optimizations . In Proceedings of the 8th Annual ACM Symosium on Principles of Programming Languages. ACM , New York , 1981 , pp. 207 - 218 . 10.1145\/567532.567555 KUCK, D. J., KUHN, R., PADUA, D., LEASURE, B., AND WOLFE, M. Dependence graphs and compiler optimizations. In Proceedings of the 8th Annual ACM Symosium on Principles of Programming Languages. ACM, New York, 1981, pp. 207-218. 10.1145\/567532.567555"},{"key":"e_1_2_1_19_2","first-page":"266","volume-title":"Proceedings of the 12th Annual ACM Symposium on Principles of Programming Languages. ACM","author":"LINDSTROM G.","year":"1985","unstructured":"LINDSTROM , G. Functional programming and the logic variable . In Proceedings of the 12th Annual ACM Symposium on Principles of Programming Languages. ACM , New York , 1985 , pp. 266 - 280 . 10.1145\/318593.318657 LINDSTROM, G. Functional programming and the logic variable. In Proceedings of the 12th Annual ACM Symposium on Principles of Programming Languages. ACM, New York, 1985, pp. 266-280. 10.1145\/318593.318657"},{"key":"e_1_2_1_20_2","volume-title":"Massachusetts Institute of Technology","author":"NIKHIL R.S.","year":"1988","unstructured":"NIKHIL , R.S. Id (version 88.1) reference manual. Tech. Rep. CSG Memo 284, MIT Lab. for Computer Science , Massachusetts Institute of Technology , Cambridge , Aug. 1988 . NIKHIL, R.S. Id (version 88.1) reference manual. Tech. Rep. CSG Memo 284, MIT Lab. for Computer Science, Massachusetts Institute of Technology, Cambridge, Aug. 1988."},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/7902.7904"},{"key":"e_1_2_1_23_2","volume-title":"The Implementation of Functional Programming Languages","author":"PEYTON JONES S. L.","year":"1987","unstructured":"PEYTON JONES , S. L. The Implementation of Functional Programming Languages . Prentice Hall , Englewood Cliffs, N.J. , 1987 . PEYTON JONES, S. L. The Implementation of Functional Programming Languages. Prentice Hall, Englewood Cliffs, N.J., 1987."},{"key":"e_1_2_1_24_2","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1007\/3-540-50517-2_92","volume-title":"Proceedings of the Conference on Foundations of Software Technology and Theoretical Computer Science. Springer-Verlag LNCS 338","author":"PINGALI K. K.","year":"1988","unstructured":"PINGALI , K. K. , AND EKANADHAM , K. Accumulators : New logic variable abstractions for functional languages . In Proceedings of the Conference on Foundations of Software Technology and Theoretical Computer Science. Springer-Verlag LNCS 338 , New York , 1988 , pp. 377 - 399 . PINGALI, K. K., AND EKANADHAM, K. Accumulators: New logic variable abstractions for functional languages. In Proceedings of the Conference on Foundations of Software Technology and Theoretical Computer Science. Springer-Verlag LNCS 338, New York, 1988, pp. 377-399."},{"key":"e_1_2_1_27_2","first-page":"328","volume-title":"Proceedings of the Workshop on Graph Reduction (Santa Fe, N. Mex.","author":"WADLER P.","year":"1986","unstructured":"WADLER , P. A new array operation for functional languages . In Proceedings of the Workshop on Graph Reduction (Santa Fe, N. Mex. Sept. 1986 ). Springer-Verlag LNCS 279, New York , 1986, pp. 328 - 335 . WADLER, P. A new array operation for functional languages. In Proceedings of the Workshop on Graph Reduction (Santa Fe, N. Mex. Sept. 1986). Springer-Verlag LNCS 279, New York, 1986, pp. 328-335."},{"key":"e_1_2_1_28_2","first-page":"45","volume-title":"Proceedings of the 1984 ACM Con{erence on Lisp and Functional Programming","author":"WADLER P.","year":"1984","unstructured":"WADLER , P. Listlessness is better than laziness: Lazy evaluation and garbage collection at compile time . In Proceedings of the 1984 ACM Con{erence on Lisp and Functional Programming ( Austin, Tex. , Aug. 1984 ), pp. 45 - 52 . 10.1145\/800055.802020 WADLER, P. Listlessness is better than laziness: Lazy evaluation and garbage collection at compile time. In Proceedings of the 1984 ACM Con{erence on Lisp and Functional Programming (Austin, Tex., Aug. 1984), pp. 45-52. 10.1145\/800055.802020"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/69558.69562","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/69558.69562","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:38:00Z","timestamp":1750282680000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/69558.69562"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,10]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1989,10]]}},"alternative-id":["10.1145\/69558.69562"],"URL":"https:\/\/doi.org\/10.1145\/69558.69562","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"value":"0164-0925","type":"print"},{"value":"1558-4593","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,10]]},"assertion":[{"value":"1989-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}