{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T07:56:05Z","timestamp":1790927765024,"version":"4.1.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T00:00:00Z","timestamp":1576800000000},"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":[[2020,1]]},"abstract":"<jats:p>\n                    Modern probabilistic programming languages aim to formalize and automate key aspects of probabilistic modeling and inference. Many languages provide constructs for\n                    <jats:italic>programmable inference<\/jats:italic>\n                    that enable developers to improve inference speed and accuracy by tailoring an algorithm for use with a particular model or dataset. Unfortunately, it is easy to use these constructs to write unsound programs that appear to run correctly but produce incorrect results. To address this problem, we present a denotational semantics for programmable inference in higher-order probabilistic programming languages, along with a type system that ensures that well-typed inference programs are sound by construction. A central insight is that the type of a probabilistic expression can track the space of its possible execution traces, not just the type of value that it returns, as these traces are often the objects that inference algorithms manipulate. We use our semantics and type system to establish soundness properties of custom inference programs that use constructs for variational, sequential Monte Carlo, importance sampling, and Markov chain Monte Carlo inference.\n                  <\/jats:p>","DOI":"10.1145\/3371087","type":"journal-article","created":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T14:45:25Z","timestamp":1576853125000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Trace types and denotational semantics for sound programmable inference in probabilistic languages"],"prefix":"10.1145","volume":"4","author":[{"given":"Alexander K.","family":"Lew","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marco F.","family":"Cusumano-Towner","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benjamin","family":"Sherman","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Carbin","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vikash K.","family":"Mansinghka","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,12,20]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1020281327116"},{"key":"e_1_2_2_2_1","volume-title":"Verifying Handcoded Probabilistic Inference Procedures. (May","author":"Atkinson Eric","year":"2018"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2103656.2103721"},{"key":"e_1_2_2_4_1","article-title":"Pyro: Deep Universal Probabilistic Programming","author":"Bingham Eli","year":"2019","journal-title":"J. Mach. Learn. Res. 20, Article 28"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.18637\/jss.v076.i01"},{"key":"e_1_2_2_7_1","volume-title":"Probabilistic Programming Inference Via Intensional Semantics. In European Symposium on Programming (ESOP 2019)","volume":"11423","author":"Castellan Simon","year":"2019"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-9574.00056"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1214\/17-AAP1326"},{"key":"e_1_2_2_10_1","volume-title":"Advances in Neural Information Processing Systems 23 (NIPS","author":"Cortes Corinna","year":"2010"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3211346.3211350"},{"key":"e_1_2_2_12_1","volume-title":"Mansinghka","author":"Cusumano-Towner Marco F.","year":"2017"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314642"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-08-01238-X"},{"key":"e_1_2_2_15_1","volume-title":"Tom Rainforth, and Noah Goodman.","author":"Foster Adam","year":"2019"},{"key":"e_1_2_2_16_1","volume-title":"Workshop on Monte Carlo Methods for Modern Applications (NIPS 2010","author":"Freer Cameron E.","year":"2010"},{"key":"e_1_2_2_17_1","volume-title":"Foundations of Software Science and Computation Structures (FOSSACS 2016) (Lecture Notes in Computer Science), Bart Jacobs and Christof L\u00f6ding (Eds.)","author":"Fujii Soichiro"},{"key":"e_1_2_2_18_1","volume-title":"Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS 2018)","volume":"84","author":"Ge Hong","year":"2018"},{"key":"e_1_2_2_19_1","volume-title":"Rubin","author":"Gelman Andrew","year":"2013"},{"key":"e_1_2_2_20_1","volume-title":"Proceedings of the 24th Annual Conference on Uncertainty in Artificial Intelligence (UAI","author":"Goodman Noah","year":"2008"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/82.4.711"},{"key":"e_1_2_2_22_1","volume-title":"Variational Program Inference. (June","author":"Harik Georges","year":"2010"},{"key":"e_1_2_2_23_1","volume-title":"The Semantic Structure of Quasi-Borel Spaces. https:\/\/pps2018.sice.indiana.edu\/files\/2018\/01\/pps18- qbs- semantic- structure.pdf Workshop on Probabilistic Programming Semantics (PPS","author":"Heunen Chris","year":"2018"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/3329995.3330072"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062375"},{"key":"e_1_2_2_26_1","volume-title":"Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL","year":"2014"},{"key":"e_1_2_2_27_1","volume-title":"Towards Verified Stochastic Variational Inference for Probabilistic Programs. (July","author":"Lee Wonyeol","year":"2019"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1998.10473765"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192409"},{"key":"e_1_2_2_30_1","volume-title":"Venture: A Higher-Order Probabilistic Programming Platform with Programmable Inference. (April","author":"Mansinghka Vikash K.","year":"2014"},{"key":"e_1_2_2_31_1","volume-title":"Bayesian State-Space Modelling on High-performance Hardware Using Libbi. (June","author":"Murray Lawrence M.","year":"2013"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29604-3_5"},{"key":"e_1_2_2_34_1","volume-title":"Goodman","author":"Ritchie Daniel","year":"2016"},{"key":"e_1_2_2_35_1","volume-title":"Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS","volume":"89","author":"Roberts David A.","year":"2019"},{"key":"e_1_2_2_36_1","volume-title":"Artificial Intelligence: A Modern Approach (4 ed.). Pearson Education Limited.","author":"Russell Stuart","year":"2016"},{"key":"e_1_2_2_37_1","volume-title":"Proc. ACM Program. Lang. 3, POPL, Article 37","author":"Saad Feras A.","year":"2019"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290351"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2804302.2804317"},{"key":"e_1_2_2_40_1","volume-title":"Proc. ACM Program. Lang. 2, ICFP, Article 83 (July","author":"\u015acibior Adam","year":"2018"},{"key":"e_1_2_2_41_1","volume-title":"Proc. ACM Program. Lang. 2, POPL (Jan.","author":"\u015acibior Adam","year":"2017"},{"key":"e_1_2_2_42_1","unstructured":"Adam \u015acibior and Michael Thomas. 2019. Strongly Typed Tracing of Probabilistic Programs. https:\/\/www.cs.ubc.ca\/ ~ascibior\/assets\/pdf\/lafi19a.pdf  Adam \u015acibior and Michael Thomas. 2019. Strongly Typed Tracing of Probabilistic Programs. https:\/\/www.cs.ubc.ca\/ ~ascibior\/assets\/pdf\/lafi19a.pdf"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2935313"},{"key":"e_1_2_2_44_1","unstructured":"Sebastian Thrun Wolfram Burgard and Dieter Fox. 2005. Probabilistic Robotics. MIT Press.  Sebastian Thrun Wolfram Burgard and Dieter Fox. 2005. Probabilistic Robotics. MIT Press."},{"key":"e_1_2_2_45_1","volume-title":"Deep Probabilistic Programming. In International Conference on Learning Representations (ICLR","author":"Tran Dustin","year":"2017"},{"key":"e_1_2_2_46_1","volume-title":"Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS 2011)","volume":"15","author":"Wingate David","year":"2011"},{"key":"e_1_2_2_47_1","volume-title":"Automated Variational Inference in Probabilistic Programming. (Jan","author":"Wingate David","year":"2013"},{"key":"e_1_2_2_48_1","volume-title":"Proceedings of the 17th International Conference on Artificial Intelligence and Statistics (AISTATS 2014)","volume":"33","author":"Wood Frank","year":"2014"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889774"},{"key":"e_1_2_2_50_1","volume-title":"Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS 2019)","volume":"89","author":"Zhou Yuan","year":"2019"},{"key":"e_1_2_2_51_1","volume-title":"Composing Inference Algorithms as Program Transformations. (March","author":"Zinkov Robert","year":"2016"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371087","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3371087","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:05:43Z","timestamp":1750259143000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371087"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,20]]},"references-count":49,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1145\/3371087"],"URL":"https:\/\/doi.org\/10.1145\/3371087","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,20]]},"assertion":[{"value":"2019-12-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}