← All papers
First page of A Gradual Probabilistic Lambda Calculus

A Gradual Probabilistic Lambda Calculus

Matías Toro, Federico Olmedo, Wenjia Ye

cs.PL Apr 6, 2026 · v2
The full metatheory of the gradual probabilistic lambda calculus, including type safety and gradual guarantee results, is mechanized in Lean 4 with a public repository.
Probabilistic programming languages extend ordinary programming languages with the ability to sample values from probability distributions. Type systems can establish invariants of such programs, for instance by assigning to a program a distribution over types that specifies the probability of each kind of outcome. However, adopting such a type discipline can be cumbersome or overly conservative. Gradual typing addresses this problem by supporting a smooth transition between static and dynamic checking, and has been successfully applied for languages with different constructs and type abstractions. Nevertheless, its benefits have never been explored in the context of probabilistic languages. In this work, we present and formalize GLANG, a gradual source probabilistic lambda calculus. GLANG includes a binary probabilistic choice operator and allows programmers to gradually introduce/remove static type—and probability—annotations. The static semantics of GLANG heavily relies on the notion of probabilistic couplings, as required for defining several relations, such as consistency, precision, and consistent transitivity. The dynamic semantics of GLANG is given via elaboration to the target language TLANG, which features a distribution-based semantics interpreting programs as probability distributions over final values. Regarding the language metatheory, we establish that TLANG—and therefore also GLANG—is type safe and satisfies two of the so-called refined criteria for gradual languages, namely, that it is a conservative extension of a fully static variant and that it satisfies (a restricted form of) the gradual guarantee, behaving smoothly with respect to type precision. The metatheory is mechanized in the Lean 4 proof assistant.

Type systems for probabilistic programs, such as those assigning distributions over types, can be cumbersome or overly conservative. Gradual typing has not previously been applied to probabilistic languages.

The authors define GLANG, a gradual probabilistic lambda calculus with a binary probabilistic choice operator and optional type and probability annotations. Its static relations (consistency, precision, consistent transitivity) are built on probabilistic couplings. Dynamic semantics come from elaboration into a target language, TLANG, with a distribution-based semantics. The metatheory is mechanized in Lean 4.

TLANG, and therefore GLANG, is proven type safe, a conservative extension of a fully static variant, and satisfies a restricted gradual guarantee. All results are mechanized in Lean 4 and available at github.com/pleiad/gplc-lean.