Type- and Control-Flow Directed Defunctionalization

Defunctionalization is a program transformation that removes all first-class functions from a source program, yielding an equivalent target program that contains only first-order functions. As originally described by Reynolds, defunctionalization transforms an untyped higher-order source program into an untyped first-order target program that uses a single, global dispatch function. In addition to being limited to untyped languages, a drawback of this approach is that obscures control flow, making it appear as though the code associated with every source function could be invoked at every call site of the target program. Subsequent work has extended defunctionalization to both simply-typed and polymorphicallytyped languages, but the latter continues to use a single, global dispatch function. Other work has extended defunctionalization to be guided by a control-flow analysis of a simply-typed source program, where the types of the target program exactly capture the results of the flow analysis and make it apparent which (limited) set of functions can be invoked at each call site. Our work draws inspiration from these previous approaches and proposes a novel flow-directed defunctionalization for a polymorphicallytyped source language. Guided by a type- and control-flow analysis, which exploits well-typedness of the source program to filter flows that are incompatible with static types, the transformation must construct evidence that filtered flows are impossible in order to ensure the well-typedness of the target program.