Principles of Probabilistic Programming

Probabilistic programming is en vogue. It is used to describe complex Bayesian networks, quantum programs, security protocols and biological systems. Programming languages like C, C#,Java, Prolog, Scala, etc. all have their probabilistic version. Key features are random sampling and means to adjust distributions based on obtained information from measurements and system observations. We give a gentle introduction to the topic, show some semantic intricacies, argue that termination is more involved than the halting problem, and discuss recursion, run-time analysis, as well as loop invariant synthesis.