Design and Implementation of Probabilistic Programming Language Anglican

David Tolpin, Jan-Willem van de Meent, Hongseok Yang, Frank D. Wood

TL;DR

This paper introduces Anglican, a probabilistic programming language designed for seamless integration with Clojure and the Java Virtual Machine (JVM). Anglican offers a functional foundation for probabilistic modeling and inference, achieving state-of-the-art efficiency by leveraging Clojure's macro system for compilation and a continuation-passing style (CPS) evaluation model.

What Problem Does This Paper Address?

Statistical inference is a crucial step in data science workflows, often requiring iterative model design and algorithm testing. While probabilistic programming systems (PPS) simplify model specification and allow for generic inference, they typically lack the broader functionality needed for data acquisition, pre-processing, and analysis. This creates a disconnect, forcing practitioners to switch between specialized PPS and general-purpose languages. The authors address this by creating Anglican, a PPS that integrates tightly with Clojure, a JVM-based language, allowing probabilistic models to be developed and executed within a familiar, feature-rich environment. This integration aims to streamline the entire data science workflow, from model definition to result analysis.

Methods

Anglican's core innovation lies in its implementation strategy:

  • Macro-based Compilation: Anglican leverages Clojure's powerful macro system to transform probabilistic programs into Clojure code. This allows Anglican to extend Clojure's syntax and alter its operational semantics for probabilistic constructs.
  • Continuation-Passing Style (CPS) Evaluation: Anglican programs are compiled into a CPS representation. This model is crucial for inference algorithms, as it allows them to intercept probabilistic operations (like sampling and observing) and manage the program's state and control flow.
  • Functional Foundation: The language is built on functional programming principles, which naturally align with probabilistic modeling concepts like distributions and random processes.
  • Tight JVM Integration: By running on the JVM, Anglican gains access to a vast ecosystem of Java and Clojure libraries for data manipulation, visualization, and other tasks, while also allowing Anglican programs to be deployed as standard JVM artifacts.
  • Checkpoint Addressing: A novel scheme for addressing probabilistic checkpoints (sample, observe) is introduced. This scheme uses checkpoint identifiers and occurrence counts to ensure correct correspondence between checkpoints across different inference runs, crucial for algorithms like Metropolis-Hastings.

Datasets

Not discussed in the paper. The paper focuses on the language design and implementation, using small illustrative examples rather than large datasets for evaluation.

Key Insights and Ideas

  • Functional Programming as a Natural Fit for Probabilistic Programming: The paper highlights how functional paradigms inherently support probabilistic concepts, making model specification more concise and expressive.
  • The Power of Macro Systems for Language Extension: Clojure's macros are demonstrated as a powerful tool for embedding a new language (Anglican) within an existing one, enabling seamless integration and custom semantics.
  • CPS Transformation for Inference Control: The CPS evaluation model is key to enabling inference algorithms to effectively "hook into" the program's execution at probabilistic checkpoints, allowing for sophisticated control and state management.
  • Bridging the Gap Between Probabilistic Modeling and General-Purpose Programming: Anglican's tight integration with Clojure/JVM addresses a practical need for data scientists, allowing them to leverage robust libraries for the entire workflow, not just model definition.
  • Memoization for Efficiency in Probabilistic Programs: The mem form is introduced to handle situations where the same random draw is needed for identical inputs across multiple executions, improving efficiency without sacrificing correctness.

Key Results

The paper demonstrates that Anglican can implement a probabilistic functional language efficiently and integrate it tightly with a conventional functional language (Clojure) with only moderate computational overhead. It shows how advanced probabilistic modeling concepts can be naturally mapped to the functional foundation. While specific quantitative results on inference speed or accuracy are not the primary focus, the paper implies that Anglican achieves state-of-the-art computational efficiency without sacrificing expressiveness, as supported by comparisons with other probabilistic programming languages. The case study on the "Deli dilemma" illustrates how Anglican can be used to formalize a problem, perform inference, and analyze results, showcasing the practical utility of the system.

Limitations and Future Work

  • Limitations:
    • The paper notes that not all Clojure forms are currently supported in Anglican, though expansion is planned.
  • While Anglican aims for efficiency, the paper acknowledges that some inference algorithms (like LMH) can be slow to converge.
  • The authors mention that selecting the "most appropriate" inference algorithm for a given probabilistic program is still a challenging task.
  • Future Work:
    • The paper suggests that new inference algorithms are continuously being developed and added to Anglican.
  • Further research is ongoing in applications of probabilistic programming.
  • The authors hint at future work on more informative labels for probabilistic forms to improve analysis.

Summary updated

Abstract

Anglican is a probabilistic programming system designed to interoperate with Clojure and other JVM languages. We introduce the programming language Anglican, outline our design choices, and discuss in depth the implementation of the Anglican language and runtime, including macro-based compilation, extended CPS-based evaluation model, and functional representations for probabilistic paradigms, such as a distribution, a random process, and an inference algorithm. We show that a probabilistic functional language can be implemented efficiently and integrated tightly with a conventional functional language with only moderate computational overhead. We also demonstrate how advanced probabilistic modeling concepts are mapped naturally to the functional foundation.
BibTeX
@inproceedings{tolpin2016design,
  author = {David Tolpin and Jan-Willem van de Meent and Hongseok Yang and Frank D. Wood},
  title = {{Design and Implementation of Probabilistic Programming Language Anglican}},
  booktitle = {IFL},
  year = {2016},
  doi = {10.1145/3064899.3064910},
}
Figure