Computer Science Department
School of Computer Science, Carnegie Mellon University


A Programming Language for Probabilistic Computation

Sungwoo Park

August 2005

Ph.D. Thesis

Keywords: Probabilistic language, Probability distribution, Sampling function, Robotics, Computational effect, Monad, Modal logic

As probabilistic computations play an increasing role in solving various problems, researchers have designed probabilistic languages to facilitate their modeling. Most of the existing probabilistic languages, however, focus only on discrete distributions, and there has been little effort to develop probabilistic languages whose expressive power is beyond discrete distributions. This dissertation presents a probabilistic language, called PTP (ProbabilisTic Programming), which supports all kinds of probability distributions.

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.

116 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by