{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T02:14:42Z","timestamp":1775873682390,"version":"3.50.1"},"publisher-location":"Cham","reference-count":43,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030720186","type":"print"},{"value":"9783030720193","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,23]],"date-time":"2021-03-23T00:00:00Z","timestamp":1616457600000},"content-version":"vor","delay-in-days":81,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Probabilistic programming is an approach to reasoning under uncertainty by encoding inference problems as programs. In order to solve these inference problems, probabilistic programming languages (PPLs) employ different inference algorithms, such as sequential Monte Carlo (SMC), Markov chain Monte Carlo (MCMC), or variational methods. Existing research on such algorithms mainly concerns their implementation and efficiency, rather than the correctness of the algorithms themselves when applied in the context of expressive PPLs. To remedy this, we give a correctness proof for SMC methods in the context of an expressive PPL calculus, representative of popular PPLs such as WebPPL, Anglican, and Birch. Previous work have studied correctness of MCMC using an operational semantics, and correctness of SMC and MCMC in a denotational setting without term recursion. However, for SMC inference\u2014one of the most commonly used algorithms in PPLs as of today\u2014no formal correctness proof exists in an operational setting. In particular, an open question is if the resample locations in a probabilistic program affects the correctness of SMC. We solve this fundamental problem, and make four novel contributions: (i) we extend an untyped PPL lambda calculus and operational semantics to include explicit resample terms, expressing synchronization points in SMC inference; (ii) we prove, for the first time, that subject to mild restrictions, any placement of the explicit resample terms is valid for a generic form of SMC inference; (iii) as a result of (ii), our calculus benefits from classic results from the SMC literature: a law of large numbers and an unbiased estimate of the model evidence; and (iv) we formalize the bootstrap particle filter for the calculus and discuss how our results can be further extended to other SMC algorithms.<\/jats:p>","DOI":"10.1007\/978-3-030-72019-3_15","type":"book-chapter","created":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T14:03:10Z","timestamp":1616421790000},"page":"404-431","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Correctness of Sequential Monte Carlo Inference for Probabilistic Programming Languages"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3127-5640","authenticated-orcid":false,"given":"Daniel","family":"Lund\u00e9n","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5990-5742","authenticated-orcid":false,"given":"Johannes","family":"Borgstr\u00f6m","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8457-4105","authenticated-orcid":false,"given":"David","family":"Broman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,3,23]]},"reference":[{"key":"15_CR1","unstructured":"Bishop, C.M.: Pattern Recognition and Machine Learning (Information Science and Statistics). Springer-Verlag (2006)"},{"key":"15_CR2","unstructured":"Blei, D.M., Ng, A.Y., Jordan, M.I.: Latent Dirichlet allocation. Journal of Machine Learning Research 3, 993\u20131022 (2003)"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Borgstr\u00f6m, J., Dal\u00a0Lago, U., Gordon, A.D., Szymczak, M.: A lambda-calculus foundation for universal probabilistic programming. In: Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming. pp. 33\u201346. Association for Computing Machinery (2016)","DOI":"10.1145\/2951913.2951942"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Bournez, O., Garnier, F.: Proving positive almost-sure termination. In: Term Rewriting and Applications. pp. 323\u2013337. Springer Berlin Heidelberg (2005)","DOI":"10.1007\/978-3-540-32033-3_24"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"Carpenter, B., Gelman, A., Hoffman, M., Lee, D., Goodrich, B., Betancourt, M., Brubaker, M., Guo, J., Li, P., Riddell, A.: Stan: A probabilistic programming language. Journal of Statistical Software, Articles 76(1), 1\u201332 (2017)","DOI":"10.18637\/jss.v076.i01"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Chopin, N.: Central limit theorem for sequential Monte Carlo methods andits application to Bayesian inference. Annals of Statistics32(6), 2385\u20132411 (2004)","DOI":"10.1214\/009053604000000698"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"Del\u00a0Moral, P.: Feynman-Kac Formulae: Genealogical and Interacting Particle Systems With Applications, Probability and Its Applications, vol.\u00a0100.Springer-Verlag New York (2004)","DOI":"10.1007\/978-1-4684-9393-1"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Douc, R., Cappe, O.: Comparison of resampling schemes for particle filtering. In: Proceedings of the 4th International Symposium on Image and Signal Processing and Analysis. pp. 64\u201369 (2005)","DOI":"10.1109\/ISPA.2005.195385"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Doucet, A., de\u00a0Freitas, N., Gordon, N.: Sequential Monte Carlo Methods in Practice. Information Science and Statistics, Springer New York (2001)","DOI":"10.1007\/978-1-4757-3437-9"},{"key":"15_CR10","unstructured":"Doucet, A., Johansen, A.: The Oxford Handbook of Nonlinear Filtering, chap. A Tutorial on Particle Filtering and Smoothing: Fifteen Years Later. Oxford University Press (2009)"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"Gilks, W.R., Berzuini, C.: Following a moving target-Monte Carlo inference for dynamic Bayesian models. Journal of the Royal Statistical Society. Series B (Statistical Methodology) 63(1), 127\u2013146 (2001)","DOI":"10.1111\/1467-9868.00280"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Gilks, W., Richardson, S., Spiegelhalter, D.: Markov Chain Monte Carlo in Practice. Chapman & Hall\/CRC Interdisciplinary Statistics, Taylor & Francis (1995)","DOI":"10.1201\/b14835"},{"key":"15_CR13","unstructured":"Goodman, N.D., Mansinghka, V.K., Roy, D., Bonawitz, K., Tenenbaum, J.B.: Church: A language for generative models. In: Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence. pp. 220\u2013229. AUAI Press (2008)"},{"key":"15_CR14","unstructured":"Goodman, N.D., Stuhlm\u00fcller, A.: The design and implementation of probabilistic programming languages. http:\/\/dippl.org (2014), accessed: 2020-07-09"},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"Gordon, A.D., Aizatulin, M., Borgstrom, J., Claret, G., Graepel, T., Nori, A.V., Rajamani, S.K., Russo, C.: A model-learner pattern for Bayesian reasoning. In: Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. pp. 403\u2013416. Association for Computing Machinery (2013)","DOI":"10.1145\/2429069.2429119"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"Gordon, N.J., Salmond, D.J., Smith, A.F.M.: Novel approach to nonlinear\/non-Gaussian Bayesian state estimation. IEE Proceedings F -Radar and Signal Processing 140(2), 107\u2013113 (1993)","DOI":"10.1049\/ip-f-2.1993.0015"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Jacobs, J.: Paradoxes of probabilistic programming: And how to condition on events of measure zero with infinitesimal probabilities. Proceedings of the ACM on Programming Languages 5(POPL) (2021)","DOI":"10.1145\/3434339"},{"key":"15_CR18","doi-asserted-by":"crossref","unstructured":"Kozen, D.: Semantics of probabilistic programs. Journal of Computer and SystemSciences 22(3), 328\u2013350 (1981)","DOI":"10.1016\/0022-0000(81)90036-2"},{"key":"15_CR19","unstructured":"Kudlicka, J., Murray, L.M., Ronquist, F., Sch\u00f6n, T.B.: Probabilistic programming for birth-death models of evolution using an alive particle filter with delayed sampling. In: Conference on Uncertainty in Artificial Intelligence (2019)"},{"key":"15_CR20","doi-asserted-by":"crossref","unstructured":"Lund\u00e9n, D., Borgstr\u00f6m, J., Broman, D.: Correctness of sequential monte carlo inference for probabilistic programming languages. arXiv e-prints p. arXiv:2003.05191 (2020)","DOI":"10.26226\/morressier.604907f41a80aac83ca25d23"},{"key":"15_CR21","unstructured":"Lund\u00e9n, D., Broman, D., Ronquist, F., Murray, L.M.: Automatic alignment of sequential monte carlo inference in higher-order probabilistic programs. arXiv e-prints p. arXiv:1812.07439 (2018)"},{"key":"15_CR22","doi-asserted-by":"crossref","unstructured":"Mak, C., Ong, C.H.L., Paquet, H., Wagner, D.: Densities of almost-surely terminating probabilistic programs are differentiable almost everywhere. arXiv e-prints p. arXiv:2004.03924 (2020)","DOI":"10.1007\/978-3-030-72019-3_16"},{"key":"15_CR23","unstructured":"McDonald, J.N., Weiss, N.A.: A Course in Real Analysis. Elsevier Science (2012)"},{"key":"15_CR24","unstructured":"Murray, L., Lund\u00e9n, D., Kudlicka, J., Broman, D., Sch\u00f6n, T.: Delayed sampling and automatic rao-blackwellization of probabilistic programs. In: Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics. vol.\u00a084, pp. 1037\u20131046. PMLR (2018)"},{"key":"15_CR25","doi-asserted-by":"crossref","unstructured":"Murray, L.M., Sch\u00f6n, T.B.: Automated learning with a probabilistic programming language: Birch. arXiv e-prints p. arXiv:1810.01539 (2018)","DOI":"10.1016\/j.arcontrol.2018.10.013"},{"key":"15_CR26","doi-asserted-by":"crossref","unstructured":"Naesseth, C.A., Lindsten, F., Sch\u00f6n, T.B.: Elements of sequential monte carlo. arXiv e-prints p. arXiv:1903.04797 (2019)","DOI":"10.1561\/9781680836332"},{"key":"15_CR27","doi-asserted-by":"crossref","unstructured":"Park, S., Pfenning, F., Thrun, S.: A probabilistic language based on sampling functions. ACM Transactions on Programming Languages and Systems 31(1) (2008)","DOI":"10.1145\/1452044.1452048"},{"key":"15_CR28","doi-asserted-by":"crossref","unstructured":"Pitt, M.K., Shephard, N.: Filtering via simulation: Auxiliary particle filters. Journal of the American Statistical Association 94(446), 590\u2013599(1999)","DOI":"10.1080\/01621459.1999.10474153"},{"key":"15_CR29","doi-asserted-by":"crossref","unstructured":"Ronquist, F., Huelsenbeck, J.P.: MrBayes 3: Bayesian phylogenetic inferenceunder mixed models. Bioinformatics 19(12), 1572\u20131574 (2003)","DOI":"10.1093\/bioinformatics\/btg180"},{"key":"15_CR30","doi-asserted-by":"crossref","unstructured":"Ronquist, F., Kudlicka, J., Senderov, V., Borgstr\u00f6m, J., Lartillot, N., Lund\u00e9n, D., Murray, L., Sch\u00f6n, T.B., Broman, D.: Universal probabilistic programming offers a powerful approach to statistical phylogenetics. bioRxiv (2020)","DOI":"10.1101\/2020.06.16.154443"},{"key":"15_CR31","unstructured":"Russell, S., Norvig, P.: Artificial Intelligence: A Modern Approach. Prentice Hall Press, 3rd edn. (2009)"},{"key":"15_CR32","doi-asserted-by":"crossref","unstructured":"\u015acibior, A., Kammar, O., Ghahramani, Z.: Functional programming for modular Bayesian inference. Proceedings of the ACM on Programming Languages 2(ICFP) (2018)","DOI":"10.1145\/3236778"},{"key":"15_CR33","doi-asserted-by":"crossref","unstructured":"\u015acibior, A., Kammar, O., V\u00e1k\u00e1r, M., Staton, S., Yang, H., Cai, Y., Ostermann, K., Moss, S.K., Heunen, C., Ghahramani, Z.: Denotational validation of higher-order Bayesian inference. Proceedings of the ACM on Programming Languages 2(POPL) (2017)","DOI":"10.1145\/3158148"},{"key":"15_CR34","doi-asserted-by":"crossref","unstructured":"Staton, S.: Commutative semantics for probabilistic programming. In: Programming Languages and Systems. pp. 855\u2013879. Springer Berlin Heidelberg (2017)","DOI":"10.1007\/978-3-662-54434-1_32"},{"key":"15_CR35","doi-asserted-by":"crossref","unstructured":"Staton, S., Yang, H., Wood, F., Heunen, C., Kammar, O.: Semantics for probabilistic programming: Higher-order functions, continuous distributions, and soft constraints. In: Proceedings of the 31st Annual ACM\/IEEE Symposium on Logic in Computer Science. pp. 525\u2013534. Association for Computing Machinery (2016)","DOI":"10.1145\/2933575.2935313"},{"key":"15_CR36","unstructured":"Stuhlm\u00fcller, A., Hawkins, R.X.D., Siddharth, N., Goodman, N.D.: Coarse-to-fine sequential monte carlo for probabilistic programs. arXiv e-prints p. arXiv:1509.02962 (2015)"},{"key":"15_CR37","doi-asserted-by":"crossref","unstructured":"Tolpin, D., van\u00a0de Meent, J.W., Yang, H., Wood, F.: Design and implementation of probabilistic programming language Anglican. In: Proceedings of the 28th Symposium on the Implementation and Application of Functional Programming Languages. Association for Computing Machinery (2016)","DOI":"10.1145\/3064899.3064910"},{"key":"15_CR38","unstructured":"Tran, D., Kucukelbir, A., Dieng, A.B., Rudolph, M., Liang, D., Blei, D.M.: Edward: A library for probabilistic modeling, inference, and criticism. arXiv e-prints p. arXiv:1610.09787 (2016)"},{"key":"15_CR39","doi-asserted-by":"crossref","unstructured":"V\u00e1k\u00e1r, M., Kammar, O., Staton, S.: A domain theory for statistical probabilistic programming. Proceedings of the ACM on Programming Languages 3(POPL) (2019)","DOI":"10.1145\/3290349"},{"key":"15_CR40","unstructured":"V\u00e1k\u00e1r, M., Ong, L.: On s-finite measures and kernels. arXiv e-prints p. arXiv:1810.01837 (2018)"},{"key":"15_CR41","unstructured":"van de Meent, J.W., Paige, B., Yang, H., Wood, F.: An introduction to probabilistic programming. arXiv e-prints p. arXiv:1809.10756 (2018)"},{"key":"15_CR42","doi-asserted-by":"crossref","unstructured":"Wainwright, M.J., Jordan, M.I.: Graphical models, exponential families, andvariational inference. Foundations and Trends in Machine Learning1(1\u20132), 1\u2013305 (2008)","DOI":"10.1561\/2200000001"},{"key":"15_CR43","unstructured":"Wood, F., Meent, J.W., Mansinghka, V.: A new approach to probabilistic programming inference. In: Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics. vol.\u00a033, pp. 1024\u20131032. PMLR (2014)"}],"container-title":["Lecture Notes in Computer Science","Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-72019-3_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,25]],"date-time":"2021-10-25T03:06:32Z","timestamp":1635131192000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-72019-3_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030720186","9783030720193"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-72019-3_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"23 March 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ESOP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"European Symposium on Programming","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg City","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 March 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 April 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"esop2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2021\/esop","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"79","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"24","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3-5","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference took place virtually due to the COVID-19 pandemic","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}