Probabilistic programming semantics for name generation Article Swipe

PDF

Related Concepts

Probabilistic logic Semantics (computer science) Calculus (dental) Computer science Analogy Operational semantics Mathematics Algebra over a field Discrete mathematics Programming language Pure mathematics Artificial intelligence Linguistics Medicine Dentistry Philosophy

Marcin Sabok , Sam Staton , Dario Stein , Michael Wolman ·

YOU? · · 2021 · Open Access · · DOI: https://doi.org/10.1145/3434292 · OA: W3042245160

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 the ν-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 ν-calculus.