Probabilistic Programming


  • 26.09.2022: We are online!


LectureTue16:30 – 18:00AH III11.10Katoen
 Thu16:30 – 18:00AH II13.10Katoen
ExerciseFri12:30 – 14:00AH I14.10Winkler, Schroer, Klinkenberg

Motivation and background

Probabilistic programs support random choices like “execute program P with probability 1/3 and program Q with probability 2/3″. Probabilistic programs are typically normal–looking sequential programs describing posterior probability distributions. Describing randomized algorithms has been the classical application of these programs. Applications in biology, machine learning, quantum computing, security, and so on, have led to a rapidly growing interest in probabilistic programs in the last decade. For almost all programming languages, such as C, C#, Prolog, Haskell, Scala, LISP, a probabilistic variant does exist; and even a variant of Microsoft’s Excel has been developed.

Most of these languages feature, in addition to sampling from probability distributions, the ability to condition values of variables in a program. Conditioning allows for adding information about observed events into the program that may influence the posterior distribution. It is one of the key features in Bayesian networks that rely on Bayes’ rule as the basis for updating information. It is this feature that distinguishes modern probabilistic programming languages from those in the early days describing randomized algorithms. 

What is special about probabilistic programs? Although probabilistic programs are normal–looking programs, reasoning about their correctness is intricate. They do not generate a single output but a distribution over outputs. The key property of program termination exemplifies this. Whereas a classical program terminates or not, this is no longer true for probabilistic programs. They can diverge, but this may happen with probability zero. That is, even if programs terminate with probability one, they may have non-terminating runs!  In addition, in contrast to classical programs that either do not terminate at all or terminate in finitely many steps, a probabilistic program may take infinitely many steps on average to terminate, even if its termination probability is one.

Establishing correctness of probabilistic programs needs—even more so than ordinary programs—formal reasoning.

This lecture series will introduce the probabilistic programming language webppl, a functional language based on JavaScript with a simple web interface.  Subsequently, we will go into elementary questions such as:

  • What do probabilistic programs mean?  Exactly.
  • What does it mean for a program to not terminate with some likelihood?
  • How to analyze that a probabilistic program does what it is supposed to do?
  • How to prove that a probabilistic program is (more) efficient?
  • What are Bayesian networks and how are they related to probabilistic programs?



Basic knowledge of programming and probability theory.


  • There will be weekly exercise sheets issued via Moodle.
  • In order to be admitted to the final exam, at least 50% of the exercise’s points have to be achieved.
  • Hand in the solutions digitally via Moodle, in groups of 3 people.


11.10.2022Slides 01 (Handout)
13.10.2022Slides 02 (Handout), WebPPL Examples
18.10.2022Slides 03 (Handout)
20.10.2022Slides 04+05 (Handout)
27.10.2022Slides 06 (Handout)
08.11.2022Slides 07 (Handout)
10.11.2022Slides 08 (Handout)
15.11.2022Slides 09 (Handout)
17.11.2022Slides 10 (Handout)
22.11.2022Slides 11 (Handout)
24.11.2022Slides 12 (Handout)


additional information about the exam will be published soon.

Further information

  • The lecture will be given in English. All course material will be in English.
  • The students will be awarded 6 ECTS credits for the lecture after passing the final exam.
  • You can find the associated RWTH Moodle Room here