The expressive power of functional and object-oriented languages
derives in part from their higher-orderness: through closures and
objects, code becomes data. This talk focuses on meeting the
challenges that such power poses for static analysis and its clients.
(To make the talk more accessible, a brief history of the higher-order
analysis is included.)
Since its discovery in the 1980s, higher-order control-flow analysis
(CFA) has enabled many critical program optimizations, such as
flow-directed inlining and static virtual-method resolution. Over the
past two decades, much research in higher-order analysis focused on
improving the speed and precision of CFA. Despite frequent encounters
with the limits of CFAs, little progress had been made in moving
beyond them, as measured by the kinds of optimizations made possible
and the kinds of questions made answerable.
The key limitation of CFAs is the inherently coarse approximation that
they inflict upon environment structure. This talk centers on my
development of environment analysis---techniques which break through
these limitations of twenty years standing. Of particular note is
that these techniques evade the cost/precision tradeoff usually found
in program analyses: compared to previous techniques, they provide
improvements in both power and precision, yet also reduce the cost of
the compile-time analysis in practice. Using environment analysis as
a foundation, my recent work on logic-flow analysis has continued to
expand the reach of higher-order analysis beyond optimization and into
realms such as security and verification.