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||31|
|Journal||Proceedings of the ACM on Programming Languages|
|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
Bibliographical noteProvisional acceptance date added, based on publication information.
- Programming Languages
- cost analysis
- resource analysis
- lambda calculus
Kavvos, G. A., Morehouse, E., Licata, D., & Danner, N. (2019). Recurrence extraction for functional programs through call-by-push-value. Proceedings of the ACM on Programming Languages, 4(POPL), . https://doi.org/10.1145/3371083