{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T14:05:59Z","timestamp":1787061959483,"version":"build-2736575974"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2018,7,30]],"date-time":"2018-07-30T00:00:00Z","timestamp":1532908800000},"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":[[2018,7,30]]},"abstract":"<jats:p>We present an architectural design of a library for Bayesian modelling and inference in modern functional programming languages. The novel aspect of our approach are modular implementations of existing state-of-the-art inference algorithms. Our design relies on three inherently functional features: higher-order functions, inductive data-types, and support for either type-classes or an expressive module system. We provide a performant Haskell implementation of this architecture, demonstrating that high-level and modular probabilistic programming can be added as a library in sufficiently expressive languages. We review the core abstractions in this architecture: inference representations, inference transformations, and inference representation transformers. We then implement concrete instances of these abstractions, counterparts to particle filters and Metropolis-Hastings samplers, which form the basic building blocks of our library. By composing these building blocks we obtain state-of-the-art inference algorithms: Resample-Move Sequential Monte Carlo, Particle Marginal Metropolis-Hastings, and Sequential Monte Carlo Squared. We evaluate our implementation against existing probabilistic programming systems and find it is already competitively performant, although we conjecture that existing functional programming optimisation techniques could reduce the overhead associated with the abstractions we use. We show that our modular design enables deterministic testing of inherently stochastic Monte Carlo algorithms. Finally, we demonstrate using OCaml that an expressive module system can also implement our design.<\/jats:p>","DOI":"10.1145\/3236778","type":"journal-article","created":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T15:41:18Z","timestamp":1533051678000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Functional programming for modular Bayesian inference"],"prefix":"10.1145","volume":"2","author":[{"given":"Adam","family":"\u015acibior","sequence":"first","affiliation":[{"name":"University of Cambridge, UK \/ MPI T\u00fcbingen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ohad","family":"Kammar","sequence":"additional","affiliation":[{"name":"University of Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zoubin","family":"Ghahramani","sequence":"additional","affiliation":[{"name":"University of Cambridge, UK \/ Uber AI Labs, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,7,30]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Mart\u00edn Abadi Ashish Agarwal Paul Barham Eugene Brevdo Zhifeng Chen Craig Citro Greg S. Corrado Andy Davis Jeffrey Dean Matthieu Devin Sanjay Ghemawat Ian Goodfellow Andrew Harp Geoffrey Irving Michael Isard Yangqing Jia Rafal Jozefowicz Lukasz Kaiser Manjunath Kudlur Josh Levenberg Dan Man\u00e9 Rajat Monga Sherry Moore Derek Murray Chris Olah Mike Schuster Jonathon Shlens Benoit Steiner Ilya Sutskever Kunal Talwar Paul Tucker Vincent Vanhoucke Vijay Vasudevan Fernanda Vi\u00e9gas Oriol Vinyals Pete Warden Martin Wattenberg Martin Wicke Yuan Yu and Xiaoqiang Zheng. 2015. TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems. (2015). https:\/\/www.tensorflow.org\/ Software available from tensorflow.org.  Mart\u00edn Abadi Ashish Agarwal Paul Barham Eugene Brevdo Zhifeng Chen Craig Citro Greg S. Corrado Andy Davis Jeffrey Dean Matthieu Devin Sanjay Ghemawat Ian Goodfellow Andrew Harp Geoffrey Irving Michael Isard Yangqing Jia Rafal Jozefowicz Lukasz Kaiser Manjunath Kudlur Josh Levenberg Dan Man\u00e9 Rajat Monga Sherry Moore Derek Murray Chris Olah Mike Schuster Jonathon Shlens Benoit Steiner Ilya Sutskever Kunal Talwar Paul Tucker Vincent Vanhoucke Vijay Vasudevan Fernanda Vi\u00e9gas Oriol Vinyals Pete Warden Martin Wattenberg Martin Wicke Yuan Yu and Xiaoqiang Zheng. 2015. TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems. (2015). https:\/\/www.tensorflow.org\/ Software available from tensorflow.org."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2011.49"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9868.2009.00736.x"},{"key":"e_1_2_2_4_1","volume-title":"Bayesian Reasoning and Machine Learning","author":"Barber David","unstructured":"David Barber . 2012. Bayesian Reasoning and Machine Learning . Cambridge University Press . David Barber. 2012. Bayesian Reasoning and Machine Learning. Cambridge University Press."},{"key":"e_1_2_2_5_1","volume-title":"Pattern Recognition and Machine Learning","author":"Bishop Christopher","unstructured":"Christopher Bishop . 2006. Pattern Recognition and Machine Learning . Springer-Verlag New York . http:\/\/www.springer.com\/ gb\/book\/9780387310732 Christopher Bishop. 2006. Pattern Recognition and Machine Learning. Springer-Verlag New York. http:\/\/www.springer.com\/ gb\/book\/9780387310732"},{"key":"e_1_2_2_6_1","volume-title":"The Monad Reader","author":"Bla\u017eevi\u0107 Mario","year":"2011","unstructured":"Mario Bla\u017eevi\u0107 . 2011. Coroutine Pipelines . The Monad Reader ( 2011 ), 29\u201350. Issue 19. Mario Bla\u017eevi\u0107. 2011. Coroutine Pipelines. The Monad Reader (2011), 29\u201350. Issue 19."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796809007205"},{"key":"e_1_2_2_8_1","volume-title":"Stan: A probabilistic programming language. Journal of Statistical Software 76","author":"Carpenter Bob","year":"2017","unstructured":"Bob Carpenter , Andrew Gelman , Matthew D. Hoffman , Daniel Lee , Ben Goodrich , Michael Betancourt , Marcus Brubaker , Jiqiang Guo , Peter Li , and Allen Riddell . 2017 . Stan: A probabilistic programming language. Journal of Statistical Software 76 (2017). Bob Carpenter, Andrew Gelman, Matthew D. Hoffman, Daniel Lee, Ben Goodrich, Michael Betancourt, Marcus Brubaker, Jiqiang Guo, Peter Li, and Allen Riddell. 2017. Stan: A probabilistic programming language. Journal of Statistical Software 76 (2017)."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926354.1926358"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9868.2012.01046.x"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1291151.1291199"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1977.tb01600.x"},{"key":"e_1_2_2_13_1","volume-title":"Johansen","author":"Doucet Arnaud","year":"2011","unstructured":"Arnaud Doucet and Adam M . Johansen . 2011 . A Tutorial on Particle Filtering and Smoothing: Fifteen years later. In The Oxford Handbook of Nonlinear Filtering, Dan Crisan and Boris Rozovskii (Eds.). Oxford University Press , Chapter 8. Arnaud Doucet and Adam M. Johansen. 2011. A Tutorial on Particle Filtering and Smoothing: Fifteen years later. In The Oxford Handbook of Nonlinear Filtering, Dan Crisan and Boris Rozovskii (Eds.). Oxford University Press, Chapter 8."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-9868.00280"},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"W. R. Gilks A. Thomas and D. J. Spiegelhalter. 1994. A Language and Program for Complex Bayesian Modelling. Journal of the Royal Statistical Society. Series D 43 (1994).  W. R. Gilks A. Thomas and D. J. Spiegelhalter. 1994. A Language and Program for Complex Bayesian Modelling. Journal of the Royal Statistical Society. Series D 43 (1994).","DOI":"10.2307\/2348941"},{"key":"e_1_2_2_16_1","unstructured":"Noah Goodman Vikash Mansinghka Daniel Roy Keith Bonawitz and Joshua Tenenbaum. 2008. Church: a language for generative models. In UAI. http:\/\/cocolab.stanford.edu\/papers\/GoodmanEtAl2008-UncertaintyInArtificialIntelligence.pdf   Noah Goodman Vikash Mansinghka Daniel Roy Keith Bonawitz and Joshua Tenenbaum. 2008. Church: a language for generative models. In UAI. http:\/\/cocolab.stanford.edu\/papers\/GoodmanEtAl2008-UncertaintyInArtificialIntelligence.pdf"},{"key":"e_1_2_2_17_1","unstructured":"Noah Goodman and Andreas Stuhlm\u00fcller. 2014. Design and Implementation of Probabilistic Programming Languages. http:\/\/dippl.org . (2014).  Noah Goodman and Andreas Stuhlm\u00fcller. 2014. Design and Implementation of Probabilistic Programming Languages. http:\/\/dippl.org . (2014)."},{"key":"e_1_2_2_18_1","doi-asserted-by":"crossref","unstructured":"Chris Heunen Ohad Kammar Sam Staton and Hongseok Yang. 2017. A convenient category for higher-order probability theory. In LiCS. http:\/\/ieeexplore.ieee.org\/document\/8005137\/  Chris Heunen Ohad Kammar Sam Staton and Hongseok Yang. 2017. A convenient category for higher-order probability theory. In LiCS. http:\/\/ieeexplore.ieee.org\/document\/8005137\/","DOI":"10.1109\/LICS.2017.8005137"},{"key":"e_1_2_2_19_1","doi-asserted-by":"crossref","unstructured":"Sheng Liang and Paul Hudak. 1996. Modular Denotational Semantics for Compiler Construction. In ESOP.   Sheng Liang and Paul Hudak. 1996. Modular Denotational Semantics for Compiler Construction. In ESOP.","DOI":"10.1007\/3-540-61055-3_39"},{"key":"e_1_2_2_20_1","volume-title":"Information Theory, Inference and Learning Algorithms","author":"MacKay David J. C.","unstructured":"David J. C. MacKay . 2003. Information Theory, Inference and Learning Algorithms . Cambridge University Press . www. inference.org.uk\/itila\/book.html David J. C. MacKay. 2003. Information Theory, Inference and Learning Algorithms. Cambridge University Press. www. inference.org.uk\/itila\/book.html"},{"key":"e_1_2_2_21_1","unstructured":"Vikash Mansinghka Daniel Selsam and Yura Perov. 2014. Venture: a higher-order probabilistic programming platform with programmable inference. arXiv:1404.0099. (2014).  Vikash Mansinghka Daniel Selsam and Yura Perov. 2014. Venture: a higher-order probabilistic programming platform with programmable inference. arXiv:1404.0099. (2014)."},{"key":"e_1_2_2_22_1","unstructured":"Tom Minka John Winn J. Guiver S. Webster Y. Zaykov B. Yangel A. Spengler and J. Bronskill. 2014. Infer.NET 2.6. Microsoft Research Cambridge. http:\/\/research.microsoft.com\/infernet. (2014).  Tom Minka John Winn J. Guiver S. Webster Y. Zaykov B. Yangel A. Spengler and J. Bronskill. 2014. Infer.NET 2.6. Microsoft Research Cambridge. http:\/\/research.microsoft.com\/infernet. (2014)."},{"key":"e_1_2_2_23_1","unstructured":"Lawrence M. Murray. 2013. Bayesian State-Space Modelling on High-Performance Hardware Using LibBi. arXiv:1306.3277. (2013).  Lawrence M. Murray. 2013. Bayesian State-Space Modelling on High-Performance Hardware Using LibBi. arXiv:1306.3277. (2013)."},{"key":"e_1_2_2_24_1","volume-title":"Handbook of Markov Chain Monte Carlo","author":"Neal Radford M.","unstructured":"Radford M. Neal . 2010. MCMC using Hamiltonian dynamics . In Handbook of Markov Chain Monte Carlo . Chapman and Hall . Radford M. Neal. 2010. MCMC using Hamiltonian dynamics. In Handbook of Markov Chain Monte Carlo. Chapman and Hall."},{"key":"e_1_2_2_25_1","unstructured":"Aditya V. Nori Chung-Kil Hur Sriram K. Rajamani and Selva Samuel. 2014. R2: An Efficient MCMC Sampler for Probabilistic Programs. In AAAI.   Aditya V. Nori Chung-Kil Hur Sriram K. Rajamani and Selva Samuel. 2014. R2: An Efficient MCMC Sampler for Probabilistic Programs. In AAAI."},{"key":"e_1_2_2_26_1","volume-title":"Fonnesbeck","author":"Patil Anand","year":"2010","unstructured":"Anand Patil , David Huard , and Christopher J . Fonnesbeck . 2010 . PyMC: Bayesian Stochastic Modelling in Python. Journal of Statistical Software 35 (2010). Anand Patil, David Huard, and Christopher J. Fonnesbeck. 2010. PyMC: Bayesian Stochastic Modelling in Python. Journal of Statistical Software 35 (2010)."},{"key":"e_1_2_2_27_1","volume-title":"IBAL: A Probabilistic Rational Programming Language. In IJCAI.","author":"Pfeffer Avi","year":"2001","unstructured":"Avi Pfeffer . 2001 . IBAL: A Probabilistic Rational Programming Language. In IJCAI. Avi Pfeffer. 2001. IBAL: A Probabilistic Rational Programming Language. In IJCAI."},{"key":"e_1_2_2_28_1","unstructured":"Avi Pfeffer. 2015. Practical Probabilistic Programming. Manning. https:\/\/www.manning.com\/books\/ practical-probabilistic-programming   Avi Pfeffer. 2015. Practical Probabilistic Programming. Manning. https:\/\/www.manning.com\/books\/ practical-probabilistic-programming"},{"key":"e_1_2_2_29_1","volume-title":"AISTATS","author":"Ranganath Rajesh","unstructured":"Rajesh Ranganath , Sean Gerrish , and David Blei . 2014. Black-Box Variational Inference . In AISTATS . http:\/\/www.jmlr.org\/ proceedings\/papers\/v33\/ranganath14.html Rajesh Ranganath, Sean Gerrish, and David Blei. 2014. Black-Box Variational Inference. In AISTATS. http:\/\/www.jmlr.org\/ proceedings\/papers\/v33\/ranganath14.html"},{"key":"e_1_2_2_30_1","volume-title":"Goodman","author":"Ritchie Daniel","year":"2016","unstructured":"Daniel Ritchie , Andreas Stuhlm\u00fcller , and Noah D . Goodman . 2016 . C3: Lightweight Incrementalized MCMC for Probabilistic Programs using Continuations and Callsite Caching. In AISTATS. http:\/\/proceedings.mlr.press\/v51\/ritchie16.html Daniel Ritchie, Andreas Stuhlm\u00fcller, and Noah D. Goodman. 2016. C3: Lightweight Incrementalized MCMC for Probabilistic Programs using Continuations and Callsite Caching. In AISTATS. http:\/\/proceedings.mlr.press\/v51\/ritchie16.html"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2804302.2804317"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158148"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54434-1_32"},{"key":"e_1_2_2_34_1","volume-title":"Machine Learning and Knowledge Discovery in Databases, Albert Bifet, Michael May, Bianca Zadrozny, Ricard Gavalda","author":"Tolpin David","unstructured":"David Tolpin , Jan-Willem van de Meent , and Frank Wood . 2015. Probabilistic Programming in Anglican . In Machine Learning and Knowledge Discovery in Databases, Albert Bifet, Michael May, Bianca Zadrozny, Ricard Gavalda , Dino Pedreschi , Francesco Bonchi, Jaime Cardoso, and Myra Spiliopoulou (Eds.). Lecture Notes in Computer Science, Vol. 9286 . Springer International Publishing , 308\u2013311. David Tolpin, Jan-Willem van de Meent, and Frank Wood. 2015. Probabilistic Programming in Anglican. In Machine Learning and Knowledge Discovery in Databases, Albert Bifet, Michael May, Bianca Zadrozny, Ricard Gavalda, Dino Pedreschi, Francesco Bonchi, Jaime Cardoso, and Myra Spiliopoulou (Eds.). Lecture Notes in Computer Science, Vol. 9286. Springer International Publishing, 308\u2013311."},{"key":"e_1_2_2_35_1","volume-title":"Blei","author":"Tran Dustin","year":"2017","unstructured":"Dustin Tran , Matthew D. Hoffman , Rif A. Saurous , Eugene Brevdo , Kevin Murphy , and David M . Blei . 2017 . Deep Probabilistic Programming. In ICLR. Dustin Tran, Matthew D. Hoffman, Rif A. Saurous, Eugene Brevdo, Kevin Murphy, and David M. Blei. 2017. Deep Probabilistic Programming. In ICLR."},{"key":"e_1_2_2_36_1","volume-title":"Owl: A General-Purpose Numerical Library in OCaml. arXiv:1707.09616.","author":"Wang Liang","year":"2017","unstructured":"Liang Wang . 2017 . Owl: A General-Purpose Numerical Library in OCaml. arXiv:1707.09616. (2017). Liang Wang. 2017. Owl: A General-Purpose Numerical Library in OCaml. arXiv:1707.09616. (2017)."},{"key":"e_1_2_2_37_1","volume-title":"Modular Implicits. ACM Workshop on ML 2014 post-proceedings. (September","author":"White Leo","year":"2015","unstructured":"Leo White , Fr\u00e9d\u00e9ric Bour , and Jeremy Yallop . 2015 . Modular Implicits. ACM Workshop on ML 2014 post-proceedings. (September 2015). Leo White, Fr\u00e9d\u00e9ric Bour, and Jeremy Yallop. 2015. Modular Implicits. ACM Workshop on ML 2014 post-proceedings. (September 2015)."},{"key":"e_1_2_2_38_1","unstructured":"David Wingate Andreas Stuhlm\u00fcller and Noah Goodman. 2011. Lightweight Implementations of Probabilistic Programming Languages Via Transformational Compilation. In AISTATS. https:\/\/web.stanford.edu\/~ngoodman\/papers\/ lightweight-mcmc-aistats2011.pdf The published version contains a serious bug in the algorithm description which was fixed in Revision 3 available from the authors page.  David Wingate Andreas Stuhlm\u00fcller and Noah Goodman. 2011. Lightweight Implementations of Probabilistic Programming Languages Via Transformational Compilation. In AISTATS. https:\/\/web.stanford.edu\/~ngoodman\/papers\/ lightweight-mcmc-aistats2011.pdf The published version contains a serious bug in the algorithm description which was fixed in Revision 3 available from the authors page."},{"key":"e_1_2_2_39_1","volume-title":"AISTATS","author":"Wood Frank","unstructured":"Frank Wood , Jan-Willem van de Meent , and Vikash Mansinghka . 2014. A New Approach to Probabilistic Programming Inference . In AISTATS . http:\/\/www.robots.ox.ac.uk\/~fwood\/assets\/pdf\/Wood-AISTATS-2014.pdf Frank Wood, Jan-Willem van de Meent, and Vikash Mansinghka. 2014. A New Approach to Probabilistic Programming Inference. In AISTATS. http:\/\/www.robots.ox.ac.uk\/~fwood\/assets\/pdf\/Wood-AISTATS-2014.pdf"},{"key":"e_1_2_2_40_1","unstructured":"Robert Zinkov and Chung-chieh Shan. 2017. Composing inference algorithms as program transformations. In UAI.  Robert Zinkov and Chung-chieh Shan. 2017. Composing inference algorithms as program transformations. In UAI."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3236778","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3236778","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:41:28Z","timestamp":1750268488000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3236778"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,30]]},"references-count":40,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2018,7,30]]}},"alternative-id":["10.1145\/3236778"],"URL":"https:\/\/doi.org\/10.1145\/3236778","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,30]]},"assertion":[{"value":"2018-07-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}