Application ofComputable Distributions to the Semantics of Probabilistic Programs

Daniel Huang; Greg Morrisett; Bas Spitters

doi:10.1017/9781108770750.004

Application ofComputable Distributions to the Semantics of Probabilistic Programs

Daniel Huang, Greg Morrisett, Bas Spitters

Research output: Contribution to book/anthology/report/proceeding › Book chapter › Research › peer-review

5 Citations (Scopus)

Abstract

In this chapter, we explore how (Type-2) computable distributions can be used to give both (algorithmic) sampling and distributional semantics to probabilistic programs with continuous distributions. To this end, we sketch an encoding of computable distributions in a fragment of Haskell and show how topological domains can be used to model the resulting PCF-like language. We also examine the implications that a (Type-2) computable semantics has for implementing conditioning. We hope to draw out the connection between an approach based on (Type-2) computability and ordinary programming throughout the chapter as well as highlight the relation with constructive mathematics (via realizability).

Original language	English
Title of host publication	Foundations of Probabilistic Programming
Number of pages	46
Publisher	Cambridge University Press
Publication date	1 Jan 2020
Pages	75-120
ISBN (Print)	9781108488518
ISBN (Electronic)	9781108770750
DOIs	https://doi.org/10.1017/9781108770750.004
Publication status	Published - 1 Jan 2020

Keywords

Computable distributions
Probabilistic programs
Realizability
Semantics
Topological domains

Access to Document

10.1017/9781108770750.004

Cite this

@inbook{0fa21fd49f5643609404f682635d70d0,

title = "Application ofComputable Distributions to the Semantics of Probabilistic Programs",

abstract = "In this chapter, we explore how (Type-2) computable distributions can be used to give both (algorithmic) sampling and distributional semantics to probabilistic programs with continuous distributions. To this end, we sketch an encoding of computable distributions in a fragment of Haskell and show how topological domains can be used to model the resulting PCF-like language. We also examine the implications that a (Type-2) computable semantics has for implementing conditioning. We hope to draw out the connection between an approach based on (Type-2) computability and ordinary programming throughout the chapter as well as highlight the relation with constructive mathematics (via realizability).",

keywords = "Computable distributions, Probabilistic programs, Realizability, Semantics, Topological domains",

author = "Daniel Huang and Greg Morrisett and Bas Spitters",

note = "Publisher Copyright: {\textcopyright} Gilles Barthe, Joost-Pieter Katoen and Alexandra Silva 2021.",

year = "2020",

month = jan,

day = "1",

doi = "10.1017/9781108770750.004",

language = "English",

isbn = "9781108488518",

pages = "75--120",

booktitle = "Foundations of Probabilistic Programming",

publisher = "Cambridge University Press",

}

TY - CHAP

T1 - Application ofComputable Distributions to the Semantics of Probabilistic Programs

AU - Huang, Daniel

AU - Morrisett, Greg

AU - Spitters, Bas

N1 - Publisher Copyright: © Gilles Barthe, Joost-Pieter Katoen and Alexandra Silva 2021.

PY - 2020/1/1

Y1 - 2020/1/1

N2 - In this chapter, we explore how (Type-2) computable distributions can be used to give both (algorithmic) sampling and distributional semantics to probabilistic programs with continuous distributions. To this end, we sketch an encoding of computable distributions in a fragment of Haskell and show how topological domains can be used to model the resulting PCF-like language. We also examine the implications that a (Type-2) computable semantics has for implementing conditioning. We hope to draw out the connection between an approach based on (Type-2) computability and ordinary programming throughout the chapter as well as highlight the relation with constructive mathematics (via realizability).

AB - In this chapter, we explore how (Type-2) computable distributions can be used to give both (algorithmic) sampling and distributional semantics to probabilistic programs with continuous distributions. To this end, we sketch an encoding of computable distributions in a fragment of Haskell and show how topological domains can be used to model the resulting PCF-like language. We also examine the implications that a (Type-2) computable semantics has for implementing conditioning. We hope to draw out the connection between an approach based on (Type-2) computability and ordinary programming throughout the chapter as well as highlight the relation with constructive mathematics (via realizability).

KW - Computable distributions

KW - Probabilistic programs

KW - Realizability

KW - Semantics

KW - Topological domains

UR - http://www.scopus.com/inward/record.url?scp=85110984819&partnerID=8YFLogxK

U2 - 10.1017/9781108770750.004

DO - 10.1017/9781108770750.004

M3 - Book chapter

AN - SCOPUS:85110984819

SN - 9781108488518

SP - 75

EP - 120

BT - Foundations of Probabilistic Programming

PB - Cambridge University Press

ER -

Application ofComputable Distributions to the Semantics of Probabilistic Programs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this