{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:21:56Z","timestamp":1750220516709,"version":"3.41.0"},"reference-count":53,"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\/"}],"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>We make a formal analogy between random sampling and fresh name generation. We show that quasi-Borel spaces, a model for probabilistic programming, can soundly interpret the \u03bd-calculus, a calculus for name generation. Moreover, we prove that this semantics is fully abstract up to first-order types. This is surprising for an \u2018off-the-shelf\u2019 model, and requires a novel analysis of probability distributions on function spaces. Our tools are diverse and include descriptive set theory and normal forms for the \u03bd-calculus.<\/jats:p>","DOI":"10.1145\/3434292","type":"journal-article","created":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T17:34:24Z","timestamp":1609781664000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Probabilistic programming semantics for name generation"],"prefix":"10.1145","volume":"5","author":[{"given":"Marcin","family":"Sabok","sequence":"first","affiliation":[{"name":"McGill University, Canada"}]},{"given":"Sam","family":"Staton","sequence":"additional","affiliation":[{"name":"University of Oxford, UK"}]},{"given":"Dario","family":"Stein","sequence":"additional","affiliation":[{"name":"University of Oxford, UK"}]},{"given":"Michael","family":"Wolman","sequence":"additional","affiliation":[{"name":"McGill University, Canada"}]}],"member":"320","published-online":{"date-parts":[[2021,1,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2004.1319609"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Robert J. Aumann. 1961. Borel structures for function spaces. Illinois Journal of Mathematics 5 ( 1961 ).  Robert J. Aumann. 1961. Borel structures for function spaces. Illinois Journal of Mathematics 5 ( 1961 ).","DOI":"10.1215\/ijm\/1255631584"},{"volume-title":"Proc. LICS","year":"2018","author":"Bacci Giorgio","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009852"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371125"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2019.8785663"},{"volume-title":"Proc. POPL","year":"2018","author":"Ehrhard Thomas","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","first-page":"309","article-title":"Probabilistic coherence spaces are fully abstract for probabilistic PCF","volume":"2014","author":"Ehrhard Thomas","year":"2014","journal-title":"Proc. POPL"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2009.07.092"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2020.107239"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386006"},{"volume-title":"Categorical Aspects of Topology and Analysis","series-title":"Lecture Notes in Mathematics","author":"Giry Mich\u00e8le","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3329995.3330072"},{"key":"e_1_2_1_15_1","unstructured":"Daniel Huang Greg Morrisett and Bas Spitters. 2018. An application of computable distributions to the semantics of probabilistic programs. arxiv:1806.07966.  Daniel Huang Greg Morrisett and Bas Spitters. 2018. An application of computable distributions to the semantics of probabilistic programs. arxiv:1806.07966."},{"volume-title":"Proc. LICS","year":"1999","author":"Jefrey A.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Paul Jung Jiho Lee Sam Staton and Hongseok Yang. 2020. A generalization of hierarchical exchangeability on trees to directed acyclic graphs. Annales Henri Lebesgue ( 2020 ). to appear.  Paul Jung Jiho Lee Sam Staton and Hongseok Yang. 2020. A generalization of hierarchical exchangeability on trees to directed acyclic graphs. Annales Henri Lebesgue ( 2020 ). to appear.","DOI":"10.5802\/ahl.74"},{"volume-title":"Foundations of Modern Probability","author":"Kallenberg Olav","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","first-page":"349","article-title":"Algebraic foundations for efect-dependent optimisations","volume":"2012","author":"Kammar Ohad","year":"2012","journal-title":"Proc. POPL"},{"volume-title":"Classical Descriptive Set Theory","author":"Kechris Alexander","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","unstructured":"Anders Kock. 2011. Commutative monads as a theory of distributions. Theory and Applications of Categories 26 (Aug. 2011 ).  Anders Kock. 2011. Commutative monads as a theory of distributions. Theory and Applications of Categories 26 (Aug. 2011 )."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90036-2"},{"volume-title":"Proc. MFPS","year":"2019","author":"Lago Ugo Dal","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24727-2_21"},{"key":"e_1_2_1_25_1","unstructured":"J Lambek and P J Scott. 1988. Introduction to higher order categorical logic. CUP.  J Lambek and P J Scott. 1988. Introduction to higher order categorical logic. CUP."},{"volume-title":"Proc. ACM Program. Lang. 4, POPL, Article 19 (","year":"2019","author":"Lew Alexander K.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","unstructured":"Robin Milner. 1999. Communicating and mobile systems-the Pi-calculus. CUP.  Robin Milner. 1999. Communicating and mobile systems-the Pi-calculus. CUP."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Eugenio Moggi. 1991. Notions of computation and monads. Inform. Comput. 93 1 ( 1991 ) 55-92.  Eugenio Moggi. 1991. Notions of computation and monads. Inform. Comput. 93 1 ( 1991 ) 55-92.","DOI":"10.1016\/0890-5401(91)90052-4"},{"volume-title":"Murawski and Nikos Tzevelekos","year":"2016","author":"Andrzej","key":"e_1_2_1_29_1"},{"volume-title":"Sch\u00f6n","year":"2018","author":"Murray Lawrence M.","key":"e_1_2_1_30_1"},{"volume-title":"Proc. AAAI","year":"2014","author":"Nori Aditya","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","first-page":"48","article-title":"A Functional Theory of Local Names","volume":"1994","author":"Odersky Martin","year":"1994","journal-title":"Proc. POPL"},{"volume-title":"Roy","year":"2015","author":"Orbanz Peter","key":"e_1_2_1_33_1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2018.11.016"},{"volume-title":"disintegrations, and Bayesian inversion in quantum Markov categories. arXiv","year":"2001","author":"Parzygnat Arthur J.","key":"e_1_2_1_35_1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2512979"},{"volume-title":"Proc. MFCS 1993 (Lecture Notes in Computer Science). 122-141","author":"Andrew","key":"e_1_2_1_38_1"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"David Pollard. 2001. A users' guide to measure-theoretic probability. CUP.  David Pollard. 2001. A users' guide to measure-theoretic probability. CUP.","DOI":"10.1017\/CBO9780511811555"},{"volume-title":"Proc. ICML Workshop on Nonparametric Bayes.","year":"2008","author":"Roy Daniel","key":"e_1_2_1_41_1"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290351"},{"volume-title":"Proceedings of the ACM on Programming Languages 2 (","year":"2017","author":"\u015acibior Adam","key":"e_1_2_1_43_1"},{"volume-title":"Categorical stochastic processes and likelihood. arXiv","year":"2005","author":"Shiebler Dan","key":"e_1_2_1_44_1"},{"volume-title":"Proc. CALCO","year":"2017","author":"Simpson Alex","key":"e_1_2_1_45_1"},{"volume-title":"A Course on Borel Sets","author":"Srivastava Shashi M.","key":"e_1_2_1_46_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-85473-6"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01806033"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12032-9_5"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54434-1_32"},{"volume-title":"Proc. ICALP","year":"2018","author":"Staton Sam","key":"e_1_2_1_51_1"},{"volume-title":"Proc. PPS","year":"2017","author":"Staton S.","key":"e_1_2_1_52_1"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2935313"},{"key":"e_1_2_1_54_1","article-title":"Logical relations for encryption","volume":"11","author":"Sumii Eijiro","year":"2003","journal-title":"J. Comput. Secur."},{"key":"e_1_2_1_56_1","unstructured":"Jan-Willem van de Meent Brooks Paige Hongseok Yang and Frank Wood. 2018. An introduction to probabilistic programming. arxiv:1809.10756.  Jan-Willem van de Meent Brooks Paige Hongseok Yang and Frank Wood. 2018. An introduction to probabilistic programming. arxiv:1809.10756."},{"volume-title":"Proc. POPL","year":"2020","author":"Vandenbroucke Alexander","key":"e_1_2_1_57_1"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45220-1_48"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434292","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434292","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:35Z","timestamp":1750195475000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434292"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,4]]},"references-count":53,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2021,1,4]]}},"alternative-id":["10.1145\/3434292"],"URL":"https:\/\/doi.org\/10.1145\/3434292","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2021,1,4]]},"assertion":[{"value":"2021-01-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}