Abstract
The main way of analysing the complexity of a program is that of extracting and solving a recurrence that expresses its running time in terms of the size of its input. We develop a method that automatically extracts such recurrences from the syntax of higher-order recursive functional programs. The resulting recurrences, which are programs in a call-by-name language with recursion, explicitly compute the running time in terms of the size of the input. In order to achieve this in a uniform way that covers both call-by-name and call-by-value evaluation strategies, we use Call-by-Push-Value (CBPV) as an intermediate language. Finally, we use domain theory to develop a denotational cost semantics for the resulting recurrences.
Original language | English |
---|---|
Article number | 15 |
Number of pages | 31 |
Journal | Proceedings of the ACM on Programming Languages |
Volume | 4 |
Issue number | POPL |
DOIs | |
Publication status | Published - 20 Dec 2019 |
Event | 47th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2020) - JW Marriott New Orleans, New Orleans, United States Duration: 19 Jan 2020 → 25 Jan 2020 Conference number: 2020 https://popl20.sigplan.org/ |
Bibliographical note
Provisional acceptance date added, based on publication information.Research Groups and Themes
- Programming Languages
Keywords
- semantics
- cost analysis
- resource analysis
- lambda calculus
- recursion