{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T23:32:53Z","timestamp":1782948773258,"version":"3.54.5"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2021,8,19]],"date-time":"2021-08-19T00:00:00Z","timestamp":1629331200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1725672,CCF-1725679,CCF-1919197"],"award-info":[{"award-number":["CCF-1725672,CCF-1725679,CCF-1919197"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/T013516\/1"],"award-info":[{"award-number":["EP\/T013516\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2021,8,22]]},"abstract":"<jats:p>Recent work showed that compiling functional programs to use dense, serialized memory representations for recursive algebraic datatypes can yield significant constant-factor speedups for sequential programs. But serializing data in a maximally dense format consequently serializes the processing of that data, yielding a tension between density and parallelism. This paper shows that a disciplined, practical compromise is possible. We present Parallel Gibbon, a compiler that obtains the benefits of dense data formats and parallelism. We formalize the semantics of the parallel location calculus underpinning this novel implementation strategy, and show that it is type-safe. Parallel Gibbon exceeds the parallel performance of existing compilers for purely functional programs that use recursive algebraic datatypes, including, notably, abstract-syntax-tree traversals as in compilers.<\/jats:p>","DOI":"10.1145\/3473596","type":"journal-article","created":{"date-parts":[[2021,8,19]],"date-time":"2021-08-19T10:44:29Z","timestamp":1629369869000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Efficient tree-traversals: reconciling parallelism and dense data representations"],"prefix":"10.1145","volume":"5","author":[{"given":"Chaitanya","family":"Koparkar","sequence":"first","affiliation":[{"name":"Indiana University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mike","family":"Rainey","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Vollmer","sequence":"additional","affiliation":[{"name":"University of Kent, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6827-345X","authenticated-orcid":false,"given":"Milind","family":"Kulkarni","sequence":"additional","affiliation":[{"name":"Purdue University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ryan R.","family":"Newton","sequence":"additional","affiliation":[{"name":"Purdue University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,8,19]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Mart\u00edn Abadi Ashish Agarwal Paul Barham Eugene Brevdo Zhifeng Chen Craig Citro Greg S. Corrado Andy Davis Jeffrey Dean Matthieu Devin Sanjay Ghemawat Ian Goodfellow Andrew Harp Geoffrey Irving Michael Isard Yangqing Jia Rafal Jozefowicz Lukasz Kaiser Manjunath Kudlur Josh Levenberg Dan Man\u00e9 Rajat Monga Sherry Moore Derek Murray Chris Olah Mike Schuster Jonathon Shlens Benoit Steiner Ilya Sutskever Kunal Talwar Paul Tucker Vincent Vanhoucke Vijay Vasudevan Fernanda Vi\u00e9gas Oriol Vinyals Pete Warden Martin Wattenberg Martin Wicke Yuan Yu and Xiaoqiang Zheng. 2015. TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems. http:\/\/tensorflow.org\/ Software available from tensorflow.org.  Mart\u00edn Abadi Ashish Agarwal Paul Barham Eugene Brevdo Zhifeng Chen Craig Citro Greg S. Corrado Andy Davis Jeffrey Dean Matthieu Devin Sanjay Ghemawat Ian Goodfellow Andrew Harp Geoffrey Irving Michael Isard Yangqing Jia Rafal Jozefowicz Lukasz Kaiser Manjunath Kudlur Josh Levenberg Dan Man\u00e9 Rajat Monga Sherry Moore Derek Murray Chris Olah Mike Schuster Jonathon Shlens Benoit Steiner Ilya Sutskever Kunal Talwar Paul Tucker Vincent Vanhoucke Vijay Vasudevan Fernanda Vi\u00e9gas Oriol Vinyals Pete Warden Martin Wattenberg Martin Wicke Yuan Yu and Xiaoqiang Zheng. 2015. TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems. http:\/\/tensorflow.org\/ Software available from tensorflow.org."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293883.3295725"},{"key":"e_1_2_2_3_1","volume-title":"Heartbeat Scheduling: Provable Efficiency for Nested Parallelism","author":"Acar Umut A","year":"2018","unstructured":"Umut A Acar , Arthur Chargu\u00e9raud , Adrien Guatto , Mike Rainey , and Filip Sieczkowski . 2018 . Heartbeat Scheduling: Provable Efficiency for Nested Parallelism . http:\/\/mike-rainey.site\/papers\/heartbeat.pdf Umut A Acar, Arthur Chargu\u00e9raud, Adrien Guatto, Mike Rainey, and Filip Sieczkowski. 2018. Heartbeat Scheduling: Provable Efficiency for Nested Parallelism. http:\/\/mike-rainey.site\/papers\/heartbeat.pdf"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2017.4"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/69558.69562"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442525"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158093"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/865063"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/209936.209958"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926354.1926358"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2784731.2784741"},{"key":"e_1_2_2_12_1","volume-title":"Proceedings of the Conference on High Performance Graphics (HPG \u201910)","author":"Choi Byn","unstructured":"Byn Choi , Rakesh Komuravelli , Victor Lu , Hyojin Sung , Robert L. Bocchino , Sarita V. Adve , and John C. Hart . 2010. Parallel SAH K-D Tree Construction . In Proceedings of the Conference on High Performance Graphics (HPG \u201910) . Eurographics Association, Goslar, DEU. 77\u201386. Byn Choi, Rakesh Komuravelli, Victor Lu, Hyojin Sung, Robert L. Bocchino, Sarita V. Adve, and John C. Hart. 2010. Parallel SAH K-D Tree Construction. In Proceedings of the Conference on High Performance Graphics (HPG \u201910). Eurographics Association, Goslar, DEU. 77\u201386."},{"key":"e_1_2_2_13_1","volume-title":"Robert Bruce Findler, and Matthew Flatt","author":"Felleisen Matthias","year":"2009","unstructured":"Matthias Felleisen , Robert Bruce Findler, and Matthew Flatt . 2009 . Semantics engineering with PLT Redex. Mit Press . Matthias Felleisen, Robert Bruce Findler, and Matthew Flatt. 2009. Semantics engineering with PLT Redex. Mit Press."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355745"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503223"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178494"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/4472.4478"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1291151.1291192"},{"key":"e_1_2_2_19_1","volume-title":"Flattening Trees. In Proceedings of the 4th International Euro-Par Conference on Parallel Processing (Euro-Par \u201998)","author":"Keller Gabriele","unstructured":"Gabriele Keller and Manuel M. T. Chakravarty . 1998 . Flattening Trees. In Proceedings of the 4th International Euro-Par Conference on Parallel Processing (Euro-Par \u201998) . Springer-Verlag, Berlin, Heidelberg. 709\u2013719. isbn:3540649522 Gabriele Keller and Manuel M. T. Chakravarty. 1998. Flattening Trees. In Proceedings of the 4th International Euro-Par Conference on Parallel Processing (Euro-Par \u201998). Springer-Verlag, Berlin, Heidelberg. 709\u2013719. isbn:3540649522"},{"key":"e_1_2_2_20_1","volume-title":"Newton","author":"Koparkar Chaitanya","year":"2021","unstructured":"Chaitanya Koparkar , Mike Rainey , Michael Vollmer , Milind Kulkarni , and Ryan R . Newton . 2021 . Efficient Tree-Traversals: Reconciling Parallelism and Dense Data Representations . arxiv:2107.00522. Chaitanya Koparkar, Mike Rainey, Michael Vollmer, Milind Kulkarni, and Ryan R. Newton. 2021. Efficient Tree-Traversals: Reconciling Parallelism and Dense Data Representations. arxiv:2107.00522."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594312"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/337449.337465"},{"key":"e_1_2_2_23_1","unstructured":"Xavier Leroy Damien Doligez Alain Frisch Jacques Garrigue Didier R\u00e9my and J\u00e9r\u00f4me Vouillon. 2020. The OCaml system release. Feb https:\/\/ocaml.org\/releases\/4.10\/htmlman\/index.html  Xavier Leroy Damien Doligez Alain Frisch Jacques Garrigue Didier R\u00e9my and J\u00e9r\u00f4me Vouillon. 2020. The OCaml system release. Feb https:\/\/ocaml.org\/releases\/4.10\/htmlman\/index.html"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(90)90231-O"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375634.1375637"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2096148.2034685"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1596550.1596563"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/99.660313"},{"key":"e_1_2_2_29_1","unstructured":"Leo A. Meyerovich Todd Mytkowicz and Wolfram Schulte. 2011. Data Parallel Programming for Irregular Tree Computations. In HotPAR. https:\/\/www.microsoft.com\/en-us\/research\/publication\/data- parallel-programming-for-irregular-tree-computations\/  Leo A. Meyerovich Todd Mytkowicz and Wolfram Schulte. 2011. Data Parallel Programming for Irregular Tree Computations. In HotPAR. https:\/\/www.microsoft.com\/en-us\/research\/publication\/data- parallel-programming-for-irregular-tree-computations\/"},{"key":"e_1_2_2_30_1","volume-title":"The Definition of Standard ML","author":"Milner Robin","year":"1814","unstructured":"Robin Milner , Mads Tofte , and David Macqueen . 1997. The Definition of Standard ML . MIT Press, Cambridge, MA , USA. isbn:026263 1814 Robin Milner, Mads Tofte, and David Macqueen. 1997. The Definition of Standard ML. MIT Press, Cambridge, MA, USA. isbn:0262631814"},{"key":"e_1_2_2_31_1","volume-title":"PyTorch: An Imperative Style","author":"Paszke Adam","unstructured":"Adam Paszke , Sam Gross , Francisco Massa , Adam Lerer , James Bradbury , Gregory Chanan , Trevor Killeen , Zeming Lin , Natalia Gimelshein , and Luca Antiga . 2019. PyTorch: An Imperative Style , High-Performance Deep Learning Library . In Advances in Neural Information Processing Systems. 8026\u20138037. Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, and Luca Antiga. 2019. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In Advances in Neural Information Processing Systems. 8026\u20138037."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3022670.2951935"},{"key":"e_1_2_2_33_1","doi-asserted-by":"crossref","unstructured":"Mike Rainey Kyle A Hale Ryan Newton Nikos Hardavellas Simone Campanoni Peter Dinda and Umut Acar. 2021. Task Parallel Assembly Language for Uncompromising Parallelism.  Mike Rainey Kyle A Hale Ryan Newton Nikos Hardavellas Simone Campanoni Peter Dinda and Umut Acar. 2021. Task Parallel Assembly Language for Uncompromising Parallelism.","DOI":"10.1145\/3453483.3460969"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1596550.1596588"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1016850.1016878"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312018"},{"key":"e_1_2_2_37_1","unstructured":"Jeremy Siek Carl Factora Andre Kuhlenschmidt Ryan Newton Scott Ryan Cameron Swords Michael Vitousek and Michael Vollmer. 2020. Essentials Of Compilation: An Incremental Approach. https:\/\/iucompilercourse.github.io\/IU-P423-P523-E313-E513-Fall-2020\/  Jeremy Siek Carl Factora Andre Kuhlenschmidt Ryan Newton Scott Ryan Cameron Swords Michael Vitousek and Michael Vollmer. 2020. Essentials Of Compilation: An Incremental Approach. https:\/\/iucompilercourse.github.io\/IU-P423-P523-E313-E513-Fall-2020\/"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3408995"},{"key":"e_1_2_2_39_1","doi-asserted-by":"crossref","unstructured":"KC Sivaramakrishnan Stephen Dolan Leo White Sadiq Jaffer Tom Kelly Anmol Sahoo Sudha Parimala Atul Dhiman and Anil Madhavapeddy. 2020. Retrofitting Parallelism onto OCaml. arXiv preprint arXiv:2004.11663.  KC Sivaramakrishnan Stephen Dolan Leo White Sadiq Jaffer Tom Kelly Anmol Sahoo Sudha Parimala Atul Dhiman and Anil Madhavapeddy. 2020. Retrofitting Parallelism onto OCaml. arXiv preprint arXiv:2004.11663.","DOI":"10.1145\/3408995"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:LISP.0000029446.78563.a4"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.2613"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951944"},{"key":"e_1_2_2_43_1","unstructured":"Kenton Varda. 2015. Cap\u2019n Proto. https:\/\/capnproto.org\/  Kenton Varda. 2015. Cap\u2019n Proto. https:\/\/capnproto.org\/"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314631"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2017.26"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371115"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2784731.2784735"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3473596","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3473596","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3473596","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:16Z","timestamp":1750195696000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3473596"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,19]]},"references-count":47,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2021,8,22]]}},"alternative-id":["10.1145\/3473596"],"URL":"https:\/\/doi.org\/10.1145\/3473596","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,19]]},"assertion":[{"value":"2021-08-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}