Book contents
- Frontmatter
- Contents
- List of Contributors
- Preface
- 1 Semantics of Probabilistic Programming: A Gentle Introduction
- 2 Probabilistic Programs as Measures
- 3 Application ofComputable Distributions to the Semantics of Probabilistic Programs
- 4 On Probabilistic λ-Calculi
- 5 Probabilistic Couplings from Program Logics
- 6 Expected Runtime Analyis by Program Verification
- 7 Termination Analysis of Probabilistic Programs with Martingales
- 8 Quantitative Analysis of Programs with Probabilities and Concentration of Measure Inequalities
- 9 The Logical Essentials of Bayesian Reasoning
- 10 Quantitative Equational Reasoning
- 11 Probabilistic Abstract Interpretation: Sound Inference and Application to Privacy
- 12 Quantitative Information Flow with Monads in Haskell
- 13 Luck: A Probabilistic Language for Testing
- 14 Tabular: Probabilistic Inference from the Spreadsheet
- 15 Programming Unreliable Hardware
10 - Quantitative Equational Reasoning
Published online by Cambridge University Press: 18 November 2020
- Frontmatter
- Contents
- List of Contributors
- Preface
- 1 Semantics of Probabilistic Programming: A Gentle Introduction
- 2 Probabilistic Programs as Measures
- 3 Application ofComputable Distributions to the Semantics of Probabilistic Programs
- 4 On Probabilistic λ-Calculi
- 5 Probabilistic Couplings from Program Logics
- 6 Expected Runtime Analyis by Program Verification
- 7 Termination Analysis of Probabilistic Programs with Martingales
- 8 Quantitative Analysis of Programs with Probabilities and Concentration of Measure Inequalities
- 9 The Logical Essentials of Bayesian Reasoning
- 10 Quantitative Equational Reasoning
- 11 Probabilistic Abstract Interpretation: Sound Inference and Application to Privacy
- 12 Quantitative Information Flow with Monads in Haskell
- 13 Luck: A Probabilistic Language for Testing
- 14 Tabular: Probabilistic Inference from the Spreadsheet
- 15 Programming Unreliable Hardware
Summary
Equational logic has been a central theme in mathematical reasoning and in reasoning about programs. We introduce a quantitative analogue of equational reasoning that allows one to reason about approximate equality. The equality symbol is annotated with a real number that describes how far apart two terms can be. We develop the counterparts of standard results of equational logic, in particular, a completeness theorem. We define quantitative algebras and free quantitative algebras which yield monads on categories of metric spaces. We show that key examples of probability metrics, in particular, the Kantorovich metric and the Wasserstein p-metrics, arise from simple quantitative theories. Finally we develop a quantitative version of the theory of effects in programming languages.
Keywords
- Type
- Chapter
- Information
- Foundations of Probabilistic Programming , pp. 333 - 360Publisher: Cambridge University PressPrint publication year: 2020
- Creative Commons
- This content is Open Access and distributed under the terms of the Creative Commons Attribution licence CC-BY 4.0 https://creativecommons.org/cclicenses/
- 2
- Cited by