λPSI: Exact Inference for Higher-Order Probabilistic Programs

We present lambda PSI, the first probabilistic programming language and system that supports higher-order exact inference for probabilistic programs with first-class functions, nested inference and discrete, continuous and mixed random variables. lambda PSI's solver is based on symbolic reasoning and computes the exact distribution represented by a program. We show that lambda PSI is practically effective-it automatically computes exact distributions for a number of interesting applications, from rational agents to information theory, many of which could so far only be handled approximately.