Developing accurate and efficient program analyses for languages with higher-order functions is known to be difficult. Here we define a new higher-order program analysis, Demand-Driven Program Analysis (DDPA), which extends well-known demand-driven lookup techniques found in first-order program analyses to higher-order programs. This task presents several unique challenges to obtain good accuracy, including the need for a new method for demand-driven lookup of non-local variable values. DDPA is flow- and context-sensitive and provably polynomial-time. To efficiently implement DDPA, we develop a novel pushdown automaton metaprogramming framework, the Pushdown Reachability automaton. The analysis is formalized and proved sound, and an implementation is described.

@article{paperbot708,
  title = {Higher-order Demand-driven Program Analysis},
  author = {Leandro Facchinetti and Zachary Palmer and Scott Smith},
  journal = {ACM Transactions on Programming Languages and Systems},
  volume = {41},
  number = {3},
  year = {2019},
  doi = {10.1145/3310340}
}