Sungwoo Park

A Programming Language for Probabilistic Computation Degree Type: Ph.D. in Computer Science
Advisor(s): Frank Pfenning, Sebastian Thrun
Graduated: August 2005

Abstract:

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.

Thesis Committee:
Frank Pfenning (Co-chair)
Sebastian Thrun (Co-chair, Stanford University)
Geoffrey Gordon
Robert Harper
Norman Ramsey (Harvard University)

Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

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