Defunctionalisation as modular closure conversion
Ulrich Schöpp · 2017
We study the problem of translating from call-by-value pcf to a first-order low-level language. Such translations are typically defined by induction on the structure of the source term. Each sub-term is translated to a low-level program fragment and the translation of the whole term is a composition of these fragments. It is desirable to follow this compositional approach also in reasoning about such translations, e.g. to show correctness of the translation by verifying the low-level fragments individually. In this paper, we define a defunctionalisation method in which the low-level program fragments are considered as little modules with a well-defined interface. We show correctness of the translation by decomposing it into a number of steps that each allows compositional reasoning. The main step is a typed closure conversion that translates pcf into a calculus based on interaction semantics. It takes into account low-level information, e.g. on closure representation and stack shape, that is obtained by global program analysis. We capture such information using an annotated type system for pcf and show that suitable annotations can be computed by type inference.