Tachis: Higher-Order Separation Logic with Credits for Expected Costs
Open Access
- 8 October 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 8 (OOPSLA2) , 1189-1218
Abstract
We present Tachis, a higher-order separation logic to reason about the expected cost of probabilistic programs. Inspired by the uses of time credits for reasoning about the running time of deterministic programs, we introduce a novel notion of probabilistic cost credit. Probabilistic cost credits are a separation logic resource that can be used to pay for the cost of operations in programs, and that can be distributed across all possible branches of sampling instructions according to their weight, thus enabling us to reason about expected cost. The representation of cost credits as separation logic resources gives Tachis a great deal of flexibility and expressivity. In particular, it permits reasoning about amortized expected cost by storing excess credits as potential into data structures to pay for future operations. Tachis further supports a range of cost models, including running time and entropy usage. We showcase the versatility of this approach by applying our techniques to prove upper bounds on the expected cost of a variety of probabilistic algorithms and data structures, including randomized quicksort, hash tables, and meldable heaps. All of our results have been mechanized using Coq, Iris, and the Coquelicot real analysis library.Keywords
All Related Versions
Funding Information
- National Science Foundation (2225441)
- Carlsbergfondet (CF23-0791)
- Villum Fonden (25804)
- European Research Council (101096090)
This publication has 48 references indexed in Scilit:
- Automated Expected Amortised Cost Analysis of Probabilistic Data Structures2022
- Time Credits and Time Receipts in Iris2019
- Tail Probabilities for Randomized Program Runtimes via Martingales for Higher Moments2019
- Termination of Nondeterministic Probabilistic Programs2019
- Weakest Precondition Reasoning for Expected Run–Times of Probabilistic Programs2016
- Relational Reasoning via Probabilistic Coupling2015
- Impredicative Concurrent Abstract Predicates2014
- Abstraction, Refinement and Proof for Probabilistic Systems2005
- Randomized Meldable Priority QueuesLecture Notes in Computer Science, 1998
- Fisher, R. A., and F. Yates: Statistical Tables for Biological, Agricultural and Medical Research. 6th Ed. Oliver & Boyd, Edinburgh and London 1963. X, 146 P. Preis 42 s netBiometrische Zeitschrift, 1971