{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T08:41:11Z","timestamp":1770280871792,"version":"3.49.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T00:00:00Z","timestamp":1634256000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["ONR-N00014-17-1-2699"],"award-info":[{"award-number":["ONR-N00014-17-1-2699"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2021,10,20]]},"abstract":"<jats:p>\n            <jats:italic>Probabilistic programming languages<\/jats:italic>\n            aid developers performing Bayesian inference. These languages provide programming constructs and tools for probabilistic modeling and automated inference. Prior work introduced a probabilistic programming language, ProbZelus, to extend probabilistic programming functionality to unbounded streams of data. This work demonstrated that the\n            <jats:italic>delayed sampling<\/jats:italic>\n            inference algorithm could be extended to work in a streaming context. ProbZelus showed that while delayed sampling could be effectively deployed on some programs, depending on the probabilistic model under consideration, delayed sampling is not guaranteed to use a bounded amount of memory over the course of the execution of the program.\n          <\/jats:p>\n          <jats:p>\n            In this paper, we the present conditions on a probabilistic program\u2019s execution under which delayed sampling will execute in bounded memory. The two conditions are dataflow properties of the core operations of delayed sampling: the\n            <jats:italic>m<\/jats:italic>\n            <jats:italic>-consumed property<\/jats:italic>\n            and the\n            <jats:italic>unseparated paths property<\/jats:italic>\n            . A program executes in bounded memory under delayed sampling if, and only if, it satisfies the\n            <jats:italic>m<\/jats:italic>\n            -consumed and unseparated paths properties. We propose a static analysis that abstracts over these properties to soundly ensure that any program that passes the analysis satisfies these properties, and thus executes in bounded memory under delayed sampling.\n          <\/jats:p>","DOI":"10.1145\/3485492","type":"journal-article","created":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T19:18:28Z","timestamp":1634325508000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Statically bounded-memory delayed sampling for probabilistic streams"],"prefix":"10.1145","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8396-1258","authenticated-orcid":false,"given":"Eric","family":"Atkinson","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillaume","family":"Baudart","sequence":"additional","affiliation":[{"name":"Inria, France \/ ENS, France \/ PSL University, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Louis","family":"Mandel","sequence":"additional","affiliation":[{"name":"IBM Research, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4918-4467","authenticated-orcid":false,"given":"Charles","family":"Yuan","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6928-0456","authenticated-orcid":false,"given":"Michael","family":"Carbin","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,10,15]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"crossref","unstructured":"Eric Atkinson Guillaume Baudart Louis Mandel Charles Yuan and Michael Carbin. 2021. Statically Bounded-Memory Delayed Sampling for Probabilistic Streams. In arXiv e-prints. arxiv:2109.12473  Eric Atkinson Guillaume Baudart Louis Mandel Charles Yuan and Michael Carbin. 2021. Statically Bounded-Memory Delayed Sampling for Probabilistic Streams. In arXiv e-prints. arxiv:2109.12473","DOI":"10.1145\/3485492"},{"key":"e_1_2_2_2_1","unstructured":"Eric Atkinson Cambridge Yang and Michael Carbin. 2018. Verifying Handcoded Probabilistic Inference Procedures. In arXiv e-prints.  Eric Atkinson Cambridge Yang and Michael Carbin. 2018. Verifying Handcoded Probabilistic Inference Procedures. In arXiv e-prints."},{"key":"e_1_2_2_3_1","volume-title":"Reactive Probabilistic Programming. In Conference on Programming Language Design and Implementation.","author":"Baudart Guillaume","year":"2020"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177699147"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3295500.3356180"},{"key":"e_1_2_2_6_1","article-title":"Pyro: Deep Universal Probabilistic Programming","volume":"20","author":"Bingham Eli","year":"2019","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_2_7_1","volume-title":"Streaming Variational Bayes. In International Conference on Neural Information Processing Systems.","author":"Broderick Tamara"},{"key":"e_1_2_2_8_1","volume-title":"SCADE 6: A formal language for embedded critical software development (invited paper)","author":"Cola\u00e7o Jean-Louis"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314642"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9868.2006.00553.x"},{"key":"e_1_2_2_11_1","volume-title":"Russell","author":"Doucet Arnaud","year":"2000"},{"key":"e_1_2_2_12_1","volume-title":"Russell","author":"Doucet Arnaud","year":"2000"},{"key":"e_1_2_2_13_1","unstructured":"Daniel Fink. 1997. A Compendium of Conjugate Priors.  Daniel Fink. 1997. A Compendium of Conjugate Priors."},{"key":"e_1_2_2_14_1","volume-title":"International Conference on Artificial Intelligence and Statistics.","author":"Ge Hong","year":"2018"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.3102\/1076998615606113"},{"key":"e_1_2_2_16_1","volume-title":"Conference on Uncertainty in Artificial Intelligence.","author":"Goodman Noah D."},{"key":"e_1_2_2_17_1","unstructured":"Noah D Goodman and Andreas Stuhlm\u00fcller. 2014. The Design and Implementation of Probabilistic Programming Languages. http:\/\/dippl.org Accessed: 2020-10-30.  Noah D Goodman and Andreas Stuhlm\u00fcller. 2014. The Design and Implementation of Probabilistic Programming Languages. http:\/\/dippl.org Accessed: 2020-10-30."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535850"},{"key":"e_1_2_2_19_1","volume-title":"Saraswat","author":"Gupta Vineet","year":"1997"},{"key":"e_1_2_2_20_1","volume-title":"Compiling Markov Chain Monte Carlo Algorithms for Probabilistic Modeling. In Conference on Programming Language Design and Implementation.","author":"Huang Daniel","year":"2017"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1115\/1.3662552"},{"key":"e_1_2_2_22_1","volume-title":"Probabilistic Graphical Models - Principles and Techniques","author":"Koller Daphne"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1998.10473765"},{"key":"e_1_2_2_24_1","volume-title":"Delayed sampling in the probabilistic programming language Anglican. Master\u2019s thesis","author":"Lund\u00e9n Daniel"},{"key":"e_1_2_2_25_1","volume-title":"Probabilistic Programming with Programmable Inference. In Conference on Programming Language Design and Implementation.","author":"Mansingkha Vikash","year":"2018"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1955.tb03788.x"},{"key":"e_1_2_2_27_1","volume-title":"BLOG: Probabilistic models with unknown objects. Statistical relational learning.","author":"Milch Brian","year":"2007"},{"key":"e_1_2_2_28_1","volume-title":"Expectation Propagation for Approximate Bayesian Inference. In Conference in Uncertainty in Artificial Intelligence.","author":"Minka Thomas P.","year":"2001"},{"key":"e_1_2_2_29_1","volume-title":"Delayed Sampling and Automatic Rao-Blackwellization of Probabilistic Programs. In International Conference on Artificial Intelligence and Statistics.","author":"Murray Lawrence M."},{"key":"e_1_2_2_30_1","volume-title":"Sch\u00f6n","author":"Murray Lawrence M.","year":"2018"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29604-3_5"},{"key":"e_1_2_2_32_1","volume-title":"Bounded Expectations: Resource Analysis for Probabilistic Programs. In Conference on Programming Language Design and Implementation.","author":"Ngo Van Chan","year":"2018"},{"key":"e_1_2_2_33_1","volume-title":"Efficient Synthesis of Probabilistic Programs. In Conference on Programming Language Design and Implementation.","author":"Nori Aditya V.","year":"2015"},{"key":"e_1_2_2_34_1","volume-title":"Figaro: An object-oriented probabilistic programming language. 137, 96.","author":"Pfeffer Avi","year":"2009"},{"key":"e_1_2_2_35_1","volume-title":"Mathematical control theory: deterministic finite dimensional systems. 6","author":"Sontag Eduardo D"},{"key":"e_1_2_2_36_1","volume-title":"Commutative Semantics for Probabilistic Programming. In European Symposium on Programming.","author":"Staton Sam","year":"2017"},{"key":"e_1_2_2_37_1","volume-title":"International Conference on Learning Representations.","author":"Tran Dustin","year":"2017"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485492","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485492","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485492","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:40Z","timestamp":1750191520000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485492"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,15]]},"references-count":37,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2021,10,20]]}},"alternative-id":["10.1145\/3485492"],"URL":"https:\/\/doi.org\/10.1145\/3485492","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,15]]},"assertion":[{"value":"2021-10-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}