research-article

Public Access

Reactive probabilistic programming

Authors:

Guillaume Baudart,

Benjamin Sherman,

Michael CarbinAuthors Info & Claims

PLDI 2020: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 898 - 912

https://doi.org/10.1145/3385412.3386009

Published: 11 June 2020 Publication History

Abstract

Synchronous modeling is at the heart of programming languages like Lustre, Esterel, or Scade used routinely for implementing safety critical control software, e.g., fly-by-wire and engine control in planes. However, to date these languages have had limited modern support for modeling uncertainty --- probabilistic aspects of the software's environment or behavior --- even though modeling uncertainty is a primary activity when designing a control system.

In this paper we present ProbZelus the first synchronous probabilistic programming language. ProbZelus conservatively provides the facilities of a synchronous language to write control software, with probabilistic constructs to model uncertainties and perform inference-in-the-loop.

We present the design and implementation of the language. We propose a measure-theoretic semantics of probabilistic stream functions and a simple type discipline to separate deterministic and probabilistic expressions. We demonstrate a semantics-preserving compilation into a first-order functional language that lends itself to a simple presentation of inference algorithms for streaming models. We also redesign the delayed sampling inference algorithm to provide efficient streaming inference. Together with an evaluation on several reactive applications, our results demonstrate that ProbZelus enables the design of reactive probabilistic applications and efficient, bounded memory inference.

References

[1]

Guillaume Baudart, Louis Mandel, Eric Atkinson, Benjamin Sherman, Marc Pouzet, and Michael Carbin. 2020.

[2]

Reactive Probabilistic Programming. CoRR abs/1908.07563 (2020).

[3]

Albert Benveniste, Paul Caspi, Stephen A. Edwards, Nicolas Halbwachs, Paul Le Guernic, and Robert de Simone. 2003. The synchronous languages 12 years later. Proc. IEEE 91, 1 (2003), 64–83.

[4]

Keni Bernardin and Rainer Stiefelhagen. 2008.

[5]

Evaluating Multiple Object Tracking Performance: The CLEAR MOT Metrics. EURASIP J. Image and Video Processing 2008 (2008).

[6]

Gérard Berry. 1989.

[7]

Real Time Programming: Special Purpose or General Purpose Languages. In IFIP Congress. North-Holland/IFIP, 11– 17.

[8]

Dariusz Biernacki, Jean-Louis Colaço, Grégoire Hamon, and Marc Pouzet. 2008. Clock-directed modular code generation for synchronous data-flow languages. In LCTES. ACM, 121–130.

[9]

Eli Bingham, Jonathan P. Chen, Martin Jankowiak, Fritz Obermeyer, Neeraj Pradhan, Theofanis Karaletsos, Rohit Singh, Paul A. Szerlip, Paul Horsfall, and Noah D. Goodman. 2019.

[10]

Pyro: Deep Universal Probabilistic Programming. J. Mach. Learn. Res. 20 (2019), 28:1–28:6.

[11]

Timothy Bourke and Marc Pouzet. 2013.

[12]

Zélus: a synchronous language with ODEs. In HSCC. ACM, 113–118.

[13]

Tamara Broderick, Nicholas Boyd, Andre Wibisono, Ashia C. Wilson, and Michael I. Jordan. 2013.

[14]

Streaming Variational Bayes. In NIPS. 1727–1735.

[15]

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. J. Statistical Software 76, 1 (2017), 1–37.

[16]

Paul Caspi. 1992. Clocks in Dataflow Languages. Theor. Comput. Sci. 94, 1 (1992), 125–140.

Digital Library

[17]

Paul Caspi and Marc Pouzet. 1998. A Co-iterative Characterization of Synchronous Stream Functions. In CMCS (Electronic Notes in Theoretical Computer Science), Vol. 11. Elsevier, 1–21.

[18]

Jean-Louis Colaço, Grégoire Hamon, and Marc Pouzet. 2006. Mixing signals and modes in synchronous data-flow systems. In EMSOFT. ACM, 73–82. Reactive Probabilistic Programming PLDI ’20, June 15–20, 2020, London, UK

[19]

Jean-Louis Colaço, Bruno Pagano, and Marc Pouzet. 2017. SCADE 6: A formal language for embedded critical software development (invited paper). In TASE. IEEE Computer Society, 1–11.

[20]

Jean-Louis Colaço and Marc Pouzet. 2004. Type-based initialization analysis of a synchronous dataflow language. Int. J. Softw. Tools Technol. Transf. 6, 3 (2004), 245–255.

Digital Library

[21]

Pierre Del Moral, Arnaud Doucet, and Ajay Jasra. 2006.

[22]

Sequential Monte Carlo samplers. J. Royal Statistical Society: Series B (Statistical Methodology) 68, 3 (2006), 411–436.

[23]

