{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T01:55:36Z","timestamp":1773194136852,"version":"3.50.1"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2023,6,6]],"date-time":"2023-06-06T00:00:00Z","timestamp":1686009600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["CCF-2143061 and CCF-2216964"],"award-info":[{"award-number":["CCF-2143061 and CCF-2216964"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2023,6,6]]},"abstract":"<jats:p>We introduce indexed streams, a formal operational model and intermediate representation that describes the fused execution of a contraction language that encompasses both sparse tensor algebra and relational algebra. We prove that the indexed stream model is correct with respect to a functional semantics. We also develop a compiler for contraction expressions that uses indexed streams as an intermediate representation. The compiler is only 540 lines of code, but we show that its performance can match both the TACO compiler for sparse tensor algebra and the SQLite and DuckDB query processing libraries for relational algebra.<\/jats:p>","DOI":"10.1145\/3591268","type":"journal-article","created":{"date-parts":[[2023,6,6]],"date-time":"2023-06-06T20:06:24Z","timestamp":1686081984000},"page":"1169-1193","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Indexed Streams: A Formal Intermediate Representation for Fused Contraction Programs"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-8484-982X","authenticated-orcid":false,"given":"Scott","family":"Kovach","sequence":"first","affiliation":[{"name":"Stanford University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-4424-2001","authenticated-orcid":false,"given":"Praneeth","family":"Kolichala","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2090-9735","authenticated-orcid":false,"given":"Tiancheng","family":"Gu","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2267-903X","authenticated-orcid":false,"given":"Fredrik","family":"Kjolstad","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00048"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129246"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523442"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.825794"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/320455.320457"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3544559"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/865063"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/232629.232650"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-04936-6_5"},{"key":"e_1_2_1_11_1","volume-title":"Eighth International Symposium on Languages for Intentional Programming, M. A. Orgun and E. A. Ashcroft (Eds.) (ISLIP \u201995)","author":"Caspi Paul","year":"1995","unstructured":"Paul Caspi and Marc Pouzet . 1995 . A Functional Extension to Lustre . In Eighth International Symposium on Languages for Intentional Programming, M. A. Orgun and E. A. Ashcroft (Eds.) (ISLIP \u201995) . World Scientific, Sydney, Australia. Paul Caspi and Marc Pouzet. 1995. A Functional Extension to Lustre. In Eighth International Symposium on Languages for Intentional Programming, M. A. Orgun and E. A. Ashcroft (Eds.) (ISLIP \u201995). World Scientific, Sydney, Australia."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 2007 Workshop on Declarative Aspects of Multicore Programming (DAMP \u201907)","author":"Chakravarty Manuel MT","year":"2007","unstructured":"Manuel MT Chakravarty , Roman Leshchinskiy , Simon Peyton Jones , Gabriele Keller , and Simon Marlow . 2007 . Data parallel Haskell: a status report . In Proceedings of the 2007 Workshop on Declarative Aspects of Multicore Programming (DAMP \u201907) . 10\u201318. Manuel MT Chakravarty, Roman Leshchinskiy, Simon Peyton Jones, Gabriele Keller, and Simon Marlow. 2007. Data parallel Haskell: a status report. In Proceedings of the 2007 Workshop on Declarative Aspects of Multicore Programming (DAMP \u201907). 10\u201318."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276493"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1176887.1176899"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1291220.1291199"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_2_1_18_1","unstructured":"Conal Elliott. 2019. Generalized Convolution and Efficient Language Recognition. arXiv:1903.10677. \t\t\t\t  Conal Elliott. 2019. Generalized Convolution and Efficient Language Recognition. arXiv:1903.10677."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.97300"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/512976.512998"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1499949.1500029"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062354"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485505"},{"key":"e_1_2_1_25_1","unstructured":"Richard D Hipp. 2020. SQLite. https:\/\/www.sqlite.org\/index.html \t\t\t\t  Richard D Hipp. 2020. SQLite. https:\/\/www.sqlite.org\/index.html"},{"key":"e_1_2_1_26_1","unstructured":"2009. Intel Math Kernel Library: Reference Manual. \t\t\t\t  2009. Intel Math Kernel Library: Reference Manual."},{"key":"e_1_2_1_27_1","volume-title":"Haskell 98 language and libraries: the revised report","author":"Jones Simon Peyton","unstructured":"Simon Peyton Jones . 2003. Haskell 98 language and libraries: the revised report . Cambridge University Press . Simon Peyton Jones. 2003. Haskell 98 language and libraries: the revised report. Cambridge University Press."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767867"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3275366.3284966"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3093333.3009880"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2019.8661185"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133901"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.7809339"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498717"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2013.6670338"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.25080\/Majora-92bf1922-00a"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151113.3151114"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/268946.268953"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21401-6_26"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-79876-5_37"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_2_1_44_1","unstructured":"Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1999. The PageRank citation ranking: Bringing order to the web.. Stanford InfoLab. \t\t\t\t  Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1999. The PageRank citation ranking: Bringing order to the web.. Stanford InfoLab."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320212"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185528"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3324961"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428226"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796818000102"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3122948.3122949"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3527333"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2015.27"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2017.7863730"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45937-5_14"},{"key":"e_1_2_1_55_1","doi-asserted-by":"crossref","unstructured":"Ruiqin Tian Luanzheng Guo Jiajia Li Bin Ren and Gokcen Kestor. 2021. A High-Performance Sparse Tensor Algebra Compiler in Multi-Level IR. arXiv:2102.05187. \t\t\t\t  Ruiqin Tian Luanzheng Guo Jiajia Li Bin Ren and Gokcen Kestor. 2021. A High-Performance Sparse Tensor Algebra Compiler in Multi-Level IR. arXiv:2102.05187.","DOI":"10.1109\/LLVMHPC54804.2021.00009"},{"key":"e_1_2_1_56_1","volume-title":"TPC Benchmark H Standard Specification","author":"Transaction Processing Performance Council","unstructured":"Transaction Processing Performance Council . TPCH. 2022. TPC Benchmark H Standard Specification . Transaction Processing Performance Council . https:\/\/www.tpc.org\/tpch\/ Transaction Processing Performance Council. TPCH. 2022. TPC Benchmark H Standard Specification. Transaction Processing Performance Council. https:\/\/www.tpc.org\/tpch\/"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/icdt.2014.13"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457399"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3591268","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3591268","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:20Z","timestamp":1750178840000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3591268"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,6]]},"references-count":58,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2023,6,6]]}},"alternative-id":["10.1145\/3591268"],"URL":"https:\/\/doi.org\/10.1145\/3591268","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,6]]},"assertion":[{"value":"2023-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}