{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T03:12:09Z","timestamp":1775790729804,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2019,7,26]],"date-time":"2019-07-26T00:00:00Z","timestamp":1564099200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/P00587X\/1"],"award-info":[{"award-number":["EP\/P00587X\/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":[[2019,7,26]]},"abstract":"<jats:p>\n            Call-by-need evaluation, also known as lazy evaluation, provides two key benefits: compositional programming and infinite data. The standard semantics for laziness is Launchbury\u2019s natural semantics\u00a0DBLP:conf\/popl\/Launchbury93, which uses a heap to memoise the results of delayed evaluations. However, the stateful nature of this heap greatly complicates reasoning about the operational behaviour of lazy programs. In this article, we propose an alternative semantics for laziness,\n            <jats:italic>clairvoyant evaluation<\/jats:italic>\n            , that replaces the state effect with nondeterminism, and prove this semantics equivalent in a strong sense to the standard semantics. We show how this new semantics greatly simplifies operational reasoning, admitting much simpler proofs of a number of results from the literature, and how it leads to the first\n            <jats:italic>denotational cost semantics<\/jats:italic>\n            for lazy evaluation.\n          <\/jats:p>","DOI":"10.1145\/3341718","type":"journal-article","created":{"date-parts":[[2019,7,29]],"date-time":"2019-07-29T20:55:51Z","timestamp":1564433751000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Call-by-need is clairvoyant call-by-value"],"prefix":"10.1145","volume":"3","author":[{"given":"Jennifer","family":"Hackett","sequence":"first","affiliation":[{"name":"University of Nottingham, UK"}]},{"given":"Graham","family":"Hutton","sequence":"additional","affiliation":[{"name":"University of Nottingham, UK"}]}],"member":"320","published-online":{"date-parts":[[2019,7,26]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796897002724"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199507"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264249"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/99370.99382"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1291220.1291193"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2784731.2784749"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1040305.1040313"},{"key":"e_1_2_2_8_1","volume-title":"A Foundation for Space-Safe Transformations of Call-by-Need Programs. Electronic Notes on Theoretical Computer Science 26","author":"Gustavsson J\u00f6rgen","year":"1999"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/507635.507667"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2628136.2628142"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236763"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/800168.811543"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/32.2.98"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.2917"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90122-9"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1707801.1706327"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/158511.158618"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00358-2"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796898003037"},{"key":"e_1_2_2_21_1","unstructured":"Andrew Moran and David Sands. 1999a. Improvement in a Lazy Context: An Operational Theory for Call-by-Need. (1999). Extended version of { Moran and Sands 1999b } available at http:\/\/tinyurl.com\/ohuv8ox .  Andrew Moran and David Sands. 1999a. Improvement in a Lazy Context: An Operational Theory for Call-by-Need. (1999). Extended version of { Moran and Sands 1999b } available at http:\/\/tinyurl.com\/ohuv8ox ."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/292540.292547"},{"key":"e_1_2_2_24_1","unstructured":"Keiko Nakata. 2010. Denotational Semantics for Lazy Initialization of letrec. In Fixed Points in Computer Science.  Keiko Nakata. 2010. Denotational Semantics for Lazy Initialization of letrec. In Fixed Points in Computer Science."},{"key":"e_1_2_2_25_1","doi-asserted-by":"crossref","volume-title":"Purely Functional Data Structures","author":"Okasaki Chris","DOI":"10.1017\/CBO9780511530104"},{"key":"e_1_2_2_26_1","volume-title":"International Summer School on Applied Semantics","author":"Pitts Andrew M"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/99370.99381"},{"key":"e_1_2_2_28_1","volume-title":"Operational Theories of Improvement in Functional Languages. In Glasgow Workshop on Functional Programming.","author":"Sands David","year":"1991"},{"key":"e_1_2_2_29_1","volume-title":"Higher Order Operational Techniques in Semantics","author":"Sands David"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/244795.244802"},{"key":"e_1_2_2_31_1","volume-title":"Space Improvements and Equivalences in a Functional Core Language. arXiv preprint arXiv:1802.06498","author":"Schmidt-Schau\u00df Manfred","year":"2018"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2790449.2790512"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897336.2897343"},{"key":"e_1_2_2_34_1","doi-asserted-by":"crossref","unstructured":"Daniel Seidel and Janis Voigtl\u00e4nder. 2011. Improvements for Free. In Quantitative Aspects of Programming Languages.  Daniel Seidel and Janis Voigtl\u00e4nder. 2011. Improvements for Free. In Quantitative Aspects of Programming Languages.","DOI":"10.4204\/EPTCS.57.7"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2364527.2364575"},{"key":"e_1_2_2_36_1","volume-title":"Functional Programming and its Applications: An Advanced Course","author":"Turner David A"},{"key":"e_1_2_2_37_1","doi-asserted-by":"crossref","unstructured":"Philip Wadler and John Hughes. 1987. Projections for Strictness Analysis. In Functional Programming Languages and Computer Architecture.   Philip Wadler and John Hughes. 1987. Projections for Strictness Analysis. In Functional Programming Languages and Computer Architecture.","DOI":"10.1007\/3-540-18317-5_21"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341718","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3341718","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:43:24Z","timestamp":1750207404000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3341718"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,26]]},"references-count":35,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2019,7,26]]}},"alternative-id":["10.1145\/3341718"],"URL":"https:\/\/doi.org\/10.1145\/3341718","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,26]]},"assertion":[{"value":"2019-07-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}