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.
|Number of pages
|Proceedings of the ACM on Programming Languages
|Published - 20 Dec 2019
|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
Bibliographical noteProvisional acceptance date added, based on publication information.
- Programming Languages
- cost analysis
- resource analysis
- lambda calculus