Arnaud Doucet, Nando de Freitas, Kevin P. Murphy, and Stuart J. Russell. 2000. Rao-Blackwellised Particle Filtering for Dynamic Bayesian Networks. In UAI. Morgan Kaufmann, 176–183.

Digital Library

[24]

Timon Gehr, Sasa Misailovic, and Martin T. Vechev. 2016. PSI: Exact Symbolic Inference for Probabilistic Programs. In CAV (1) (Lecture Notes in Computer Science), Vol. 9779. Springer, 62–83.

[25]

Noah D. Goodman and Andreas Stuhlmüller. 2014. The Design and Implementation of Probabilistic Programming Languages. http: //dippl.org Accessed April 2020.

[26]

N. J. Gordon, D. J. Salmond, and A. F. M. Smith. 1993. Novel approach to nonlinear/non-Gaussian Bayesian state estimation. IEE Proceedings F - Radar and Signal Processing 140, 2, 107–113.

[27]

N. Halbwachs, P. Caspi, P. Raymond, and D. Pilaud. 1991. The Synchronous Dataflow Programming Language Lustre. Proc. IEEE 79, 9 (September 1991), 1305–1320.

[28]

Daniel Huang, Jean-Baptiste Tristan, and Greg Morrisett. 2017. Compiling Markov chain Monte Carlo algorithms for probabilistic modeling. In PLDI. ACM, 111–125.

[29]

Gilles Kahn. 1974. The Semantics of a Simple Language for Parallel Programming. In IFIP Congress. North-Holland, 471–475.

[30]

Daniel Lundén. 2017.

[31]

Delayed sampling in the probabilistic programming language Anglican. Master’s thesis. KTH Royal Institute of Technology.

[32]

Daniel Lundén, David Broman, Fredrik Ronquist, and Lawrence M. Murray. 2018. Automatic Alignment of Sequential Monte Carlo Inference in Higher-Order Probabilistic Programs. CoRR abs/1812.07439 (2018).

[33]

David Lunn, David Spiegelhalter, Andrew Thomas, and Nicky Best. 2009.

[34]

The BUGS project: Evolution, critique and future directions. Statistics in medicine 28, 25 (2009), 3049–3067.

[35]

Thomas P. Minka. 2001.

[36]

Expectation Propagation for approximate Bayesian inference. In UAI. Morgan Kaufmann, 362–369.

[37]

Lawrence M. Murray, Daniel Lundén, Jan Kudlicka, David Broman, and Thomas B. Schön. 2018. Delayed Sampling and Automatic Rao-Blackwellization of Probabilistic Programs. In AISTATS (Proceedings of Machine Learning Research), Vol. 84. PMLR, 1037–1046.

[38]

Lawrence M. Murray and Thomas B. Schön. 2018. Automated learning with a probabilistic programming language: Birch. Annual Reviews in Control 46 (2018), 29–43.

[39]

Praveen Narayanan, Jacques Carette, Wren Romano, Chung-chieh Shan, and Robert Zinkov. 2016.

[40]

Probabilistic Inference by Program Transformation in Hakaru (System Description). In FLOPS (Lecture Notes in Computer Science), Vol. 9613. Springer, 62–79.

[41]

Avi Pfeffer. 2005.

[42]

Functional Specification of Probabilistic Process Models. In AAAI. AAAI Press / The MIT Press, 663–669.

[43]

Avi Pfeffer. 2009. CTPPL: A Continuous Time Probabilistic Programming Language. In IJCAI. 1943–1950.

[44]

Pascal Raymond, Yvan Roux, and Erwan Jahier. 2008. Lutin: A Language for Specifying and Executing Reactive Scenarios. EURASIP Journal of Embedded Sytems 2008 (2008).

[45]

Daniel Ritchie, Andreas Stuhlmüller, and Noah D. Goodman. 2016. C3: Lightweight Incrementalized MCMC for Probabilistic Programs using Continuations and Callsite Caching. In AISTATS (JMLR Workshop and Conference Proceedings), Vol. 51. JMLR.org, 28–37.

[46]

Eduardo D Sontag. 2013.

[47]

Mathematical control theory: deterministic finite dimensional systems. Vol. 6. Springer Science & Business Media.

[48]

Sam Staton. 2017. Commutative Semantics for Probabilistic Programming. In ESOP (Lecture Notes in Computer Science), Vol. 10201. Springer, 855–879.

[49]

David Tolpin, Jan-Willem van de Meent, Hongseok Yang, and Frank D. Wood. 2016. Design and Implementation of Probabilistic Programming Language Anglican. In IFL. ACM, 6:1–6:12.

[50]

Dustin Tran, Matthew D. Hoffman, Rif A. Saurous, Eugene Brevdo, Kevin Murphy, and David M. Blei. 2017. Deep Probabilistic Programming. In ICLR (Poster). OpenReview.net.

