{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T07:58:54Z","timestamp":1790927934775,"version":"4.1.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2018,7,30]],"date-time":"2018-07-30T00:00:00Z","timestamp":1532908800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2018,7,30]]},"abstract":"<jats:p>We present a complete reasoning principle for contextual equivalence in an untyped probabilistic language. The language includes continuous (real-valued) random variables, conditionals, and scoring. It also includes recursion, since the standard call-by-value fixpoint combinator is expressible.<\/jats:p>\n          <jats:p>We demonstrate the usability of our characterization by proving several equivalence schemas, including familiar facts from lambda calculus as well as results specific to probabilistic programming. In particular, we use it to prove that reordering the random draws in a probabilistic program preserves contextual equivalence. This allows us to show, for example, that<\/jats:p>\n          <jats:p>\n            (let x =\n            <jats:italic>e<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            in let y =\n            <jats:italic>e<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            in\n            <jats:italic>e<\/jats:italic>\n            <jats:sub>0<\/jats:sub>\n            ) =\n            <jats:sub>\n              <jats:italic>ctx<\/jats:italic>\n            <\/jats:sub>\n            (let y =\n            <jats:italic>e<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            in let x =\n            <jats:italic>e<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            in\n            <jats:italic>e<\/jats:italic>\n            <jats:sub>0<\/jats:sub>\n            )\n          <\/jats:p>\n          <jats:p>\n            (provided\n            <jats:italic>x<\/jats:italic>\n            does not occur free in\n            <jats:italic>e<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            and\n            <jats:italic>y<\/jats:italic>\n            does not occur free in\n            <jats:italic>e<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            ) despite the fact that\n            <jats:italic>e<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            and\n            <jats:italic>e<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            may have sampling and scoring effects.\n          <\/jats:p>","DOI":"10.1145\/3236782","type":"journal-article","created":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T19:41:18Z","timestamp":1533066078000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["Contextual equivalence for a probabilistic language with continuous random variables and recursion"],"prefix":"10.1145","volume":"2","author":[{"given":"Mitchell","family":"Wand","sequence":"first","affiliation":[{"name":"Northeastern University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ryan","family":"Culpepper","sequence":"additional","affiliation":[{"name":"Czech Technical University, Czechia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Theophilos","family":"Giannakopoulos","sequence":"additional","affiliation":[{"name":"BAE Systems, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew","family":"Cobb","sequence":"additional","affiliation":[{"name":"Northeastern University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,7,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11693024_6"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46678-0_18"},{"key":"e_1_2_2_3_1","volume-title":"Andrew D. Gordon, and Marcin Szymczak.","author":"Borgstr\u00f6m Johannes","year":"2017","unstructured":"Johannes Borgstr\u00f6m , Ugo Dal Lago , Andrew D. Gordon, and Marcin Szymczak. 2017 . A Lambda-calculus Foundation for Universal Probabilistic Programming ( long version). https:\/\/arxiv.org\/abs\/1512.08990 Johannes Borgstr\u00f6m, Ugo Dal Lago, Andrew D. Gordon, and Marcin Szymczak. 2017. A Lambda-calculus Foundation for Universal Probabilistic Programming (long version). https:\/\/arxiv.org\/abs\/1512.08990"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951913.2951942"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54833-8_12"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54434-1_14"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535865"},{"key":"e_1_2_2_8_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 (1st ed.). The MIT Press . Matthias Felleisen, Robert Bruce Findler, and Matthew Flatt. 2009. Semantics Engineering with PLT Redex (1st ed.). The MIT Press."},{"key":"e_1_2_2_9_1","volume-title":"Proc. 24th Conference in Uncertainty in Artificial Intelligence (UAI \u201908)","author":"Goodman Noah D.","unstructured":"Noah D. Goodman , Vikash K. Mansinghka , Daniel M. Roy , Keith Bonawitz , and Joshua B. Tenenbaum . 2008. Church: a language for generative models . In Proc. 24th Conference in Uncertainty in Artificial Intelligence (UAI \u201908) . 220\u2013229. Noah D. Goodman, Vikash K. Mansinghka, Daniel M. Roy, Keith Bonawitz, and Joshua B. Tenenbaum. 2008. Church: a language for generative models. In Proc. 24th Conference in Uncertainty in Artificial Intelligence (UAI \u201908). 220\u2013229."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49498-1_14"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03034-5_17"},{"key":"e_1_2_2_12_1","unstructured":"Vikash Mansinghka Daniel Selsam and Yura Perov. 2014. Venture: a higher-order probabilistic programming platform with programmable inference. http:\/\/arxiv.org\/abs\/1404.0099  Vikash Mansinghka Daniel Selsam and Yura Perov. 2014. Venture: a higher-order probabilistic programming platform with programmable inference. http:\/\/arxiv.org\/abs\/1404.0099"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800000125"},{"key":"e_1_2_2_14_1","unstructured":"Kevin P. Murphy. 2007. Conjugate Bayesian analysis of the Gaussian distribution. https:\/\/www.cs.ubc.ca\/~murphyk\/ Papers\/bayesGauss.pdf  Kevin P. Murphy. 2007. Conjugate Bayesian analysis of the Gaussian distribution. https:\/\/www.cs.ubc.ca\/~murphyk\/ Papers\/bayesGauss.pdf"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29604-3_5"},{"key":"e_1_2_2_16_1","volume-title":"Proc. 31th International Conference on Machine Learning (ICML \u201914)","author":"Paige Brooks","year":"2014","unstructured":"Brooks Paige and Frank Wood . 2014 . A Compilation Target for Probabilistic Programming Languages . In Proc. 31th International Conference on Machine Learning (ICML \u201914) . 1935\u20131943. Brooks Paige and Frank Wood. 2014. A Compilation Target for Probabilistic Programming Languages. In Proc. 31th International Conference on Machine Learning (ICML \u201914). 1935\u20131943."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1452044.1452048"},{"key":"e_1_2_2_18_1","volume-title":"Controlling and Reasoning About State (Dagstuhl Seminar Proceedings), Amal Ahmed, Nick Benton, Lars Birkedal, and Martin Hofmann (Eds.). http: \/\/drops.dagstuhl.de\/opus\/volltexte\/2010\/2806\/","author":"Pitts Andrew M.","year":"2010","unstructured":"Andrew M. Pitts . 2010 . Step-Indexed Biorthogonality: a Tutorial Example. In Modelling , Controlling and Reasoning About State (Dagstuhl Seminar Proceedings), Amal Ahmed, Nick Benton, Lars Birkedal, and Martin Hofmann (Eds.). http: \/\/drops.dagstuhl.de\/opus\/volltexte\/2010\/2806\/ Andrew M. Pitts. 2010. Step-Indexed Biorthogonality: a Tutorial Example. In Modelling, Controlling and Reasoning About State (Dagstuhl Seminar Proceedings), Amal Ahmed, Nick Benton, Lars Birkedal, and Martin Hofmann (Eds.). http: \/\/drops.dagstuhl.de\/opus\/volltexte\/2010\/2806\/"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01019462"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837651"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54434-1_32"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2935313"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236782"},{"key":"e_1_2_2_24_1","volume-title":"Proc. 17th International Conference on Artificial Intelligence and Statistics (AISTATS \u201914)","author":"Wood Frank","unstructured":"Frank Wood , Jan-Willem van de Meent, and Vikash Mansinghka. 2014. A New Approach to Probabilistic Programming Inference . In Proc. 17th International Conference on Artificial Intelligence and Statistics (AISTATS \u201914) . 1024\u20131032. Frank Wood, Jan-Willem van de Meent, and Vikash Mansinghka. 2014. A New Approach to Probabilistic Programming Inference. In Proc. 17th International Conference on Artificial Intelligence and Statistics (AISTATS \u201914). 1024\u20131032."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3236782","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3236782","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:41:28Z","timestamp":1750282888000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3236782"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,30]]},"references-count":24,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2018,7,30]]}},"alternative-id":["10.1145\/3236782"],"URL":"https:\/\/doi.org\/10.1145\/3236782","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,30]]},"assertion":[{"value":"2018-07-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}