Better Defunctionalization through Lambda Set Specialization
Open Access
- 6 June 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 7 (PLDI) , 977-1000
Abstract
Higher-order functions pose a challenge for both static program analyses and optimizing compilers. To simplify the analysis and compilation of languages with higher-order functions, a rich body of prior work has proposed a variety of defunctionalization techniques, which can eliminate higher-order functions from a program by transforming the program to a semantically-equivalent first-order representation. Several modern languages take this a step further, specializing higher-order functions with respect to the functions on which they operate, and in turn allowing compilers to generate more efficient code. However, existing specializing defunctionalization techniques restrict how function values may be used, forcing implementations to fall back on costly dynamic alternatives. We propose lambda set specialization (LSS), the first specializing defunctionalization technique which imposes no restrictions on how function values may be used. We formulate LSS in terms of a polymorphic type system which tracks the flow of function values through the program, and use this type system to recast specialization of higher-order functions with respect to their arguments as a form of type monomorphization. We show that our type system admits a simple and tractable type inference algorithm, and give a formalization and fully-mechanized proof in the Isabelle/HOL proof assistant showing soundness and completeness of the type inference algorithm with respect to the type system. To show the benefits of LSS, we evaluate its impact on the run time performance of code generated by the MLton compiler for Standard ML, the OCaml compiler, and the new Morphic functional programming language. We find that pre-processing with LSS achieves run time speedups of up to 6.85x under MLton, 3.45x for OCaml, and 78.93x for Morphic.Keywords
Funding Information
- NSF (CCF-1730628)
This publication has 19 references indexed in Scilit:
- Control-flow analysis of functional programsACM Computing Surveys, 2012
- Polymorphic typed defunctionalization and concretizationHigher-Order and Symbolic Computation, 2006
- Secrets of the Glasgow Haskell Compiler inlinerJournal of Functional Programming, 2002
- Functioning without closure2001
- Flow-Directed Closure Conversion for Typed Languages2000
- Typed closure conversion1996
- Simple imperative polymorphismHigher-Order and Symbolic Computation, 1995
- A theory of type polymorphism in programmingJournal of Computer and System Sciences, 1978
- Definitional interpreters for higher-order programming languages1972
- The Principal Type-Scheme of an Object in Combinatory LogicTransactions of the American Mathematical Society, 1969