Computer Science Department
School of Computer Science, Carnegie Mellon University
A Programming Language for Probabilistic Computation
The key idea behind PTP is to use sampling functions, i.e., mappings from the unit interval (0.0, 1.0] to probability domains, to specify probability distributions. By using sampling functions as its mathematical basis, PTP provides a unified representation scheme for probability distributions, without drawing a syntactic or semantic distinction between different kinds of probability distributions.
Independently of PTP, we develop a linguistic framework, called λo , to account for computational effects in general. λo extends a monadic language by applying the possible world interpretation of modal logic. A characteristic feature of λo is the distinction between stateful computational effects, called world effects, and contextual computational effects, called control effects. PTP arises as an instance of λo with a language construct for probabilistic choices.
We use a sound and complete translator of PTP to embed it in Objective CAML. The use of PTP is demonstrated with three applications in robotics: robot localization, people tracking, and robotic mapping. Thus PTP serves as another example of high-level language applied to a problem domain where imperative languages have been traditionally dominant.