{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T11:10:53Z","timestamp":1784200253228,"version":"3.55.0"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T00:00:00Z","timestamp":1759968000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1917852, CCF-2247088, and CCF-233877"],"award-info":[{"award-number":["CCF-1917852, CCF-2247088, and CCF-233877"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008536","name":"Amazon Web Services","doi-asserted-by":"publisher","award":["Amazon Research Award Fall 2023, Amazon\/ASSET Gift for Research in Trustworthy AI"],"award-info":[{"award-number":["Amazon Research Award Fall 2023, Amazon\/ASSET Gift for Research in Trustworthy AI"]}],"id":[{"id":"10.13039\/100008536","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,10,9]]},"abstract":"<jats:p>\n                    Scripting languages are widely used to compose\n                    <jats:italic toggle=\"yes\">external calls<\/jats:italic>\n                    such as native libraries and network services. In such scripts, execution time is often dominated by waiting for these external calls, rendering traditional single-language optimizations ineffective. To address this, we propose a novel\n                    <jats:italic toggle=\"yes\">opportunistic<\/jats:italic>\n                    evaluation strategy for scripting languages based on a core lambda calculus that\n                    <jats:italic toggle=\"yes\">automatically<\/jats:italic>\n                    dispatches independent external calls in parallel and streams their results. We prove that our approach is confluent, ensuring that it preserves the programmer\u2019s original intent, and that it eventually executes every external call. We implement this approach in a scripting language called\n                    <jats:sc>Opal<\/jats:sc>\n                    . We demonstrate the versatility and performance of\n                    <jats:sc>Opal<\/jats:sc>\n                    , focusing on programs that invoke heavy external computation through the use of large language models (LLMs) and other APIs. Across five scripts, we compare to several state-of-the-art baselines and show that opportunistic evaluation improves total running time (up to 6.2\u00d7) and latency (up to 12.7\u00d7) compared to standard sequential Python, while performing very close (between 1.3% and 18.5% running time overhead) to hand-tuned manually optimized asynchronous Rust. For Tree-of-Thoughts, a prominent LLM reasoning approach, we achieve a 6.2 \u00d7 performance improvement over the authors\u2019 own implementation.\n                  <\/jats:p>","DOI":"10.1145\/3763143","type":"journal-article","created":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T08:51:31Z","timestamp":1759999891000},"page":"2596-2622","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Opportunistically Parallel Lambda Calculus"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-7469-8974","authenticated-orcid":false,"given":"Stephen","family":"Mell","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philedlphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8984-6648","authenticated-orcid":false,"given":"Konstantinos","family":"Kallas","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles, Los Angeles, 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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9990-7566","authenticated-orcid":false,"given":"Osbert","family":"Bastani","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,10,9]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"2022. Guidance. https:\/\/github.com\/guidance-ai\/guidance"},{"key":"e_1_3_1_3_2","unstructured":"2023. Official Repo of Tree of Thoughts. https:\/\/github.com\/princeton-nlp\/tree-of-thought-llm"},{"key":"e_1_3_1_4_2","volume-title":"Technical Report","author":"Adams Duane A","year":"1968","unstructured":"Duane A. Adams. 1968. A Computation Model with Data-Sequenced Control. Technical Report. Stanford University. Technical Report CGTM 45."},{"key":"e_1_3_1_5_2","unstructured":"Duane A. Adams. 1969. A Computation Model with Data Flow Sequencing. Ph. D. Dissertation."},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824076"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/2.3.297"},{"key":"e_1_3_1_8_2","doi-asserted-by":"crossref","unstructured":"Sotiris Apostolakis Ziyang Xu Greg Chan Simone Campanoni and David I August. 2020. Perspective: A sensible approach to speculative automatic parallelization. In Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems. 351-367.","DOI":"10.1145\/3373376.3378458"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0014548"},{"key":"e_1_3_1_10_2","doi-asserted-by":"crossref","unstructured":"Rishiyur S Nikhil Arvind. 1992. Id: a language with implicit parallelism. In A Comparative Study of Parallel Programming Languages. Elsevier 169-215.","DOI":"10.1016\/B978-0-444-88135-9.50010-3"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591300"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","unstructured":"Sid Black Gao Leo Phil Wang Connor Leahy and Stella Biderman. 2021. GPT-Neo: Large Scale Autoregressive Language Modeling with Mesh-Tensorflow. doi:10.5281\/zenodo.5297715 If you use this software please cite it using these metadata.","DOI":"10.5281\/zenodo.5297715"},{"key":"e_1_3_1_13_2","doi-asserted-by":"crossref","unstructured":"Guy Blelloch and John Greiner. 1995. Parallelism in Sequential Functional Languages. In Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture.","DOI":"10.1145\/224164.224210"},{"key":"e_1_3_1_14_2","unstructured":"Guy E Blelloch. 1995. NESL:A nested data-parallel language (version 3.1). Citeseer."},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/301970.301974"},{"key":"e_1_3_1_16_2","doi-asserted-by":"crossref","unstructured":"Corrado B\u00f6hm and Alessandro Berarducci. 1985. Automatic synthesis of typed \u03bb-programs on term algebras. Theoretical Computer Science 39 (1985) 135-154.","DOI":"10.1016\/0304-3975(85)90135-5"},{"key":"e_1_3_1_17_2","article-title":"Apache flink: Stream and batch processing in a single engine","volume":"4","author":"Carbone Paris","year":"2015","unstructured":"Paris Carbone, Asterios Katsifodimos, Stephan Ewen, Volker Markl, Seif Haridi, and Kostas Tzoumas. 2015. Apache flink: Stream and batch processing in a single engine. The Bulletin of the Technical Committee on Data Engineering 38, 4 (2015).","journal-title":"The Bulletin of the Technical Committee on Data Engineering 38"},{"key":"e_1_3_1_18_2","doi-asserted-by":"crossref","unstructured":"Bradford L Chamberlain David Callahan and Hans P Zima. 2007. Parallel programmability and the chapel language. The International Journal of High Performance Computing Applications 21 3 (2007) 291-312.","DOI":"10.1177\/1094342007078442"},{"key":"e_1_3_1_19_2","unstructured":"Harrison Chase. 2022. LangChain. https:\/\/github.com\/langchain-ai\/langchain"},{"key":"e_1_3_1_20_2","first-page":"26","article-title":"Data Flow Program Graphs","volume":"02","author":"Davis Alan L.","year":"1982","unstructured":"Alan L. Davis and Robert M. Keller. 1982. Data Flow Program Graphs. Computer 15, 02 (2 1982), 26-41.","journal-title":"Computer 15"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-06859-7_145"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(90)90035-N"},{"key":"e_1_3_1_23_2","doi-asserted-by":"crossref","unstructured":"Cormac Flanagan Amr Sabry Bruce FDuba and Matthias Felleisen. 1993. The Essence of Compiling with Continuations. In Proceedings of the ACM SIGPLAN 1993 conference on Programming Language Design and Implementation (PLDI). 237-247.","DOI":"10.1145\/155090.155113"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/277652.277725"},{"key":"e_1_3_1_25_2","unstructured":"Kanishk Gandhi. 2022. Synchromesh. https:\/\/github.com\/kanishkg\/synchromesh."},{"key":"e_1_3_1_26_2","first-page":"1","article-title":"Linear logic","volume":"1","author":"Girard Jean-Yves","year":"1987","unstructured":"Jean-Yves Girard. 1987. Linear logic. Theoretical computer science 50,1 (1987), 1-101.","journal-title":"Theoretical computer science 50"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/4472.4478"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2345156.2254107"},{"key":"e_1_3_1_29_2","first-page":"47","article-title":"Tackling the awkward squad: monadic input\/output, concurrency, exceptions, and foreign-language calls in Haskell","volume":"180","author":"Jones Simon Peyton","year":"2001","unstructured":"Simon Peyton Jones. 2001. Tackling the awkward squad: monadic input\/output, concurrency, exceptions, and foreign-language calls in Haskell. NATO SCIENCE SERIES SUB SERIES III COMPUTER AND SYSTEMS SCIENCES 180 (2001), 47-96.","journal-title":"NATO SCIENCE SERIES SUB SERIES III COMPUTER AND SYSTEMS SCIENCES"},{"key":"e_1_3_1_30_2","first-page":"295","article-title":"Concurrent haskell","volume":"96","author":"Jones Simon Peyton","year":"1996","unstructured":"Simon Peyton Jones, Andrew Gordon, and Sigbjorn Finne. 1996. Concurrent haskell. In POPL, Vol. 96. 295-308.","journal-title":"POPL"},{"key":"e_1_3_1_31_2","unstructured":"Konstantinos Kallas Tammam Mustafa Jan Bielak Dimitris Karnikis Thurston HY Dang Michael Greenberg and Nikos Vasilakis. 2022. Practically correct Just-in-Time shell script parallelization. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22). 769-785."},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/0114108"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(69)80011-5"},{"key":"e_1_3_1_34_2","unstructured":"Omar Khattab Arnav Singhvi Paridhi Maheshwari Zhiyuan Zhang Keshav Santhanam Sri Vardhamanan Saiful Haq Ashutosh Sharma Thomas T Joshi Hanna Moazam et al. 2023. DSPy: Compiling declarative language model calls into self-improving pipelines. arXiv preprint arXiv:2310.03714 (2023)."},{"key":"e_1_3_1_35_2","first-page":"9459","article-title":"Retrieval-augmented generation for knowledge-intensive nlp tasks","volume":"33","author":"Lewis Patrick","year":"2020","unstructured":"Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich K\u00fcttler, Mike Lewis, Wen-tau Yih, Tim Rockt\u00e4schel, et al. 2020. Retrieval-augmented generation for knowledge-intensive nlp tasks. Advances in Neural Information Processing Systems 33 (2020), 9459-9474.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3593856.3595891"},{"key":"e_1_3_1_37_2","unstructured":"Jerry Liu. 2022. LlamaIndex. https:\/\/github.com\/jerryjliu\/llama_index"},{"key":"e_1_3_1_38_2","unstructured":"JW Maessen RS Nikhil and JE Stoy. 1996. S: an Implicitly Parallel-Calculus with Letrec Synchronization and Side-E ects. (1996)."},{"key":"e_1_3_1_39_2","unstructured":"Shail Aditya Arvind Jan-Willem Maessen Lennart Augustsson and Rishiyur S Nikhil. 1995. Semantics of pH: A parallel dialect of Haskell. In In Proceedings from the Haskell Workshop (at FPCA 95). 35-49."},{"key":"e_1_3_1_40_2","volume-title":"Parallel and concurrent programming in Haskell: Techniques for multicore and multithreaded programming","author":"Marlow Simon","year":"2013","unstructured":"Simon Marlow. 2013. Parallel and concurrent programming in Haskell: Techniques for multicore and multithreaded programming. \u201cO\u2019Reilly Media, Inc.\u201d."},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2692915.2628144"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/357153.357157"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","unstructured":"Stephen Mell. 2025. Artifact for Opportunistically Parallel Lambda Calculus. doi:10.5281\/zenodo.16929280","DOI":"10.5281\/zenodo.16929280"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.4204\/eptcs.377.4"},{"key":"e_1_3_1_45_2","first-page":"341","volume-title":"20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23)","author":"Mustafa Tammam","year":"2023","unstructured":"Tammam Mustafa, Konstantinos Kallas, Pratyush Das, and Nikos Vasilakis. 2023. DiSh: Dynamic Shell-Script Distribution. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23) (Boston, MA). USENIX Association, 341-356. https:\/\/www.usenix.org\/conference\/nsdi23\/presentation\/mustafa"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/2.660187"},{"key":"e_1_3_1_47_2","article-title":"Pytorch: An imperative style, high-performance deep learning library","volume":"32","author":"Paszke Adam","year":"2019","unstructured":"Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems 32 (2019).","journal-title":"Advances in neural information processing systems"},{"key":"e_1_3_1_48_2","unstructured":"Gabriel Poesia Oleksandr Polozov Vu Le Ashish Tiwari Gustavo Soares Christopher Meek and Sumit Gulwani. 2022. Synchromesh: Reliable code generation from pre-trained language models. arXiv preprint arXiv:2201.11227 (2022)."},{"key":"e_1_3_1_49_2","unstructured":"Jorge E. Rodriguez. 1969. A Graph Model for Parallel Computations. Ph. D. Dissertation. MIT-LCS-TR64."},{"key":"e_1_3_1_50_2","unstructured":"Mohammed Saeed Nicola De Cao and Paolo Papotti. 2023. Querying large language models with SQL. arXiv preprint arXiv:2304.00472 (2023)."},{"key":"e_1_3_1_51_2","article-title":"Toolformer: Language models can teach themselves to use tools","volume":"36","author":"Schick Timo","year":"2024","unstructured":"Timo Schick, Jane Dwivedi-Yu, Roberto Dess\u00cc, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. 2024. Toolformer: Language models can teach themselves to use tools. Advances in Neural Information Processing Systems 36 (2024).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_1_52_2","unstructured":"Enrico Shippole. 2023. ReAct. https:\/\/github.com\/conceptofmind\/toolformer."},{"key":"e_1_3_1_53_2","unstructured":"Keenneth R Traub. 1988. Sequential implementation of lenient programming languages. (1988)."},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0096-0551(01)00006-6"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0096-0551(01)00007-8"},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447786.3456228"},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","DOI":"10.1109\/85.329757"},{"key":"e_1_3_1_58_2","first-page":"38","volume-title":"Transformers: State-of-the-Art Natural Language Processing","author":"Wolf Thomas","year":"2020","unstructured":"Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Perric Cistac, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. 2020. Transformers: State-of-the-Art Natural Language Processing. Association for Computational Linguistics, 38-45. https:\/\/www.aclweb.org\/anthology\/2020.emnlp-demos.6"},{"key":"e_1_3_1_59_2","unstructured":"Shunyu Yao. 2023. ReAct. https:\/\/github.com\/ysymyth\/ReAct."},{"key":"e_1_3_1_60_2","article-title":"Tree of thoughts: Deliberate problem solving with large language models","volume":"36","author":"Yao Shunyu","year":"2024","unstructured":"Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. 2024. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems 36 (2024).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_1_61_2","unstructured":"Lianmin Zheng Liangsheng Yin Zhiqiang Xie Jeff Huang Chuyue Sun Cody Hao Yu Shiyi Cao Christos Kozyrakis Ion Stoica Joseph E Gonzalez et al. 2023. Efficiently programming large language models using sglang. arXiv preprint arXiv:2312.07104 (2023)."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763143","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763143","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:14:54Z","timestamp":1784196894000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763143"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,9]]},"references-count":60,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2025,10,9]]}},"alternative-id":["10.1145\/3763143"],"URL":"https:\/\/doi.org\/10.1145\/3763143","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,9]]},"assertion":[{"value":"2025-03-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-12","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}