[51]

Yi Wu, Lei Li, Stuart J. Russell, and Rastislav Bodík. 2016. Swift: Compiled Inference for Probabilistic Programming Languages. In IJCAI. IJCAI/AAAI Press, 3637–3645.

Cited By

Caylak GLundén DSenderov VBroman DLaemmel RPereira JMosses P(2024)Statically and Dynamically Delayed Sampling for Typed Probabilistic Programming LanguagesProceedings of the 17th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3687997.3695634(157-170)Online publication date: 17-Oct-2024
https://dl.acm.org/doi/10.1145/3687997.3695634
Chen Jde Mendonça JAyele BBekele BJalili SSharma PWohlfeil NZhang YJeannin J(2024)Synchronous Programming with Refinement TypesProceedings of the ACM on Programming Languages10.1145/36746578:ICFP(938-972)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674657
Li JWang EZhang Y(2024)Compiling Probabilistic Programs for Variable Elimination with Information FlowProceedings of the ACM on Programming Languages10.1145/36564488:PLDI(1755-1780)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656448
Show More Cited By

Index Terms

Reactive probabilistic programming
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Data flow languages
2. Theory of computation
  1. Models of computation
    1. Streaming models

Recommendations

JAX based parallel inference for reactive probabilistic programming
LCTES 2022: Proceedings of the 23rd ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems

ProbZelus is a synchronous probabilistic language for the design of reactive probabilistic models in interaction with an environment. Reactive inference methods continuously learn distributions over the unobserved parameters of the model from ...
Interactive Programming of Reactive Systems

ReactiveML is a synchronous reactive extension of the general purpose programming language OCaml. It allows to program reactive systems such as video games or simulators. This paper presents rmltop, the ReactiveML counterpart of the OCaml toplevel. This ...
Statically bounded-memory delayed sampling for probabilistic streams

Probabilistic programming languages 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, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI 2020: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2020

1174 pages

ISBN:9781450376136

DOI:10.1145/3385412

General Chair:
Alastair F. Donaldson
Imperial College London, UK
,
Program Chair:
Emina Torlak
University of Washington, USA

Copyright © 2020 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

Office of Naval Research

Conference

PLDI '20

Sponsor:

SIGPLAN

PLDI '20: 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation

June 15 - 20, 2020

London, UK

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
828
Total Downloads

Downloads (Last 12 months)220
Downloads (Last 6 weeks)29

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Caylak GLundén DSenderov VBroman DLaemmel RPereira JMosses P(2024)Statically and Dynamically Delayed Sampling for Typed Probabilistic Programming LanguagesProceedings of the 17th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3687997.3695634(157-170)Online publication date: 17-Oct-2024
https://dl.acm.org/doi/10.1145/3687997.3695634
Chen Jde Mendonça JAyele BBekele BJalili SSharma PWohlfeil NZhang YJeannin J(2024)Synchronous Programming with Refinement TypesProceedings of the ACM on Programming Languages10.1145/36746578:ICFP(938-972)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674657
Li JWang EZhang Y(2024)Compiling Probabilistic Programs for Variable Elimination with Information FlowProceedings of the ACM on Programming Languages10.1145/36564488:PLDI(1755-1780)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656448
Ben Amara OHadouaj SMeneghetti N(2024)StarfishDB: A Query Execution Engine for Relational Probabilistic ProgrammingProceedings of the ACM on Management of Data10.1145/36549882:3(1-31)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654988
Lai JBurroni JGuan HSheldon DKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Automatically marginalized MCMC in probabilistic programmingProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619163(18301-18318)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3619163
Misra ALaurel JMisailovic S(2023)ViX: Analysis-driven Compiler for Efficient Low-Precision Variational Inference2023 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE56975.2023.10137324(1-6)Online publication date: Apr-2023
https://doi.org/10.23919/DATE56975.2023.10137324
Tassarotti JTristan J(2023)Verified Density Compilation for a Probabilistic Programming LanguageProceedings of the ACM on Programming Languages10.1145/35912457:PLDI(615-637)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591245
Benveniste ARaclet J(2023)Mixed Nondeterministic-Probabilistic AutomataDiscrete Event Dynamic Systems10.1007/s10626-023-00375-x33:4(455-505)Online publication date: 19-Oct-2023
https://doi.org/10.1007/s10626-023-00375-x
Atkinson EYuan CBaudart GMandel LCarbin M(2022)Semi-symbolic inference for efficient streaming probabilistic programmingProceedings of the ACM on Programming Languages10.1145/35633476:OOPSLA2(1668-1696)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563347
Baudart GMandel LTekin RGrosser TLee K(2022)JAX based parallel inference for reactive probabilistic programmingProceedings of the 23rd ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3519941.3535066(26-36)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1145/3519941.3535066
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents