# Probabilistic Programming Semantics for Name Generation

arXiv: https://arxiv.org/abs/2007.08638 · HTML: https://mlsanity.com/paper/2007.08638/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2020.

## Built on by (most cited first, 1 of 1)

- [String Diagrams with Factorized Densities](https://mlsanity.com/paper/2305.02506/) (2023)

## Abstract (arXiv)

We make a formal analogy between random sampling and fresh name generation. We show that quasi-Borel spaces, a model for probabilistic programming, can soundly interpret Stark's nu-calculus, a calculus for name generation. Moreover, we prove that this semantics is fully abstract up to first-order types. This is surprising for an 'off-the-shelf' model, and requires a novel analysis of probability distributions on function spaces. Our tools are diverse and include descriptive set theory and normal forms for the nu-calculus.