On probabilistic termination of functional programs with continuous distributions

Raven Beutner, Luke Ong

TL;DR

This paper tackles the challenge of proving whether probabilistic programs—specifically those using continuous distributions and complex recursion—will eventually finish running. The authors introduce a novel "interval-based" semantics that makes reasoning about continuous probabilities computationally feasible and provide a new verification method for "non-affine" programs (those that make multiple recursive calls), reducing complex program behavior to simple, decidable random walks.

What Problem Does This Paper Address?

In standard programming, termination is a binary "yes/no" question. In probabilistic programming, it’s a spectrum: what is the probability that a program terminates? We say a program is Almost-Sure Terminating (AST) if it finishes with probability 1.

While we have good tools for programs with discrete choices (like flipping a coin), programs that sample from continuous distributions (like picking a random number between 0 and 1) are much harder to analyze. In a continuous space, any single execution path has a probability of exactly zero, making standard "path-counting" methods useless. Furthermore, most existing tools struggle with non-affine recursion—where a single function body might trigger multiple recursive calls—which can drastically change termination behavior compared to simple loops.

Methods

The authors propose two major breakthroughs:

  1. Interval-based Operational Semantics: Instead of tracking exact real-valued samples, the authors track "traces of intervals." By grouping uncountably many individual executions into countable sets of interval-based paths, they create a framework where one can compute increasingly tight lower bounds on termination probability. They prove this approach is both sound and complete.
  2. Counting-based Recursion Analysis: To handle non-affine recursion, they shift focus from the size of function arguments to the number of recursive calls. They instrument the program to count pending calls and model this as a random walk on integers. If the "drift" of this random walk is toward zero, the program is AST.
  3. Game-Playing Perspective: To automate the analysis when branching depends on random values, they treat the environment as an adversary in a two-player game. If the program terminates regardless of the environment's "strategy" (which branch is taken), it provides a safe lower bound for AST.
  4. Intersection Type System: They formalize these ideas into a type system that can compositionally derive termination probabilities and expected execution times.

Datasets

As a theoretical programming languages paper, the "datasets" consist of a suite of benchmark probabilistic programs used to evaluate their prototype tools:

  • geo_p: A program modeling a geometric distribution.
  • 1dRW: A 1-dimensional biased random walk.
  • gr: A complex term inspired by prior work that terminates with a probability related to the golden ratio.
  • 3print: A non-affine recursive program modeling a faulty 3D printer.
  • pedestrian: A model of a "forgetful pedestrian" moving randomly on a line.

Key Insights and Ideas

  • The Power of Intervals: You don't need to know the exact value of a random sample to know if a program will terminate; you just need to know if it falls within a certain range. This observation turns an uncountable problem into a countable one.
  • Complexity Bounds: The paper establishes for the first time that deciding AST for programs with continuous distributions is $\Pi^0_2$-complete in the arithmetic hierarchy—the same complexity as for discrete programs.
  • Non-Affine Matters: In probabilistic settings, the number of call sites in a recursive function is a first-class citizen. A program that calls itself twice might fail to terminate where a similar program calling itself once would succeed.
  • Zero-One Law Generalization: They provide a functional generalization of the "zero-one law," which states that for certain types of loops, if there's a non-zero chance of exiting, the loop is almost-surely terminating.

Key Results

  • Verification Success: Their prototype tool successfully verified AST for several non-affine programs that were beyond the reach of previous state-of-the-art methods (like those based on ranking functions).
  • Precision: For lower-bound computation, their tool provided extremely tight bounds (e.g., $0.999999...$) for known AST programs within milliseconds to seconds.
  • Efficiency: The AST verification for complex non-affine terms typically took less than a second, demonstrating that the reduction to random walks is computationally efficient.

Limitations and Future Work

  • Incompleteness: While powerful, interval-based reasoning can still fail on "pathological" continuous functions (like those involving the Smith-Volterra-Cantor set) where no interval can capture the termination behavior.
  • Primitive Restrictions: The current implementation for AST verification is optimized for linear operations (addition and multiplication by constants). Handling non-linear constraints would require more complex volume-computation oracles.
  • Hybrid Analysis: The authors suggest that a future "unified framework" combining their call-counting approach with traditional size-based ranking functions would be the "holy grail" of probabilistic termination analysis.

Summary updated

Abstract

We study termination of higher-order probabilistic functional programs with recursion, stochastic conditioning and sampling from continuous distributions. Reasoning about the termination probability of programs with continuous distributions is hard, because the enumeration of terminating executions cannot provide any non-trivial bounds. We present a new operational semantics based on traces of intervals, which is sound and complete with respect to the standard sampling-based semantics, in which (countable) enumeration can provide arbitrarily tight lower bounds. Consequently we obtain the first proof that deciding almost-sure termination (AST) for programs with continuous distributions is $\Pi^0_2$-complete. We also provide a compositional representation of our semantics in terms of an intersection type system. In the second part, we present a method of proving AST for non-affine programs, i.e., recursive programs that can, during the evaluation of the recursive body, make multiple recursive calls (of a first-order function) from distinct call sites. Unlike in a deterministic language, the number of recursion call sites has direct consequences on the termination probability. Our framework supports a proof system that can verify AST for programs that are well beyond the scope of existing methods. We have constructed prototype implementations of our method of computing lower bounds of termination probability, and AST verification.
BibTeX
@inproceedings{beutner2021probabilistic,
  author = {Raven Beutner and Luke Ong},
  title = {{On probabilistic termination of functional programs with continuous distributions}},
  booktitle = {PLDI},
  year = {2021},
  url = {https://openreview.net/forum?id=Sjo5dj6gf-N},
}

Loading related content...

Figure