[PRL] Thesis defense (Brandeis): The Complexity of Flow Analysis in Higher-Order Languages

[David Van Horn]

This work has benefited so much from so many here at Northeastern.  I 
would be grateful if you could come celebrate its completion.  Brandeis 
is easily accessible via the commuter rail; if you'd like details, just 
email me.

Thanks,
David

************************************************************************

PhD Thesis Defense
Computer Science Department
Brandeis University

Date: Wednesday, July 22, 2009
Time: 2-4pm
Place: Volen 101

The Complexity of Flow Analysis in Higher-Order Languages
David Van Horn

Abstract:

This dissertation proves lower bounds on the inherent difficulty of 
deciding flow analysis problems in higher-order programming languages. 
We give exact characterizations of the computational complexity of 0CFA, 
the kCFA hierarchy, and related analyses. In each case, we precisely 
capture both the expressiveness and feasibility of the analysis, 
identifying the elements responsible for the trade-off.

0CFA is complete for polynomial time. This result relies on the insight 
that when a program is linear (each bound variable occurs exactly once), 
the analysis makes no approximation; abstract and concrete 
interpretation coincide, and therefore program analysis becomes 
evaluation under another guise. Moreover, this is true not only for 
0CFA, but for a number of further approximations to 0CFA. In each case, 
we derive polynomial time completeness results.

For any k > 0, kCFA is complete for exponential time. Even when k = 1, 
the distinction in binding contexts results in a limited form of 
closures, which do not occur in 0CFA. This theorem validates empirical 
observations that kCFA is intractably slow for any k > 0. There is, in 
the worst case---and plausibly, in practice---no way to tame the cost of 
the analysis. Exponential time is required. The empirically observed 
intractability of this analysis can be understood as being inherent in 
the approximation problem being solved, rather than reflecting 
unfortunate gaps in our programming abilities.