Probabilistic Programming


  • The first exam will take place in room 5055 instead of AH6.
  • 13.12.2016, regarding exercise 2: Since the weakest liberal precondition (wlp) calculus has not been introduced in the lecture yet, you can ignore part (a), (d), and (e) of task 4.
  • The exercise class on 23.12.2016 is cancelled and rescheduled for 09.01.2017 at 14:15 in room 9U10. 
  • Registration for the written exam on Tuesday February 14, 2017 is open.
  • The kick-off lecture takes place on Monday October 24, 2016.
  • This is a condensed course (“Blockveranstaltung“), taking place two lectures/week in the weeks 49, 50, 51, 2, 3 and 5.


Type Day Time Hall Start Lecturer
Lecture Mon  16:15 – 17:45 9U10 24.10 Katoen
  Tue 10:15 – 11:45 9U10 06.12 Katoen
Exercise Fri 14:15 – 15:45 9U10 09.12  Olmedo, Kaminski, Matheja

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 recently developed, see the

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.  Randomized quicksort is an example of such program:

screen-shot-2016-10-18-at-13-16-12What 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, 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 with a simple web interface.  Subsequently, we will go into 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?



Basic knowledge of programming and probability theory.


  • Exercises can be worked on in groups of at most two students.
  • To achieve a certificate to this course or to be admitted to the final exam, at least half of the exercises has to be reasonably dealt.
  • The exercise sheets will be issued weekly, starting from December 6, 2017.


  • Exam admission: at least 50% of all points in the homework exercises need to be achieved.
  • First written exam: Tuesday February 14, 2017, 10:00-13:00 (AH6 5055)
  • Second written exam: Monday March 20, 2017, 09:00-12:00 (AH3)


No. Date Subject Material Exercise Solution
1  24.10 Introduction PP_lecture1.pdf    
2  05.12 WebPPL webppl_examples  ex-01  s-01
3  06.12 Weakest preconditions for GCL    ex-02  s-02
4  12.12 Weakest preconditions for probabilistic GCL    ex-03  s-03
5  13.12 Operational semantics of pGCL      
6  19.12 Axiomatic versus operational pGCL semantics      
7  20.12 Conditioning: operationally webppl_examples  ex-04  s-04
8  09.01 Conditioning: denotationally removing_observe  ex-05  s-05
9  10.01 Bayesian networks bayesian-networks    
10  16.01 Termination    ex-06  s-06
11  17.01 Termination      
12  30.01 Nondeterminism      
13  31.01 Expected run-time analysis      s-07

Further information

  • The lecture will be given in English. All course material will be in English.
  • The students will be awarded 4 ECTS credits for the lecture after passing the final exam.

The course is based several research papers and material from several books: