Probabilistic Programming Semantics for Name Generation

07/16/2020
by   Marcin Sabok, et al.
0

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

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset