Modular, higher order cardinality analysis in theory and practice

Since the mid '80s, compiler writers for functional languages (especially lazy ones) have been writing papers about identifying and exploiting thunks and lambdas that are used only once. However, it has proved difficult to achieve both power and simplicity in practice. In this paper, we describ...

Full description

Saved in:
Bibliographic Details
Published in:Journal of functional programming 2017-01, Vol.27, p.1-55, Article e11
Main Authors: SERGEY, ILYA, VYTINIOTIS, DIMITRIOS, JONES, SIMON L. PEYTON, BREITNER, JOACHIM
Format: Article
Language:English
Subjects:
Compilers
Conferences
Languages
Optimization
Programming
Semantics
State of the art
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Since the mid '80s, compiler writers for functional languages (especially lazy ones) have been writing papers about identifying and exploiting thunks and lambdas that are used only once. However, it has proved difficult to achieve both power and simplicity in practice. In this paper, we describe a new, modular analysis for a higher order language, which is both simple and effective. We prove the analysis sound with respect to a standard call-by-need semantics, and present measurements of its use in a full-scale, state-of-the-art optimising compiler. The analysis finds many single-entry thunks and one-shot lambdas and enables a number of program optimisations. This paper extends our preceding conference publication (Sergey et al. 2014 Proceedings of the 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2014). ACM, pp. 335–348) with proofs, expanded report on evaluation and a detailed examination of the factors causing the loss of precision in the analysis.
ISSN:0956-7968
1469-7653
DOI:10.1017/S0956796817000016