Monolingual Probabilistic Programming Using Generalized Coroutines

Oleg Kiselyov, Chung-chieh ShanUAI 2009

Abstract

This paper presents a novel approach to probabilistic programming that bridges the gap between modeling toolkits and dedicated languages. By leveraging generalized coroutines (delimited continuations) in OCaml, the authors enable stochastic models to be written as native code. This "monolingual" approach allows inference engines to reify programs into search trees, facilitating high-performance inference that benefits from native execution speeds and standard development tools. Evaluation on benchmarks like music motif modeling and radar tracking demonstrates that this method achieves accuracy comparable to specialized probabilistic languages while maintaining the flexibility of a general-purpose environment.

Introduction

In probabilistic programming, researchers typically face a "two-language problem." On one hand, modeling toolkits (like the Bayes Net Toolbox for MATLAB) offer easy integration but often suffer from clunky syntax for complex distributions. On the other hand, dedicated probabilistic languages (like Church or IBAL) provide expressive power but introduce significant "interpretive overhead," running slower than native code and complicating debugging. This paper introduces a monolingual approach where both stochastic models and inference algorithms are written in OCaml, providing the speed and type-checking of a general-purpose language alongside the mathematical flexibility of a probabilistic framework.

Methodology: Reification via Continuations

The core innovation lies in using generalized coroutines, specifically delimited control operators (shift and reset). When a model encounters a random choice, it uses shift to suspend the program's state and return control to the inference engine. The engine can then resume the program multiple times with different values to explore the probability tree.

OCaml implementation of a Bayesian network model

Because the model is a standard OCaml function, deterministic code runs at full native speed. The authors also implement Importance Sampling with Look-ahead, which "sniffs" ahead in the search tree to avoid branches that lead to immediate failure, significantly improving efficiency. Furthermore, higher-order functions enable memoization, essential for non-parametric models and lazy evaluation.

Evaluation and Benchmarks

The approach was evaluated using three classic benchmarks:

  1. Hidden Markov Model (HMM): A 1D random walk used to demonstrate how standard profiling tools can optimize probabilistic code.
  2. Music Motif Model: A complex model of motivic development in Beethoven’s piano sonatas, involving recursive structures and transpositions.
  3. Radar Blip Tracking: A model for tracking aircraft on a 10x10 grid, identifying planes amidst noise.

Key Results and Insights

The monolingual approach allows inference to act as a "self-interpreter," reasoning about its own accuracy without the exponential slowdown of nested interpreters. A significant advantage is the ability to use standard OCaml debuggers and profilers to identify bottlenecks.

Accuracy comparison on the music motif model

On the Beethoven music model, the OCaml-based sampler achieved accuracy levels competitive with IBAL, a highly optimized standalone probabilistic language. In several instances, 90-second runs outperformed IBAL's native sampler. In the radar tracking task, the system successfully identified the most likely number of aircraft with a conditional probability of 0.987.

Conclusion

By reifying programs into search trees through delimited continuations, this work demonstrates that high-performance probabilistic programming is possible within a general-purpose language. While the technique requires specific language features like delimited control, it offers a powerful path toward integrating probabilistic reasoning into standard software development workflows. Future work may explore "AND-nodes" to represent independent choices, further optimizing search tree complexity.

Summary updated

BibTeX
@inproceedings{kiselyov2009monolingual,
  author = {Oleg Kiselyov and Chung-chieh Shan},
  title = {{Monolingual Probabilistic Programming Using Generalized Coroutines}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2009},
}
Figure