POPL 2027
Sun 10 - Sat 16 January 2027 Mexico City, Mexico

Stochastic processes such as independent and identically distributed (i.i.d.) sequences, Markov chains, Brownian motion, and stochastic differential equations are infinite probabilistic objects, and modern probabilistic programming languages can express them as lazy recursive programs. Giving such programs a compositional semantics has remained a challenge: the category of measurable spaces is not Cartesian closed, and the classical semantic universes each fall short of at least one of higher-order functions, continuous probability over the standard-Borel reals, and random infinite objects recovered from their finite stages. We develop the theory in $\boldsymbol{\omega}\textbf{Qbs}$, a mixture of quasi-Borel spaces and $\omega$cpos that supports all three and carries a commutative probability monad $P$. We establish two main theorems. The first is an \emph{extension theorem}: random streams correspond exactly to consistent families of finite marginals, a Kolmogorov extension theorem internal to $\boldsymbol{\omega}\textbf{Qbs}$. The second is a \emph{coinduction principle}: the space of streams is the final coalgebra in the Kleisli category of $P$, and more generally, so is $\mu F$ for every locally continuous functor $F$ with a distributive law over $P$, yielding random trees as well. These theorems make classical constructions compositional: L'evy’s construction of Brownian motion, Euler–Maruyama approximation of stochastic differential equations, switching diffusions, and branching Brownian motion all arise as random streams or trees of functions. We complement them with impossibility results: over $\mathbf{Qbs}$, without order structure, distributions on $X^{\mathbb N}$ are not determined by their finite marginals and i.i.d.\ sequences are not definable; over $\mathbf{Set}$, finality fails. Finally, we give a higher-order lazy probabilistic language whose programs compute the processes above, and prove its $\boldsymbol{\omega}\textbf{Qbs}$ semantics adequate.