@conference {19593,
	title = {Resolving and Exploiting the k-CFA Paradox: Illuminating Functional vs. Object-oriented Program Analysis},
	booktitle = {PLDI {\textquoteright}10 Proceedings of the 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation},
	series = {PLDI {\textquoteright}10},
	year = {2010},
	month = {2010///},
	pages = {305 - 315},
	publisher = {ACM},
	organization = {ACM},
	abstract = {Low-level program analysis is a fundamental problem, taking the shape of "flow analysis" in functional languages and "points-to" analysis in imperative and object-oriented languages. Despite the similarities, the vocabulary and results in the two communities remain largely distinct, with limited cross-understanding. One of the few links is Shivers{\textquoteright}s k-CFA work, which has advanced the concept of "context-sensitive analysis" and is widely known in both communities. Recent results indicate that the relationship between the functional and object-oriented incarnations of k-CFA is not as well understood as thought. Van Horn and Mairson proved k-CFA for k >= 1 to be EXPTIME-complete; hence, no polynomial-time algorithm can exist. Yet, there are several polynomial-time formulations of context-sensitive points-to analyses in object-oriented languages. Thus, it seems that functional k-CFA may actually be a profoundly different analysis from object-oriented k-CFA. We resolve this paradox by showing that the exact same specification of k-CFA is polynomial-time for object-oriented languages yet exponential-time for functional ones: objects and closures are subtly different, in a way that interacts crucially with context-sensitivity and complexity. This illumination leads to an immediate payoff: by projecting the object-oriented treatment of objects onto closures, we derive a polynomial-time hierarchy of context-sensitive CFAs for functional programs.},
	keywords = {control-flow analysis, functional, k-cfa, m-cfa, object-oriented, pointer analysis, static analysis},
	isbn = {978-1-4503-0019-3},
	url = {http://doi.acm.org/10.1145/1806596.1806631},
	author = {Might, Matthew and Smaragdakis, Yannis and David Van Horn}
}
