{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,30]],"date-time":"2025-12-30T23:29:26Z","timestamp":1767137366181,"version":"build-2238731810"},"publisher-location":"Cham","reference-count":48,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031300431","type":"print"},{"value":"9783031300448","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,17]],"date-time":"2023-04-17T00:00:00Z","timestamp":1681689600000},"content-version":"vor","delay-in-days":106,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Probabilistic Programming Languages (PPLs) allow users to encode statistical inference problems and automatically apply an\n                    <jats:italic>inference algorithm<\/jats:italic>\n                    to solve them. Popular inference algorithms for PPLs, such as sequential Monte Carlo (SMC) and Markov chain Monte Carlo (MCMC), are built around\n                    <jats:italic>checkpoints<\/jats:italic>\n                    \u2014relevant events for the inference algorithm during the execution of a probabilistic program. Deciding the location of checkpoints is, in current PPLs, not done optimally. To solve this problem, we present a static analysis technique that automatically determines checkpoints in programs, relieving PPL users of this task. The analysis identifies a set of checkpoints that execute in the same order in every program run\u2014they are\n                    <jats:italic>aligned<\/jats:italic>\n                    . We formalize alignment, prove the correctness of the analysis, and implement the analysis as part of the higher-order functional PPL Miking CorePPL. By utilizing the alignment analysis, we design two novel inference algorithm variants:\n                    <jats:italic>aligned SMC<\/jats:italic>\n                    and\n                    <jats:italic>aligned lightweight MCMC<\/jats:italic>\n                    . We show, through real-world experiments, that they significantly improve inference execution time and accuracy compared to standard PPL versions of SMC and MCMC.\n                  <\/jats:p>","DOI":"10.1007\/978-3-031-30044-8_20","type":"book-chapter","created":{"date-parts":[[2023,4,16]],"date-time":"2023-04-16T16:28:25Z","timestamp":1681662505000},"page":"535-563","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Automatic Alignment in Higher-Order 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-9703-6912","authenticated-orcid":false,"given":"Gizem","family":"\u00c7aylak","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3929-251X","authenticated-orcid":false,"given":"Fredrik","family":"Ronquist","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":[[2023,4,17]]},"reference":[{"key":"20_CR1","unstructured":"Turing.jl. https:\/\/turing.ml\/dev\/ (2022), accessed: 2022-02-24"},{"key":"20_CR2","unstructured":"Miking DPPL. https:\/\/github.com\/miking-lang\/miking-dppl (2023), accessed: 2023-01-02"},{"key":"20_CR3","unstructured":"Bingham, E., Chen, J.P., Jankowiak, M., Obermeyer, F., Pradhan, N., Karaletsos, T., Singh, R., Szerlip, P., Horsfall, P., Goodman, N.D.: Pyro: Deep universal probabilistic programming. Journal of Machine Learning Research 20(28), 1\u20136 (2019)"},{"key":"20_CR4","unstructured":"Bishop, C.M.: Pattern Recognition and Machine Learning (Information Science and Statistics). Springer-Verlag (2006)"},{"key":"20_CR5","unstructured":"Blei, D.M., Ng, A.Y., Jordan, M.I.: Latent Dirichlet allocation. Journal of Machine Learning Research 3, 993\u20131022 (2003)"},{"key":"20_CR6","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":"20_CR7","doi-asserted-by":"crossref","unstructured":"Broman, D.: A vision of Miking: Interactive programmatic modeling, sound language composition, and self-learning compilation. In: Proceedings of the 12th ACM SIGPLAN International Conference on Software Language Engineering. pp. 55\u201360. Association for Computing Machinery (2019)","DOI":"10.1145\/3357766.3359531"},{"key":"20_CR8","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":"20_CR9","doi-asserted-by":"crossref","unstructured":"Cusumano-Towner, M., Bichsel, B., Gehr, T., Vechev, M., Mansinghka, V.K.: Incremental inference for probabilistic programs. In: Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation. pp. 571\u2013585. Association for Computing Machinery, New York, NY, USA (2018)","DOI":"10.1145\/3192366.3192399"},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"Cusumano-Towner, M.F., Saad, F.A., Lew, A.K., Mansinghka, V.K.: Gen: A general-purpose probabilistic programming system with programmable inference. In: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation. pp. 221\u2013236. Association for Computing Machinery (2019)","DOI":"10.1145\/3314221.3314642"},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"Flanagan, C., Sabry, A., Duba, B.F., Felleisen, M.: The essence of compiling with continuations. In: Proceedings of the ACM SIGPLAN 1993 Conference on Programming Language Design and Implementation. pp. 237\u2013247. Association for Computing Machinery, New York, NY, USA (1993)","DOI":"10.1145\/173262.155113"},{"key":"20_CR12","unstructured":"Ge, H., Xu, K., Ghahramani, Z.: Turing: a language for flexible probabilistic inference. In: International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain. pp. 1682\u20131690 (2018)"},{"key":"20_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":"20_CR14","unstructured":"Goodman, N.D., Stuhlm\u00fcller, A.: The design and implementation of probabilistic programming languages. http:\/\/dippl.org (2014), accessed: 2022-02-24"},{"key":"20_CR15","unstructured":"Goodman, N.D., Tenenbaum, J.B., Contributors, T.P.: Probabilistic Models of Cognition. http:\/\/probmods.org\/v2 (2016), accessed: 2022-06-10"},{"key":"20_CR16","unstructured":"Gothoskar, N., Cusumano-Towner, M., Zinberg, B., Ghavamizadeh, M., Pollok, F., Garrett, A., Tenenbaum, J., Gutfreund, D., Mansinghka, V.: 3DP3: 3D scene perception via probabilistic programming. In: Advances in Neural Information Processing Systems. vol.\u00a034, pp. 9600\u20139612. Curran Associates, Inc. (2021)"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Griffiths, T.L., Steyvers, M.: Finding scientific topics. Proceedings of the National academy of Sciences 101(suppl_1), 5228\u20135235 (2004)","DOI":"10.1073\/pnas.0307752101"},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"Huang, D., Tristan, J.B., Morrisett, G.: Compiling markov chain monte carlo algorithms for probabilistic modeling. In: Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation. p. 111\u2013125. Association for Computing Machinery, New York, NY, USA (2017)","DOI":"10.1145\/3062341.3062375"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Jetz, W., Thomas, G.H., Joy, J.B., Hartmann, K., Mooers, A.O.: The global diversity of birds in space and time. Nature 491(7424), 444\u2013448 (2012)","DOI":"10.1038\/nature11631"},{"key":"20_CR20","doi-asserted-by":"crossref","unstructured":"Kahn, G.: Natural semantics. In: Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science. pp. 22\u201339. Springer-Verlag, Berlin, Heidelberg (1987)","DOI":"10.1007\/BFb0039592"},{"key":"20_CR21","unstructured":"Kiselyov, O.: Problems of the lightweight implementation of probabilistic programming. In: Proceedings of Workshop on Probabilistic Programming Semantics (2016)"},{"key":"20_CR22","doi-asserted-by":"crossref","unstructured":"Kozen, D.: Semantics of probabilistic programs. Journal of Computer and System Sciences 22(3), 328\u2013350 (1981)","DOI":"10.1016\/0022-0000(81)90036-2"},{"key":"20_CR23","unstructured":"Lew, A., Agrawal, M., Sontag, D., Mansinghka, V.: PClean: Bayesian data cleaning at scale with domain-specific probabilistic programming. In: Proceedings of The 24th International Conference on Artificial Intelligence and Statistics. vol.\u00a0130, pp. 1927\u20131935. PMLR (2021)"},{"key":"20_CR24","doi-asserted-by":"crossref","unstructured":"Lund\u00e9n, D., Borgstr\u00f6m, J., Broman, D.: Correctness of sequential monte carlo inference for probabilistic programming languages. In: Programming Languages and Systems. pp. 404\u2013431. Springer International Publishing, Cham (2021)","DOI":"10.1007\/978-3-030-72019-3_15"},{"key":"20_CR25","doi-asserted-by":"crossref","unstructured":"Lund\u00e9n, D., \u00d6hman, J., Kudlicka, J., Senderov, V., Ronquist, F., Broman, D.: Compiling universal probabilistic programming languages with efficient parallel sequential monte carlo inference. In: Programming Languages and Systems. pp. 29\u201356. Springer International Publishing, Cham (2022)","DOI":"10.1007\/978-3-030-99336-8_2"},{"key":"20_CR26","doi-asserted-by":"publisher","unstructured":"Lund\u00e9n, D., Caylak, G., Ronquist, F., Broman, D.: Artifact: Automatic alignment in higher-order probabilistic programming languages (Jan 2023). https:\/\/doi.org\/10.5281\/zenodo.7572555","DOI":"10.5281\/zenodo.7572555"},{"key":"20_CR27","doi-asserted-by":"crossref","unstructured":"Lund\u00e9n, D., Caylak, G., Ronquist, F., Broman, D.: Automatic alignment in higher-order probabilistic programming languages. arXiv e-prints p. arXiv:2301.11664 (2023)","DOI":"10.1007\/978-3-031-30044-8_20"},{"key":"20_CR28","doi-asserted-by":"crossref","unstructured":"Maliet, O., Hartig, F., Morlon, H.: A model with many small shifts for estimating species-specific diversification rates. Nature Ecology & Evolution 3(7), 1086\u20131092 (2019)","DOI":"10.1038\/s41559-019-0908-0"},{"key":"20_CR29","doi-asserted-by":"crossref","unstructured":"Mansinghka, V.K., Schaechtle, U., Handa, S., Radul, A., Chen, Y., Rinard, M.: Probabilistic programming with programmable inference. In: Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation. p. 603\u2013616. Association for Computing Machinery, New York, NY, USA (2018)","DOI":"10.1145\/3192366.3192409"},{"key":"20_CR30","doi-asserted-by":"crossref","unstructured":"Midtgaard, J.: Control-flow analysis of functional programs. ACM Computing Surveys 44(3) (2012)","DOI":"10.1145\/2187671.2187672"},{"key":"20_CR31","doi-asserted-by":"crossref","unstructured":"Murray, L.M., Sch\u00f6n, T.B.: Automated learning with a probabilistic programming language: Birch. Annual Reviews in Control 46, 29\u201343 (2018)","DOI":"10.1016\/j.arcontrol.2018.10.013"},{"key":"20_CR32","doi-asserted-by":"crossref","unstructured":"Naesseth, C., Lindsten, F., Sch\u00f6n, T.: Elements of Sequential Monte Carlo. Foundations and Trends in Machine Learning Series, Now Publishers (2019)","DOI":"10.1561\/9781680836332"},{"key":"20_CR33","doi-asserted-by":"crossref","unstructured":"Nee, S.: Birth-death models in macroevolution. Annual Review of Ecology, Evolution, and Systematics 37(1), 1\u201317 (2006)","DOI":"10.1146\/annurev.ecolsys.37.091305.110035"},{"key":"20_CR34","doi-asserted-by":"crossref","unstructured":"Nielson, F., Nielson, H.R., Hankin, C.: Principles of Program Analysis. Springer-Verlag (1999)","DOI":"10.1007\/978-3-662-03811-6"},{"key":"20_CR35","doi-asserted-by":"crossref","unstructured":"Nori, A., Hur, C.K., Rajamani, S., Samuel, S.: R2: An efficient MCMC sampler for probabilistic programs. Proceedings of the AAAI Conference on Artificial Intelligence 28(1) (2014)","DOI":"10.1609\/aaai.v28i1.9060"},{"key":"20_CR36","unstructured":"Paige, B., Wood, F.: A compilation target for probabilistic programming languages. In: Xing, E.P., Jebara, T. (eds.) Proceedings of the 31st International Conference on Machine Learning. vol.\u00a032, pp. 1935\u20131943. PMLR, Bejing, China (22\u201324 Jun 2014)"},{"key":"20_CR37","unstructured":"Pierce, B.C.: Types and programming languages. MIT press (2002)"},{"key":"20_CR38","unstructured":"Ritchie, D., Stuhlm\u00fcller, A., Goodman, N.: C3: Lightweight incrementalized MCMC for probabilistic programs using continuations and callsite caching. In: Proceedings of the 19th International Conference on Artificial Intelligence and Statistics. vol.\u00a051, pp. 28\u201337. PMLR, Cadiz, Spain (2016)"},{"key":"20_CR39","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. Communications Biology 4(1), 244 (2021)","DOI":"10.1038\/s42003-021-01753-7"},{"key":"20_CR40","doi-asserted-by":"crossref","unstructured":"Sabelfeld, A., Myers, A.: Language-based information-flow security. IEEE Journal on Selected Areas in Communications 21(1), 5\u201319 (2003)","DOI":"10.1109\/JSAC.2002.806121"},{"key":"20_CR41","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":"20_CR42","unstructured":"Shivers, O.G.: Control-flow analysis of higher-order languages or taming lambda. Carnegie Mellon University (1991)"},{"key":"20_CR43","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":"20_CR44","unstructured":"Tran, D., Hoffman, M.D., Saurous, R.A., Brevdo, E., Murphy, K., Blei, D.M.: Deep probabilistic programming. In: International Conference on Learning Representations (2017)"},{"key":"20_CR45","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":"20_CR46","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":"20_CR47","unstructured":"Wingate, D., Stuhlmueller, A., Goodman, N.: Lightweight implementations of probabilistic programming languages via transformational compilation. In: Proceedings of the 14th International Conference on Artificial Intelligence and Statistics. vol.\u00a015, pp. 770\u2013778. PMLR (2011)"},{"key":"20_CR48","unstructured":"Wood, F., Meent, J.W., Mansinghka, V.: A new approach to probabilistic programming inference. In: Proceedings of the 17th International Conference on Artificial Intelligence and Statistics. vol.\u00a033, pp. 1024\u20131032. PMLR (2014)"}],"updated-by":[{"DOI":"10.1007\/978-3-031-30044-8_21","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T00:00:00Z","timestamp":1686182400000}}],"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-031-30044-8_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T05:06:03Z","timestamp":1686114363000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-30044-8_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031300431","9783031300448"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-30044-8_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"17 April 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"8 June 2023","order":2,"name":"change_date","label":"Change Date","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"Correction","order":3,"name":"change_type","label":"Change Type","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"A correction has been published.","order":4,"name":"change_details","label":"Change Details","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":"Paris","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 April 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 April 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"32","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"esop2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2023\/esop","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-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":"55","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":"20","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":"36% - 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","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":"5.5","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)"}}]}}