First blog post about readings of papers. This one is called Better Defunctionalization through Lambda Set Specialization.
The basic idea is to keep track of the lambdas that could flow to a particular location in the type system as a sort of set / effect type.
This allows for a large majority of call sites to reference first order functions, with just tags for which lambda is being called.
Additionally there is support for polymorphic lambda sets, recursive definitions, etc. The part I found really interesting was that they mention regular control flow analysis as introducing poisoning due to the fact that it is an overapproximation. The type system approach has less information about lambda environments, but it does prevent some poisoning. It made me wonder how well it would do as a preprocessing step for static analysis.
He mentions a paper that might have used it as a preprocessing step, which I'll have to read:
- Corentin De Souza. 2022. Higher-order function specialization in Infer. Presented at the 43rd ACM SIGPLAN Conference on Programming Language Design and Implementation
Additionally, it seems like they have a good set of benchmark programs that use higher order control flow (through libraries such as parser combinators, state monads and iterators, etc). They implement a transpiler to get these benchmarks into a few languages that they compare. We should see if we could use some of these programs for our own benchmarks.
Also, in a way it might find all of the first order closures (or at least lambdas that do not have recursion) - similar to TP-mCFA where m=0 and the lambda variant. It just takes all of the closures in the flow set and then defunctionalizes them, but only the ones that are guaranteed to happen, not spurious lambda from other flow sets. As such, I think it is probably a very good preprocessor for any analysis.