{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T11:05:17Z","timestamp":1784199917591,"version":"3.55.0"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T00:00:00Z","timestamp":1749772800000},"content-version":"vor","delay-in-days":3,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2247088"],"award-info":[{"award-number":["2247088"]}],"id":[{"id":"10.13039\/100000001","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":[[2025,6,10]]},"abstract":"<jats:p>\n                    Nondeterminism introduced by race conditions and message reorderings makes parallel and distributed programming hard. Nevertheless, promising approaches such as LVars and CRDTs address this problem by introducing a partial order structure on shared state that describes how the state evolves over time.\n                    <jats:italic toggle=\"yes\">Monotone<\/jats:italic>\n                    programs that respect the order are deterministic. Datalog-inspired languages incorporate this idea of monotonicity in a first-class way but they are not general-purpose. We would like parallel and distributed languages to be as natural to use as any functional language, without sacrificing expressivity, and with a formal basis of study as appealing as the lambda calculus.\n                  <\/jats:p>\n                  <jats:p>\n                    This paper presents\n                    <jats:italic toggle=\"yes\">\u03bb<\/jats:italic>\n                    <jats:sub>\u2228<\/jats:sub>\n                    , a core language for deterministic parallelism that embodies the ideas above. In\n                    <jats:italic toggle=\"yes\">\u03bb<\/jats:italic>\n                    <jats:sub>\u2228<\/jats:sub>\n                    , values may increase over time according to a\n                    <jats:italic toggle=\"yes\">streaming order<\/jats:italic>\n                    and all computations are monotone with respect to that order. The streaming order coincides with the approximation order found in Scott semantics and so unifies the foundations of functional programming with the foundations of deterministic distributed computation. The resulting lambda calculus has a computationally adequate model rooted in domain theory. It integrates the compositionality and power of abstraction characteristic of functional programming with the declarative nature of Datalog.\n                  <\/jats:p>","DOI":"10.1145\/3729299","type":"journal-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T16:02:27Z","timestamp":1749830547000},"page":"1220-1244","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Functional Meaning for Parallel Streaming"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5277-8920","authenticated-orcid":false,"given":"Nick","family":"Rioux","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3516-1512","authenticated-orcid":false,"given":"Steve","family":"Zdancewic","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1044"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824076"},{"key":"e_1_3_2_4_1","first-page":"249","volume-title":"CIDR","author":"Alvaro Peter","year":"2011","unstructured":"Peter Alvaro, Neil Conway, Joseph M. Hellerstein, and William R. Marczak. 2011a. Consistency Analysis in Bloom: a CALM and Collected Approach. In CIDR. 249\u2013260. http:\/\/cidrdb.org\/cidr2011\/Papers\/CIDR11_Paper35.pdf"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24206-9_16"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450151"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371090"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951948"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273659"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855591.1855595"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1003"},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3607853"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3665252.3665271"},{"key":"e_1_3_2_14_1","unstructured":"Robert Cartwright Rebecca Parsons and Moez AbdelGawad. 2016. Domain Theory: An Introduction. arXiv:1605.05858 [cs.PL] https:\/\/arxiv.org\/abs\/1605.05858"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2391229.2391230"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11693024_20"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02011875"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3656434"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294281"},{"key":"e_1_3_2_20_1","volume-title":"Deterministic Execution for Arbitrary Multithreaded Programs. Ph. D. Dissertation","author":"Devietti Joseph","year":"2012","unstructured":"Joseph Devietti. 2012. Deterministic Execution for Arbitrary Multithreaded Programs. Ph. D. Dissertation. University of Washington."},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57887-0_88"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796813000270"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/258948.258973"},{"key":"e_1_3_2_24_1","unstructured":"Jeremy Gibbons. 2010. The stream monad. https:\/\/web.archive.org\/web\/20241117073300\/https:\/\/patternsinfp.wordpress.com\/2010\/12\/31\/stream-monad\/Accessed: 2025-03-23."},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3446804.3446855"},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341718"},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1860702.1860704"},{"key":"e_1_3_2_28_1","unstructured":"Joseph M. Hellerstein. 2021. A Programmable Cloud: CALM Foundations and Open Challenges. (Jan. 2021). https:\/\/www.youtube.com\/watch?v=dgOhwMmiiG0 POPL Keynote."},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3369736"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1624775.1624804"},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37036-6_4"},{"key":"e_1_3_2_32_1","first-page":"471","volume-title":"Information Processing, Proceedings of the 6th IFIP Congress 1974, Stockholm, Sweden, August 5-10, 1974","author":"Kahn Gilles","year":"1974","unstructured":"Gilles Kahn. 1974. The Semantics of a Simple Language for Parallel Programming. In Information Processing, Proceedings of the 6th IFIP Congress 1974, Stockholm, Sweden, August 5-10, 1974, Jack L. Rosenfeld (Ed.). North-Holland, 471\u2013475."},{"key":"e_1_3_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/IC2EW.2016.56"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2502323.2502326"},{"key":"e_1_3_2_35_1","volume-title":"Workshop on Deterministic and Correctness in Parallel Programming (WoDet\u201914)","author":"Kuper Lindsey","year":"2014","unstructured":"Lindsey Kuper and Ryan R. Newton. 2014. Joining forces: Toward a Unified Account of LVars and Convergent Replicated Data Types. In Workshop on Deterministic and Correctness in Parallel Programming (WoDet\u201914)."},{"key":"e_1_3_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535842"},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3704845"},{"key":"e_1_3_2_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3574245.3574268"},{"key":"e_1_3_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_3_2_40_1","volume-title":"The Problem with Threads. Technical Report UCB\/EECS-2006-1","author":"Lee Edward A.","year":"2006","unstructured":"Edward A. Lee. 2006. The Problem with Threads. Technical Report UCB\/EECS-2006-1. University of California, Berkeley."},{"key":"e_1_3_2_41_1","volume-title":"Call-By-Push-Value: A Functional\/Imperative Synthesis (Semantics Structures in Computation, V. 2)","author":"Levy Paul Blain","year":"2004","unstructured":"Paul Blain Levy. 2004. Call-By-Push-Value: A Functional\/Imperative Synthesis (Semantics Structures in Computation, V. 2). Kluwer Academic Publishers, USA."},{"key":"e_1_3_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592761.1592785"},{"key":"e_1_3_2_43_1","volume-title":"Distributed Algorithms","author":"Lynch Nancy","year":"1996","unstructured":"Nancy Lynch. 1996. Distributed Algorithms. Morgan Kaufmann Publishers."},{"key":"e_1_3_2_44_1","volume-title":"Sixth Biennial Conference on Innovative Data Systems Research, CIDR 2013, Asilomar, CA, USA, January 6-9, 2013, Online Proceedings","author":"McSherry Frank","year":"2013","unstructured":"Frank McSherry, Derek Gordon Murray, Rebecca Isaacs, and Michael Isard. 2013. Differential Dataflow. In Sixth Biennial Conference on Innovative Data Systems Research, CIDR 2013, Asilomar, CA, USA, January 6-9, 2013, Online Proceedings. http:\/\/cidrdb.org\/cidr2013\/Papers\/CIDR13_Paper111.pdf"},{"key":"e_1_3_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3631991.3632000"},{"key":"e_1_3_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951945"},{"key":"e_1_3_2_47_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2022.7"},{"key":"e_1_3_2_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90044-5"},{"key":"e_1_3_2_49_1","doi-asserted-by":"publisher","unstructured":"Nick Rioux. 2025. nrioux\/lambda-join-hs: Version 1.0. https:\/\/doi.org\/10.5281\/zenodo.15097242 10.5281\/zenodo.15097242","DOI":"10.5281\/zenodo.15097242"},{"key":"e_1_3_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3571211"},{"key":"e_1_3_2_51_1","unstructured":"Nick Rioux and Steve Zdancewic. 2025. Functional Meaning for Parallel Streaming. arXiv:2504.02975v1 [cs.PL] https:\/\/arxiv.org\/abs\/2504.02975v1"},{"key":"e_1_3_2_52_1","first-page":"169","volume-title":"Proceedings of the Fourth Annual Princeton Conference on Information Sciences and Systems","author":"Scott Dana S.","year":"1970","unstructured":"Dana S. Scott. 1970. Outline of a Mathematical Theory of Computation. In Proceedings of the Fourth Annual Princeton Conference on Information Sciences and Systems. 169\u2013176."},{"key":"e_1_3_2_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0012801"},{"key":"e_1_3_2_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24550-3_29"},{"key":"e_1_3_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3281366.3281370"},{"key":"e_1_3_2_56_1","unstructured":"Philip Wadler Wen Kokke and Jeremy G. Siek. 2022. Programming Language Foundations in Agda. https:\/\/plfa.inf.ed.ac.uk\/20.08\/"},{"key":"e_1_3_2_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90037-4"},{"key":"e_1_3_2_58_1","doi-asserted-by":"publisher","unstructured":"Chenggang Wu Jose Faleiro Yihan Lin and Joseph M. Hellerstein. 2018. Anna: A KVS for Any Scale. In 2018 IEEE 34th International Conference on Data Engineering (ICDE). 401\u2013412. https:\/\/doi.org\/10.1109\/ICDE.2018.00044 10.1109\/ICDE.2018.00044","DOI":"10.1109\/ICDE.2018.00044"},{"key":"e_1_3_2_59_1","doi-asserted-by":"publisher","unstructured":"Weixin Zhang Yaozhu Sun and Bruno C. d. S. Oliveira. 2021. Compositional Programming. ACM Transactions on Programming Languages and Systems (April 2021). https:\/\/doi.org\/10.1145\/3460228 10.1145\/3460228","DOI":"10.1145\/3460228"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729299","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729299","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:05:44Z","timestamp":1784196344000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3729299"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,10]]},"references-count":58,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2025,6,10]]}},"alternative-id":["10.1145\/3729299"],"URL":"https:\/\/doi.org\/10.1145\/3729299","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,10]]},"assertion":[{"value":"2024-11-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}