Batz, K;
Gallus, A;
Kaminski, BL;
Katoen, JP;
Winkler, T;
(2022)
Weighted programming: A programming paradigm for specifying mathematical models.
Proceedings of the ACM on Programming Languages
, 6
(OOPSLA1)
, Article 66. 10.1145/3527310.
Preview |
Text
3527310.pdf - Published Version Download (466kB) | Preview |
Abstract
We study weighted programming, a programming paradigm for specifying mathematical models. More specifically, the weighted programs we investigate are like usual imperative programs with two additional features: (1) nondeterministic branching and (2) weighting execution traces. Weights can be numbers but also other objects like words from an alphabet, polynomials, formal power series, or cardinal numbers. We argue that weighted programming as a paradigm can be used to specify mathematical models beyond probability distributions (as is done in probabilistic programming). We develop weakest-precondition- and weakest-liberal-precondition-style calculi à la Dijkstra for reasoning about mathematical models specified by weighted programs. We present several case studies. For instance, we use weighted programming to model the ski rental problem - an optimization problem. We model not only the optimization problem itself, but also the best deterministic online algorithm for solving this problem as weighted programs. By means of weakest-precondition-style reasoning, we can determine the competitive ratio of the online algorithm on source code level.
| Type: | Article |
|---|---|
| Title: | Weighted programming: A programming paradigm for specifying mathematical models |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1145/3527310 |
| Publisher version: | https://doi.org/10.1145/3527310 |
| Language: | English |
| Additional information: | © 2022 Copyright held by the owner/author(s). This is an open access article under the CC BY 4.0 license Attribution 4.0 International (https://creativecommons.org/licenses/by/4.0/) |
| UCL classification: | UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science UCL > Provost and Vice Provost Offices > UCL BEAMS UCL |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10148858 |
Archive Staff Only
 |
View Item |
