{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T20:31:14Z","timestamp":1792787474001,"version":"4.5.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T00:00:00Z","timestamp":1786924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/501100001381","name":"National Research Foundation Singapore","doi-asserted-by":"publisher","award":["NRF-RSS2022-009"],"award-info":[{"award-number":["NRF-RSS2022-009"]}],"id":[{"id":"10.13039\/501100001381","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-21-1-0038"],"award-info":[{"award-number":["FA9550-21-1-0038"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["BLAST"],"award-info":[{"award-number":["BLAST"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Advanced Research and Invention Agency","award":["Safeguarded AI"],"award-info":[{"award-number":["Safeguarded AI"]}],"id":[{"id":"https:\/\/ror.org\/028y4g372","id-type":"ROR","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2026,8,17]]},"abstract":"<jats:p>Hamiltonian Monte Carlo (HMC) is a successful generic inference method in probabilistic programming, but in its ordinary formulation it needs gradients and finite-dimensional parameter spaces. In Haskell, lazy evaluation lets probabilistic programs express stochastic processes and other non-parametric Bayesian models over implicit infinite-dimensional spaces. This paper develops new formulations of gradient-based HMC for this infinite-dimensional setting, via lazy evaluation. For automatic differentiation, we provide an analysis based on a new notion of \u201cpiecewise analytic under cylindrical analytic partition\u201d (PACAP), to show that even if a program is infinite-dimensional and defined lazily, the gradient of the likelihood function is finitely supported. For the Monte Carlo method itself, we develop several HMC variants and a No-U-Turn Sampler that operate over the infinite-dimensional parameter space but are still productive because of lazy evaluation. Experiments cover Gaussian mixture clustering, random walks, and piecewise-constant regression with Poisson-process changepoints.<\/jats:p>","DOI":"10.1145\/3828696","type":"journal-article","created":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T20:23:46Z","timestamp":1786998226000},"page":"692-720","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["LazyHMC: Hamiltonian Monte Carlo Simulation for Lazy, Infinite Dimensional Probabilistic Programs"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-0108-1692","authenticated-orcid":false,"given":"Maria-Nicoleta","family":"Cr\u0103ciun","sequence":"first","affiliation":[{"name":"University of Oxford, Department of Computer Science, Oxford, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7509-680X","authenticated-orcid":false,"given":"C.-H. Luke","family":"Ong","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, College of Computing and Data Science, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8771-5559","authenticated-orcid":false,"given":"Tom","family":"Schrijvers","sequence":"additional","affiliation":[{"name":"KU Leuven, Department of Computer Science, Leuven, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7149-3805","authenticated-orcid":false,"given":"Sam","family":"Staton","sequence":"additional","affiliation":[{"name":"University of Oxford, Department of Computer Science, Oxford, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,8,17]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"Christophe Andrieu Anthony Lee and Samuel Livingstone. 2020. A general perspective on the Metropolis\u2013Hastings kernel. arXiv preprint arXiv:2012.14881 (2020). https:\/\/arxiv.org\/abs\/2012.14881"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-44914-8_3"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108770750"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.spa.2011.06.003"},{"key":"e_1_3_2_6_2","article-title":"A conceptual introduction to Hamiltonian Monte Carlo","author":"Betancourt Michael","year":"2017","unstructured":"Michael Betancourt. 2017. A conceptual introduction to Hamiltonian Monte Carlo. arXiv preprint arXiv:1701.02434 (2017).","journal-title":"arXiv preprint arXiv:1701.02434"},{"key":"e_1_3_2_7_2","article-title":"GIST: Gibbs self-tuning for locally adaptive Hamiltonian Monte Carlo","author":"Bou-Rabee Nawaf","year":"2024","unstructured":"Nawaf Bou-Rabee, Bob Carpenter, and Milo Marsden. 2024. GIST: Gibbs self-tuning for locally adaptive Hamiltonian Monte Carlo. arXiv preprint arXiv:2404.15253 (2024).","journal-title":"arXiv preprint arXiv:2404.15253"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3729325"},{"key":"e_1_3_2_9_2","article-title":"Automating Involutive MCMC using Probabilistic and Differentiable Programming","author":"Cusumano-Towner Marco","year":"2020","unstructured":"Marco Cusumano-Towner, Alexander K. Lew, and Vikash K. Mansinghka. 2020. Automating Involutive MCMC using Probabilistic and Differentiable Programming. arXiv preprint arXiv:2007.09871 (2020). https:\/\/arxiv.org\/abs\/2007.09871","journal-title":"arXiv preprint arXiv:2007.09871"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314642"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3571239"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005137"},{"issue":"1","key":"e_1_3_2_13_2","first-page":"1593","article-title":"The No-U-turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo","volume":"15","author":"Hoffman Matthew D.","year":"2014","unstructured":"Matthew D. Hoffman and Andrew Gelman. 2014. The No-U-turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo. J. Mach. Learn. Res. 15, 1 (2014), 1593\u20131623. http:\/\/dl.acm.org\/citation.cfm?id=2638586","journal-title":"J. Mach. Learn. Res"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS56636.2023.10175739"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45231-5_17"},{"key":"e_1_3_2_16_2","unstructured":"Wonyeol Lee Hangyeol Yu Xavier Rival and Hongseok Yang. 2020. On Correctness of Automatic Differentiation for Non-Differentiable Functions. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020 NeurIPS 2020 December 6-12 2020 virtual Hugo Larochelle Marc\u2019Aurelio Ranzato Raia Hadsell Maria-Florina Balcan and Hsuan-Tien Lin (Eds.). https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/4aaa76178f8567e05c8e8295c96171d8-Abstract.html"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511614118"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.3150\/18-BEJ1083"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21500-6"},{"key":"e_1_3_2_20_2","first-page":"7336","volume-title":"Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event (Proceedings of Machine Learning Research, Vol. 139)","author":"Mak Carol","year":"2021","unstructured":"Carol Mak, Fabian Zaiser, and Luke Ong. 2021. Nonparametric Hamiltonian Monte Carlo. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event (Proceedings of Machine Learning Research, Vol. 139), Marina Meila and Tong Zhang (Eds.). PMLR, 7336\u20137347. http:\/\/proceedings.mlr.press\/v139\/mak21a.html"},{"key":"e_1_3_2_21_2","first-page":"14802","volume-title":"International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA (Proceedings of MachineLearning Research, Vol. 162)","author":"Mak Carol","year":"2022","unstructured":"Carol Mak, Fabian Zaiser, and Luke Ong. 2022. Nonparametric Involutive Markov Chain Monte Carlo. In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA (Proceedings of MachineLearning Research, Vol. 162), Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesv\u00e1ri, Gang Niu, and Sivan Sabato (Eds.). PMLR, 14802\u201314859. https:\/\/proceedings.mlr.press\/v162\/mak22a.html"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","unstructured":"Radford M. Neal. 2012. MCMC using Hamiltonian dynamics. (6 2012). doi:10.1201\/b10905","DOI":"10.1201\/b10905"},{"key":"e_1_3_2_23_2","first-page":"7273","volume-title":"Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event (Proceedings of Machine Learning Research, Vol. 119)","author":"Neklyudov Kirill","year":"2020","unstructured":"Kirill Neklyudov, Max Welling, Evgenii Egorov, and Dmitry P. Vetrov. 2020. Involutive MCMC: a Unifying Framework. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event (Proceedings of Machine Learning Research, Vol. 119). PMLR, 7273\u20137282. http:\/\/proceedings.mlr.press\/v119\/neklyudov20a.html"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-30164-8_66"},{"key":"e_1_3_2_25_2","first-page":"513","volume-title":"Information Processing 83 (IFIP Congress Series, Vol. 9)","author":"Reynolds John C.","year":"1983","unstructured":"John C. Reynolds. 1983. Types, Abstraction and Parametric Polymorphism. In Information Processing 83 (IFIP Congress Series, Vol. 9), R.E.A. Mason (Ed.). Elsevier Science Publishers B.V., Amsterdam, The Netherlands, 513\u2013523."},{"key":"e_1_3_2_26_2","volume-title":"Workshop on Nonparametric Bayes (ICML 2008)","author":"Roy Daniel M.","year":"2008","unstructured":"Daniel M. Roy, Vikash K. Mansinghka, Noah D. Goodman, and Joshua B. Tenenbaum. 2008. A stochastic programming perspective on nonparametric Bayes. In Workshop on Nonparametric Bayes (ICML 2008). Helsinki, Finland. https:\/\/danroy.org\/papers\/RoyManGooTen-ICMLNPB-2008.pdf Filename: RoyManGooTen-ICMLNPB-2008.pdf; MIT."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341701"},{"key":"e_1_3_2_28_2","article-title":"An Introduction to Probabilistic Programming","author":"van de Meent Jan-Willem","year":"2018","unstructured":"Jan-Willem van de Meent, Brooks Paige, Hongseok Yang, and Frank Wood. 2018. An Introduction to Probabilistic Programming. CoRR abs\/1809.10756 (2018). arXiv:1809.10756 http:\/\/arxiv.org\/abs\/1809.10756","journal-title":"CoRR"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2023.103010"},{"key":"e_1_3_2_30_2","unstructured":"Aki Vehtari A Gelman D Dunson D Rubin H Stern and JB Carlin. 2014. Bayesian data analysis."},{"key":"e_1_3_2_31_2","first-page":"770","volume-title":"Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2011, Fort Lauderdale, USA, April 11-13, 2011 (JMLR Proceedings, Vol. 15)","author":"Wingate David","year":"2011","unstructured":"David Wingate, Andreas Stuhlm\u00fcller, and Noah D. Goodman. 2011. Lightweight Implementations of Probabilistic Programming Languages Via Transformational Compilation. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2011, Fort Lauderdale, USA, April 11-13, 2011 (JMLR Proceedings, Vol. 15), Geoffrey J. Gordon, David B. Dunson, and Miroslav Dud\u00edk (Eds.). JMLR.org, 770\u2013778. http:\/\/proceedings.mlr.press\/v15\/wingate11a\/wingate11a.pdf"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/3054.001.0001"},{"key":"e_1_3_2_33_2","first-page":"1024","volume-title":"Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, AISTATS 2014, Reykjavik, Iceland, April 22-25, 2014 (JMLR Workshop and Conference Proceedings, Vol. 33)","author":"Wood Frank D.","year":"2014","unstructured":"Frank D. Wood, Jan-Willem van de Meent, and Vikash Mansinghka. 2014. A New Approach to Probabilistic Programming Inference. In Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, AISTATS 2014, Reykjavik, Iceland, April 22-25, 2014 (JMLR Workshop and Conference Proceedings, Vol. 33). JMLR.org, 1024\u20131032. http:\/\/proceedings.mlr.press\/v33\/wood14.html"},{"key":"e_1_3_2_34_2","first-page":"11534","volume-title":"Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event (Proceedings of Machine Learning Research, Vol. 119)","author":"Zhou Yuan","year":"2020","unstructured":"Yuan Zhou, Hongseok Yang, Yee Whye Teh, and Tom Rainforth. 2020. Divide, Conquer, and Combine: a New Inference Strategy for Probabilistic Programs with Stochastic Support. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event (Proceedings of Machine Learning Research, Vol. 119). PMLR, 11534\u201311545. http:\/\/proceedings.mlr.press\/v119\/zhou20e.html"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3828696","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3828696","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T08:10:10Z","timestamp":1790410210000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3828696"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8,17]]},"references-count":33,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2026,8,17]]}},"alternative-id":["10.1145\/3828696"],"URL":"https:\/\/doi.org\/10.1145\/3828696","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,8,17]]},"assertion":[{"value":"2026-02-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-05-13","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-08-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}