If we view the semantics of the underlying deterministic language as a map from programs to executions of the program, the semantics of a PPL built on it will be a map from programs to distributions over executions. When the program halts with probability one, this induces a proper distribution over return values. Indeed, any computable distribution can be represented as the distribution induced by a Church program in this way (see Freer and Roy, 2012, and citations therein).
The critical obstacle to probabilistic programming as a practical tool is efficient implementation of the inference operator. An obvious implementation technique is to enumerate all execution paths of the program, for instance by using co-routines. To implement this approach cleanly we will introduce continuations and transform our program into continuation passing style. Unfortunately, naive enumeration takes time proportional to the number of executions, which grows exponentially in the number of random choices. This can be ameliorated in some cases by using dynamic programming and by priority-based queueing of continuations. Indeed it is possible to do inference for a number of useful models (e.g. models of natural language pragmatics) by using a dynamic programming approach. In the class we will explore in depth how to implement enumeration with caching and priority-queueing. We will then switch our focus to approximate inference technique based on Particle Filtering which can often scale much better in practice.
Next chapter: The WebPPL language