CS 7470: Topics in Programming Languages: Foundations of Probabilistic Programming

• Instructor: Steven Holtzen, s.holtzen@northeastern.edu
• Session: Fall 2023
• Meeting time: Tuesday/Friday 9:50 am - 11:30 am (EST)
• Location: Ryder Hall 433 (email Steven for remote participation link)
• Office hours by appointment

Probabilistic programming languages (PPLs) use the syntax and semantics of programming languages to define probabilistic models. PPLs enable a diverse audience – data scientists, systems designers, medical doctors, etc. – to design and reason about probabilistic systems. PPLs are becoming a central topic in artificial intelligence and programming languages research, with increasing interest from industry and academia in designing and applying PPLs.

The goal of this course is to introduce the core ideas of probabilistic programming languages: probabilistic inference, semantics, program analysis, language design, and applications. The course will consist of formal lectures as well as research presentations by students surveying the modern landscape of developments in probabilistic programming. There will be a minor project involving implementing a probabilistic programming language, and a self-directed term project that aims to deeply explore some of the core ideas of probabilistic programming.

Evaluation & graded material

The course grade will be determined by the following graded material:

• 40% minor projects (20% each). The two minor projects are implementing a discrete PPL and implementing a continuous language.
• 20% participation.
• 40% final course project

All graded material is turned in on Canvas. Join our Slack!

Schedule

Date	Topic
Fri Sept 8	Introduction & Overview Lecture 1 Slides Reading: Lecture 1 course notes Recommended exercises if you have not programmed in OCaml before
Foundations
Tues Sept 12	Propositional Probability I: Semantics Lecture 2 notes Reading: Chapter 2 of (Darwiche, 2009) Supplemental Reading: Chapter 1 of (Biere et al., 2009)
Fri. Sept. 15	Propositional Probability II: A propositional PPL Lecture 3 notes Reading: Chapter 3 of (Darwiche, 2009) Supplemental Reading: Chapter 8.1, 8.2 of (Graham et al., 1989).
Tues. Sept 19	Propositional Probability III: Knowledge compilation Lecture 4 notes Reading: (Darwiche & Marquis, 2002) Supplemental reading: (Chavira & Darwiche, 2008)
Fri. Sept 22	Propositional Probability IV: Binary decision diagrams Lecture 5 notes
Tues. Sept 26	No Class (please attend Software Day)
Fri. Sept 29	Discrete probabilistic programming I: Syntax & semantics Lecture 6 notes
Tues Oct. 3	Discrete probabilistic programming II: Compilation Lecture 7 notes
Fri Oct. 6	Discrete probabilistic programming III: Observation Lecture 8 notes
Designing and Implementing a Continuous PPL
Tues Oct. 10	Discrete sampling semantics Reading: Chapter 2 up to section 2.4 of (Barthe et al., 2020) General reference on continuous probability: (Axler, 2020)
Fri Oct. 13	Importance sampling & continuous languages
Systems Week
Tues Oct. 17	Systems Week. See the Systems Week page.
Fri Oct. 20	Systems Week
Automatic Differentiation
Tues Oct. 24	Automatic Differentiation I: Theory Reading: Baydin, A. G., Pearlmutter, B. A., Radul, A. A., & Siskind, J. M. (2018). Automatic differentiation in machine learning: a survey. Journal of Marchine Learning Research, 18, 1–43.
Fri Oct. 27	Automatic Differentiation II: Applications Reading: Supplemental reading: (Lew et al., 2023)
Static Analysis
Tues Oct 31	Probabilistic Separation Logics I Reading: (Li et al., 2023) Supplemental reading: (O’Hearn, 2019), this textbook draft, (Reynolds, 2002)
Fri Nov. 3	Probabilistic Separation Logics II Reading: Continue (Li et al., 2023)
Tues Nov 7	Weakest Pre-Expectations Reading: (Morgan et al., 1996). This is a difficult read; do your best.
Fri Nov 10	Weakest Pre-Expectations II Reading: (Morgan et al., 1996) Supplemental Reading: (Olmedo et al., 2016)
Potpourri: A collection of modern topics in PPLs
Tues Nov. 13	Verified Inference Reading: (Beutner et al., 2022)
Fri Nov. 17	Generating Functions Reading: (Klinkenberg et al., 2020)
Tues Nov. 21	Non-Standard Semantics of PPLs Reading: (Baudart et al., 2020)
Fri Nov. 24	No Class (Fall Break)
Tues Nov. 28	Advanced Semantics of PPLs Reading: (Dash et al., 2023)
Fri Dec. 1	Discussion & Outlook
Final Presentations
Tues Dec. 4	Presentation Slot 1
Fri Dec. 8	Presentation Slot 2

See the reading list for more reading

Bibliography

1. Darwiche, A. (2009). Modeling and reasoning with Bayesian networks. Cambridge university press.
2. Biere, A., Heule, M., & van Maaren, H. (2009). Handbook of satisfiability (Vol. 185). IOS press.
3. Graham, R. L., Knuth, D. E., Patashnik, O., & Liu, S. (1989). Concrete mathematics: a foundation for computer science.
4. Darwiche, A., & Marquis, P. (2002). A knowledge compilation map. Journal of Artificial Intelligence Research, 17, 229–264.
5. Chavira, M., & Darwiche, A. (2008). On probabilistic inference by weighted model counting. Artificial Intelligence, 172(6-7), 772–799.
6. Barthe, G., Katoen, J.-P., & Silva, A. (2020). Foundations of probabilistic programming. Cambridge University Press.
7. Axler, S. (2020). Measure, integration & real analysis. Springer Nature.
8. Lew, A. K., Huot, M., Staton, S., & Mansinghka, V. K. (2023). ADEV: Sound automatic differentiation of expected values of probabilistic programs. Proceedings of the ACM on Programming Languages, 7(POPL), 121–153.
9. Li, J. M., Ahmed, A., & Holtzen, S. (2023). Lilac: a Modal Separation Logic for Conditional Probability. Proceedings of the ACM on Programming Languages, 7(PLDI), 148–171.
10. O’Hearn, P. (2019). Separation logic. Communications of the ACM, 62(2), 86–95.
11. Reynolds, J. C. (2002). Separation logic: A logic for shared mutable data structures. Proceedings 17th Annual IEEE Symposium on Logic in Computer Science, 55–74.
12. Morgan, C., McIver, A., & Seidel, K. (1996). Probabilistic predicate transformers. ACM Transactions on Programming Languages and Systems (TOPLAS), 18(3), 325–353.
13. Olmedo, F., Kaminski, B. L., Katoen, J.-P., & Matheja, C. (2016). Reasoning about recursive probabilistic programs. Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 672–681.
14. Beutner, R., Ong, C.-H. L., & Zaiser, F. (2022). Guaranteed bounds for posterior inference in universal probabilistic programming. Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation, 536–551.
15. Klinkenberg, L., Batz, K., Kaminski, B. L., Katoen, J.-P., Moerman, J., & Winkler, T. (2020). Generating functions for probabilistic programs. International Symposium on Logic-Based Program Synthesis and Transformation, 231–248.
16. Baudart, G., Mandel, L., Atkinson, E., Sherman, B., Pouzet, M., & Carbin, M. (2020). Reactive probabilistic programming. Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, 898–912.
17. Dash, S., Kaddar, Y., Paquet, H., & Staton, S. (2023). Affine monads and lazy structures for bayesian programming. Proceedings of the ACM on Programming Languages, 7(POPL), 1338–1368.