{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T07:53:19Z","timestamp":1781855599269,"version":"3.54.5"},"reference-count":142,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T00:00:00Z","timestamp":1609718400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["CCF-1408940, CCF-1901381"],"award-info":[{"award-number":["CCF-1408940, CCF-1901381"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2021,1,4]]},"abstract":"<jats:p>Because of its many desirable properties, such as its ability to control effects and thus potentially disastrous race conditions, functional programming offers a viable approach to programming modern multicore computers. Over the past decade several parallel functional languages, typically based on dialects of ML and Haskell, have been developed. These languages, however, have traditionally underperformed procedural languages (such as C and Java). The primary reason for this is their hunger for memory, which only grows with parallelism, causing traditional memory management techniques to buckle under increased demand for memory. Recent work opened a new angle of attack on this problem by identifying a memory property of determinacy-race-free parallel programs, called disentanglement, which limits the knowledge of concurrent computations about each other\u2019s memory allocations. The work has showed some promise in delivering good time scalability.<\/jats:p>\n                  <jats:p>\n                    In this paper, we present provably space-efficient automatic memory management techniques for determinacy-race-free functional parallel programs, allowing both pure and imperative programs where memory may be destructively updated. We prove that for a program with sequential live memory of\n                    <jats:italic toggle=\"yes\">R<\/jats:italic>\n                    <jats:sup>*<\/jats:sup>\n                    , any\n                    <jats:italic toggle=\"yes\">P<\/jats:italic>\n                    -processor garbage-collected parallel run requires at most\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">R<\/jats:italic>\n                    <jats:sup>*<\/jats:sup>\n                    \u00b7\n                    <jats:italic toggle=\"yes\">P<\/jats:italic>\n                    ) memory. We also prove a work bound of\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">W<\/jats:italic>\n                    +\n                    <jats:italic toggle=\"yes\">R<\/jats:italic>\n                    <jats:sup>*<\/jats:sup>\n                    <jats:italic toggle=\"yes\">P<\/jats:italic>\n                    ) for\n                    <jats:italic toggle=\"yes\">P<\/jats:italic>\n                    -processor executions, accounting also for the cost of garbage collection. To achieve these results, we integrate thread scheduling with memory management. The idea is to coordinate memory allocation and garbage collection with thread scheduling decisions so that each processor can allocate memory without synchronization and independently collect a portion of memory by consulting a collection policy, which we formulate. The collection policy is fully distributed and does not require communicating with other processors. We show that the approach is practical by implementing it as an extension to the MPL compiler for Parallel ML. Our experimental results confirm our theoretical bounds and show that the techniques perform and scale well.\n                  <\/jats:p>","DOI":"10.1145\/3434299","type":"journal-article","created":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T12:34:24Z","timestamp":1609763664000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Provably space-efficient parallel functional programming"],"prefix":"10.1145","volume":"5","author":[{"given":"Jatin","family":"Arora","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sam","family":"Westrick","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Umut A.","family":"Acar","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,1,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2011. Finagle: A Protocol-Agnostic RPC System. https:\/\/twitter.github.io\/finagle\/."},{"key":"e_1_2_1_2_1","unstructured":"2015. Folly: Facebook Open-source Library. https:\/\/github.com\/facebook\/folly."},{"key":"e_1_2_1_3_1","unstructured":"Umut A. Acar Guy Blelloch Matthew Fluet Stefan K. Muller and Ram Raghunathan. 2015. Coupling Memory and Computation for Locality Management. In Summit on Advances in Programming Languages (SNAPL)."},{"key":"e_1_2_1_4_1","volume-title":"Blumofe","author":"Acar Umut A.","year":"2002","unstructured":"Umut A. Acar, Guy E. Blelloch, and Robert D. Blumofe. 2002. The Data Locality of Work Stealing. Theory of Computing Systems 35, 3 ( 2002 ), 321-347."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192391"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442538"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Umut A. Acar Arthur Chargu\u00e9raud and Mike Rainey. 2016a. Oracle-guided scheduling for controlling granularity in implicitly parallel languages. Journal of Functional Programming (JFP) 26 ( 2016 ) e23.","DOI":"10.1017\/S0956796816000101"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951946"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Sarita V. Adve. 2010. Data races are evil with no exceptions: technical perspective. Commun. ACM 53 11 ( 2010 ) 84.","DOI":"10.1145\/1839676.1839697"},{"key":"e_1_2_1_10_1","first-page":"229","volume-title":"SPAA 2007: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures","author":"Agarwal Shivali","year":"2007","unstructured":"Shivali Agarwal, Rajkishore Barik, Dan Bonachea, Vivek Sarkar, R. K. Shyamasundar, and Katherine A. Yelick. 2007. Deadlock-free scheduling of X10 computations with bounded resources. In SPAA 2007: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures, San Diego, California, USA, June 9-11, 2007. 229-240."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 1987 International Conference on Parallel Processing. 721-727","author":"Allen T. R.","unstructured":"T. R. Allen and D. A. Padua. 1987. Debugging Fortran on a Shared Memory Machine. In Proceedings of the 1987 International Conference on Parallel Processing. 721-727."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806651.1806655"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Andrew W. Appel. 1989. Simple Generational Garbage Collection and Fast Allocation. Software Prac. Experience 19 2 ( 1989 ) 171-183. http:\/\/www.cs.princeton.edu\/fac\/~appel\/papers\/143.ps","DOI":"10.1002\/spe.4380190206"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1017\/S095679680000157X"},{"key":"e_1_2_1_16_1","first-page":"119","volume-title":"Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures","author":"Arora Nimar S.","unstructured":"Nimar S. Arora, Robert D. Blumofe, and C. Greg Plaxton. 1998. Thread scheduling for multiprogrammed multiprocessors. In Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures (Puerto Vallarta, Mexico) (SPAA '98). ACM Press, 119-129."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Nimar S. Arora Robert D. Blumofe and C. Greg Plaxton. 2001. Thread Scheduling for Multiprogrammed Multiprocessors. Theory of Computing Systems 34 2 ( 2001 ) 115-144.","DOI":"10.1007\/s002240011004"},{"key":"e_1_2_1_18_1","first-page":"4","article-title":"I-structures: Data Structures for Parallel Computing","volume":"11","author":"Nikhil Rishiyur S.","year":"1989","unstructured":"Arvind, Rishiyur S. Nikhil, and Keshav K. Pingali. 1989. I-structures: Data Structures for Parallel Computing. ACM Trans. Program. Lang. Syst. 11, 4 (Oct. 1989 ), 598-632.","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 2011 ACM SIGPLAN workshop on Memory Systems Performance and Correctness (MSPC). 51-57","author":"Auhagen Sven","unstructured":"Sven Auhagen, Lars Bergstrom, Matthew Fluet, and John H. Reppy. 2011. Garbage collection for multicore NUMA machines. In Proceedings of the 2011 ACM SIGPLAN workshop on Memory Systems Performance and Correctness (MSPC). 51-57."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1275808.1276390"},{"key":"e_1_2_1_21_1","volume-title":"Conference Record of the Thirtieth Annual ACM Symposium on Principles of Programming Languages (ACM SIGPLAN Notices). ACM Press","author":"Bacon David F.","unstructured":"David F. Bacon, Perry Cheng, and V.T. Rajan. 2003. A Real-Time Garbage Collecor with Low Overhead and Consistent Utilization. In Conference Record of the Thirtieth Annual ACM Symposium on Principles of Programming Languages (ACM SIGPLAN Notices). ACM Press, New Orleans, LA."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Ales Bizjak Daniel Gratzer Robbert Krebbers and Lars Birkedal. 2019. Iron: managing obligations in higher-order concurrent separation logic. PACMPL 3 POPL ( 2019 ) 65 : 1-65 : 30.","DOI":"10.1145\/3290378"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/224164.224210"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Guy E. Blelloch. 1996. Programming Parallel Algorithms. Commun. ACM 39 3 ( 1996 ) 85-97.","DOI":"10.1145\/227234.227246"},{"key":"e_1_2_1_26_1","volume-title":"Blelloch and Perry Cheng","author":"Guy","year":"1999","unstructured":"Guy E. Blelloch and Perry Cheng. 1999. On Bounding Time and Space for Multiprocessor Garbage Collection. In Proceedings of SIGPLAN'99 Conference on Programming Languages Design and Implementation (ACM SIGPLAN Notices ). ACM Press, Atlanta, 104-117."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Guy E. Blelloch Jeremy T. Fineman Phillip B. Gibbons and Julian Shun. 2012. Internally deterministic parallel algorithms can be fast. In PPoPP ' 12 (New Orleans Louisiana USA). 181-192.","DOI":"10.1145\/2145816.2145840"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989553"},{"key":"e_1_2_1_29_1","volume-title":"Gibbons","author":"Blelloch Guy E.","year":"2004","unstructured":"Guy E. Blelloch and Phillip B. Gibbons. 2004. Efectively sharing a cache among threads. In SPAA (Barcelona, Spain)."},{"key":"e_1_2_1_30_1","volume-title":"Provably eficient scheduling for languages with fine-grained parallelism. J. ACM 46 (","author":"Blelloch Guy E.","year":"1999","unstructured":"Guy E. Blelloch, Phillip B. Gibbons, and Yossi Matias. 1999. Provably eficient scheduling for languages with fine-grained parallelism. J. ACM 46 ( March 1999 ), 281-321. Issue 2."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the Ninth Annual ACM Symposium on Parallel Algorithms and Architectures","author":"Blelloch Guy E.","unstructured":"Guy E. Blelloch, Phillip B. Gibbons, Yossi Matias, and Girija J. Narlikar. 1997. Space-eficient Scheduling of Parallelism with Synchronization Variables. In Proceedings of the Ninth Annual ACM Symposium on Parallel Algorithms and Architectures (Newport, Rhode Island, USA) ( SPAA '97). 12-23."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810519"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 1st ACM SIGPLAN International Conference on Functional Programming. ACM, 213-225","author":"Guy","unstructured":"Guy E. Blelloch and John Greiner. 1996. A provable time and space eficient implementation of NESL. In Proceedings of the 1st ACM SIGPLAN International Conference on Functional Programming. ACM, 213-225."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1994.1038"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1145\/209936.209958","volume-title":"Proceedings of the Fifth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","author":"Blumofe Robert D.","year":"1995","unstructured":"Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, and Yuli Zhou. 1995. Cilk: An Eficient Multithreaded Runtime System. In Proceedings of the Fifth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. Santa Barbara, California, 207-216."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0107"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793259471"},{"key":"e_1_2_1_38_1","volume-title":"Leiserson","author":"Blumofe Robert D.","year":"1999","unstructured":"Robert D. Blumofe and Charles E. Leiserson. 1999. Scheduling multithreaded computations by work stealing. J. ACM 46 ( Sept. 1999 ), 720-748. Issue 5."},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Robert L. Bocchino Stephen Heumann Nima Honarmand Sarita V. Adve Vikram S. Adve Adam Welc and Tatiana Shpeisman. 2011. Safe nondeterminism in a deterministic-by-default parallel language. In ACM POPL.","DOI":"10.1145\/1926385.1926447"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1640089.1640097"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855591.1855595"},{"key":"e_1_2_1_42_1","volume-title":"3rd USENIX Workshop on Hot Topics in Parallelism, HotPar'11","author":"Boehm Hans-Juergen","year":"2011","unstructured":"Hans-Juergen Boehm. 2011. How to Miscompile Programs with \"Benign\" Data Races. In 3rd USENIX Workshop on Hot Topics in Parallelism, HotPar'11, Berkeley, CA, USA, May 26-27, 2011."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"e_1_2_1_44_1","series-title":"SIAM SDM.","volume-title":"R-MAT: A recursive model for graph mining","author":"Chakrabarti Deepayan","unstructured":"Deepayan Chakrabarti, Yiping Zhan, and Christos Faloutsos. 2004. R-MAT: A recursive model for graph mining. In SIAM SDM."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248648.1248652"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094852"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 10th ACM Symposium on Parallel Algorithms and Architectures (SPAA '98)","author":"Cheng Guang-Ien","unstructured":"Guang-Ien Cheng, Mingdong Feng, Charles E. Leiserson, Keith H. Randall, and Andrew F. Stark. 1998. Detecting data races in Cilk programs that use locks. In Proceedings of the 10th ACM Symposium on Parallel Algorithms and Architectures (SPAA '98)."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378823"},{"key":"e_1_2_1_49_1","first-page":"207","volume-title":"Proc. 20th ACM Symposium on Parallelism in Algorithms and Architectures","author":"Chowdhury Rezaul Alam","year":"2008","unstructured":"Rezaul Alam Chowdhury and Vijaya Ramachandran. 2008. Cache-eficient dynamic programming algorithms for multicores. In Proc. 20th ACM Symposium on Parallelism in Algorithms and Architectures (Munich, Germany). ACM, New York, NY, USA, 207-216."},{"key":"e_1_2_1_50_1","unstructured":"Intel Corp. 2017. Knights landing (KNL): 2nd Generation Intel Xeon Phi processor. In Intel Xeon Processor E7 v4 Family Specification. https:\/\/ark.intel.com\/products\/series\/93797\/ Intel-Xeon-Processor-E7-v4-Family."},{"key":"e_1_2_1_51_1","volume-title":"Unobtrusive Garbage Collection for Multiprocessor Systems. In Conference Record of the Twenty-first Annual ACM Symposium on Principles of Programming Languages (ACM SIGPLAN Notices). ACM Press","author":"Doligez Damien","year":"1994","unstructured":"Damien Doligez and Georges Gonthier. 1994. Portable, Unobtrusive Garbage Collection for Multiprocessor Systems. In Conference Record of the Twenty-first Annual ACM Symposium on Principles of Programming Languages (ACM SIGPLAN Notices). ACM Press, Portland, OR. ftp:\/\/ftp.inria.fr\/INRIA\/Projects\/para\/doligez\/DoligezGonthier94.ps.gz"},{"key":"e_1_2_1_52_1","volume-title":"Conference Record of the Twentieth Annual ACM Symposium on Principles of Programming Languages (ACM SIGPLAN Notices). ACM Press, 113-123","author":"Doligez Damien","year":"1993","unstructured":"Damien Doligez and Xavier Leroy. 1993. A Concurrent Generational Garbage Collector for a Multi-Threaded Implementation of ML. In Conference Record of the Twentieth Annual ACM Symposium on Principles of Programming Languages (ACM SIGPLAN Notices). ACM Press, 113-123. file:\/\/ftp.inria.fr\/INRIA\/Projects\/cristal\/Xavier.Leroy\/publications\/concurrentgc.ps.gz"},{"key":"e_1_2_1_53_1","first-page":"76","volume-title":"Thread-Local Heaps for Java. In ISMM'02 Proceedings of the Third International Symposium on Memory Management (ACM SIGPLAN Notices), David Detlefs (Ed.). ACM Press","author":"Domani Tamar","year":"2002","unstructured":"Tamar Domani, Elliot K. Kolodner, Ethan Lewis, Erez Petrank, and Dafna Sheinwald. 2002. Thread-Local Heaps for Java. In ISMM'02 Proceedings of the Third International Symposium on Memory Management (ACM SIGPLAN Notices), David Detlefs (Ed.). ACM Press, Berlin, 76-87. http:\/\/www.cs.technion.ac.il\/~erez\/publications.html"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.21127"},{"key":"e_1_2_1_55_1","volume-title":"Padua","author":"Emrath Perry A.","year":"1991","unstructured":"Perry A. Emrath, Sanjoy Ghosh, and David A. Padua. 1991. Event Synchronization Analysis for Debugging Parallel Programs. In Supercomputing ' 91. 580-588."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1188455.1188543"},{"key":"e_1_2_1_57_1","volume-title":"Proceedings of the Ninth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA). 1-11","author":"Feng Mingdong","unstructured":"Mingdong Feng and Charles E. Leiserson. 1997. Eficient Detection of Determinacy Races in Cilk Programs. In Proceedings of the Ninth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA). 1-11."},{"key":"e_1_2_1_58_1","volume-title":"Leiserson","author":"Feng Mingdong","year":"1999","unstructured":"Mingdong Feng and Charles E. Leiserson. 1999. Eficient Detection of Determinacy Races in Cilk Programs. Theory of Computing Systems 32, 3 ( 1999 ), 301-326."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1543135.1542490"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1377492.1377495"},{"key":"e_1_2_1_61_1","volume-title":"Proceedings of the 15th Annual European Symposium on Programming (ESOP).","author":"Fluet Matthew","unstructured":"Matthew Fluet, Greg Morrisett, and Amal J. Ahmed. 2006. Linear Regions Are All You Need. In Proceedings of the 15th Annual European Symposium on Programming (ESOP)."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411204.1411239"},{"key":"e_1_2_1_63_1","first-page":"5","article-title":"Implicitly threaded parallelism in Manticore","volume":"20","author":"Fluet Matthew","year":"2011","unstructured":"Matthew Fluet, Mike Rainey, John Reppy, and Adam Shaw. 2011. Implicitly threaded parallelism in Manticore. Journal of Functional Programming 20, 5-6 ( 2011 ), 1-40.","journal-title":"Journal of Functional Programming"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584017"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277725"},{"key":"e_1_2_1_66_1","volume-title":"Lucassen","author":"Giford David K.","year":"1986","unstructured":"David K. Giford and John M. Lucassen. 1986. Integrating Functional and Imperative Programming. In Proceedings of the ACM Symposium on Lisp and Functional Programming (LFP). ACM Press, 22-38."},{"key":"e_1_2_1_67_1","unstructured":"Marcelo J. R. Gon\u00e7alves. 1995. Cache Performance of Programs with Intensive Heap Allocation and Generational Garbage Collection. Ph.D. Dissertation. Department of Computer Science Princeton University."},{"key":"e_1_2_1_68_1","volume-title":"Cache Performance of Fast-Allocating Programs. In Record of the 1995 Conference on Functional Programming and Computer Architecture.","author":"Marcelo J.","unstructured":"Marcelo J. R. Gon\u00e7alves and Andrew W. Appel. 1995. Cache Performance of Fast-Allocating Programs. In Record of the 1995 Conference on Functional Programming and Computer Architecture."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/512529.512563"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178494"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/800055.802017"},{"key":"e_1_2_1_72_1","volume-title":"UK","author":"Hammond Kevin","year":"2011","unstructured":"Kevin Hammond. 2011. Why Parallel Functional Programming Matters: Panel Statement. In Reliable Software Technologies-Ada-Europe 2011-16th Ada-Europe International Conference on Reliable Software Technologies, Edinburgh, UK, June 20-24, 2011. Proceedings. 201-205."},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380200104"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/2647508.2647514"},{"key":"e_1_2_1_75_1","unstructured":"Intel. 2011. Intel Threading Building Blocks. https:\/\/www.threadingbuildingblocks.org\/."},{"key":"e_1_2_1_76_1","unstructured":"Intel Corporation 2009a. Intel Cilk++ SDK Programmer's Guide. Intel Corporation. Document Number: 322581-001US."},{"key":"e_1_2_1_77_1","unstructured":"Intel Corporation 2009b. Intel(R) Threading Building Blocks. Intel Corporation. Available from http:\/\/www. threadingbuildingblocks.org\/documentation.php."},{"key":"e_1_2_1_78_1","volume-title":"The garbage collection handbook: the art of automatic memory management","author":"Jones Richard","unstructured":"Richard Jones, Antony Hosking, and Eliot Moss. 2011. The garbage collection handbook: the art of automatic memory management. Chapman & Hall\/CRC."},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","unstructured":"Ralf Jung Jacques-Henri Jourdan Robbert Krebbers and Derek Dreyer. 2018a. RustBelt: securing the foundations of the rust programming language. PACMPL 2 POPL ( 2018 ) 66 : 1-66 : 34. https:\/\/doi.org\/10.1145\/3158154 10.1145\/3158154","DOI":"10.1145\/3158154"},{"key":"e_1_2_1_80_1","doi-asserted-by":"crossref","unstructured":"Ralf Jung Robbert Krebbers Jacques-Henri Jourdan Ales Bizjak Lars Birkedal and Derek Dreyer. 2018b. Iris from the ground up: A modular foundation for higher-order concurrent separation logic. J. Funct. Program. 28 ( 2018 ) e20.","DOI":"10.1017\/S0956796818000151"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/1863543.1863582"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/169627.169724"},{"key":"e_1_2_1_83_1","volume-title":"Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation (San Diego, California, USA) ( PLDI '07). 211-222","author":"Kulkarni Milind","unstructured":"Milind Kulkarni, Keshav Pingali, Bruce Walter, Ganesh Ramanarayanan, Kavita Bala, and L. Paul Chew. 2007. Optimistic Parallelism Requires Abstractions. In Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation (San Diego, California, USA) ( PLDI '07). 211-222."},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/2502323.2502326"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594312"},{"key":"e_1_2_1_86_1","first-page":"257","volume-title":"Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (San Diego, California, USA) ( POPL '14). ACM","author":"Kuper Lindsey","unstructured":"Lindsey Kuper, Aaron Turon, Neelakantan R. Krishnaswami, and Ryan R. Newton. 2014b. Freeze After Writing: Quasideterministic Parallel Programming with LVars. In Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (San Diego, California, USA) ( POPL '14). ACM, New York, NY, USA, 257-270."},{"key":"e_1_2_1_87_1","first-page":"24","volume-title":"Proceedings of the ACM SIGPLAN'94 Conference on Programming Language Design and Implementation (PLDI)","author":"Launchbury John","year":"1994","unstructured":"John Launchbury and Simon L. Peyton Jones. 1994. Lazy Functional State Threads. In Proceedings of the ACM SIGPLAN'94 Conference on Programming Language Design and Implementation (PLDI), Orlando, Florida, USA, June 20-24, 1994. 24-35."},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/2784731.2784736"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1145\/337449.337465"},{"key":"e_1_2_1_90_1","doi-asserted-by":"crossref","unstructured":"I-Ting Angelina Lee Charles E. Leiserson Tao B. Schardl Zhunping Zhang and Jim Sukha. 2015. On-the-Fly Pipeline Parallelism. TOPC 2 3 ( 2015 ) 17 : 1-17 : 42.","DOI":"10.1145\/2809808"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1145\/1640089.1640106"},{"key":"e_1_2_1_92_1","first-page":"107","volume-title":"Proceedings of the ACM SIGPLAN Workshop on Haskell, Haskell 2007","author":"Li Peng","year":"2007","unstructured":"Peng Li, Simon Marlow, Simon L. Peyton Jones, and Andrew P. Tolmach. 2007. Lightweight concurrency primitives for GHC. In Proceedings of the ACM SIGPLAN Workshop on Haskell, Haskell 2007, Freiburg, Germany, September 30, 2007. 107-118."},{"key":"e_1_2_1_93_1","first-page":"47","volume-title":"Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (San Diego, California, USA) ( POPL '88). ACM","author":"Lucassen J. M.","unstructured":"J. M. Lucassen and D. K. Giford. 1988. Polymorphic Efect Systems. In Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (San Diego, California, USA) ( POPL '88). ACM, New York, NY, USA, 47-57."},{"key":"e_1_2_1_94_1","volume-title":"Proceedings of the 10th International Symposium on Memory Management, ISMM 2011","author":"Marlow Simon","year":"2011","unstructured":"Simon Marlow and Simon L. Peyton Jones. 2011. Multicore garbage collection with local heaps. In Proceedings of the 10th International Symposium on Memory Management, ISMM 2011, San Jose, CA, USA, June 04-05, 2011, Hans-Juergen Boehm and David F. Bacon (Eds.). ACM, 21-32."},{"key":"e_1_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1145\/125826.125861"},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386013"},{"key":"e_1_2_1_97_1","first-page":"71","volume-title":"Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016, Asilomar State Beach\/Pacific Grove, CA, USA","author":"Stefan","year":"2016","unstructured":"Stefan K. Muller and Umut A. Acar. 2016. Latency-Hiding Work Stealing: Scheduling Interacting Parallel Computations with Work Stealing. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016, Asilomar State Beach\/Pacific Grove, CA, USA, July 11-13, 2016. 71-82."},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062370"},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236790"},{"key":"e_1_2_1_100_1","volume-title":"Proceedings of the 14th ACM SIGPLAN International Conference on Functional Programming (ICFP '18)","author":"Muller Stefan K.","year":"2018","unstructured":"Stefan K. Muller, Umut A. Acar, and Robert Harper. 2018b. Types and Cost Models for Responsive Parallelism. In Proceedings of the 14th ACM SIGPLAN International Conference on Functional Programming (ICFP '18)."},{"key":"e_1_2_1_101_1","volume-title":"Blelloch","author":"Narlikar Girija J.","year":"1999","unstructured":"Girija J. Narlikar and Guy E. Blelloch. 1999. Space-Eficient Scheduling of Nested Parallelism. ACM Transactions on Programming Languages and Systems 21 ( 1999 )."},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.1145\/130616.130623"},{"key":"e_1_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.1145\/289918.289920"},{"key":"e_1_2_1_104_1","unstructured":"Atsushi Ohori Kenjiro Taura and Katsuhiro Ueno. 2018. Making SML# a General-purpose High-performance Language. Unpublished Manuscript."},{"key":"e_1_2_1_105_1","volume-title":"Version 5.0. Accessed in July","author":"MP","year":"2018","unstructured":"OpenMP 5.0 2018. OpenMP Application Programming Interface, Version 5.0. Accessed in July 2018."},{"key":"e_1_2_1_106_1","doi-asserted-by":"publisher","DOI":"10.1145\/1452044.1452048"},{"key":"e_1_2_1_107_1","volume-title":"Chakravarty","author":"Peyton Jones Simon L.","year":"2008","unstructured":"Simon L. Peyton Jones, Roman Leshchinskiy, Gabriele Keller, and Manuel M. T. Chakravarty. 2008. Harnessing the Multicores: Nested Data Parallelism in Haskell. In FSTTCS. 383-414."},{"key":"e_1_2_1_108_1","volume-title":"Proceedings of the 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Charleston, South Carolina, USA) ( POPL '93). 71-84","author":"Simon","unstructured":"Simon L. Peyton Jones and Philip Wadler. 1993. Imperative Functional Programming. In Proceedings of the 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Charleston, South Carolina, USA) ( POPL '93). 71-84."},{"key":"e_1_2_1_109_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993501"},{"key":"e_1_2_1_110_1","doi-asserted-by":"crossref","unstructured":"Filip Pizlo Erez Petrank and Bjarne Steensgaard. 2008. A study of concurrent real-time garbage collectors. ACM SIGPLAN Notices 43 6 ( 2008 ) 33-44.","DOI":"10.1145\/1379022.1375587"},{"key":"e_1_2_1_111_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951935"},{"key":"e_1_2_1_112_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254127"},{"key":"e_1_2_1_113_1","doi-asserted-by":"publisher","DOI":"10.1145\/512760.512766"},{"key":"e_1_2_1_114_1","volume-title":"Separation Logic: A Logic for Shared Mutable Data Structures. In 17th IEEE Symposium on Logic in Computer Science (LICS 2002 ), 22-25 July 2002, Copenhagen, Denmark, Proceedings. 55-74","author":"Reynolds John C.","year":"2002","unstructured":"John C. Reynolds. 2002. Separation Logic: A Logic for Shared Mutable Data Structures. In 17th IEEE Symposium on Logic in Computer Science (LICS 2002 ), 22-25 July 2002, Copenhagen, Denmark, Proceedings. 55-74."},{"key":"e_1_2_1_115_1","volume-title":"HPE shows The Machine-with 160TB of shared memory","author":"Robinson Dan","year":"2017","unstructured":"Dan Robinson. 2017. HPE shows The Machine-with 160TB of shared memory. Data Center Dynamics (May 2017 )."},{"key":"e_1_2_1_116_1","first-page":"144","article-title":"Automatic complexity analysis. In FPCA '89: Functional Programming Languages and Computer Architecture","author":"Rosendahl Mads","year":"1989","unstructured":"Mads Rosendahl. 1989. Automatic complexity analysis. In FPCA '89: Functional Programming Languages and Computer Architecture. ACM, 144-156.","journal-title":"ACM"},{"key":"e_1_2_1_117_1","doi-asserted-by":"publisher","DOI":"10.1145\/363534.363546"},{"key":"e_1_2_1_118_1","unstructured":"Rust Team. 2019. Rust Language. https:\/\/www.rust-lang.org\/"},{"key":"e_1_2_1_119_1","unstructured":"David Sands. 1990a. Calculi for Time Analysis of Functional Programs. Ph.D. Dissertation. University of London Imperial College."},{"key":"e_1_2_1_120_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-52592-0_74"},{"key":"e_1_2_1_121_1","volume-title":"Peyton Jones","author":"Sansom Patrick M.","year":"1995","unstructured":"Patrick M. Sansom and Simon L. Peyton Jones. 1995. Time and space profiling for non-strict, higher-order functional languages. In Principles of Programming Languages (San Francisco, California, United States). 355-366."},{"key":"e_1_2_1_122_1","doi-asserted-by":"crossref","unstructured":"Jacob T. Schwartz. 1975. Optimization of very high level languages (parts I and II). Computer Languages 2-3 1 ( 1975 ) 161-194 197-218.","DOI":"10.1016\/0096-0551(75)90015-6"},{"key":"e_1_2_1_123_1","first-page":"135","volume-title":"PPOPP '13","author":"Shun Julian","unstructured":"Julian Shun and Guy E. Blelloch. 2013. Ligra: a lightweight graph processing framework for shared memory. In PPOPP '13. ACM, New York, NY, USA, 135-146."},{"key":"e_1_2_1_124_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312018"},{"key":"e_1_2_1_125_1","volume-title":"Retrofitting Parallelism onto OCaml. arXiv preprint arXiv","author":"Sivaramakrishnan KC","year":"2004","unstructured":"KC Sivaramakrishnan, Stephen Dolan, Leo White, Sadiq Jafer, Tom Kelly, Anmol Sahoo, Sudha Parimala, Atul Dhiman, and Anil Madhavapeddy. 2020. Retrofitting Parallelism onto OCaml. arXiv preprint arXiv: 2004. 11663 ( 2020 )."},{"key":"e_1_2_1_126_1","doi-asserted-by":"crossref","unstructured":"K. C. Sivaramakrishnan Lukasz Ziarek and Suresh Jagannathan. 2014. MultiMLton: A multicore-aware runtime for standard ML. Journal of Functional Programming FirstView (6 2014 ) 1-62.","DOI":"10.1017\/S0956796814000161"},{"key":"e_1_2_1_127_1","doi-asserted-by":"publisher","DOI":"10.1109\/HOTCHIPS.2015.7477467"},{"key":"e_1_2_1_128_1","unstructured":"Daniel Spoonhower. 2009. Scheduling Deterministic Parallel Programs. Ph.D. Dissertation. Carnegie Mellon University. https:\/\/www.cs.cmu.edu\/~rwh\/theses\/spoonhower.pdf"},{"key":"e_1_2_1_129_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584019"},{"key":"e_1_2_1_130_1","volume-title":"Space Profiling for Parallel Functional Programs. In International Conference on Functional Programming.","author":"Spoonhower Daniel","unstructured":"Daniel Spoonhower, Guy E. Blelloch, Robert Harper, and Phillip B. Gibbons. 2008. Space Profiling for Parallel Functional Programs. In International Conference on Functional Programming."},{"key":"e_1_2_1_131_1","doi-asserted-by":"publisher","DOI":"10.1145\/174675.178068"},{"key":"e_1_2_1_132_1","doi-asserted-by":"publisher","DOI":"10.1145\/96709.96731"},{"key":"e_1_2_1_133_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353445.1353449"},{"key":"e_1_2_1_134_1","doi-asserted-by":"crossref","unstructured":"Mads Tofte and Jean-Pierre Talpin. 1997. Region-Based Memory Management. Information and Computation (Feb. 1997 ). http:\/\/www.diku.dk\/research-groups\/topps\/activities\/kit2\/infocomp97.ps","DOI":"10.1006\/inco.1996.2613"},{"key":"e_1_2_1_135_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500365.2500600"},{"key":"e_1_2_1_136_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629643"},{"key":"e_1_2_1_137_1","first-page":"83","volume-title":"Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016, Asilomar State Beach\/Pacific Grove, CA, USA","author":"Utterback Robert","year":"2016","unstructured":"Robert Utterback, Kunal Agrawal, Jeremy T. Fineman, and I-Ting Angelina Lee. 2016. Provably Good and Practically Eficient Parallel Race Detection for Fork-Join Programs. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016, Asilomar State Beach\/Pacific Grove, CA, USA, July 11-13, 2016. 83-94."},{"key":"e_1_2_1_138_1","volume-title":"CONCUR 2007-Concurrency Theory, 18th International Conference, CONCUR 2007, Lisbon, Portugal, September 3-8, 2007, Proceedings. 256-271","author":"Vafeiadis Viktor","unstructured":"Viktor Vafeiadis and Matthew J. Parkinson. 2007. A Marriage of Rely\/Guarantee and Separation Logic. In CONCUR 2007-Concurrency Theory, 18th International Conference, CONCUR 2007, Lisbon, Portugal, September 3-8, 2007, Proceedings. 256-271."},{"key":"e_1_2_1_139_1","volume-title":"Proceedings of the First workshop on Semantics, Program Analysis and Computing Environments for Memory Management (SPACE'01)","author":"Walker David","year":"2001","unstructured":"David Walker. 2001. On Linear Types and Regions. In Proceedings of the First workshop on Semantics, Program Analysis and Computing Environments for Memory Management (SPACE'01). London. http:\/\/www.diku.dk\/topps\/space2001\/program. html#DavidWalker"},{"key":"e_1_2_1_140_1","volume-title":"Proceedings of the 47th Annual ACM Symposium on Principles of Programming Languages (POPL)\".","author":"Westrick Sam","unstructured":"Sam Westrick, Rohan Yadav, Matthew Fluet, and Umut A. Acar. 2020. Disentanglement in Nested-Parallel Programs. In Proceedings of the 47th Annual ACM Symposium on Principles of Programming Languages (POPL)\"."},{"key":"e_1_2_1_141_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1096-9128(199809\/11)10:11\/13<825::AID-CPE383>3.0.CO;2-H"},{"key":"e_1_2_1_142_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993572"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434299","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434299","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434299","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T07:27:06Z","timestamp":1781854026000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434299"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,4]]},"references-count":142,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2021,1,4]]}},"alternative-id":["10.1145\/3434299"],"URL":"https:\/\/doi.org\/10.1145\/3434299","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,4]]},"assertion":[{"value":"2021-01-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}